SVD

SVD

$A\in R^{m \times n}$ with $m\ge n$, $A=U\binom{\Sigma}{0}V^{T}$

其中$U\in R^{m \times m}$,$V\in R^{n \times n}$均为正交阵，$\Sigma\in R^{n\times n}$为对角阵。

$\Sigma=diag(\sigma_{1},\sigma_{2},...,\sigma_{n}),\sigma_{1}\ge\sigma_{2}\ge ...\ge\sigma_{n}\ge 0$

"Skinny version"： $A=U_{1}\Sigma V^{T},U_{1}\in�R^{m \times n}$.

性质：

1）SVD 的等价形式  $A^{T}Av_{j}=\sigma_{j}^{2}v_{j}$,$AA^{T}u_{j}=\sigma_{j}^{2}u_{j}$

其中$u_{j}$和$v_{j}$分别为$U$和$V$的列向量。

2）令$U_{k}=u_{1},u_{2},...,u_{k}$,$V_{k}=v_{1},v_{2},...,v_{k}$,$\Sigma_{k}=diag(\sigma_{1},\sigma_{2},...,\sigma_{k})$,

定义$A_{k}=U_{k}\Sigma_{k}V_{k}^{T}$.

那么 $min_{rank(B)\leq k} \lVert A-B \rVert_{2}=\lVert A-A_{k} \rVert_{2}=\sigma_{k+1}$

也就是说，矩阵A的最佳rank k近似为$A_{k}=U_{k}\Sigma_{k}V_{k}^{T}$.

联系我们在KSVD中用到了矩阵的最佳Rank 1近似。$A_{1}=U_{1}\Sigma_{1}V_{1}^{T}$.

结论：假定$\sigma_{1}\ge\sigma_{2}\ge ...\ge\sigma_{j}>\sigma_{j+1}= 0=\sigma_{j+2}=...=\sigma_{m}$,那么

$min_{rank(B)\leq j} \lVert A-B \rVert_{2}=\lVert A-A_{j} \rVert_{2}=\sigma_{j+1}=0$

所以矩阵A的秩就是A的非零奇异值数。

扰动理论 定理：如果A和A+E都是$R^{m \times n}$ with $m\ge n$,对于$k=1,...,n$,将E认为噪声

$\lvert \sigma_{k}(A+E)-\sigma_{k}(A) \rvert\leq=\sigma_{1}(E)= \lVert E\rVert_{2}$

low rank matrix plus noise example:

• 假定A为低秩矩阵加上噪声，即$A=A_{*}+N$,$\lVert N\rVert\leq\lVert A_{*}\rVert$
• 当$\lVert N\rVert$很小时，较大奇异值的数量可以视为矩阵A的秩。(numerial rank)
• 可以通过从奇异值中估计秩k来去除噪声，近似矩阵A通过截断SVD (truncated SVD) $U_{k}\Sigma_{k}V_{k}^{T}$.
• ”Correct” rank can be estimated by looking at singular values: when choosing a good k, look for gaps in singular values!

图二中可以注意到在第11个奇异值和第12个奇异值中有一个gap，所以其估计的numerical rank为11。

对于对称矩阵A，其SVD与eigen decomposition 紧密联系，$A=U\Lambda U^{T}$,$\Lambda$和$U$分别为特征值和特征向量。

如何计算SVD？

我们是否可以通过计算$A^{T}A$的特征值来获得奇异值？

这样做是可以，但是这样做非常不好。组成$A^{T}A$会导致信息的损失。

1、Use Householder transformations to transform A into bidiagonal form(对角形式) B. Now $B^{T}B$ is tridiagonal.(三对角形式)

2、Use QR iteration with Wilkinson shift μ to transform tridiagonal B to diagonal form (without forming$B^{T}B$implicitly!)

• Can be computed in $6mn^{2} + 20n^{3}$ flops.
• Efficiently implemented everywhere.

Sparse Matrices

• 在许多应用中，矩阵中只有一些项是非零项(比如term-document matrices)
• 迭代方法常用于求解稀疏问题
• Transformation to tridiagonal form would destroy sparsity, which leads to excessive storage requirements,同时计算复杂度也会过高(prohibitively high)当数据矩阵的维度很大时。

 

 

Rank-1 approximation

SVD分解后，通过matlab验证我们发现可以用分解后得到U、E、V的第一个值或者列向量来近似原来的矩阵。这个也就是所谓的Rank-1 Approximation。

如果A是一个 m x n 的矩阵，而B是一个 p x q 的矩阵，克罗内克积则是一个 mp x nq 的矩阵，表示为如图所示：

 

the kronecker product of a row vector and a column vector is essentially their outer product。