2018年4月25日 星期三

[訊號與系統] LTI系統輸入輸出關係由 Convolution 決定 - 從離散時間觀點

以下我們討論 為何 線性非時變 (Linear Time-Invariant, LTI) 系統 輸入與輸出關係 由 所謂的 convolution 表示。為了避免過多繁雜的數學,以下僅討論離散時間的情況。首先我們需要一些定義的幫助:

========================
Definition: Unit Impulse Function in Discrete-Time (Kronecker Delta)
我們說函數 $\delta: \mathbb{N} \to \{0,1\}$ 為 unit impulse function in discrete-time time 若 $\delta$ 滿足
\[\delta \left[ n \right] = \left\{ \begin{gathered}
  1,\;\;\;\;n = 0 \hfill \\
  0,\;\;\;\; o.w. \hfill \\
\end{gathered}  \right.
\]========================

========================
Definition: Impulse Response
給定任意系統配備輸入 $x[n]$ 與輸出 $y[n]$ 關係為 $y[n] = T\{x[n]\}$其中 $T$ 視為 operator (定義在某函數空間),若輸入為 $x[n]=\delta[n]$ 則 輸出
\[
h[n] := y[n] = T\{\delta[n]\}
\]稱為系統 $T$ 的 脈衝響應 (impulse response)
========================


========================
FACT: 任意離散訊號 $x[n]$ 可由 $\delta$ 做組合疊加,亦即
\[
x[n] = \sum_{k=-\infty}^{\infty}x[i] \delta[n-k]
\]========================
Proof: 證明顯然,在此不做贅述。$\square$



========================
Definition: Linear System
給定系統 $T$ 滿足以下輸入與輸出關係: $y_1[n]=T\{x_1[n]\}$ 且 $y_2[n] = T\{x_2[n]\}$。現在定義 $x[n] =ax_1[n] + bx_2[n]$ 其中 $a,b \in \mathbb{R}$則我們說系統 $T$ 為 linear 若下列條件成立
\[
y[n] = T\{x[n]\}
\]且 $y[n] = a y_1[n] + b y_2[n]$
========================

Remarks:
上述 系統 $T$  其實可看按作 泛函分析中的 operator。故線性系統 就是 泛函分析中的 線性算子 (linear operator)。



========================
Definition: Time-Invariant System
給定系統 $T$ 滿足以下輸入與輸出關係: $y[n]=T\{x[n]\}$。現在定義 $x[n] :=x[n-d]$  其中 $d \in \mathbb{N}$ 則我們說 $T$ 為 time-invariant 若下列條件成立
\[
y[n-d] = T\{x[n-d]\}
\]========================


有了以上定義的幫助,我們現在有辦法給出以下為何 LTI 系統的輸入輸出關係確實為 convolution。


========================
Theorem: LTI input-output Relationship is Governed by Convolution
給定 線性非時變 (LTI)系統 $L$ 滿足
\[
y[n] = L\{x[n]\}
\]其中 $L$ 為 linear operator,則
\[
y[n] = \sum_k h[k] x[n-k]
\]========================
Proof:
由於 任意 輸入 $x[n]$ 皆可被表為 脈衝函數的 組合:
\[
x[n] = \sum_{k = -\infty}^\infty x[k] \delta[n-k]
\]現在將此訊號作為LTI系統 $L$ 的輸入,則由於 $L$ 為 linear operator 我們有
\begin{align*}
  y[n] &= L\left\{ {x\left[ n \right]} \right\} \\
&= L\left\{ {\sum\limits_{k =  - \infty }^\infty  x [k]\delta [n - k]} \right\} \hfill \\
   &= \sum\limits_{k =  - \infty }^\infty  x[k] L\left\{ \delta [n - k] \right\}  \;\;\;\; (*)
\end{align*} 接著因為 $L$ 為 time-invariant 我們可進一步改寫
\[L\left\{ {\delta [n - k]} \right\} = h\left[ {n - k} \right] \;\;\;\; (**)
\]故由 $(*)$ 與 $(**)$ 可得
\[y[n] = \sum\limits_{k =  - \infty }^\infty  {x[k]h\left[ {n - k} \right]} \]即為所求。$\square$

Comments:
上述 \[
y[n] = \sum\limits_{k =  - \infty }^\infty  {x[k]h\left[ {n - k} \right]}
\]一般又稱作 $x[n]$ 與 $h[n]$ convolution sum。記作
\[
y[n] = x[n] * h[n]
\]

2018年4月4日 星期三

[測度論] 從 測度論 觀點看 Chebyshev Inequality

Chebyshev inequality 是 機率論 中一個非常好用的不等式,此不等式可以從 更廣義的 測度論觀點來證明,且不僅僅局限於使用機率測度。
令 $L^1(\mu)$ 為所有可測函數 $g$ 滿足 $\int |g| d\mu <\infty$ 所成之集合, $\mu$ 為測度。

Claim: Chebyshev Inequality in Measure-Theoretic Setting
令 $g \in  L^1$ 且 $\alpha >0$ 則
\[
\mu (\{x:|g(x)| \geq \alpha\}) \leq \frac{1}{\alpha}\int |g| d\mu
\]
Proof: 令 $\alpha >0$ 觀察
\begin{align*}
  \mu (\{ x:|g(x)| \geqslant \alpha \})  &= \int {{1_{\{ |g(x)| \geqslant \alpha \} }}} d\mu  \hfill \\
   &= \int {{1_{\left\{ {\frac{{|g(x)|}}{\alpha } \geqslant 1} \right\}}}} d\mu  \;\;\;\; (*)
\end{align*} 其中 $1_A(x)$ 為 indicator function 滿足 $x\in A$ 則 $1_A(x) =1$ 反之則 $1_A(x) = 0$。注意到 \[\frac{{|g(x)|}}{\alpha } \geqslant 1 \Rightarrow \frac{{|g(x)|}}{\alpha } \geqslant {1_{\left\{ {\frac{{|g(x)|}}{\alpha } \geqslant 1} \right\}}}\]故 $(*)$ 改寫
\[\int {{1_{\left\{ {\frac{{|g(x)|}}{\alpha } \geqslant 1} \right\}}}} d\mu  \leqslant \int {\frac{{|g(x)|}}{\alpha }} d\mu  = \frac{1}{\alpha }\int {|g(x)|} d\mu \]即為所求。$\square$


Comments:
1. 上述證明儘管相當容易但對於 測度,積分 以及 indicator function 之間的操作頗具巧思值得多加注意。(關於 indicator 相關討論可參閱 [機率論] 指示函數 ( Indicator function) )。

2. 測度論觀點之下的 Chebyshev inequality 證明比 (初等)機率論 或者 數理統計 中的證明來的簡潔許多 (參閱 [機率論]   Chebyshev's Inequality 的推廣型),讀者不需煩惱積分範圍,是否要分段積分或者考慮是否有無機率密度函數。這現象在較高等的數學中非常常見 (e.g., 泛函分析中將 函數所成的空間 利用線性代數的觀念 將其視為 無窮維向量空間,則不論多複雜的函數都變成該空間上的一"點"),也就是 抽象化之後 可以在某種程度上避免許多複雜的操作,但代價就是抽象化後的觀念需要時間沈澱。

3.  上述 Chebyshev inequality 陳述在 $L^p$ 空間也對。
Claim:
若 $g \in L^p$  其中 $p \in (0,\infty)$ 且 $\alpha >0$ 則
\[
\mu (\{x:|g(x)|^p \geq \alpha^p \}) \leq \frac{1}{\alpha^p}\int |g|^p d\mu
\] 證明雷同,在此不贅述。