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: 


*

*What is the objective function of PCA?

*What norm of the reconstruction error is minimized by the low-rank approximation matrix obtained with PCA?

*http://infolab.stanford.edu/~ullman/mmds/ch11.pdf
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$?
 A: 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. 
