11
$\begingroup$

Let $A$ be an $m \times n$ matrix with a singular value decomposition $A=U\Sigma V^T$. Show that the matrix $Q=UV^T$ is the nearest orthogonal matrix to $A$, i.e.,

$$\min_{Q^TQ=I_{n \times n}} \|A-Q\|_F$$

$\endgroup$
  • 2
    $\begingroup$ If $A$ is $m\times n$, then also $UV^T$ is $m\times n$. So, I guess it is assumed that $m = n$? $\endgroup$ – Friedrich Philipp Apr 3 '17 at 2:09
9
$\begingroup$

Note that, as stated, the question only makes sense if $n=m$, because in the singular value decomposition of $A$, $U$ will be $m\times m$ and $V^T$ will be $n\times n$.

Because the Frobenius norm is unitarily invariant, you have $$ \|A-Q\|_F=\|U\Sigma V^T-Q\|_F=\|\Sigma-U^TQV\|_F. $$ But the orthogonal (or the unitary) matrices form a group, so you want to minimize $$ \|\Sigma-Q\|_F $$ over all orthogonal matrices. You have \begin{align} \|\Sigma-Q\|_F^2&=\sum_k(\Sigma_{kk}-Q_{kk})^2+\sum_{j\ne k}Q_{kj}^2\\ \ \\ &=\sum_k(\Sigma_{kk}^2+Q_{kk}^2-2\Sigma_{kk}Q_{kk})+\sum_{j\ne k}Q_{kj}^2\\ \ \\ &=\sum_k(\Sigma_{kk}^2-2\Sigma_{kk}Q_{kk})+\sum_{j,k}Q_{kj}^2\\ \ \\ &=\text{Tr}(\Sigma^2)+\text{Tr}(Q^TQ)-2\sum_k\Sigma_{kk}Q_{kk}\\ \ \\ &=\text{Tr}(\Sigma^2)+n-2\sum_k\Sigma_{kk}Q_{kk} \end{align} To minimize this quantity over $Q$, since the entries of $\Sigma$ are non-negative and $Q_{kk}\in[-1,1]$, we need to choose $Q_{kk}=1$ for all $k$, which makes $Q=I$.

So the minimum is $$ \|\Sigma-I\|_F=\|U\Sigma V^T-UV^T\|_F=\|A-UV^T\|_F. $$

$\endgroup$
  • $\begingroup$ It is $Tr(\Sigma^2)$, not $Tr(\Sigma)$. It should also be $\|\Sigma-Q\|_F^2$ with square. $\endgroup$ – Friedrich Philipp Apr 3 '17 at 1:55
  • $\begingroup$ Indeed! Editing. $\endgroup$ – Martin Argerami Apr 3 '17 at 2:26
  • $\begingroup$ Some SVD formulas are based on ${U}$ being ${m}$x${q}$, $\Lambda$ being ${q}$x${q}$ where ${q}$ is the number of positive singular values, and ${V^T}$ being ${q}$x${n}$, so the original question can perhaps go through if we just assume orthonormal columns for ${UV^T}$. $\endgroup$ – FinanceGuyThatCantCode Jul 1 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.