## 每週問題 January 13, 2014

Let $A$ be an $m\times n$ real matrix, $m\ge n$, with $\hbox{rank}A=n$. Suppose the singular value decomposition of $A$ is $A=U\Sigma V^T$, where $U=\begin{bmatrix} \mathbf{u}_1&\cdots&\mathbf{u}_m \end{bmatrix}$ is an $m\times m$ real orthogonal matrix, $V=\begin{bmatrix} \mathbf{v}_1&\cdots&\mathbf{v}_n \end{bmatrix}$ is an $n\times n$ real orthogonal matrix, and $\Sigma=\begin{bmatrix} D\\ 0 \end{bmatrix}$ is $m\times n$, with $D=\hbox{diag}(\sigma_1,\ldots,\sigma_n)$ and $\sigma_i>0$ for all $i$. Show that the least squares solution of $A\mathbf{x}=\mathbf{b}$ is given by

$\displaystyle \hat{\mathbf{x}}=\sum_{i=1}^n\frac{\mathbf{u}_i^T\mathbf{b}}{\sigma_i}\mathbf{v}_i$.

$\displaystyle A^TA=(U\Sigma V^T)^T(U\Sigma V^T)=V\begin{bmatrix} D&0 \end{bmatrix}U^TU\begin{bmatrix} D\\ 0 \end{bmatrix} V^T=VD^2V^T$

\displaystyle\begin{aligned} \hat{\mathbf{x}}&=(A^TA)^{-1}A^T\mathbf{b}=(VD^2V^T)^{-1}\left(U\begin{bmatrix} D\\ 0 \end{bmatrix}V^T\right)^T\mathbf{b}\\ &=VD^{-2}V^TV\begin{bmatrix} D&0 \end{bmatrix}U^T\mathbf{b}=VD^{-2}\begin{bmatrix} D&0 \end{bmatrix}U^T\mathbf{b}=V\begin{bmatrix} D^{-1}&0 \end{bmatrix}U^T\mathbf{b}\\ &=\begin{bmatrix} \mathbf{v}_1&\cdots&\mathbf{v}_n \end{bmatrix}\begin{bmatrix} \sigma_1^{-1}&& &0&\cdots&0\\ &\ddots&&\vdots&&\vdots\\ &&\sigma_n^{-1}&0&\cdots&0 \end{bmatrix}\begin{bmatrix} \mathbf{u}_1^T\\ \vdots\\ \mathbf{u}_m^T \end{bmatrix}\mathbf{b}\\ &=\begin{bmatrix} \mathbf{v}_1&\cdots&\mathbf{v}_n \end{bmatrix}\begin{bmatrix} \sigma_1^{-1}\mathbf{u}_1^T\mathbf{b}\\ \vdots\\ \sigma_n^{-1}\mathbf{u}_n^T\mathbf{b} \end{bmatrix}\\ &=\sum_{i=1}^n\frac{\mathbf{u}_i^T\mathbf{b}}{\sigma_i}\mathbf{v}_i.\end{aligned}