跳到主要內容

發表文章

[線性代數] 一類含有反矩陣的等式

Claim:
令 $A \in \mathbb{R}^{m \times n}$,且 $\lambda >0$ 則以下等式成立
\[
(A^TA+\lambda I)^{-1}A^T = A^T(AA^T+\lambda I)^{-1}
\]

Proof: 觀察 $A^TAA^T+\lambda A^T$ 可對其從左方或者右方提出 $A^T$,亦即
\[\begin{align*}
A^T(AA^T+\lambda I) = (A^TA+\lambda I)A^T
\end{align*}\]由於 $(AA^T +\lambda I)$ 為可逆,$(AA^T+\lambda I)^{-1}$存在,故對上式兩邊從右方同乘此項可得
\[
A^T = (A^TA+\lambda I)A^T(AA^T+\lambda I)^{-1}
\]又注意到 $(A^TA+\lambda I)$ 為可逆,$(A^TA+\lambda I)^{-1}$存在,對上式從左方同乘此項可得
\[
(A^TA+\lambda I)^{-1}A^T = A^T(AA^T+\lambda I)^{-1}
\]至此證明完畢。$\square$


Comments:
上述結果多出現於一類稱作 Tikhonov Regularization (或者有拘束的最小二乘方問題)問題之中:亦即令 $A \in \mathbb{R}^{m \times n}$ 且 ${\bf x},{\bf y}\in \mathbb{R}^{n}$,$\lambda >0$考慮
\[
\min_{\bf x}\|A{\bf x} - {\bf y}\|_2^2 + \lambda \|{\bf x}\|_2^2
\]則不難證明上述最佳化問題之解為
\[
{\bf x}= (A^TA+\lambda I)^{-1}A^T {\bf y}  = A^T(AA^T+\lambda I)^{-1}{\bf y}
\]上述第二等式成立因為 前述 claim。故我們在實際計算反矩陣時,可以決定到底要用 哪一個 inverse來加速計算速度,比如 $A \in \mathbb{R}^{5000\times 100}$ 那麼 $(A^TA+\lambda I)^{-1}$ 要求對 $100\times 100$ 矩陣做 反矩陣,但是 $(…
最近的文章

[機器學習] 回歸問題應用例:Dow Jones 指數的 回歸模型估計

考慮歷史 Dow Jones 指數如下圖所示


令 $v(t)$ 表示 從1795年到 2019年每年的 Dow Jones 指數其中 $t=1,1,\ldots,T$ 且 $t=1$表示 1795年,$t=T$表示至今 (上圖為2019年,但任意年皆可)。由上圖,我們假設 $v_t$ 可由以下 指數函數 近似:亦即  $v: \mathbb{N} \to \mathbb{R}$ 滿足
\[
v(t):= e^{at+b}
\]其中  $t=1,...,T$,$a,b$ 為 待估計參數。我們想問是否能找出 $a,b$ 使得我們可以用此模型來預估未來 Dow Jones 指數的走向:

上述問題可化簡為回歸問題。首先對 $v_t$ 等式兩邊同取 $\log$,我們可得
\[
\log v(t) = at+b
\]故對任意 $t=1,...,T$我們有
\[
\begin{bmatrix}\log v(1)\\\log v(2)\\ \vdots \\ \log v(T) \end{bmatrix} = \begin{bmatrix}1 & 1 \\ 2 & 1 \\ 3 & 1\\ \vdots & \vdots \\ T & 1  \end{bmatrix} \begin{bmatrix} a\\b\end{bmatrix}
\]
令  ${\bf x}=[a \;\; b]^T$,${\bf b}=\begin{bmatrix}\log v(1) & \log v(2) & \vdots \log v(T) \end{bmatrix}^T$ 且 $$A:=\begin{bmatrix}1 & 1 \\ 2 & 1 \\ 3 & 1\\ \vdots & \vdots \\ T & 1  \end{bmatrix} \in \mathbb{R}^{T \times 2} $$ 則我們得到 $
A{\bf x} = {\bf b}
$ 。由於 $T>>2$,方程 $A{\bf x} = {\bf b}$無解 (參閱 comment 2),但我們可問是否有近似解。為此, 欲求解 ${\bf x}$ 一種常見的手段是採用最小平方法:考慮以下無拘束最小平方最佳化問題
\…

[線性代數] 構造 正定矩陣 其元素含有負值的例子

首先回憶 正定 (positive definite)矩陣 定義:

Definition: 令 $Q \in \mathbb{R}^{n\times n}$且 $Q^T=Q$。我們說 $Q$ 為 positive definite 若下列條件成立: 對任意 ${\bf x} \in \mathbb{R}^n$ 且 ${\bf x} \neq {\bf 0}$,
$$
{\bf x}^TQ{\bf x}>0
$$


我們想問是否有可能構造出一正定矩陣其部分元素取值為負。答案是肯定的。請看以下例子:

==============
Example: 
令 $Q = \begin{bmatrix}2 & -1 \\ -1 & 2 \end{bmatrix}$。試証 $Q$ 為 positive definite。
================

Proof: 首先注意到 $Q^T=Q$ 為顯然。故我們僅需証明 對任意 ${\bf x} \neq 0$, ${\bf x}^TQ{\bf x}>0。$為此,取${\bf x}=[x_1\;\;x_2]^T$ 且 $x_1,x_2$不全為零, 觀察
$$
{\bf x}^TQ{\bf x} = [x_1 \;\; x_2]  \begin{bmatrix}2 & -1 \\ -1 & 2 \end{bmatrix} \begin{bmatrix}x_1\\x_2 \end{bmatrix} = 2x_1^2+2x_2^2-2x_1x_2$$上述稱為 矩陣二次式(quadratic form)。

以下我們分幾個情況討論:

Case 1: 若 $x_2 \neq 0$ 且 $x_1 \neq 0$:
若 $x_1\geq x_2$ ,則 $2x_1^2+2x_2^2-2x_1x_2 \geq 2x_2^2>0$
若 $x_2 \geq x_1$,則 $2x_1^2+2x_2^2-2x_1x_2 \geq 2x_1^2>0$

Case 2: 若 $x_2 \neq 0$ 且 $x_1 = 0$:則我們有
$$
 2x_1^2+2x_2^2-2x_1x_2 = 2x_2^2 > 0
$$

Case 3: 若 $x_1 \neq 0$ 且 $x_2 = 0$:則我們有
$$
 2x_…

[三角函數] 一類 離散餘弦取負值的條件

Claim 1: 令 $\omega \in (0, \pi/2)$,則 存在 正整數 $k $ 使得
\[
\cos(\omega k ) <0
\]==========


Proof: 首先回憶 floor 函數:對任意 $x \in \mathbb{R}$, $\lfloor x \rfloor$具備以下性質
\[
x-1 < \lfloor x \rfloor \leq x
\]現在給定 $0 < \omega < \pi/2$,並取
\[
k := 1 + \bigg \lfloor \frac{\pi}{2\omega} \bigg\rfloor
\]則利用前述的 floor 函數性質,我們有
\[
\frac{\pi}{2\omega} < k \leq 1 + \frac{\pi}{2\omega}
\]兩邊同乘 $\omega$ 則
\[
\frac{\pi}{2} < \omega k \leq \omega + \frac{\pi}{2}
\]因為 $\omega \in (0, \pi/2)$,我們可以進一步取上述不等式右方的上界,亦即 $ \omega + \frac{\pi}{2} < \pi$。故
\[
\omega k \in \bigg(\frac{\pi}{2}, \pi \bigg) \subset \bigg( \frac{\pi}{2}, \frac{3\pi}{2}\bigg)
\]注意到對任意 $\theta \in  \bigg( \frac{\pi}{2}, \frac{3\pi}{2}\bigg)$, $\cos \theta < 0$ ,故 $\cos(\omega k) < 0$。至此得證。 $\square$



Comment: 我們可將 claim 1 結果進一步推廣到包含有相位的情況:




==========
Claim 2: 令 $\omega \in (0, \pi/2)$ 且 $\theta \in (-\pi/2, \pi/2)$,則 存在 整數 $k >2$ 使得
\[
\cos(\omega(k- 1) + \theta) <0
\]==========


Proof:
\[
k_0 := 1 + \bigg\lfloor \frac{\…

[測度論] 關於 Almost Everywhere

給定測度空間 $(X,\mathcal{M},\mu)$我們說 某性質 $P$ almost everywhere 成立 意思是 對所有非零測度集合此性質 $P$ 都成立。(換言之,除零測度集之外,此性質 $P$ 都成立。)

Lemma:
假設 $f(x) \geq 0$ 且 $f$ 為 $(\mathcal{M}, \mathcal{B}_{\mathbb{R}})$ 可測。假設 $\int f d\mu = 0$ 則 $f(x) = 0$ almost everywhere (i.e., $\mu\{x: f(x)>0\} = 0$)

Proof:
令 $E:= \{x:f(x)>0\}$,我們要證明$\mu(E) = 0$ 。為此,我們首先證明 $\mu(E_n) = 0$ 其中 $E_n :=\{x: f(x) > 1/n\}$。觀察以下事實 $\cup_n E_n = E$ 且 $E_n \uparrow E$。

觀察
\[
\mu(E_n) := \int 1_{E_n}  \;\;\;\;(*)
\]注意到對任意 $x\in E_n$,我們有 $f(x) > 1/n $,此等同於 $n f(x) > 1$ ,故對任意 $x\in E_n$, $nf(x) 1_{E_n}(x) > 1 \cdot 1_{E_n}(x)$ 。將此用到 $(*)$ 我們得到
\[
\mu(E_n) = \int 1_{E_n} < \int nf(x)1_{E_n} \leq \int nf(x) =n \underbrace{\int f(x) d\mu(x)}_{=0}
\]亦即
\[
\mu(E_n) = 0
\]最後我們檢驗
$$\mu(E) = \mu(\cup_n E_n) = \lim_n \mu(E_n) = 0$$即為所求。$\square$


Lemma 2:
給定 測度空間 $(X,\mathcal{M}, \mu)$ 且 $\mu$ 為complete measure,若 $f$ 為 $(\mathcal{M},\overline{\mathcal{B}}_{\mathbb{R}})$ measurable 且 $f=g$ almost everywhere 則 $g$ 亦為 $(\mathcal{M},\overl…