3.4 奇异值分解

奇异值分解 (Singular Value Decomposition, SVD) 分解是矩阵计算中非常有用的工具之一, 在图像处理、机器学习、数据科学等领域有着非常重要的应用.

3.4.1 奇异值，奇异向量和奇异值分解

设 $A \in \mathbb{C}^{m \times n}$ ( $m \geq n$ ), 则 $A^{*}A \in \mathbb{C}^{n \times n}$ 和 $AA^{*} \in \mathbb{C}^{m \times m}$ 都是Hermite半正定矩阵, 且它们具有相同的非零特征值 (都是正实数).

定理3.12 (SVD) [57] 设 $A \in \mathbb{C}^{m \times n}$ ( $m \geq n$ ), 则存在酉矩阵 $U \in \mathbb{C}^{m \times m}$ 和 $V \in \mathbb{C}^{n \times n}$ 使得

U ^ {*} A V = {\left[ \begin{array}{l} {\Sigma} \\ {0} \end{array} \right]} \quad {\text {或}} \quad A = U {\left[ \begin{array}{l} {\Sigma} \\ {0} \end{array} \right]} V ^ {*}, \qquad \qquad (3. 1 1)

其中 $\Sigma = \mathrm{diag}(\sigma_1, \sigma_2, \dots, \sigma_n) \in \mathbb{R}^{n \times n}$ , 且 $\sigma_1 \geq \sigma_2 \geq \dots \geq \sigma_n \geq 0$ . 分解 (3.11) 称为 $A$ 的奇异值分解 (SVD), 而 $\sigma_1, \sigma_2, \dots, \sigma_n$ 则称为 $A$ 的奇异值. (板书)

证明. 首先假设 $A \neq 0$ , 否则只需令 $\Sigma = 0$ 即可, $U$ 和 $V$ 可以是任意酉矩阵.

下面我们对 $m$ 和 $n$ 用归纳法来证明

当 $n = 1, m \geq 1$ 时, 我们取 $\Sigma = \|A\|_2, V = 1, U \in \mathbb{C}^{m \times m}$ 是第一列为 $u_1 = A / \|A\|_2$ 的酉矩阵, 于是

A = U \left[ \begin{array}{c} \Sigma \\ 0 \end{array} \right] V ^ {*}

即为 $A$ 的奇异值分解

假设 $\mathbb{C}^{(m - 1)\times (n - 1)}$ 中的矩阵都存在奇异值分解, 下面证明 $A\in \mathbb{C}^{m\times n}$ 也存在有奇异值分解.由2-范数的定义可知, 存在向量 $v\in \mathbb{C}^n$ 满足 $\| v\| _2 = 1$ 使得 $\| A\| _2 = \| Av\| _2.$ 令

u = \frac {1}{\sigma} A v \in \mathbb {C} ^ {m}, \quad \text {其 中} \sigma = \| A \| _ {2},

则 $\| u\| _2 = 1$ .我们将 $v$ 和 $u$ 都扩充成酉矩阵，即存在 $\tilde{U}\in \mathbb{C}^{m\times (m - 1)}$ 和 $\tilde{V}\in \mathbb{C}^{n\times (n - 1)}$ ，使得 $[u,\tilde{U} ]\in \mathbb{C}^{m\times m}$ 和 $[v,\tilde{V} ]\in \mathbb{C}^{n\times n}$ 都是酉矩阵.于是

\tilde {U} ^ {*} A v = \tilde {U} ^ {*} (\sigma u) = 0, \quad u ^ {*} A v = u ^ {*} (\sigma u) = \sigma .

所以

\tilde {A} \triangleq \left[ u, \tilde {U} \right] ^ {*} A \left[ v, \tilde {V} \right] = \left[ \begin{array}{c c} u ^ {*} A v & u ^ {*} A \tilde {V} \\ \tilde {U} ^ {*} A v & \tilde {U} ^ {*} A \tilde {V} \end{array} \right] = \left[ \begin{array}{c c} \sigma & u ^ {*} A \tilde {V} \\ 0 & \tilde {U} ^ {*} A \tilde {V} \end{array} \right].

又

\sigma = \| A \| _ {2} = \left\| \tilde {A} \right\| _ {2} = \left\| \tilde {A} ^ {*} \right\| _ {2} \geq \left\| \tilde {A} ^ {*} e _ {1} \right\| _ {2} = \left\| \left[ \sigma , u ^ {*} A \tilde {V} \right] ^ {*} \right\| _ {2} = \sqrt {\sigma^ {2} + \| u ^ {*} A \tilde {V} \| _ {2} ^ {2}},

所以 $\| u^{*}A\tilde{V}\|_{2} = 0$ ，即 $u^{*}A\tilde{V} = 0.$ 于是

\left[ u, \tilde {U} \right] ^ {*} A \left[ v, \tilde {V} \right] = \left[ \begin{array}{c c} \sigma & 0 \\ 0 & A _ {1} \end{array} \right],

其中 $A_{1} = \tilde{U}^{*}A\tilde{V}\in \mathbb{C}^{(m - 1)\times (n - 1)}$ .由归纳假设可知， $A_{1}$ 存在奇异值分解，设为

A _ {1} = U _ {1} \left[ \begin{array}{c} \Sigma_ {1} \\ 0 \end{array} \right] V _ {1} ^ {*},

其中 $U_{1}\in \mathbb{C}^{(m - 1)\times (m - 1)}$ 和 $V_{1}\in \mathbb{C}^{(n - 1)\times (n - 1)}$ 都是酉矩阵, $\Sigma_1\in \mathbb{R}^{(n - 1)\times (n - 1)}$ 是对角矩阵,且其对角线元素按降序排列.令

U = \left[ u, \tilde {U} \right] \left[ \begin{array}{c c} 1 & 0 \\ 0 & U _ {1} \end{array} \right], \quad V = \left[ v, \tilde {V} \right] \left[ \begin{array}{c c} 1 & 0 \\ 0 & V _ {1} \end{array} \right],

则 $U \in \mathbb{C}^{m \times m}$ 和 $V \in \mathbb{C}^{n \times n}$ 都是酉矩阵, 且

\begin{array}{l} U ^ {*} A V = \left[ \begin{array}{c c} 1 & 0 \\ 0 & U _ {1} \end{array} \right] ^ {*} \left[ \begin{array}{c} u, \tilde {U} \end{array} \right] ^ {*} A \left[ \begin{array}{c} v, \tilde {V} \end{array} \right] \left[ \begin{array}{c c} 1 & 0 \\ 0 & V _ {1} \end{array} \right] \\ = \left[ \begin{array}{c c} 1 & 0 \\ 0 & U _ {1} \end{array} \right] ^ {*} \left[ \begin{array}{c c} \sigma & 0 \\ 0 & A _ {1} \end{array} \right] \left[ \begin{array}{c c} 1 & 0 \\ 0 & V _ {1} \end{array} \right] \\ = \left[ \begin{array}{c c} \sigma & 0 \\ 0 & U _ {1} ^ {*} A _ {1} V _ {1} \end{array} \right] = \left[ \begin{array}{l} \Sigma \\ 0 \end{array} \right], \tag {3.12} \\ \end{array}

其中 $\Sigma = \begin{bmatrix} \sigma & 0 \\ 0 & \Sigma_1 \end{bmatrix}$ . 又

\sigma^ {2} = \| A \| _ {2} ^ {2} = \| U ^ {*} A V \| _ {2} ^ {2} = \left\| \left[ \begin{array}{c} \Sigma \\ 0 \end{array} \right] \right\| _ {2} ^ {2} = \rho \left(\left[ \begin{array}{c c} \sigma^ {2} & 0 \\ 0 & \Sigma_ {1} ^ {2} \end{array} \right]\right),

所以 $\sigma$ 不小于 $\Sigma_{1}$ 中的所有对角线元素, 即 $\Sigma$ 的对角线元素也是按降序排列. 因此, (??) 这就是 $A$ 的奇异值分解.

由归纳法可知, 定理的结论成立.

该定理也可以通过Hermite半正定矩阵的特征值分解来证明
如果 $A\in \mathbb{R}^{m\times n}$ 是实矩阵,则 $U,V$ 也都可以是实矩阵[73].

由(3.11)可知，

A ^ {*} A = V \Sigma^ {*} \Sigma V ^ {*}, \quad A A ^ {*} = U \left[ \begin{array}{c c} \Sigma \Sigma^ {*} & 0 \\ 0 & 0 \end{array} \right] U ^ {*}.

所以 $\sigma_1^2, \sigma_2^2, \ldots, \sigma_n^2$ 是 $A^* A$ 和 $AA^*$ 的特征值. 因此, $A$ 的奇异值就是 $A^* A$ 的特征值的平方根.

奇异向量

由SVD(3.11)可知

A v _ {i} = \sigma_ {i} u _ {i}, \quad i = 1, 2, \dots , n,

A ^ {*} u _ {i} = \sigma_ {i} v _ {i}, \quad i = 1, 2, \dots , n,

A ^ {*} u _ {i} = 0, \quad i = n + 1, n + 2, \ldots , m.

我们称 $U = [u_{1}, u_{2}, \ldots, u_{m}]$ 和 $V = [v_{1}, v_{2}, \ldots, v_{n}]$ 的列向量分别称为 $A$ 的左奇异向量和右奇

异向量.

细SVD(降阶SVD)

由定理3.12可知

A = U \left[ \begin{array}{c} \Sigma \\ 0 \end{array} \right] V ^ {*} = \sigma_ {1} u _ {1} v _ {1} ^ {*} + \sigma_ {2} u _ {2} v _ {2} ^ {*} + \dots + \sigma_ {n} u _ {n} v _ {n} ^ {*} = \sum_ {i = 1} ^ {n} \sigma_ {i} u _ {i} v _ {i} ^ {*}.

记 $U_{n} = [u_{1},u_{2},\ldots ,u_{n}]\in \mathbb{C}^{m\times n}$ ，则 $U_{n}$ 是单位列正交矩阵(即 $U_{n}^{*}U_{n} = I_{n\times n})$ ，且

A = U _ {n} \Sigma V ^ {*}. \tag {3.13}

这就是所谓的细SVD（或瘦SVD,thinSVD,skinnySVD)[57]或降阶SVD（reducedSVD）[125],有的文献将(3.12)称为奇异值分解.

压缩SVD

设 $r \triangleq \operatorname{rank}(A) \leq n$ , 则有

\sigma_ {1} \geq \sigma_ {2} \geq \dots \geq \sigma_ {r} > 0, \quad \sigma_ {r + 1} = \dots = \sigma_ {n} = 0.

我们称

A _ {r} = \sum_ {i = 1} ^ {r} \sigma_ {i} u _ {i} v _ {i} ^ {*}

为 $A$ 的压缩SVD (condensedSVD).

截断SVD

设 $k < n$ ，我们称

A _ {k} = \sigma_ {1} u _ {1} v _ {1} ^ {*} + \sigma_ {2} u _ {2} v _ {2} ^ {*} + \dots + \sigma_ {k} u _ {k} v _ {k} ^ {*} = \sum_ {i = 1} ^ {k} \sigma_ {i} u _ {i} v _ {i} ^ {*}

为 $A$ 的截断SVD (truncated SVD).

由于压缩SVD和截断SVD在计算和存储方面存在优势，因此实际应用中经常使用的是压缩SVD或截断SVD.

奇异值的应用

SVD 可用来计算矩阵的低秩逼近, 矩阵行空间和列空间的一组正交基, 以及矩阵的秩.

矩阵计算：矩阵范数，矩阵条件数，最小二乘问题，广义逆，矩阵和张量的低秩分解，等等.
工程应用: 信号处理, 图像压缩, 机器学习, 主成分分析, 数据降维, 等等.

Six Great Theorems of Linear Algebra

Dimension Theorem: All bases for a vector space have the same number of vectors.
Counting Theorem: Dimension of column space + dimension of nullspace = number of columns.
Rank Theorem: Dimension of column space $=$ dimension of rowspace. This is the rank.
Fundamental Theorem: The row space and nullspace of $A$ are orthogonal complements in $\mathbb{R}^n$ .
SVD: There are orthonormal bases ( $v$ 's and $u$ 's for the row and column spaces) so that $Av_{i} = \sigma_{i}u_{i}$ .
Spectral Theorem: If $A^{\mathsf{T}} = A$ there are orthonormal $q$ 's so that $Aq_{i} = \lambda_{i}q_{i}$ and $A = Q\Lambda Q^{\mathsf{T}}$ .

— Introduction to Linear Algebra, 5th, G. Strang, 2016.

3.4.2 奇异值基本性质

下面是关于奇异值的一些基本性质：

定理3.13 设 $A = U\left[ \begin{array}{c}\Sigma \\ 0 \end{array} \right]V^{*}$ 是 $A\in \mathbb{C}^{m\times n}$ ( $m\geq n$ ) 的奇异值分解, 则下面结论成立:

(1) $A^{*}A$ 的特征值是 $\sigma_{i}^{2}$ , 对应的特征向量是 $v_{i}, i = 1,2,\ldots,n$ ;
(2) $AA^{*}$ 的特征值是 $\sigma_{i}^{2}$ 和 $m - n$ 个零, 对应的特征向量是 $u_{i}, i = 1,2,\ldots,m$ ;
(3) $\| A\| _2 = \sigma_1$ $\| A\| _F = \sqrt{\sigma_1^2 + \sigma_2^2 + \cdots + \sigma_n^2};$
(4) 若 $\operatorname{rank}(A) = r \leq n$ , 则

\operatorname {R a n} (A) = \operatorname {s p a n} \left\{u _ {1}, u _ {2}, \dots , u _ {r} \right\}, \quad \operatorname {K e r} (A) = \operatorname {s p a n} \left\{v _ {r + 1}, v _ {r + 2}, \dots , v _ {n} \right\};

(5) 设 $x \in \mathbb{C}^n$ 且 $\| x \|_2 = 1$ , 则 $\sigma_n \leq \| Ax \|_2 \leq \sigma_1$ ;
(事实上有 $\sigma_{1} = \max_{\| x\|_{2} = 1}\| Ax\|_{2},\sigma_{n} = \min_{\| x\|_{2} = 1}\| Ax\|_{2})$
(6) (酉不变性) 设 $X \in \mathbb{C}^{m \times m}$ 和 $Y \in \mathbb{C}^{n \times n}$ 是酉矩阵, 则 $\sigma_i(X^*AY) = \sigma_i(A)$ .

(留作练习)

性质 (4) 可以用来计算矩阵的像空间和零空间.

定理3.14 设 $A = U\Sigma V^{*}$ 是 $A\in \mathbb{C}^{n\times n}$ 的奇异值分解, 则下面结论成立:

(1) $|\operatorname{det}(A)| = \sigma_1\sigma_2\cdots \sigma_n;$
(2) 若 $A$ 非奇异, 则 $\| A^{-1}\|_2 = \sigma_n^{-1}, \kappa_2(A) = \sigma_1 / \sigma_n$ ;
(3) 若 $A$ 是Hermite的, 且 $A = U\Lambda U^{*}$ 是 $A$ 的酉特征值分解, 即 $U^{*}U = I, \Lambda = \mathrm{diag}(\lambda_{1}, \lambda_{2}, \ldots, \lambda_{n})$ . 设 $|\lambda_1| \geq |\lambda_2| \geq \dots \geq |\lambda_n|$ , 则 $A = U\Sigma V$ 是 $A$ 的奇异值分解, 其中 $\sigma_{i} = |\lambda_{i}|$ , $v_{i} = \mathrm{sign}(\lambda_{i})u_{i}$ , 若 $\lambda_{i} = 0$ , 则取 $v_{i} = u_{i}$ ;
(4) 矩阵 $H = \begin{bmatrix} 0 & A^{*}\\ A & 0 \end{bmatrix}$ 的特征值是 $\pm \sigma_{i}$ , 对应的单位特征向量为 $\frac{1}{\sqrt{2}}\left[ \begin{array}{l}v_{i}\\ \pm u_{i} \end{array} \right]$ . ( $A\in \mathbb{C}^{m\times n}$ 时也有类似结论)

(留作练习)

例3.5 由奇异值的性质可知, 矩阵的谱条件数取决于最大奇异值和最小奇异值的比值, 如果最大奇异值与最小奇异值比较接近, 则谱条件数就比较小. 那么, 谱条件数与特征值有没有直接关系? 我们知道, 如果矩阵 $A$ 对称正定, 则其谱条件数就是最大特征值与最小特征值的比值. 但是,对于一般的矩阵, 则没有这个性质. 如下面的矩阵:

A = \left[ \begin{array}{c c c c} 1 & - \frac {1}{2} & \dots & - \frac {1}{2} \\ & 1 & \ddots & \vdots \\ & & \ddots & - \frac {1}{2} \\ & & & 1 \end{array} \right] \in \mathbb {R} ^ {n \times n},

即对角线全是1, 严格上三角部分全是 $-\frac{1}{2}$ , 其它为0. 易知 $A$ 的所有特征值都是1, 但其谱条件数却随着矩阵规模的增长而快速变大, 见下表:

另外，通过直接计算可知

A ^ {- 1} = \left[ \begin{array}{c c c c c c} 1 & \frac {1}{2} & \frac {1 . 5}{2} & \frac {1 . 5 ^ {2}}{2} & \dots & \frac {1 . 5 ^ {n - 2}}{2} \\ & 1 & \frac {1}{2} & \frac {1 . 5}{2} & \ddots & \vdots \\ & & 1 & \ddots & \ddots & \frac {1 . 5 ^ {2}}{2} \\ & & & \ddots & \frac {1}{2} & \frac {1 . 5}{2} \\ & & & & 1 & \frac {1}{2} \\ & & & & & 1 \end{array} \right].

因此, $\kappa_{1}(A)$ 和 $\kappa_{\infty}(A)$ 都是矩阵维数 $n$ 的幂函数

3.4.3 奇异值更多性质

下面是关于矩阵 $A$ 的一个低秩逼近

定理3.15 设 $A = U_{n}\Sigma V^{*}$ 是 $A \in \mathbb{C}^{m \times n}$ 的细奇异值分解, 令 $A_{k} = \sum_{i=1}^{k} \sigma_{i}u_{i}v_{i}^{*}$ , 则 $A_{k}$ 是

\min _ {B \in \mathbb {C} ^ {m \times n}, \operatorname {r a n k} (B) = k} \| A - B \| _ {2} \tag {3.14}

的一个解，且

\left\| A - A _ {k} \right\| _ {2} = \sigma_ {k + 1}.

此时，我们称 $A_{k}$ 是 $A$ 的一个秩 $k$ 逼近

(板书)

证明. 设 $B \in \mathbb{C}^{m \times n}$ 且 $\operatorname{rank}(B) = k$ , 则

\dim (\operatorname {K e r} (B)) + \dim (\operatorname {s p a n} \{V _ {k + 1} \}) = (n - k) + (k + 1) = n + 1 > n,

其中 $V_{k + 1} = [v_1,v_2,\ldots ,v_{k + 1}]\in \mathbb{C}^{n\times (k + 1)}$ .所以 $\operatorname {Ker}(B)$ 与 $\operatorname {span}\{V_{k + 1}\}$ 有非零公共元素.令 $0\neq$ $x\in \mathrm{Ker}(B)\cap \mathrm{span}\{V_{k + 1}\}$ ，不失一般性,我们假设 $\| x\| _2 = 1$ .故存在 $y\in \mathbb{C}^{k + 1}$ 满足 $\| y\| _2 = 1$ 使得

$x = V_{k + 1}y.$ 于是

\begin{array}{l} \| A - B \| _ {2} ^ {2} \geq \| (A - B) x \| _ {2} ^ {2} = \| A x \| _ {2} ^ {2} = \| U _ {n} \Sigma V ^ {*} V _ {k + 1} y \| _ {2} ^ {2} \\ = \left\| \Sigma \left[ \begin{array}{c} I _ {k + 1} \\ 0 \end{array} \right] y \right\| _ {2} ^ {2} = \left\| \Sigma \left[ \begin{array}{c} y \\ 0 \end{array} \right] \right\| _ {2} ^ {2} = \sum_ {i = 1} ^ {k + 1} \sigma_ {i} ^ {2} | y _ {i} | ^ {2} \geq \sigma_ {k + 1} ^ {2}, \\ \end{array}

其中 $\Sigma_{1} = \mathrm{diag}(\sigma_{1},\sigma_{2},\ldots ,\sigma_{k + 1})$ .这里我们利用了性质 $\sum_{i = 1}^{k + 1}|y_i|^2 = \| y\| _2^2 = 1.$ 所以

\min_{\substack{B\in \mathbb{C}^{m\times n},\operatorname {rank}(B) = k}}\| A - B\|_{2}\geq \sigma_{k + 1}.

又 $\operatorname{rank}(A_k) = k$ , 且

\| A - A _ {k} \| _ {2} = \left\| \sum_ {i = k + 1} ^ {n} \sigma_ {i} u _ {i} v _ {i} ^ {*} \right\| _ {2} = \left\| U _ {n} \left[ \begin{array}{c c c c c c} 0 & & & & & \\ & \ddots & & & & \\ & & 0 & & & \\ & & & \sigma_ {k + 1} & & \\ & & & & \ddots & \\ & & & & & \sigma_ {n} \end{array} \right] V ^ {*} \right\| _ {2} = \sigma_ {k + 1},

所以

\min _ {B \in \mathbb {C} ^ {m \times n}, \operatorname {r a n k} (B) = k} \| A - B \| _ {2} = \sigma_ {k + 1},

且 $A_{k}$ 是问题(3.13)的一个解

定理中的(3.13)式也可以改写为

\min _ {B \in \mathbb {C} ^ {m \times n}, \operatorname {r a n k} (B) \leq k} \| A - B \| _ {2} \tag {3.15}

对于 Frobenius 范数, 我们有类似的结论, 见习题 3.13.

定理3.16 (Weyl) [119] 设 $A, B \in \mathbb{C}^{m \times n}$ ( $m \geq n$ ), 且 $\operatorname{rank}(B) = k$ , 则有

\max _ {x \in \operatorname {K e r} (B), \| x \| _ {2} = 1} \| A x \| _ {2} \geq \sigma_ {k + 1} (A), \tag {3.16}

和

\min _ {x \in \operatorname {K e r} (B), \| x \| _ {2} = 1} \| A x \| _ {2} \leq \sigma_ {n - k} (A). \tag {3.17}

因此,

\sigma_ {1} (A - B) \geq \sigma_ {k + 1} (A), \quad \sigma_ {n} (A - B) \leq \sigma_ {n - k} (A). \tag {3.18}

(板书)

证明. 不等式 (3.15) 的证明与定理 3.15 的证明类似, 不再赘述.

下面证明结论 (3.16). 令 $\tilde{V}_{k+1} = [v_{n-k}, v_{n-k+1}, \ldots, v_n] \in \mathbb{C}^{n \times (k+1)}$ . 类似地, 存在向量 $y \in \mathbb{C}^{k+1}$ 满足 $\|y\|_2 = 1$ , 使得 $x = \tilde{V}_{k+1}y \in \operatorname{Ker}(B)$ . 于是

\| A x \| _ {2} ^ {2} = \| U _ {n} \Sigma V ^ {*} \tilde {V} _ {k + 1} y \| _ {2} ^ {2} = \left\| \left[ \begin{array}{c} 0 \\ I _ {k + 1} \end{array} \right] y \right\| _ {2} ^ {2} = \left\| \Sigma \left[ \begin{array}{c} 0 \\ y \end{array} \right] \right\| _ {2} ^ {2} = \sum_ {i = 1} ^ {k + 1} \sigma_ {n - k - 1 + i} ^ {2} (A) | y _ {i} | ^ {2} \leq \sigma_ {n - k} ^ {2} (A).

所以

\min _ {x \in \operatorname {K e r} (B), \| x \| _ {2} = 1} \| A x \| _ {2} \leq \sigma_ {n - k} (A).

根据定理3.13中的性质5，以及(3.15)和(3.16)可得

\begin{array}{l} \sigma_ {1} (A - B) = \max _ {\| x \| _ {2} = 1} \| (A - B) x \| _ {2} \\ \geq \max _ {x \in \operatorname {K e r} (B), \| x \| _ {2} = 1} \| (A - B) x \| _ {2} = \max _ {x \in \operatorname {K e r} (B), \| x \| _ {2} = 1} \| A x \| _ {2} \geq \sigma_ {k + 1} (A), \\ \end{array}

\begin{array}{l} \sigma_ {n} (A - B) \leq \min _ {\| x \| _ {2} = 1} \| (A - B) x \| _ {2} \\ \leq \min _ {x \in \operatorname {K e r} (B), \| x \| _ {2} = 1} \| (A - B) x \| _ {2} = \min _ {x \in \operatorname {K e r} (B), \| x \| _ {2} = 1} \| A x \| _ {2} \leq \sigma_ {n - k} (A). \\ \end{array}

因此不等式 (3.17) 成立

不等式(3.15)和(3.16)也可以写为：设 $\mathcal{L}$ 是 $\mathbb{C}^n$ 中的任意一个 $n - k$ 维子空间，则有

\max _ {x \in \mathcal {L}, \| x \| _ {2} = 1} \| A x \| _ {2} \geq \sigma_ {k + 1} (A), \quad \min _ {x \in \mathcal {L}, \| x \| _ {2} = 1} \| A x \| _ {2} \leq \sigma_ {n - k} (A).

特别地, 当 $k = 0$ 时 $\mathcal{L} = \mathbb{R}^n$ , 因此

\max _ {\| x \| _ {2} = 1} \| A x \| _ {2} \geq \sigma_ {1} (A), \quad \min _ {\| x \| _ {2} = 1} \| A x \| _ {2} \leq \sigma_ {n} (A).

事实上, 我们有 (第一个等式就是 2-范数的定义, 第二个等式留作自行练习)

\max _ {\| x \| _ {2} = 1} \| A x \| _ {2} = \sigma_ {1} (A), \quad \min _ {\| x \| _ {2} = 1} \| A x \| _ {2} = \sigma_ {n} (A).

从该结论可知, 如果通过对 $A$ 进行秩 $k (1 \leq k \leq \frac{n}{2})$ 修正来改善其谱条件数, 则最佳情况是降低到 $\frac{\sigma_{n-k}(A)}{\sigma_{k+1}}$ .

定理3.17 [119] 设 $A, B \in \mathbb{C}^{m \times n}$ ( $m \geq n$ ), 则有

\sigma_ {i + j - 1} (A + B) \leq \sigma_ {i} (A) + \sigma_ {j} (B), \quad i = 1, 2, \dots , n, j = 1, 2, \dots , n - i + 1. \tag {3.19}

(板书)

证明. 首先证明 $i = j = 1$ 时结论成立. 事实上, 我们有

\sigma_ {1} (A + B) = \| A + B \| _ {2} \leq \| A \| _ {2} + \| B \| _ {2} = \sigma_ {1} (A) + \sigma_ {1} (B).

设 $A_{i-1}$ 和 $B_{j-1}$ 分别是 $A$ 和 $B$ 的秩 $i-1$ 和秩 $j-1$ 逼近, 则由定理3.15可知

\| A - A _ {i - 1} \| _ {2} = \sigma_ {i} (A), \quad \| B - B _ {j - 1} \| _ {2} = \sigma_ {j} (B).

所以

\sigma_ {i} (A) + \sigma_ {j} (B) = \| A - A _ {i - 1} \| _ {2} + \| B - B _ {j - 1} \| _ {2} \geq \| A + B - (A _ {i - 1} + B _ {j - 1}) \| _ {2}.

又 $\operatorname{rank}(A_{i-1} + B_{j-1}) \leq i + j - 2$ , 所以由不等式 (3.17) 可知

\sigma_ {i} (A) + \sigma_ {j} (B) \geq \| A + B - (A _ {i - 1} + B _ {j - 1}) \| _ {2} \geq \sigma_ {i + j - 1} (A + B).

令 $A = X - Y, B = Y$ ，则该结论也可以描述为

\sigma_ {i} (X - Y) \geq \sigma_ {i + j - 1} (X) - \sigma_ {j} (Y), \quad i = 1, 2, \ldots , n, j = 1, 2, \ldots , n - i + 1.

根据定理3.16, 我们可以得到矩阵奇异值的最小最大定理

定理3.18 设 $\sigma_1 \geq \sigma_2 \geq \dots \geq \sigma_n \geq 0$ 是矩阵 $A \in \mathbb{C}^{m \times n}$ ( $m \geq n$ ) 的奇异值, 则

\sigma_ {k} (A) = \min _ {\dim (\mathcal {L}) = n - k + 1} \max _ {x \in \mathcal {L}, \| x \| _ {2} = 1} \| A x \| _ {2}, \quad k = 1, 2, \dots , n

和

\sigma_{k}(A) = \max_{\dim (\mathcal{L}) = k}\min_{x\in \mathcal{L}, \| x\|_{2} = 1}\| Ax\|_{2},\quad k = 1,2,\ldots ,n,

其中 $\mathcal{L}$ 表示 $\mathbb{C}^n$ 的一个子空间

(留作练习)

引理3.19(交错不等式)[74]设 $A\in \mathbb{C}^{m\times n}$ ， $A_{r}$ 是由 $A$ 去除 $r$ 列 (或 $r$ 行)后得到的子矩阵，则

\sigma_ {i} (A) \geq \sigma_ {i} \left(A _ {r}\right) \geq \sigma_ {i + r} (A), \quad i = 1, 2, \dots , \min \{m, n \}.

这里, 当下标 $k$ 大于矩阵的维数时, 我们令 $\sigma_{k} = 0$ . 进一步, 如果 $B \in \mathbb{C}^{(m - r) \times (n - s)}$ 是 $A$ 的子矩阵, 则

\sigma_ {i} (A) \geq \sigma_ {i} (B) \geq \sigma_ {i + r + s} (A).

(留作课外自习)

证明. 只需证明 $r = 1$ 的情形, 其余情形可以通过递推实现

假设 $A_{1}$ 是由 $A$ 中去除第 $k$ 列后的子矩阵. 令 $e_k \in \mathbb{C}^n$ 为单位矩阵的第 $k$ 列, 即第 $k$ 个元素是 1, 其它均为 0. 由定理 3.18 可知

\sigma_ {k} (A) = \min _ {\dim (\mathcal {L}) = n - k + 1} \max _ {x \in \mathcal {L}, \| x \| _ {2} = 1} \| A x \| _ {2} \geq \min _ {\dim (\mathcal {L}) = n - k + 1} \max _ {x \in \mathcal {L}, \| x \| _ {2} = 1, x \perp e _ {k}} \| A x \| _ {2}.

如果 $x \perp e_k$ , 则 $x_k = 0$ , 所以

A x = A _ {1} \tilde {x},

其中 $\tilde{x} = [x_1,\ldots ,x_{k - 1},x_{k + 1},\ldots ,x_n]^{\top}\in \mathbb{C}^{n - 1}$ 故条件“ $x\in \mathcal{L}$ ， $\| x\| _2 = 1$ ， $x\bot e_k$ ”就等价于 $x\in \tilde{\mathcal{L}},\|\tilde{x}\|_2 = 1"$ ，其中 $\tilde{\mathcal{L}}\subset \mathbb{C}^{n - 1}$ 是由 $\mathcal{L}$ 中的向量去除第 $k$ 个分量后组成的集合．因此 $\dim (\tilde{\mathcal{L}}) = \dim (\mathcal{L}) = n - k + 1$ 或 $\dim (\tilde{\mathcal{L}}) = \dim (\mathcal{L}) - 1 = n - k.$ 于是

\min _ {\dim (\mathcal {L}) = n - k + 1} \max _ {x \in \mathcal {L}, \| x \| _ {2} = 1, x \perp e _ {k}} \| A x \| _ {2} \geq \min _ {\dim (\tilde {\mathcal {L}}) = n - k + 1 \text {或} \dim (\tilde {\mathcal {L}}) = n - k} \max _ {\tilde {x} \in \tilde {\mathcal {L}}, \| \tilde {x} \| _ {2} = 1} \| A _ {1} \tilde {x} \| _ {2}.

又

\min _ {\dim (\tilde {\mathcal {L}}) = n - k + 1} \max _ {\tilde {x} \in \tilde {\mathcal {L}}, \| \tilde {x} \| _ {2} = 1} \| A _ {1} \tilde {x} \| _ {2} \geq \min _ {\dim (\tilde {\mathcal {L}}) = n - k} \max _ {\tilde {x} \in \tilde {\mathcal {L}}, \| \tilde {x} \| _ {2} = 1} \| A _ {1} \tilde {x} \| _ {2},

且 $A_{1}\in \mathbb{C}^{m\times (n - 1)}$ ，所以

\begin{array}{l} \sigma_ {k} (A) \geq \min _ {\dim (\mathcal {L}) = n - k + 1} \max _ {x \in \mathcal {L}, \| x \| _ {2} = 1, x \perp e _ {k}} \| A x \| _ {2} \\ \geq \min_{\dim (\tilde{\mathcal{L}}) = (n - 1) - k + 1}\max_{\tilde{x}\in \tilde{\mathcal{L}},\| \tilde{x}\|_{2} = 1}\| A_{1}\tilde{x}\|_{2} \\ = \sigma_ {k} (A _ {1}). \\ \end{array}

同理可得

\begin{array}{l} \sigma_ {k + 1} (A) = \max _ {\dim (\mathcal {L}) = k + 1} \min _ {x \in \mathcal {L}, \| x \| _ {2} = 1} \| A x \| _ {2} \\ \leq \max _ {\dim (\mathcal {L}) = k + 1} \min _ {x \in \mathcal {L}, \| x \| _ {2} = 1, x \perp e _ {k}} \| A x \| _ {2} \\ \leq \max _ {\dim (\tilde {\mathcal {L}}) = k} \min _ {\tilde {x} \in \tilde {\mathcal {L}}, \| \tilde {x} \| _ {2} = 1} \| A _ {1} \tilde {x} \| _ {2} \\ = \sigma_ {k} (A _ {1}). \\ \end{array}

我们注意到, 在前面的证明中, 并没有要求 $m \geq n$ . 因此对于 $m < n$ 的情形, 上面的结论仍然成立.

如果 $A_{1}$ 是由 $A$ 中去除第 $k$ 行后的子矩阵. 由于 $A^{*}$ 与 $A$ 具有相同的奇异值, 因此只需将上面的讨论运用到 $A^{*}$ 上即可. $\square$

引理3.20 [74] 设 $A \in \mathbb{C}^{n \times n}, 1 \leq k \leq n,$ 则对任意的单位列正交矩阵 $U_k \in \mathbb{C}^{n \times k}$ 和 $V_k \in \mathbb{C}^{n \times k}$ , 有

\sigma_ {i} \left(U _ {k} ^ {*} A V _ {k}\right) \leq \sigma_ {i} (A), \quad i = 1, 2, \dots , k. \tag {3.20}

因此,

\left| \det \left(U _ {k} ^ {*} A V _ {k}\right) \right| \leq \sigma_ {1} (A) \sigma_ {2} (A) \dots \sigma_ {k} (A). \tag {3.21}

(板书)

证明. 我们将 $U_{k}$ 和 $V_{k}$ 都扩充成酉矩阵 $U \in \mathbb{C}^{m \times m}$ 和 $V \in \mathbb{C}^{n \times n}$ , 则 $U_{k}^{*}AV_{k}$ 是 $U^{*}AV$ 的子矩阵. 由引理3.19可知,

\sigma_ {i} \left(U _ {k} ^ {*} A V _ {k}\right) \leq \sigma_ {i} \left(U ^ {*} A V\right).

又 $U^{*}AV$ 与 $A$ 有相同的奇异值, 故结论 (3.19) 成立

利用定理3.14中的性质1，即可得到不等式(3.20).

定理3.21 (Weyl不等式, 1949) [74] 设 $A \in \mathbb{C}^{n \times n}$ , 其奇异值和特征值分别为 $\sigma_1 \geq \sigma_2 \geq \dots \geq \sigma_n \geq 0$ 和 $|\lambda_1| \geq |\lambda_2| \geq \dots \geq |\lambda_n|$ , 则

\left| \lambda_ {1} \lambda_ {2} \dots \lambda_ {k} \right| \leq \sigma_ {1} \sigma_ {2} \dots \sigma_ {k}, \quad k = 1, 2, \dots , n

且当 $k = n$ 时，等号成立.

(板书)

证明. 设 $A = U R U^{*}$ 是 $A$ 的 Schur 分解, 其中 $U \in \mathbb{C}^{n \times n}$ 是酉矩阵, $R \in \mathbb{C}^{n \times n}$ 是上三角矩阵, 且其对角线元素依次为 $\lambda_{1}, \lambda_{2}, \ldots, \lambda_{n}$ . 取 $U$ 的前 $k$ 列组成一个单位列正交矩阵 $U_{k}$ , 则 $R_{k} \triangleq U_{k}^{*} A U_{k}$ 为 $U^{*} A U = R$ 的 $k$ 阶顺序主子矩阵, 即 $R_{k}$ 也是上三角矩阵, 且其对角线元素依次为 $\lambda_{1}, \lambda_{2}, \ldots, \lambda_{k}$ . 所以由引理 3.20 可得

| \lambda_ {1} \lambda_ {2} \dots \lambda_ {k} | = | \det (R _ {k}) | = | \det (U _ {k} ^ {*} A U _ {k}) | \leq \sigma_ {1} \sigma_ {2} \dots \sigma_ {k}.

当 $k = n$ 时，

\left| \lambda_ {1} \lambda_ {2} \dots \lambda_ {n} \right| = | \det (A) | = \sigma_ {1} \sigma_ {2} \dots \sigma_ {n}.

3.4.4 奇异值扰动分析

下面的定理是关于奇异值的一个扰动性质.

定理3.22 [119] 设 $A, E \in \mathbb{C}^{m \times n} (m \geq n)$ , 则

\left| \sigma_ {i} (A + E) - \sigma_ {i} (A) \right| \leq \| E \| _ {2}, \quad i = 1, 2, \dots , n.

(留作练习, 可直接利用不等式 (3.18))

3.4_奇异值分解

3.4 奇异值分解

3.4.1 奇异值，奇异向量和奇异值分解

奇异向量

异向量.

细SVD(降阶SVD)

压缩SVD

截断SVD

奇异值的应用

Six Great Theorems of Linear Algebra

3.4.2 奇异值基本性质

3.4.3 奇异值更多性质

3.4.4 奇异值扰动分析