每週問題 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.

 
參考解答:

線性方程 A\mathbf{x}=\mathbf{b} 的最小平方近似解為 \hat{\mathbf{x}}=(A^TA)^{-1}A^T\mathbf{b}。使用奇異值分解,

\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}

廣告
本篇發表於 pow 二次型, 每週問題 並標籤為 , 。將永久鏈結加入書籤。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s