# SVD

SVD

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

$\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}\inR^{m \times n}$.

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

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})$,

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

$\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!

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。

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