SVD from Matrix formulation to objective function

Question

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

Answer 1

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.