向量的 norm 我們很熟悉了, 但對於一個矩陣的 norm 又該怎麼定義呢?
最直覺的想法就是把矩陣 flatten 成一個向量, 套用向量的 norm 即可. 這引導出了 Frobenius norm.
但是矩陣還包含了將向量做線性轉換的作用, 所以向量經過矩陣轉換後的 norm 變化是不是可以用來當作矩陣 norm 的度量方式呢? 這樣的想法引導出了 operator norm 或 spectral norm.
先給出 take away 總結:
Frobenius norm: 開根號的 “singular value 平方和”
$$\begin{aligned} \|A\|_F := \sqrt{\sum_{i,j}|a_{ij}|^2} =\mathrm{Tr}(A^HA)=\sqrt{\sum_i^{\min\{m,n\}}\sigma_i^2(A)} \end{aligned}$$Spectral norm: 最大的 singular value
$$\begin{aligned} \|A\|_2 :=\sup_{\|x\|_2\leq1}\{\|Ax\|_2\}=\sqrt{\lambda_{\max}(A^HA)}=\sigma_{\max}(A) \end{aligned}$$
💡 為什麼 spectral norm 這麼定義?
推薦閱讀周老師的文章, 矩陣範數, 非常具有啟發性！更多延伸：譜半徑與矩陣範數
- 兩者的關係: $$\begin{aligned} \|A\|_2 \leq \|A\|_F \end{aligned}$$
接著詳細記錄定義和推導證明 (參考自黃子嘉線性代數講義)
Operator, Spectral 與 Frobenius Norm 的定義
對於一個 $m\times n$ 矩陣 $A$ 來說, 令有兩個 vector norm $\|\cdot\|_\alpha$ 和 $\|\cdot\|_\beta$.
則 $A$ 的 operator norm 定義如下 [wiki]:
$$\begin{align}
\|A\|_p=\sup_{\|x\|_p\leq1}\{\|Ax\|_p\}
\end{align}$$ 當 $p=2$ 的時候我們稱為 spectral norm, 它有一個重要的特性為
$$\begin{align}
{\color{orange}{\|A\|_2=\sqrt{\lambda_{\max}(A^HA)}=\sigma_{\max}(A)}}
\end{align}$$ 其中 $\lambda_{\max},\sigma_{\max}$ 分別是最大的 eigenvalue 和 singular value
對於矩陣還有一個常見的 norm 為 Frobenius norm, 定義如下:
$$\begin{align}
{\color{orange}{\|A\|_F}} &= \sqrt{\sum_{i,j}|a_{ij}|^2} \\ &
{\color{orange}{=\sqrt{\mathrm{Tr}(A^HA)}=\sqrt{\sum_i^{\min\{m,n\}}\sigma_i^2(A)} }}
\end{align}$$ 其中 $\sigma_i$ 表示 i-th singular value of $A$.
則可以看出, 如果 $A$ 只有一個非 $0$ 的 singular value, 則剛好 $\|A\|_F=\sigma_{\max}(A)=\|A\|_2$.
因此 spectral norm 和 Frobenius norm 有如下關係:
$$\begin{align}
{\color{orange}{ \|A\|_2 \leq \|A\|_F }}
\end{align}$$ 接著來證明 spectral norm 與 eigen/singular value 的關係 (式 (2))
證明 Spectral Norm 是最大的 Singular Value
先定義 Rayleigh Quotient, 假設 $A\in\mathbb{C}^{n\times n}$ 為 Hermitian matrix, i.e. $A^H=A$
Rayleigh Quotient Principle
定義 Rayleigh Quotient $\rho(x)$ 為
$$\begin{align}
\rho(x)=\frac{Q(x)}{\|x\|_2^2} \\
, \text{where }\quad Q(x)=x^HAx
\end{align}$$ 則 $\lambda_1\leq\rho(x)\leq\lambda_n$, 其中 $\lambda_i$ 為 i-th eigenvalue 且為由小到大排序.
並且有 $\max_x\rho(x)=\lambda_n$ 和 $\min_x\rho(x)=\lambda_1$ 的關係.
茲證明如下
因為 $A$ 為 Hermitian 矩陣, 所以 $A$ 可以對角化:
$A=PDP^H$, 其中 $P$ 為 unitary matrix, $D$ 為由 eigenvalues $\{\lambda_i\}_{i=1}^n$ 構成的對角矩陣
代入 (6) 得到
$$\begin{aligned}
\rho(x) &=\frac{x^HPDP^Hx}{x^Hx}=\frac{(P^Hx)^HD(P^Hx)}{x^HPP^Hx} \\
&= \frac{(P^Hx)^HD(P^Hx)}{(P^Hx)^H(P^Hx)}=:\frac{y^HDy}{y^Hy}=\frac{\sum_{i=1}^n y_i^2\lambda_i}{\sum_{i=1}^n y_i^2}
\end{aligned}$$ 其中我們令 $y:=P^Hx$. 所以得到:
$$\begin{align}
\lambda_{\color{orange}{1}}= \frac{\sum_{i=1}^n y_i^2\lambda_{\color{orange}{1}}}{\sum_{i=1}^n y_i^2}\leq \rho(x)=\frac{\sum_{i=1}^n y_i^2\lambda_i}{\sum_{i=1}^n y_i^2}\leq \frac{\sum_{i=1}^n y_i^2\lambda_{\color{orange}{n}}}{\sum_{i=1}^n y_i^2}=\lambda_{\color{orange}{n}}
\end{align}$$ Q.E.D.
Spectral Norm 對應最大的 eigenvalue/singular value
從矩陣 $A$ 的 spectral norm 定義出發, 我們討論有限維度因此 $\sup$ 改為 $\max$ 即可
$$\begin{aligned}
\|A\|_2^2 &=\left(\max_{\|x\|_2\leq1}\{\|Ax\|_2\}\right)^2 \\
&= \left(\max_{x\neq0}\frac{\|Ax\|_2}{\|x\|_2}\right)^2 = \max_{x\neq0}\frac{\|Ax\|_2^2}{\|x\|_2^2} \\
&=\max_{x\neq0}\frac{x^HA^HAx}{x^Hx}=:\max_{x\neq0}\rho(x)
\end{aligned}$$ 注意到 $\rho(x)$ 是矩陣 $A^HA$ 的 Rayliegh quotient, 則我們已經知道 則 $\lambda_1\leq\rho(x)\leq\lambda_n$. 因此
$$\begin{aligned}
\|A\|_2^2 &=\cdots=\max_{x\neq0}\rho(x)=\lambda_{\max}(A^HA)
\end{aligned}$$ 則 $\|A\|_2=\sqrt{\lambda_{\max}(A^HA)}$.
令 $A$ 的 SVD 分解為 $A=U\Sigma V^H$, 則
$$\begin{aligned}
\|A\|_2 &=\sqrt{\lambda_{\max}(A^HA)}=\sqrt{\lambda_{\max}(V\Sigma^H U^HU\Sigma V^H)} \\
&= \sqrt{\lambda_{\max}(V\Sigma ^H\Sigma V^H)}
\end{aligned}$$ 由於 $V\Sigma^H\Sigma V^H$ 與 $\Sigma^H\Sigma$ unitary similar (么正相似) 則它們的 eigenvlues 不變, 因此
$$\begin{aligned}
\|A\|_2 &=\cdots
= \sqrt{\lambda_{\max}(V\Sigma ^H\Sigma V^H)} \\
&= \sqrt{\lambda_{\max}(\Sigma^H\Sigma)}=\sigma_{\max}(A)
\end{aligned}$$ Q.E.D.
證明 Frobenius Norm 是 Singular Value 平方和的開根號
證明式 (4)
首先如果 $Q$ 是 unitary matrix, 我們知道 $\|M\|_F^2$ 在算所有 elements 的平方和, 則
$$\begin{aligned}
\|QA\|_F^2 &=
\|\begin{array}{cccc}Qa_1&Qa_2&\cdots&Qa_n\end{array}\|_F^2 \\
&= \sum_{i=1}^n\|Qa_i\|_2^2 = \sum_{i=1}^n a_i^TQ^TQa_i
\\ &=\sum_{i=1}^n a_i^Ta_i = \sum_{i=1}^n\|a_i\|_2^2=\|A\|_F^2
\end{aligned}$$ 得到若 $Q$ 是 unitary, 則對 Frobenius norm 同樣有”保長”的特性, $\|Qx\|_F=\|x\|_F$.
令 $A$ 的 SVD 分解為 $A=U\Sigma V^T$, 則
$$\begin{aligned}
\|A\|_F &=\|U\Sigma V^T\|_F=\|\Sigma V^T\|_F=\|(\Sigma V^T)^T\|_F \\
&= \|V\Sigma^T\|_F=\|\Sigma\|_F=\sqrt{\sum_i^{\min\{m,n\}}\sigma_i^2(A)}
\end{aligned}$$ Q.E.D.
範例: Unitary Matrix 的 Spectral 與 Frobenius Norm
令 $A$ 是 unitary 矩陣, i.e. $A^HA=AA^H=I$. 我們知道 unitary 矩陣 “保長”
$$\begin{aligned}
\|Ax\|_2^2=x^HA^HAx=x^Hx=\|x\|_2^2 \\
\Longrightarrow\|Ax\|_2=\|x\|_2
\end{aligned}$$ 我們先直覺想一下, 由於 eigenvalue 表示對 eigenvector 方向的”拉伸”程度
因為 $A$ 保長, 是不是表示不應該有”拉伸”才對, 所以 eignevalues 的大小應該都等於 $1$? 也因此 spectral norm 等於 $1$? Frobenius norm 等於 $\sqrt{n}$?
Determinant 大小等於 $1$? (因為是 eignevalues 乘積, 參考 determinant 的物理意義)
我們先證明一下 eignevalues 的大小都等於 $1$, 從保長出發:
$$\begin{aligned}
\|x\|_2^2=\|Ax\|_2^2=\|\lambda x\|_2^2=|\lambda|^2\|x\|_2^2
\end{aligned}$$ 得到 $|\lambda|=1$. 因此 $|\det(A)|=1$.
所以 spectral norm 為
$$\begin{aligned}
\|A\|_2=\sqrt{\lambda_{\max}(A^HA)}=\sqrt{\lambda_{\max}(I)}=1
\end{aligned}$$ Frobenius norm 為
$$\begin{aligned}
\|A\|_F=\sqrt{\mathrm{Tr}(A^HA)}=\sqrt{\mathrm{Tr}(I)}=\sqrt{n}
\end{aligned}$$ 這樣的結果符合物理直覺, unitary matrix or orthogonal matrix 在做的事情只是座標旋轉.