矩阵分解

SVD分解

对任何一个矩阵\(A_{m,n}\)

\[A_{m,n}=U_{m,m}\Sigma_{m,n} V^T_{n,n}\]

其中\(U_{m,m},V_{n,n}\)是正交矩阵，\(\Sigma_{m,n}\)是对角矩阵，对角矩阵中对角线的值称为A的奇异值，U中每一列是A的左奇异向量，V中每一列是A的右奇异向量。

\[A^TA = V(\Sigma^T\Sigma)V^T\]

\[AA^T = U(\Sigma\Sigma^T)U^T\]

可以看到U,V分别是\(AA^T\)和\(A^TA\)的特征向量，\(\sigma^2\)是\(AA^T\)和\(A^TA\)的特征值

QR分解

实数矩阵A可以分解为：

\[A_{m,n}=Q_{m,m}R_{m,n}\]

其中Q是正交矩阵，R是上三角矩阵。

用矩阵分解求Linear least squares(LLS)

SVD分解最稳定，但耗时最长。正规方程求解用了LDLT分解，最不稳定，但耗时最少。QR分解介于两者之间。

SVD分解

LLS问题可以定位为求解：

\[\min_x\|Ax-b\|^2_2\]

\[\|Ax-b\|_2^2=\|U^T(AVVTx-b)\|^2_2=\|\Sigma V^Tx-U^Tb\|_2^2 \]

令\(V^Tx=Z\)

\[=\sum^r_{i=1}(\sigma_iz_i-u_i^Tb)^2+\sum^m_{i=r+1}(u_i^Tb)^2\]

则解为：

\[z_i=\frac{u_i^Tb}{\sigma_i}, i = 1, 2,...,r\]

\[z_i = arbitrary, i = r+1,...,n\]

\[x=VZ\]

QR分解

A可以分解为：

\[A = Q\left[\begin{matrix} R \\ 0 \end{matrix}\right]\]

则有：

\[Q^T(Ax-b) = Q^T(Q\left[\begin{matrix} R \\ 0 \end{matrix}\right]x-b)=\left[\begin{matrix} Rx-(Q^Tb)_n \\ (Q^Tb)_{m-n} \end{matrix}\right]=\left[\begin{matrix} u \\ v \end{matrix}\right]\]

优化的函数为：

\[\|Ax-b\|^2_2=(Ax-b)^T(Ax-b)=(Ax-b)^TQQ^T(Ax-b)=u^Tu+v^Tv\]

由于v与x无关，令u=0，得到

\[\hat{x}=R^{-1}(Q^Tb)_n\]

正规方程

\[f(x) = \|Ax-b\|^2_2 = (Ax-b)^T(Ax-b) = x^TA^TAx-x^TA^Tb-b^TAx+b^Tb\]

矩阵求导有以下三个等式：

\[ \nabla ( x^ {T} A^ {T} b)= A^ {T} b, \nabla ( b^ {T} Ax)= A^ {T} b, \nabla ( x^ {T} A^ {T} Ax)= 2A^ {T} Ax \]

\[\nabla f(x)= 2 A^TAx - 2A^Tb\]

令\(\nabla f(x)=0\) 得 \(A^TAx=A^Tb\)

导数为0处一定是局部最小值吗？为什么不是最大值或者是鞍点？进一步分析二阶导的性质。 由于\(\nabla^2f(x)=2A^TA\)半正定，因此一定是极小值。