数值的稳定性与条件数

当输入d受到扰动时，输出f(d) 的扰动情况

目的：解决病态问题

条件数

A 数据矩阵 n*n
b 数据向量 n*1
x 未知向量 n*1

在这里我们研究x受A，或者b扰动的影响

A (x + δ x) = b + δ b

A δ x = δ b

δ x = A^{- 1} δ b

由

| | A B | | <= | | A | | | | B | |

\to {\begin{cases} | | δ x | |_{2} <= | | A^{- 1} | |_{2} | | δ b | |_{2} \\ | | b | |_{2} <= | | A | |_{2} | | x | |_{2} \to \frac{1}{| | x | |_{2}} <= \frac{| | A | |_{2}}{| | b | |_{2}} \end{cases}

两边相乘

\to \frac{| | δ x | |_{2}}{| | x | |_{2}} <= | | A^{- 1} | |_{2} | | A | |_{2} \frac{| | δ b | |_{2}}{| | b | |_{2}}

一起考虑A扰动的影响，可以得到

(A + δ A) (x + δ x) = b

\begin{array}{l} δ x = (A + δ A)^{- 1} b - A^{- 1} b \\ = A^{- 1} [A - (A + δ A)] (A + δ A)^{- 1} b \\ = A^{- 1} (- δ A) (A + δ A)^{- 1} b \\ \to \frac{| | δ x | |_{2}}{| | x + δ x | |_{2}} <= | | A^{- 1} | | | | A | |_{2} \frac{| | δ A | |_{2}}{| | A | |_{2}} \end{array}

可以看出噪声（解向量x的误差）与某个数成正比，这个数被称为条件数

c o n d (A) = | | A^{- 1} | |_{2} | | A | |_{2}

有性质

c o n d (A^{H} A) = [c o n d (A)]^{2}

如果矩阵A不是方阵，可以求出最小二乘解

A x = b \to x = (A^{H} A)^{- 1} A^{H} b

求此时的条件数

c o n d (A^{H} A) = | | A^{H} A | |_{2} | | (A^{H} A)^{- 1} | |_{2} = c o n d (A)^{2}

条件数平方后变大，所以此时的最小二乘解不稳定

奇异值分解

奇异值分解定理对于矩阵 $A : m \times n$ ,存在正交或者酉矩阵 $U : m \times m, V : n \times n$ 使得

A = U Σ V^{H}

Σ = [\begin{matrix} Σ_{r} & 0 \\ 0 & 0 \end{matrix}]

d i a g (Σ_{r}) = [σ_{1}, σ_{2} . . . σ_{r}]

r = r a n k (A)

$\sigma1,\sigma_2…\sigma_r，\sigma{r+1}=…\sigma_n=0$被称为A的奇异值

A V = U Σ

\to A v_{i} = {\begin{cases} u_{i} σ_{i} & i <= r \\ 0 & i > r \end{cases}

U^{H} A = Σ V^{H}

u_{i}^{H} A = σ_{i} v_{i}^{H}

$v_{i}$ 为右奇异向量, $u_{i}$ 为左奇异向量

矩阵A的奇异值分解式可以改写成向量表达式 $A = Σ_{i = 1}^{r} σ_{i} u_{i} v_{i}^{H}$
当矩阵的秩 $r = r a n k (A) < m i n (m, n)$
奇异值分解可以被简化为

A = U_{r} Σ_{r} V_{r}^{H}

被称为截断奇异值分解，
只取前r个非0度奇异值

奇异值分解和特征分解的关系

A^{H} A = V Σ U^{H} U Σ V^{H}

= V Σ^{2} V^{H}

$A^{H} A$ 的特征值是A奇异值的平方，是右奇异向量
$A A^{H}$ 的特征值是A奇异值的平方，是左奇异向量 $A A^{H} = U \sum^{2} U^{H}$
广义逆 $A^{†} = V Σ^{†} U^{H}$
奇异值的性质
范数性质
诱导谱范数 $| | A | |_{s p e c} = | | A | |_{2} = σ_{i} (最大奇异值)$
f范数 $| | A | |_{F} = s q r t < A, A > = \sqrt{t r (A^{H}, A)} = \sqrt{\sum σ_{i}}$ 所以特征值之和=奇异值平方和 $λ_{1} + λ_{2} . . . + λ_{r} = σ_{1}^{2} + σ_{2}^{2} . . . + σ_{r}^{2}$

根据矩阵A的谱范数可以确定最大奇异值

酉不变性

A = U Σ V^{H}

在矩阵A的基础上再左乘或者右乘一个酉矩阵

B = P U Σ V^{H} Q^{H}

B的奇异值不变

奇异值与行列式

因为酉矩阵行列式绝对值为1

所以

| d e t A | = | d e t \sum | = σ_{1} σ_{2} . . . σ_{n}

如果 $d e t A \neq 0$ 表明A是非奇异的，若存在 $σ_{i} = 0, d a t A = 0$ ,则A奇异，这是把 $σ$ 称为奇异值的原因

奇异值与条件数

c o n d (A) = σ_{1} / σ_{p} (p = {m, n})

所以条件数总大于1

奇异值的内在含义，如果一个矩阵有一个奇异值为0，对于正方矩阵，代表，矩阵奇异，行列式为0，非正方矩阵代表秩亏缺

秩亏缺矩阵（LS）

应用奇异值分解求解最小二乘问题的方法常简称为奇异值分解方法。

\begin{array}{l} A x = b \\ U Σ V^{H} x = b \\ Σ V^{H} x = U^{H} b \end{array}

令

x^{'} = V^{H} x, y = U^{H} b

得到

\to Σ x^{'} = y

我们的目标变为优化问题

m i n | | Σ x^{'} - y | |_{2}^{2} = \sum_{i = 1}^{r} | σ_{i} x_{i} - y_{i} |^{2} + \sum_{i = r + 1}^{N} | y_{i} |^{2} = 0

得到最小范数解

x_{L S} = \sum_{i = 1}^{r} (u_{i}^{H} b / σ_{i}) v_{i}

相应的最小残差为

ρ_{L S} = | | A x_{L S} - b | |_{2} = | | [u_{r + 1}, . ., u_{m}]^{H} b | |_{2}

有效秩的确定

如果要衡量衡量A，B的逼近程度，P,K分别为A、B的秩

A = \sum_{i = 1}^{P} σ_{i} u_{i} v_{i}^{H}

B = \sum_{i = 1}^{K} σ_{i} u_{i} v_{i}^{H}

谱范数法 $| | A - B | |_{s p e c} = σ_{k + 1}$
F范数法 $| | A - B | |_{F} = \sqrt{\sum_{i = k + 1}^{P} σ_{i}^{2}}$
衡量标准

对应谱范数

ϵ = \frac{σ_{k}}{σ_{1}} >= 5 %

对应F范数（范数比方法）

V (k) = \frac{\sqrt{\sum^{k} σ^{2}}}{\sqrt{\sum^{P} σ^{2}}}

= \frac{| | A_{k} | |_{F}}{| | A | |_{F}} >= α

奇异值分解在图像视频压缩中的作用

在矩阵A稀疏的情况下

A \to n \times n

A_{k} = U_{k} \sum_{k} V_{k}^{H}