跳到主要內容

發表文章

目前顯示的是 二月, 2015的文章

[線性代數] Ax=b 何時有解? 何時解為唯一?

令 $A \in \mathbb{R}^{m \times n}$ 為 實數矩陣 (有 $m$ rows 與 $n$ columns 故 $A$ 可不為方陣 )。我們通常有興趣求解下列形式的線性方程組
\[
A {\bf x} = {\bf b}
\] 其中 ${\bf b} \in \mathbb{R}^m$ 且 ${\bf x} \in \mathbb{R}^n$ 為未知數待求。

往下閱讀之前,強烈建議讀者先回憶 以下幾個 線性代數 中的 基本名詞定義:
向量空間 (Vector Space)子空間 (Subspace)線性獨立 與 線性相關 (Linear Independence & Dependence)矩陣的秩 (Rank) 線性生成 (Span)基底 (Basis)維度 (Dimension)正交空間 (Orthogonal Space) 待上述基本概念補齊之後再往下閱讀:


線性代數基本定理 (Fundamental Theorem of Linear Algebra)
對於 $A {\bf x} = {\bf b}$ 何時有解 以及 何時有唯一解 給出了完整的條件 (參閱 G. Strang, "Linear Algebra and its Applications") 。亦即 任意矩陣 $A_{m \times n}$ 且 $rank(A)=r$ ,則我們可將 $\mathbb{R}^n$ 空間 與 $\mathbb{R}^m$ 空間分解到四個基本子空間:
列空間(Column space) or  (Range space ) $:= \mathcal{R}(A) \subset \mathbb{R}^m$;維度為 rank $r$零空間 (Null Space) or kernel $:=\mathcal{N}(A) \subset \mathbb{R}^n$;維度為 rank $n-r$行空間 (Row space) $:= \mathcal{R}(A') \subset \mathbb{R}^n $;維度為 rank $r$左零空間 (Left null space) $:= \mathcal{N}(A') \subset \mathbb{R}^m $;維度為 rank $m-r$
Comments:
1…

[最佳估計] 狀態估測器的收斂性

考慮離散時間 LTI 系統
\[\begin{array}{l}
x(k + 1) = Ax(k) + w(k)\\
y(k) = Cx\left( k \right) + v(k)
\end{array}\]其中 $x \in \mathbb{R}^n, u \in \mathbb{R}^m, y \in \mathbb{R}^p$ 且 $x(0) = x_0$;

基本狀態估計問題:給定初始估計誤差 ( i.e., $\bar x(0) \neq x_0$) 且 不考慮 雜訊 無外部干擾的情況 ($w(k) = v(k)=0$),我們想問 $\hat x(k) \to x(k)$ as $k \to \infty$ ?

=================
Theorem: (Convergence of Estimator Cost)
給定無 noise 量測輸出 ${\bf y}( T) = \{Cx(0), CAx(0),..., CA^T x(0)\}$ 則最佳估測器的 cost $V_T^*({\bf y}(T)) $ 在 $T \to \infty$ 時收斂 。
=================

Proof:
由於
\[V_T^{} = \frac{1}{2}\left( \begin{array}{l}
\left| {\hat x\left( 0 \right) - \bar x\left( 0 \right)} \right|_{{{\left( {{P^ - }\left( 0 \right)} \right)}^{ - 1}}}^2\\
\begin{array}{*{20}{c}}
{}&{}
\end{array} + \sum\limits_{k = 0}^{T - 1} {|\hat x\left( {k + 1} \right) - A\hat x\left( k \right)|_{{Q^{ - 1}}}^2}  + \sum\limits_{k = 0}^T {\left| {y\left( k \right) - C\hat x\left( k \right)} \right|_{{R^{ - 1}}}^2}
\end{array} \right)\]故我們分三個步驟證明 $V_T^*({\bf y}(T)) $ 在 $T …

[控制理論] 離散線性系統的 追蹤 與 調節 問題

Setpoint Tracking
考慮離散線性系統
\[\left\{ \begin{array}{l}
x\left( {k + 1} \right) = Ax\left( k \right) + Bu\left( k \right)\\
y\left( k \right) = Cx\left( k \right)
\end{array} \right.\] $x \in \mathbb{R}^n, y \in \mathbb{R}^p, u \in \mathbb{R}^m$;一般而言,控制系統中常見的 追蹤(setpoint tracking)問題 (或稱 servo problem) 如下:
給定 setpoint  $y_{sp}$ (e.g., 步階訊號 or 常數),我們希望在系統達到穩態(steady-state) 之後,系統的輸出 $ y  = y_{sp} $。

若我們考慮給定的 setpoint $y_{sp} = 0$ 則稱此類問題為 regulation problem。

回憶在最佳控制理論中的 LQR 方法給予我們對於線性系統的 regulation 問題提供一組最佳解,故我們的想問是否能將此法應用在 一般的追蹤問題?

答案是肯定的,僅需引入 deviation variable 做基本 座標轉換 即可。

現在我們令 $y_{sp}$ 為 output setpoint,定義系統穩態時候的狀態 與 控制力為 $(x_s, u_s)$ 則線性系統方程可改寫為
\[\left\{ \begin{array}{l}
{x_s} = A{x_s} + B{u_s}\\
{y_s} = C{x_s}
\end{array} \right.\]注意到對於穩態時 我們希望 $y_s = y_{sp}$ 故 我們有 $y_{sp} = C x_s$ 現在我們將上式改寫為矩陣形式
\[\left\{ \begin{array}{l}
{x_s} = A{x_s} + B{u_s}\\
{y_{sp}} = C{x_s}
\end{array} \right. \Rightarrow \left[ {\begin{array}{*{20}{c}}
{I - A}&{ - B}\\
C&0
\end{array}} \right]\left…

[線性系統] Hautus Lemma 與 控制性/可穩定性質

以下我們介紹 線性系統理論中關於 控制性的 重要結果
==========================
Lemma: Hautus Lemma for Controllability
一個離散線性系統
\[
x(k+1) = A x(k) + Bu(k)
\]為 controllable 或稱 (A,B) controllable 若且唯若
\[
rank[\lambda I - A\;\; B] =n, \;\; \forall \lambda \in \mathbb{C}
\]其中 $\mathbb{C}$ 表示 任意 complex number 所形成的集合。
==========================
Proof: omitted.
Comment:
1. 上述 Lemma 等價為 矩陣 $[\lambda I - A\;\; B]$ 有 $n$ 個 independent rows (full row rank) 。

2. 也許讀者會好奇為何需要如此多 控制性 檢驗工具? 為什麼不使用 可控性矩陣(controllability matrix) 檢驗法就好? 事實上此 Hautus Lemma 主要是功用是大幅簡化 理論證明,但一般實際 檢驗 系統的 可控性 仍多仰賴  可控性矩陣(controllability matrix) 檢驗法。

3. 注意到上述條件需要檢驗 "任意" complex number $\lambda$ 此條件明顯過於嚴苛。不過我們可以注意到 若 $\lambda $ 並非為 $A$ 矩陣的特徵值,則 $rank[\lambda I - A\;\; B] =n$ 必然成立,故我們只需檢驗 $\lambda$ 為 $A$ 矩陣的特徵值部分即可。故

==========================
Lemma (Modified): Hautus Lemma for Controllability
一個離散線性系統
\[
x(k+1) = A x(k) + Bu(k)
\]為 controllable 或稱 (A,B) controllable 若且唯若
\[
rank[\lambda I - A\;\; B] =n, \;\; \forall \lambda \in eig(A)
\]=========…

[最佳控制] 離散時間 穩態 LQR 控制問題 (2) - LQR convergence

回憶離散時間穩態LQR問題: 定義 cost function
\[\begin{array}{l}
V\left( {x,{\bf{u}}} \right): = \frac{1}{2}\sum\limits_{k = 0}^\infty  {{x^T}\left( k \right)Qx\left( k \right) + {u^T}\left( k \right)Ru\left( k \right)} \\
s.t.\\
x\left( {k + 1} \right) = Ax\left( k \right) + Bu\left( k \right)\\
x\left( 0 \right) = x
\end{array}\]且 $Q, R >0$ 為正定矩陣。若 $(A,B)$ 為可控制 則 最佳化問題
\[
\min_{\bf u} V(x,{\bf u})
\]解存在 且唯一 (why?)。

現在我們將此解 (控制力序列) 記做 ${\bf u}^*(x)$;其中第一項為 $u^*(x)$。且對應的最佳控制律 $K_{\infty}(\cdot)$  故我們有
\[
K_\infty(x) = u^*(x) = {\bf u}^* (0;x)
\]

以下定理說明若可控制系統 採用 穩態 LQR 控制,則保證閉迴路穩定度:

=====================
Theorem: Steady State LQR Guarantees the Closed-Loop Stability
對 $(A,B)$ 可控制,穩態LQR問題 且 $Q,R >0$ 保證閉迴路系統
\[
x(k+1) = A x(k) + B K_\infty (x)
\]穩定。
=====================
Comment:
線性系統中,漸進穩定度 等價 漸進收斂 $x(k) \to 0$
Proof:
首先證明 穩態 cost function 有界。注意到由於  $(A,B)$ 可控制,由定義可知存在 一組控制力
\[
{\bf u} = \{u(0), u(1),...,u(n-1)\}
\] 使得 控制後的系統能在有限時間 $n$ 步之內,可由任意給定初始狀態 $x(0)$ 移動到 給定的終止狀態 $x(n) = 0$;且 在時間 $ n$ 之後的控制力…

[最佳控制] 線性系統的最佳參數估計 - Kalman Filter (1)

此文章基於前篇 [最佳控制] 線性系統的最佳參數估計 - Kalman Filter (0);強烈建議讀者先參閱前篇再行閱讀此文。此文將利用 計算 probability density 方式來求解 Kalman filter。


考慮離散時間動態系統
\[
x(k+1) = Ax(k) + w(k);\;\; y(k) = Cx(k) + v(k)
\]且 $w \sim N(0,Q)$ 為製程雜訊 process noise 或稱 干擾 process disturbance;$v \sim N(0,R)$ 為量測雜訊 (measurement noise) ; $x(0) \sim N(\bar x(0), Q(0))$;$x \in \mathbb{R}^n, A \in \mathbb{R}^{n \times n}, C \in \mathbb{R}^{p \times n}, y \in \mathbb{R}^p$,Kalman filter 便是在試圖回答:假設狀態未知我們只能拿到量測輸出,則最佳的狀態估計該是如何?


First Step : $k=0$
假設 初始狀態 $x(0)$ 為 mean $\bar x(0)$ 且 convariance matrix $Q(0)$ 的 normal distrbuted 隨機向量,亦即
\[
x(0) \sim N(\bar x(0), Q(0))
\]接著獲得 初始 (受雜訊污染的) 量測輸出 $y(0)$ 滿足下式
\[
y(0) = C x(0) + v(0)
\]其中 $v(0) \sim N(0, R)$ 為 雜訊 (measurement noise)。

我們的目標:獲得 conditional density $p_{x(0)|y(0)}(x(0) | y(0))$ ,則我們的狀態估計 $\hat x$ 即可透過此 conditional density 求得
$$\hat x := \arg \max_x p_{x(0)|y(0)}(x(0) | y(0))$$

Comments:
1. 若未知 $\bar x(0)$ 或者 $Q(0)$ 則我們通常選 $\bar x(0) :=0$ 且 $Q(0)$ 很大 來表示我們對初始狀態所知甚少 (noninformative prior)。
2. 若量測過…

[最佳控制] 線性系統的最佳參數估計 Kalman Filter (0)- 預備知識

這次要介紹 Kalman filter 或稱 Optimal Linear State Estmator,以下我們將簡單介紹一些在下一篇文章需要使用的一些結果。

Preliminary
回憶若 $x$ 為 mean $m$ 且 variance $\sigma^2$ 的 Normal 隨機變數 則 我們表示為 $x \sim N(m, \sigma^2)$ 。其 probability density function 可記做
\[
\frac{1}{\sqrt{2 \pi} \sigma} \exp(\frac{-1}{2 \sigma^2}(x-m)^2)
\]現在若我們拓展上述結果到 多個隨機變數 (又稱 random vector 隨機向量) 的情況,令 $x$ 為Normal 隨機向量 記做
\[
x \sim N(m,P); \;\;
p_x(x) := n(x,m,P)
\]上述符號 表示 $x$ 為 normal distributed 且 mean vector $m$ 與 convariance matrix $P$。另外 $n(x,m,P)$ 表示 normal probability density function
\[\;n\left( {x,m,P} \right): = \frac{1}{{{{\left( {2\pi } \right)}^{n/2}}{{\left( {\det P} \right)}^{1/2}}}}\exp \left( { - \frac{1}{2}{{\left( {x - m} \right)}^T}{P^{ - 1}}\left( {x - m} \right)} \right)\]
Comment:
若 $x \in \mathbb{R}^n$ 則 mean vector $m \in \mathbb{R}^n$ 且 convariance matrix $P \in \mathbb{R}^{n \times n}$ 且為 實數 對稱 正定 矩陣 (正定條件用以確保 $P^{-1}$ 存在,使得上述的 probability density function 可以被定義)。若 $P$ 不為對 正定 我們稱為 singular normal distribution 或稱 degenerate norma…

[機器學習] Prediction with Expert Advice - exp strategy

Prediction with Expert Advice, PWEA 又稱 repeated game ( 預測者 v.s. 外部環境)

此 PWEA 運作過程如下:
假設有 $N$ 個專家(expert);對 預測回合  $t := 1,2,...T$,
STEP1:環境會產生 1. 專家建議 $\{f_{i,t}\}_{i=1}^N$ 與 2. 真實輸出 $y_t$ (我們想要預測此值,但目前未知)
STEP2 :我們 獲得 前述 由環境產生的 該回合 專家建議
STEP3:我們由專家建議 建構 該回合的 預測函數 $\hat p_t$
STEP4:一旦完成 $\hat p_t$,我們可獲得真實輸出 $y_t$,此時 可計算 loss $l(\hat p_t, y_t)$ 且 對每一個 (第 $i$ 個) 專家 而言,可計算其對應 loss $l(f_{i,t},y_t)$

目標:使 cumulative regret 最小
\[{R_T}: = \sum\limits_{t = 1}^T l ({{\hat p}_t},{y_t}) - \underbrace {\mathop {\min }\limits_{i = 1,...,N} \sum\limits_{t = 1}^T l ({f_{i,t}} - {y_t})}_{{\rm{Best\;\;expert\;\;in\;\;hindersight}}}\]最好的情況是 $R(T) = o(T) $ 亦即 當 $T \to \infty$,$R_T/T \to 0$

General PWEA Strategy
對每一個專家 $i$ ,透過 給定適當的權重 weight $w_{i,t}$ 來反映我們對此專家的信心。最常見的方法為使用 Weighted Average or Weighted majority。
\[{\hat p_t}: = \frac{{\sum\limits_{i = 1}^N {{w_{i,t}}{f_{i,t}}} }}{{\sum\limits_{i = 1}^N {{w_{i,t}}} }}
\]
那麼權重該如何計算?
對時刻 $t+1$ 而言,我們定義 $\eta := \ln q$ 則
\[\begin{array}{l}
{w_{i,t + 1}} = {w_{i,t}}{\le…