38 LOW-RANK APPROXIMATIONS
38.1. Low-rank approximations
We consider a matrix 
, with SVD given as in the SVD theorem:
![\[ A = U \tilde{S} V^T, \quad \tilde{S} = \mathbf{diag}\left(\sigma_1, \ldots, \sigma_r, 0, \ldots, 0\right), \]](https://pressbooks.pub/app/uploads/quicklatex/quicklatex.com-2ee4f7667e72dacd21e723e20223ad5e_l3.png "Rendered by QuickLaTeX.com")
where the singular values are ordered in decreasing order, 
. In many applications, it can be useful to approximate 
with a low-rank matrix.
Example: Assume that contains the log returns of 
assets over 
time periods so that each column of is a time series for a particular asset. Approximating by a rank-one matrix of the form 
, with 
and 
amounts to model the assets’ movements as all following the same pattern given by the time-profile 
, each asset’s movements being scaled by the components in 
. Specifically, the 
component of , which is the log-return of asset 
at time 
, then expresses as 
.
We consider the low-rank approximation problem
![\[ \min _X\|A-X\|_F: \mathbf{rank}(X) = k, \]](https://pressbooks.pub/app/uploads/quicklatex/quicklatex.com-ff9a791506dbf6b447f7f7dfeca5f29b_l3.png "Rendered by QuickLaTeX.com")
where 
(
) is given. In the above, we measure the error in the approximation using the Frobenius norm; using the largest singular value norm leads to the same set of solutions 
.
Theorem: Low-rank approximation
|
A best
The minimal error is given by the Euclidean norm of the singular values that have been zeroed out in the process:
|
is given by zeroing out the 
trailing singular values of ![\[ \hat{A}_k = U \hat{S}_k V^T, \quad \hat{S}_k = \mathbf{diag}\left(\sigma_1, \ldots, \sigma_k, 0, \ldots, 0\right) . \]](https://pressbooks.pub/app/uploads/quicklatex/quicklatex.com-59766bbc444596a7a77206aa0f955514_l3.png "Rendered by QuickLaTeX.com")
![\[ \|A-\hat{A}_k\|_F = \sqrt{\sigma_{k+1}^2+\ldots+\sigma_r^2} . \]](https://pressbooks.pub/app/uploads/quicklatex/quicklatex.com-6627e24109584b5da196f0af3b3580fb_l3.png "Rendered by QuickLaTeX.com")
Sketch of proof: The proof rests on the fact that the Frobenius norm, is invariant by rotation of the input and output spaces, that is, 
for any matrix 
, and orthogonal matrices 
of appropriate sizes. Since the rank is also invariant, we can reduce the problem to the case when 
.
Example: low-rank approximation of a 
matrix.
38.2. Link with Principal Component Analysis
Principal Component Analysis operates on the covariance matrix of the data, which is proportional to 
and sets the principal directions to be the eigenvectors of that (symmetric) matrix. As noted here, the eigenvectors of are simply the left singular vectors of . Hence, both methods, the above approximation method, and PCA rely on the same tool, the SVD. The latter is a more complete approach as it also provides the eigenvectors of , which can be useful if we want to analyze the data in terms of rows instead of columns.
In particular, we can express the explained variance directly in terms of the singular values. In the context of visualization, the explained variance is simply the ratio of the total amount of variance in the projected data, to that in the original. More generally, when we are approximating a data matrix by a low-rank matrix, the explained variance compares the variance in the approximation to that in the original data. We can also interpret it geometrically, as the ratio of the squared norm of the approximation matrix to that of the original matrix:
![\[ \frac{\|\hat{A}_k\|_F^2}{\|A\|_F^2} = \frac{\sigma_1^2+\ldots+\sigma_k^2}{\sigma_1^2+\ldots+\sigma_n^2} . \]](https://pressbooks.pub/app/uploads/quicklatex/quicklatex.com-2c6a3f5fce6e7cc80717b3390c82c47e_l3.png "Rendered by QuickLaTeX.com")
