3
$\begingroup$

Consider a square real symmetric matrix $A$. The singular value decomposition (SVD) is given as

$A = U\Sigma U^T$,

and it can also be found by minimizing $|A-U\Sigma U^T|$ where $|.|$ is the $l$2 norm, $U$ is constrained to be orthonormal and $\Sigma$ is diagonal, or simply $A=UU^T$ if $U$ is orthogonal.

Now since $A$ is square, real and symmetric, is the SVD the same as the eigenvalue decomposition? I think so.

Now suppose I want to find the rank=1 approximation to A. I can take the first row of $U$ (corresponding to the largest element of $\Sigma$). This is the eigenvector with the largest (absolute) eigenvalue.

Is this the same as minimizing $| A - U_1 U_1^{T} |$ where $U_1$ is a $N$x$1$ row vector?

So is it true that the first eignevector $U_1$ is the solution to

$\arg\min_{U_1} |A-U_1 U_1^{T}|$

Can I simply state this result as a known result in my work?

$\endgroup$
3
$\begingroup$

In general, the SVD decomposition of a matrix $A$ is $A = U \Sigma V^T$ where $\Sigma$ is diagonal with non-negative entries (the singular values), the columns of $U$ are the eigenvectors of $A^T A$ and the columns of $V$ are the eigenvectors of $A A^T$. If $A$ is symmetric and positive semidefinite (so all the eigenvalues of $A$ are non-negative), then the SVD decomposition of $A$ coincide with the eigenvalue decomposition. If $A$ is symmetric but not necessarily positive semidefinite, the eigenvalue decomposition of $A$ is not the same as the SVD decomposition but quite close:

If you take a basis $(u_1, \ldots ,u_n)$ of eigenvectors of $A$ with $Av_i = \lambda_i v_i$ such that $|\lambda_1| \geq \ldots \geq |\lambda_n|$ then the SVD decomposition of $A$ can be constructed by choosing $U = (u_1 | \ldots | u_n)$ and $V = (\pm u_1 | \ldots | \pm u_n)$ (where you choose $-u_i$ if $\lambda_i < 0$ and $+u_i$ otherwise).

Finally, the matrix $\lambda_1 u_i u_i^T$ is indeed the best rank one approximation of $A$ in the sense that

$$ \lambda_1 u_1 u_1^T = \arg \min_{u,v} |A - uv^T| $$

where $| \cdot |$ is the Frobenius norm. You can read about this (and see the proof) here. It is well-known and you can find many sources if you need to refer to the result.

$\endgroup$
  • $\begingroup$ Thank you! You mean $u_1 = \arg \min_{u}|A-uu^T|$, right? $\endgroup$ – highBandWidth Nov 13 '15 at 19:23
  • $\begingroup$ No - A general rank one matrix is of the form $uv^T$ (for which each row is of the form $u_i \cdot v^T$) and not $uu^T$. $\endgroup$ – levap Nov 13 '15 at 21:24
  • $\begingroup$ The theorem you are looking for is known as the Eckart-Young theorem (1936) and it says that the truncated SVD is the best low rank approximation for the Frobenius norm. The same truncated SVD is also the best low rank approximation for the spectral norm as well. $\endgroup$ – Gil Nov 19 '15 at 15:42

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.