# SVD from Matrix formulation to objective function

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$?

• 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$. – amoeba Jul 30 '15 at 14:33

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.
• +1. A latex nazi remark: \| is better than ||. – amoeba Aug 1 '15 at 14:49