0
$\begingroup$

I'm writing the question to try to complete the circle after reading the 2 other questions on Cross Validated and the link on the third bullet point:

SVD of $X$ gives us a nice matrix factorization $USV^{T}$ that allows us to obtain the best k-rank approximation of a matrix (by zeroing the k-r smallest singular values in the matrix $S$ and obtain $X_k=US_kV^{T}$ - the subscript represents the rank of the reconstructed matrix).

This can be proved by showing that $\| X - X_k \|$ is minimized by zeroing the smallest $k$ singular values in $S$ (check third link for complete proof).

My question is the following:

  • How do I go from all the above to the formulation of SVD in terms of solving the problem of residual minimization? I.e. in the first link above: $\min_{\mu, \lambda_1,\ldots, \lambda_n, \mathbf{V}_q} \sum_{i=1}^n ||x_i - \mu - \mathbf{V}_q \lambda_i||^2$

In other words why does finding the minimum of $\| X - X_k \|$ convert to solving this objective function $\min_{\mu, \lambda_1,\ldots, \lambda_n, \mathbf{V}_q} \sum_{i=1}^n ||x_i - \mu - \mathbf{V}_q \lambda_i||^2$?

$\endgroup$
  • $\begingroup$ Doesn't the first link contain a mathematical answer to your question? If you want an intuitive understanding, then notice that the matrix $\mu - V_q \lambda_i$ (each $i$ corresponds to one row) is of rank $q$, so your objective function can be rewritten as $\|X-X_q\|^2$, and that's the same as $\|X-X_k\|^2$. $\endgroup$ – amoeba Jul 30 '15 at 14:33
2
$\begingroup$

Suppose in the following that the rank of $X$ is at least $q$.

The rank-$q$ reconstruction without the centering (the $\mu$) with minimal error is given as a solution to the minimization problem $$\min_{\lambda_1,\ldots, \lambda_n, \mathbf{V}_q} \sum_{i=1}^n \|x_i - \mathbf{V}_q \lambda_i\|^2,$$ where the norm $\|\cdot\|$ denotes the 2-norm. Here $\mathbf{V}_q$ is a $p \times q$ matrix with orthonormal columns and $\lambda_i \in \mathbb{R}^q$ for $i = 1, \ldots, n$.

If $X_q$ denotes a rank-$q$ matrix its $i$'th row can be written as the transpose of $\mathbf{V}_q \lambda_i$, where $\mathbf{V}_q$ denotes the $p \times q$ matrix, whose columns are $q$ orthonormal basis vectors for the column space of $X_q$. In terms of the Frobenius norm we have the identity $$\|X - X_q \|_F^2 = \sum_{i=1}^n \|x_i - \mathbf{V}_q \lambda_i\|^2.$$
This shows that finding the rank-$q$ matrix that minimizes the Frobenius norm is equivalent to finding the $p\times q$ orthogonal matrix $\mathbf{V}_q$ that minimises the rank-$q$ reconstruction error.

$\endgroup$
  • $\begingroup$ +1. A latex nazi remark: \| is better than ||. $\endgroup$ – amoeba Aug 1 '15 at 14:49

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.