# 線性代數的最小平方/範數問題與與主成分分析(PCA)
###### tags: `線性代數`
###### 撰寫時間 : 2022/08/31

## 最小平方問題(least square problem)
考慮$\mathbf{A}_{m \times n} \mathbf{x}_{n \times 1} = \mathbf{b}_{m \times 1}$，若$m > n, \mathrm{rank}(\mathbf{A}) = n$，也就是說有效方程式$m$條，多於未知數$n$個，屬於overdetermined problem，解不存在(或是只存在一組解)，但問題總不能這樣就結束，因此我們"試圖"找到一個近似解的折衷方案 - 找$\mathbf{x} \in \mathbb{R}^n$能最小化$\mathbf{Ax} -\mathbf{b}\in \mathbb{R}^{ m \times n}$的長度。

## 最小平方問題解法1 - 線性代數理論
<br>
在$\mathbb{R}^m$空間下
$$
\mathbf{A} \mathbf{x} = \begin{bmatrix} \mathbf{A}_1 & \mathbf{A}_2 & \cdots & \mathbf{A}_n \end{bmatrix} \begin{bmatrix} \mathbf{x}_1\\ \mathbf{x}_2\\ \vdots\\ \mathbf{x}_n \end{bmatrix} = \mathbf{x}_1 \mathbf{A}_1 + \mathbf{x}_2 \mathbf{A}_2 + \cdots + \mathbf{x}_n \mathbf{A}_n
$$
只會落在$\mathbb{R}^n$的平面，也就是$\mathrm{Col}(\mathbf{A})$，如果$\mathbf{b}$沒落在這個平面上，記為$\mathbf{b} \not\in \mathrm{Col}(\mathbf{A})$，則解不存在。這時我們希望能在這個$\mathrm{Col}(\mathbf{A})$的平面上找到一個向量，使得$\mathbf{Ax} -\mathbf{b}$的距離能短越好，記為$\min \|\mathbf{Ax} -\mathbf{b} \|$，根據幾何的知識，要讓$\mathbf{Ax} -\mathbf{b}$向量能垂直於$\mathrm{Col}(\mathbf{A})$的平面，因此
$$
\begin{align*}
&\min \|\mathbf{Ax} -\mathbf{b} \|\\
\Rightarrow\;& \mathbf{Ax} -\mathbf{b} \in \mathrm{Col}(\mathbf{A})^\perp = \mathrm{Null}(\mathbf{A}^T)\\
\Rightarrow\;& \mathbf{A}^T (\mathbf{Ax} -\mathbf{b}) = \mathbf{0}\\
\Rightarrow\;& \mathbf{A}^T \mathbf{A} \mathbf{x} = \mathbf{A}^T \mathbf{b} \quad \ldots \text{normal equation}
\end{align*}
$$
由於問題一開始假設$\mathbf{A}$是full column rank，即$\mathrm{rank}(\mathbf{A}_{m \times n}) = n$，根據性質$\mathrm{rank}(\mathbf{A}^T\mathbf{A}) = \mathrm{rank}(\mathbf{A})$，因此$\mathrm{rank}(\mathbf{A}^T \mathbf{A}) = n$，屬於full rank，$\det(\mathbf{A}^T \mathbf{A}) \neq 0$，因此矩陣$\mathbf{A}^T \mathbf{A}$可逆。最後推得
$$
\mathbf{x} = (\mathbf{A}^T \mathbf{A})^{-1} \mathbf{A}^T \mathbf{b}
$$

:::info
- 證明性質$\mathrm{rank}(\mathbf{A}^T\mathbf{A}) = \mathrm{rank}(\mathbf{A})$<br>
證明思路為先證明零核空間相同，再根據rank–nullity theorem證明。
1. 證明$\mathrm{Null(\mathbf{A}^T\mathbf{A})} = \mathrm{Null(\mathbf{A})}$，使用左包右，右包左證明<br>
- 左包右$\mathrm{Null(\mathbf{A})} \subseteq \mathrm{Null(\mathbf{A}^T\mathbf{A})}$
$$
\begin{align*}
& \forall \mathbf{x} \in \mathrm{Null(\mathbf{A})}\\
\Rightarrow\;& \mathbf{A} \mathbf{x} = \mathbf{0}\\
\Rightarrow\;& \mathbf{A}^T \mathbf{A} \mathbf{x} = \mathbf{A}^T \mathbf{0} = \mathbf{0}\\
\Rightarrow\;& \mathbf{x} \in \mathrm{Null(\mathbf{A}^T\mathbf{A})}
\end{align*}
$$
- 右包左$\mathrm{Null(\mathbf{A}^T\mathbf{A})} \subseteq \mathrm{Null(\mathbf{A})}$
$$
\begin{align*}
& \forall \mathbf{x} \in \mathrm{Null(\mathbf{A}^T \mathbf{A})}\\
\Rightarrow\;& \mathbf{A}^T \mathbf{A} \mathbf{x} = \mathbf{0}\\
\Rightarrow\;& \mathbf{x}^T \mathbf{A}^T \mathbf{A} \mathbf{x} = \mathbf{x}^T \mathbf{0} = \mathbf{0}\\
\Rightarrow\;& (\mathbf{A} \mathbf{x})^T(\mathbf{A} \mathbf{x}) = \mathbf{0}\\
\Rightarrow\;& \| \mathbf{A} \mathbf{x} \|^2 = 0\\
\Rightarrow\;& \mathbf{A} \mathbf{x} = \mathbf{0}\\
\Rightarrow\;& \mathbf{x} \in \mathrm{Null(\mathbf{A})}
\end{align*}
$$
2. 根據rank–nullity theorem證明$\mathrm{rank}(\mathbf{A}^T\mathbf{A}) = \mathrm{rank}(\mathbf{A})$<br>
給定矩陣$\mathbf{A}_{m \times n}$，因此$(\mathbf{A}^T \mathbf{A})_{n \times n}$，由rank–nullity theorem列出聯立方程式
$$
\begin{cases}
\mathrm{nullity}(\mathbf{A}) &= \dim(\mathrm{Null}(\mathbf{A})) &= n - \mathrm{rank}(\mathbf{\mathbf{A}})\\
\mathrm{nullity}(\mathbf{A}^T \mathbf{A}) &= \dim(\mathrm{Null}(\mathbf{A}^T \mathbf{A})) &= n - \mathrm{rank}(\mathbf{A}^T\mathbf{\mathbf{A}})\\
\end{cases}
$$
由於$\mathbf{A}$和$\mathbf{A}^T \mathbf{A}$的零核空間相同$\mathrm{Null(\mathbf{A}^T\mathbf{A})} = \mathrm{Null(\mathbf{A})}$，因此零核空間維數相同$\mathrm{nullity}(\mathbf{A}) = \mathrm{nullity}(\mathbf{A}^T \mathbf{A})$，根據rank–nullity theorem關係式就可以推得$\mathrm{rank}(\mathbf{A}^T\mathbf{A}) = \mathrm{rank}(\mathbf{A})$。
:::

## 最小平方問題解法2 - 微積分理論
定義一函數$\mathbf{Ax} -\mathbf{b}$為取norm的平方，這是取距離平方是為了方便運算。
$$
F : \mathbb{R}^n \to \mathbb{R}, F(\mathbf{x}) = \| \mathbf{Ax} -\mathbf{b} \|^2
$$
欲求極值，就是找critical point，對於一個多變數實函數而言，要使所有方向的一階偏導數等於0，也就是**梯度等於0**。
$$
\text{find critical point} \Rightarrow \nabla F(\mathbf{x}) \triangleq \frac{\partial F(\mathbf{x})}{\partial\mathbf{x}} = [\frac{\partial F(\mathbf{x})}{\partial x_1}, \frac{\partial F(\mathbf{x})}{\partial x_2}, \ldots, \frac{\partial F(\mathbf{x})}{\partial x_n}] = 0
$$
欲求梯度$\nabla F(\mathbf{x})$除了可以將將函數對每一項分量做偏微分，另一種較方便的解法是先求方向導數，再**根據"方向導數為梯度與該方向的內積"這個關係式求得梯度**。
$$
D_\mathbf{y} F(\mathbf{x}) = (\nabla F(\mathbf{x})) \cdot \mathbf{y} \quad\text{for any unit vector } \mathbf{y}
$$
觀察上式的form，欲求梯度，嘗試先求方向導數，並整理成一個向量跟單位方向向量的內積的form，這個向量就是梯度。
$$
\begin{align*}
D_\mathbf{y} F(\mathbf{x}) &\triangleq \lim_{\epsilon \to 0} \frac{F(\mathbf{x} + \epsilon \mathbf{y}) - F(\mathbf{x})}{\epsilon}\\
&= \lim_{\epsilon \to 0} \frac{1}{\epsilon} \left[ \| \mathbf{A} (\mathbf{x} + \epsilon \mathbf{y}) -\mathbf{b} \|^2 - \| \mathbf{A}\mathbf{x} -\mathbf{b} \|^2 \right]\\
&= \lim_{\epsilon \to 0} \frac{1}{\epsilon} \left[ \| (\mathbf{A} (\mathbf{x} -\mathbf{b}) + \epsilon \mathbf{y}) \|^2 - \| \mathbf{A}\mathbf{x} -\mathbf{b} \|^2 \right]\\
&= \lim_{\epsilon \to 0} \frac{1}{\epsilon} \left[ \| \mathbf{A}\mathbf{x} -\mathbf{b} \|^2 + 2(\mathbf{Ax} - \mathbf{b}) \cdot (\epsilon \mathbf{Ay}) + \| \epsilon \mathbf{Ay} \|^2 - \| \mathbf{A}\mathbf{x} -\mathbf{b} \|^2 \right]\\
&= 2(\mathbf{A}\mathbf{x} -\mathbf{b}) \cdot (\mathbf{Ay})\\
&= 2(\mathbf{A}\mathbf{x} -\mathbf{b})^T (\mathbf{Ay})\\
&= 2[\mathbf{A}^T (\mathbf{A}\mathbf{x} -\mathbf{b})]^T \mathbf{y}\\
&= \underbrace{ 2[\mathbf{A}^T (\mathbf{A}\mathbf{x} -\mathbf{b})] }_{\nabla F(\mathbf{x})} \cdot \mathbf{y}\\
\end{align*}
$$
故critical point即為
$$
\begin{align*}
& \text{find critical point}\\
\Rightarrow\;& \nabla F(\mathbf{x}) = 0\\
\Rightarrow\;& 2[\mathbf{A}^T (\mathbf{A}\mathbf{x} -\mathbf{b})] = 0\\
\Rightarrow\;& \mathbf{A}^T \mathbf{A}\mathbf{x} = \mathbf{A}^T \mathbf{b}
\end{align*}
$$
同法一最後推得
$$
\mathbf{x} = (\mathbf{A}^T \mathbf{A})^{-1} \mathbf{A}^T \mathbf{b}
$$

## 最小範數問題(least norm problem)
考慮$\mathbf{A}_{m \times n} \mathbf{x}_{n \times 1} = \mathbf{b}_{m \times 1}$，若$m < n, \mathrm{rank}(\mathbf{A}) = m$，也就是說有效方程式$m$條，少於未知數$n$個，屬於underdetermined problem，具有無限多組解，可將解拆為齊次解與特解。
$$
\mathbf{x} = \mathbf{x}_h + \mathbf{x}_p
$$
其中齊次解$\{\mathbf{x}_h \mid \mathbf{Ax}_h = \mathbf{0}\}$為$\mathbb{R}^n$的子空間，屬於null space，以下圖$\mathbb{R}^3$空間為例，就是通過原點的平面，而特解就是將此平面做平移。欲求最佳的解，加上限制項 - 要讓解的距離最小。

## 最小範數問題解法1 - 線性代數理論
<br>
要使$\mathbf{x} = \mathbf{x}_h + \mathbf{x}_p$的集合落在平面，要使$\mathbf{x}$的距離最小，就是讓向量$\mathbf{x}$跟平面垂直。
$$
\begin{align*}
&\min \|\mathbf{x} \|\\
\Rightarrow\;& \mathbf{x} \in \mathrm{Null}(\mathbf{A})^\perp = \mathrm{Row}(\mathbf{A}) = \mathrm{Col}(\mathbf{A}^T)\\
\Rightarrow\;& \mathbf{x} = \mathbf{A}^T \mathbf{w}\\
\Rightarrow\;& \mathbf{A} \mathbf{x} = \mathbf{A} \mathbf{A}^T \mathbf{w} = \mathbf{b}\\
\end{align*}
$$
由於問題假設$\mathrm{rank}(\mathbf{A}) = m$加上性質$\mathrm{rank}(\mathbf{A}) = \mathrm{rank}(\mathbf{A}\mathbf{A}^T)$，因此矩陣$\mathbf{A}\mathbf{A}^T$是full rank，行列式值不等於0，存在可逆矩陣$(\mathbf{A}\mathbf{A}^T)^{-1}$，因此進一步推導
$$
\begin{align*}
& \mathbf{A} \mathbf{x} = \mathbf{A} \mathbf{A}^T \mathbf{w} = \mathbf{b}\\
\Rightarrow\;& \mathbf{w} = (\mathbf{A} \mathbf{A}^T)^{-1} \mathbf{b}\\
\Rightarrow\;& \mathbf{x} = \mathbf{A}^T \mathbf{w} = \mathbf{A}^T (\mathbf{A} \mathbf{A}^T)^{-1} \mathbf{b}
\end{align*}
$$

## 最小範數問題解法2 - 微積分理論
定義一函數$\mathbf{x}$距離的平方，取距離平方是為了方便運算。
$$
F : \mathbb{R}^n \to \mathbb{R}, f(\mathbf{x}) = \| \mathbf{x} \|^2 = \mathbf{x}^T \mathbf{x}
$$
在限制條件$\vec{g}(\mathbf{x}) = \mathbf{Ax} - \mathbf{b} = 0$之下，欲求$\min f(\mathbf{x})$，這種帶有限制條件的極值問題，就需要使用Lagrange multiplier，把Lagrange multiplier $\mathbf{\lambda}$想像是變數，因此將**帶有限制項的單變數向量$\mathbf{x}$求極值問題，拓展為雙變數向量$\mathbf{x}, \mathbf{\lambda}$求極值問題**。需要注意這裡Lagrange multiplier $\mathbf{\lambda}$是帶有$m$條限制式的向量形式。
$$
\begin{align*}
& \min f(\mathbf{x}) \;\text{subject to } \vec{g}(\mathbf{x})\\
\Rightarrow\;& \min \left[ F(\mathbf{x}, \mathbf{\lambda}) = f(\mathbf{x}) + \mathbf{\lambda} \cdot \vec{g}(\mathbf{x}) \right]\\
\Rightarrow\;&
\begin{cases}
\nabla_{\mathbf{\lambda}}F(\mathbf{x}, \mathbf{\lambda}) = \vec{g}(\mathbf{x}) = \mathbf{0}\\
\nabla_{\mathbf{\mathbf{y}}} F(\mathbf{x}, \mathbf{\lambda}) = \nabla_{\mathbf{\mathbf{x}}} f(\mathbf{x}) + \mathbf{\lambda} \cdot \nabla_{\mathbf{x}} \vec{g}(\mathbf{x})
\end{cases}
\end{align*}
$$
由上式可以看出[Lagrange multiplier在幾何上的意義](https://www.youtube.com/watch?v=3ahgXXv-_j8)，假設在向量空間$\mathbb{R}^3$，發生極值的條件為$f(\mathbf{x})$的等位曲面與$\vec{g}(\mathbf{x})$的等位曲面相切，兩個等位曲面相切，則代表兩個梯度向量會平行，彼此只會差上一個常數倍，這個常數就是Lagrange multiplier。

帶入數值計算
$$
\begin{align*}
& \min f(\mathbf{x}) = \mathbf{x}^T \mathbf{x} \;\text{subject to } \vec{g}(\mathbf{x}) = \mathbf{Ax} - \mathbf{b} = 0\\
\Rightarrow\;& \min \left[ F(\mathbf{x}, \mathbf{\lambda}) = \mathbf{x}^T \mathbf{x} + \mathbf{\lambda}^T (\mathbf{Ax} - \mathbf{b}) \right]\\
\Rightarrow\;&
\begin{cases}
\nabla_{\mathbf{\lambda}}F(\mathbf{x}, \mathbf{\lambda}) = \mathbf{Ax} - \mathbf{b} = \mathbf{0}\\
\nabla_{\mathbf{\mathbf{y}}} F(\mathbf{x}, \mathbf{\lambda}) = \;? = 0
\end{cases}
\end{align*}
$$
欲求梯度$\nabla_{\mathbf{\mathbf{y}}} F(\mathbf{x})$，同前面最小平方問題的技巧，先求方向導數，並整理成一個向量跟單位方向向量的內積的form，這個向量就是梯度。
$$
\begin{align*}
D_\mathbf{y} F(\mathbf{x}, \mathbf{\lambda}) &\triangleq \lim_{\epsilon \to 0} \frac{F(\mathbf{x} + \epsilon \mathbf{y}, \mathbf{\lambda}) - F(\mathbf{x}, \mathbf{\lambda})}{\epsilon}\\
&= \lim_{\epsilon \to 0} \frac{1}{\epsilon} \left[ \underbrace{ (\mathbf{x} + \epsilon \mathbf{y})^T (\mathbf{x} + \epsilon \mathbf{y}) }_{= \mathbf{x}^T\mathbf{x} + \epsilon \mathbf{x}^T \mathbf{y} + \epsilon^2 \mathbf{y}^T \mathbf{x} + \epsilon^2 \mathbf{y}^T \mathbf{y} } + \mathbf{\lambda}^T ( \underbrace{ \mathbf{A}(\mathbf{x} + \epsilon \mathbf{y}) }_{= \mathbf{Ax} + \epsilon \mathbf{Ay}} - \mathbf{b}) - \mathbf{x}^T \mathbf{x} - \mathbf{\lambda}^T (\mathbf{Ax} - \mathbf{b}) \right]\\
&= \lim_{\epsilon \to 0} \frac{1}{\epsilon} \left[ \epsilon \mathbf{x}^T \mathbf{y} + \epsilon \mathbf{y}^T \mathbf{x} + \epsilon^2 \mathbf{y}^T \mathbf{y} - \epsilon \mathbf{\lambda}^T \mathbf{A}\mathbf{y} \right]\\
&= 2 \mathbf{x}^T \mathbf{y} - \mathbf{\lambda}^T \mathbf{A} \mathbf{y}\\
&= (2 \mathbf{x} - \mathbf{A}^T \mathbf{\lambda})^T \mathbf{y}\\
&= \underbrace{ (2 \mathbf{x} - \mathbf{A}^T \mathbf{\lambda}) }_{\nabla_{\mathbf{\mathbf{y}}} F(\mathbf{x}, \mathbf{\lambda})} \cdot \mathbf{y}
\end{align*}
$$
解得梯度$\nabla_{\mathbf{\mathbf{y}}} F(\mathbf{x})$，因此聯立方程式為
$$
\begin{cases}
\nabla_{\mathbf{\lambda}}F(\mathbf{x}, \mathbf{\lambda}) = \mathbf{Ax} - \mathbf{b} = \mathbf{0} &(1)\\
\nabla_{\mathbf{\mathbf{y}}} F(\mathbf{x}, \mathbf{\lambda}) = 2 \mathbf{x} - \mathbf{A}^T \mathbf{\lambda} = 0 \Rightarrow \mathbf{x} = \frac{1}{2} \mathbf{A}^T \mathbf{\lambda} &(2)
\end{cases}
$$
將式(2)帶入式(1)得
$$
\mathbf{A}(\frac{1}{2} \mathbf{A}^T \mathbf{\lambda}) - \mathbf{b} = \mathbf{0} \Rightarrow \mathbf{A} \mathbf{A}^T \mathbf{\lambda} = 2\mathbf{b}
$$
由於問題假設$\mathrm{rank}(\mathbf{A}) = m$加上性質$\mathrm{rank}(\mathbf{A}) = \mathrm{rank}(\mathbf{A}\mathbf{A}^T)$，因此矩陣$\mathbf{A}\mathbf{A}^T$是full rank，行列式值不等於0，存在可逆矩陣$(\mathbf{A}\mathbf{A}^T)^{-1}$，使得
$$
\Rightarrow \mathbf{\lambda} = 2 (\mathbf{A} \mathbf{A}^T )^{-1} \mathbf{b} \tag{3}
$$
將式(3)帶回式(2)得
$$
\mathbf{x} = \frac{1}{2} \mathbf{A}^T \mathbf{\lambda} = \mathbf{A}^T (\mathbf{A} \mathbf{A}^T)^{-1} \mathbf{b}
$$

## 最小平方與範數問題同時發生(least square & norm problem)
考慮$\mathbf{A}_{m \times n} \mathbf{x}_{n \times 1} = \mathbf{b}_{m \times 1}$，若$\mathrm{rank}(\mathbf{A}) = r < m, n$，想要找到向量$\mathbf{x}$使得$\min \| \mathbf{Ax} - \mathbf{b} \|$，並且在這些無限多組解中找到能$\min \| \mathbf{x} \|$。

## 最小平方與範數問題同時發生解法
- 由於$\mathrm{rank}(\mathbf{A}) = r < n$，故$\mathbf{A}^T \mathbf{A}$不可逆，若使用最小平方法只能解到$\mathbf{A}^T \mathbf{A}\mathbf{x} = \mathbf{A}^T \mathbf{b}$而卡住。
- 由於$\mathrm{rank}(\mathbf{A}) = r < m$，故$\mathbf{A} \mathbf{A}^T$不可逆，若使用最小範數法只能解到$\mathbf{x} = \mathbf{A}^T \mathbf{w}, \mathbf{A} \mathbf{A}^T \mathbf{w} = \mathbf{b}$而卡住。

因此使用SVD這個好用的工具下去求解，將$\mathbf{A}$做SVD分解，再求$\| \mathbf{Ax} - \mathbf{b} \|$
$$
\begin{align*}
\| \mathbf{A} \mathbf{x} - \mathbf{b} \|
&= (\mathbf{U\Sigma V}^T) \mathbf{x} - \mathbf{b} \|\\
&= \| \mathbf{U}^T (\mathbf{U\Sigma V}^T \mathbf{x} - \mathbf{b}) \| \quad\text{where } \mathbf{U} \text{ is orthogonal matrix}\\
&= \| \mathbf{\Sigma V}^T \mathbf{x} - \mathbf{U}^T \mathbf{b} \|
\end{align*}
$$
這時再將$\mathbf{x}$做基底轉換為$\mathbf{y}$，將$\mathbf{b}$做基底轉換為$\mathbf{c}$
$$
\text{denote } \mathbf{V}^T \mathbf{x} = \mathbf{y} \in \mathbb{R}^n, \mathbf{U}^T \mathbf{b} = \mathbf{c} \in \mathbb{R}^m \quad\text{ie } \mathbf{x} = \mathbf{Vy}, \mathbf{b} = \mathbf{Uc}
$$
因此轉換為
$$
\begin{align*}
\| \mathbf{\Sigma V}^T \mathbf{x} - \mathbf{U}^T \mathbf{b} \| &= \| \mathbf{\Sigma y} - \mathbf{c} \|\\
&= \left\|
\begin{bmatrix}
\sigma_1 & \cdots & \mathbf{0} & \mathbf{0}\\
\vdots & \ddots & \vdots & \mathbf{0}\\
\mathbf{0} & \cdots & \sigma_r & \mathbf{0}\\
\mathbf{0} & \mathbf{0} & \mathbf{0} & \mathbf{0}
\end{bmatrix}
\begin{bmatrix}
y_1\\ \vdots\\ \vdots\\ y_n
\end{bmatrix}
- \begin{bmatrix}
c_1\\ \vdots\\ \vdots\\ c_n
\end{bmatrix}
\right\|\\
&= \left\|
\begin{bmatrix}
\sigma_1 y_1 - c_1\\ \vdots\\ \sigma_r y_r - c_r\\ - c_{r + 1}\\ \vdots\\ c_m
\end{bmatrix}
\right\|\\
\end{align*}
$$
因此我們把$\min \| \mathbf{A} \mathbf{x} - \mathbf{b} \|$的問題，轉換為$\min \| \mathbf{\Sigma y} - \mathbf{c} \|$，其中可以變動的是解$\mathbf{x}$，而解$\mathbf{x}$經過基底轉換後變成$\mathbf{y}$，因此只有$\mathbf{y}$可變動，根據上面推導的form，把最小化$\| \mathbf{\Sigma y} - \mathbf{c} \|$就是把$r$項弄為0，選擇
$$
y_i = \sigma_i^{-1} c_i, \; 1 \leq i \leq r
$$
再滿足最小平方問題後，再來滿足最小範數問題，欲$\min \| \mathbf{x} \|$，即為$\min \| \mathbf{y} \|$，因此後面$r$項取0
$$
y_i = 0, \; r + 1 \leq i \leq n
$$
總結$\mathbf{y}$為
$$
\mathbf{y} =
\begin{bmatrix}
\sigma_1^{-1} c_1\\ \vdots\\ \sigma_r^{-1} c_r\\ 0\\ \vdots\\ 0
\end{bmatrix}_{n \times 1}
= \begin{bmatrix}
\sigma_1^{-1} & \cdots & \mathbf{0} & \mathbf{0}\\
\vdots & \ddots & \vdots & \vdots\\
\mathbf{0} & \cdots & \sigma_r^{-1} & \mathbf{0}\\
\mathbf{0} & \mathbf{0} & \mathbf{0} & \mathbf{0}\\
\vdots & \vdots & \vdots & \vdots\\
\mathbf{0} & \mathbf{0} & \mathbf{0} & \mathbf{0}
\end{bmatrix}_{n \times m}
\begin{bmatrix}
c_1\\ \vdots\\ c_r\\ c_{r + 1}\\ \vdots\\ c_m
\end{bmatrix}_{m \times 1} = \mathbf{\Sigma}^+ \mathbf{c}
$$
最後變數變換(基底轉換)回原本的變數
$$
\mathbf{y} = \mathbf{\Sigma}^+ \mathbf{c} \Rightarrow \mathbf{V}^{-1} \mathbf{x} = \mathbf{\Sigma}^+ \mathbf{U}^T \mathbf{b} \Rightarrow \mathbf{x} = \mathbf{V\Sigma}^+ \mathbf{U}^T \mathbf{b}
$$

## 總結 - 定義虛反矩陣(pseudoinverse)
給定秩數$r$的矩陣$\mathbf{A}_{m \times n}$，做奇異值分解為
$$
\mathbf{A}_{m \times n} = \mathbf{U}_{m \times m} \mathbf{\Sigma}_{m \times n} (\mathbf{V}^T)_{n \times n}, \text{ where } \mathbf{\Sigma} =
\begin{bmatrix}
\sigma_1 & \cdots & \mathbf{0} & \mathbf{0}\\
\vdots & \ddots & \vdots & \vdots\\
\mathbf{0} & \cdots & \sigma_r & \mathbf{0}\\
\mathbf{0} & \mathbf{0} & \mathbf{0} & \mathbf{0}\\
\vdots & \vdots & \vdots & \vdots\\
\mathbf{0} & \mathbf{0} & \mathbf{0} & \mathbf{0}
\end{bmatrix}_{m \times n}
$$
則虛反矩陣(pseudoinverse)定義為
$$
\mathbf{A}^+ = \mathbf{V}\mathbf{\Sigma}^+\mathbf{U}^T, \text{ where } \mathbf{\Sigma}^+ =
\begin{bmatrix}
\sigma_1^{-1} & \cdots & \mathbf{0} & \mathbf{0}\\
\vdots & \ddots & \vdots & \vdots\\
\mathbf{0} & \cdots & \sigma_r^{-1} & \mathbf{0}\\
\mathbf{0} & \mathbf{0} & \mathbf{0} & \mathbf{0}\\
\vdots & \vdots & \vdots & \vdots\\
\mathbf{0} & \mathbf{0} & \mathbf{0} & \mathbf{0}
\end{bmatrix}_{n \times m}
$$

在求解線性方程式$\mathbf{Ax} = \mathbf{b}$，其最小平方問題與最小範數問題的通解就是
$$
\text{solve } \mathbf{Ax} = \mathbf{b} \Rightarrow \mathbf{x} = \mathbf{A}^+ \mathbf{b} = (\mathbf{V}\mathbf{\Sigma}^+\mathbf{U}^T) \mathbf{b}
$$
而經過數學推導(省略)，可以得出結論 - 最小平方問題、最小範數問題都是用虛反矩陣求解$\mathbf{x} = \mathbf{A}^+ \mathbf{b}$時的特例

給定矩陣$\mathbf{}$
- 最小平方問題 - 如果$m \geq n$且$\mathrm{rank}(\mathbf{A}) = n$，則$\mathbf{A}^+ = (\mathbf{A}^T \mathbf{A})^{-1} \mathbf{A}^T$。
- 最小範數問題 - 如果$m \leq n$且$\mathrm{rank}(\mathbf{A}) = m$，則$\mathbf{A}^+ = \mathbf{A}^T(\mathbf{A} \mathbf{A}^T)^{-1}$。

## 主成分分析(PCA)問題與前處理
給定二維資料$\{ x_i, y_i\}_{i = 1}^n$，我們想找到一條直線來擬合這些資料，這就是線性回歸問題，有以下2種方法
1. 找最小的垂直距離，誤差函數即為
$$
E(a_0, a_1) = \sum^n_{i = 1} (a_0 + a_1 x_i - y_i)^2
$$
這就是underdetermined problem，使用最小平方法求解。
2. 找最小的水平距離，誤差函數即為
$$
E(b_0, b_1) = \sum^n_{i = 1} (b_0 + b_1 y_i - x_i)^2
$$

寫垂直距離所隱含的意義為預設預設$y$是$x$的函數，記為$y = f(x)$，$x$為自變數，$y$是應變數，兩變數有這種從屬關係，舉例來說$x$軸代表實驗時測量的時間，$y$軸代表測量數據。但是在現實中的有些資料並不存在這種變數之間的從屬關係，因此用線性回歸做資料分析，對資料本身還是不太公平，而就數學的觀點來說對$y= f(x)$或是$x = f(y)$做線性回歸出來的直線並不同。

因此我們開始思考 - 要如何讓$x, y$這兩個變數能平等對待?我們嘗試**找擬合直線與數據點的最小距離，這樣就沒有變數之間的從屬關係**，誤差函數即為
$$
E(c_0, c_1) = \sum^n_{i = 1} (c_0 + c_1 y_i - x_i)^2
$$
若要計算該直線，就發現$\frac{\partial E}{\partial c_0} = \frac{\partial E}{\partial c_1} = 0$難以計算。

因此我們的想法是把所有資料**移到資料中心**，這樣就不需要計算截距。第二步就是將資料根據資料的"特性"做適當的**正規化**，避免受到原數據特性的影響。
$$
\begin{align*}
& \overline{x}_i = \frac{x_i - \overline{x}}{x_c}, \overline{y}_i = \frac{y_i - \overline{y}}{y_c}\\
& \text{where mean } \overline{x} = \frac{1}{n} \sum^n_{i = 1} x_i, \overline{y} = \frac{1}{n} \sum^n_{i = 1} y_i\\
& \text{where characteristic value } x_c, y_c
\end{align*}
$$

## 1個分量的PCA推導
給已中心化與正規化的$m$筆資料，每筆資料有$n$分量$\mathbf{p}_1, \mathbf{p}_2, \ldots, \mathbf{p}_m \in \mathbb{R}^n$，並定義資料矩陣
$$
\mathbf{P} = \begin{bmatrix} \mathbf{p}_1^T\\ \mathbf{p}_2^T\\ \vdots\\ \mathbf{p}_m^T\\ \end{bmatrix}_{m \times n}
$$
欲擬合的方程式為
$$
\{ \alpha \mathbf{v} \mid \alpha \in \mathbb{R} \}, \mathbf{v} \in \mathbb{R}^n, \| \mathbf{v} \| = 1
$$
定義數據點到擬合直線的距離，並由下圖幾何圖形圖解
$$
\begin{align*}
d_i &= \min_{\alpha \in \mathbb{R}} \|\mathbf{p}_i - \alpha \mathbf{v}\|\\
&= \sqrt{\| \mathbf{p}_i \|^2 - |\mathbf{p}_i \cdot \mathbf{v} |^2}\\
&= \sqrt{ \mathbf{p}_i \cdot \mathbf{p}_i - ( \mathbf{p}_i \cdot \mathbf{v})^2 }
\end{align*}
$$
定義誤差函數為最小距離的平方和，可以變動的擬合直線的向量$\mathbf{v}$
$$
E(\mathbf{v}) = \sum^m_{i = 1} d_i^2 = \sum^m_{i = 1} \left[ \mathbf{p}_i \cdot \mathbf{p}_i - ( \mathbf{p}_i \cdot \mathbf{v})^2 \right]
$$
因此目標為要找到一個擬合的向量$\mathbf{v}$，使得誤差函數能極小化$\min E(\mathbf{v})$，但是這個$\mathbf{v}$在選擇上有限制要是單位向量$\| \mathbf{v} \| = 1$，因此有限制的極值問題就需要使用Lagrange multiplier
$$
\begin{align*}
&\min F(\mathbf{v}, \lambda) = \min \left[ \sum^m_{i = 1} \left[ \mathbf{p}_i \cdot \mathbf{p}_i - ( \mathbf{p}_i \cdot \mathbf{v})^2 \right] + \lambda (\|\mathbf{v}\|^2 - 1) \right]\\
\Rightarrow\;&
\begin{cases}
\frac{\partial F}{\partial \lambda} = \| \mathbf{v} \|^2 - 1 = 0\\
\frac{\partial F}{\partial \mathbf{v}} = -2 \sum^m_{i = 1}(\mathbf{p}_i \cdot \mathbf{v})\mathbf{p}_i + 2\lambda \mathbf{v} = 0
\end{cases}
\end{align*}
$$
其中$\frac{\partial F}{\partial \mathbf{v}}$的求法，同前面最小平方法的技巧，先求方向導數，並整理為方向導數為梯度向量與方向向量的內積關係式，得梯度向量$\frac{\partial F}{\partial \mathbf{v}}$。再進一步推導
$$
\begin{align*}
&\frac{\partial F}{\partial \mathbf{v}} = 0\\
\Rightarrow\;& -2 \sum^m_{i = 1}(\mathbf{p}_i \cdot \mathbf{v})\mathbf{p}_i + 2\lambda \mathbf{v} = 0\\
\Rightarrow\;& \sum^m_{i = 1}(\mathbf{p}_i \cdot \mathbf{v})\mathbf{p}_i = \lambda \mathbf{v}\\
\Rightarrow\;& [\mathbf{p}_1, \ldots, \mathbf{p}_m]
\begin{bmatrix}
\mathbf{p}_1^T \mathbf{v}\\ \vdots\\ \mathbf{p}_m^T \mathbf{v}
\end{bmatrix}
= [\mathbf{p}_1, \ldots, \mathbf{p}_m]
\begin{bmatrix}
\mathbf{p}_1^T\\ \vdots\\ \mathbf{p}_m^T
\end{bmatrix} \mathbf{v} = \lambda \mathbf{v}\\
\Rightarrow\;& \mathbf{P}^T \mathbf{P} \mathbf{v} = \lambda \mathbf{v}\\
\Rightarrow\;& \mathbf{v} \text{ is an eigenvector of } \mathbf{P}^T \mathbf{P} \text{ with eigenvalue } \lambda\\
\Rightarrow\;& \mathbf{v}^T \mathbf{P}^T \mathbf{P} \mathbf{v} = \lambda \mathbf{v}^T \mathbf{v}\\
\Rightarrow\;& \| \mathbf{P} \mathbf{v} \|^2 = \lambda \| \mathbf{v} \|^2\\
\Rightarrow\;& \| \mathbf{P} \mathbf{v} \|^2 = \lambda \qquad \because \frac{\partial F}{\partial \lambda} = \| \mathbf{v} \|^2 - 1 = 0\\
\Rightarrow\;& \left\|
\begin{bmatrix}
\mathbf{p}_1^T\\ \vdots\\ \mathbf{p}_m^T
\end{bmatrix} \mathbf{v} \right\|^2
= \left\| \begin{bmatrix}
\mathbf{p}_1 \cdot \mathbf{v}\\ \vdots\\ \mathbf{p}_m^ \cdot \mathbf{v}
\end{bmatrix}
\right\|^2
= \sum^m_{i = 1} (\mathbf{m}_i \cdot \mathbf{v})^2 = \lambda
\end{align*}
$$
帶入誤差函數
$$
E(\mathbf{v}) = \sum^m_{i = 1} d_i^2 = \sum^m_{i = 1} \left[ \mathbf{p}_i \cdot \mathbf{p}_i - ( \mathbf{p}_i \cdot \mathbf{v})^2 \right] = \sum^m_{i = 1} \| \mathbf{p}_i \|^2 - \lambda
$$
其中的Lagrange multiplier $\lambda$就是前面求的$\mathbf{P}^T \mathbf{P}$的特徵值，即為資料矩陣做SVD分解$\mathbf{P} = \mathbf{U\Sigma V}^T$後，得到奇異值平方$\lambda = \sigma^2$，要極小化誤差函數$E(\mathbf{v})$就是想辦法讓$\mathbf{P}$的奇異值越大越好，因此選擇最大的奇異值$\lambda = \sigma_1^2$，而該奇異值對應到右奇異值向量就是擬合直線的向量$\mathbf{v} = \mathbf{v}_1$。

## 高維度分量的PCA推導
同理兩個分量的PCA，推廣至高維度的分量，即可得到結論。

Given centered data $\mathbf{p}_1, \mathbf{p}_2, \ldots, \mathbf{p}_m \in \mathbb{R}^n$ and data matrix $\mathbf{P} = \begin{bmatrix} \mathbf{p}_1^T\\ \mathbf{p}_2^T\\ \vdots\\ \mathbf{p}_m^T\\ \end{bmatrix} \in \mathbb{R}^{m \times n}$

SVD : $\mathbf{P} = \mathbf{U\Sigma V}^T$

Fit the data by k-dimensional subspace ($k < n$) ${\alpha_1 \mathbf{w}_1 + \ldots + \alpha_k \mathbf{w}_k \mid \alpha_1, \ldots, \alpha_k }$ with orthonormal basis $\{ \mathbf{w}_1, \ldots \mathbf{w}_k \}$

Error function
$$
E(\mathbf{w}_1, \ldots, \mathbf{w}_k) = \sum^m_{i = 1} \mathbf{p}_i \cdot \mathbf{p}_i - (\mathbf{p}_i \cdot \mathbf{w}_i)^2 - \ldots - (\mathbf{p}_i \cdot \mathbf{w}_k)^2
$$
is minimized by choosing first $k$ sigular vectors of $V$ with $E(\mathbf{v}_1, \ldots, \mathbf{v}_k) = \sum^m_{i = 1} \mathbf{p}_i \cdot \mathbf{p}_i - \sigma_1^2 - \ldots - \sigma_k^2$