Explaining dimensionality reduction using SVD (without reference to PCA)

I have seen Dimensionality reduction mentioned as one of the practical usages of SVD. However, the explanation for me has always been

1. Let me find the directions in which the variance of the data is maximum

2. The derivation for PCA follows

3. The principle axis are the eigenvectors of covariance matrix ($AA^T$)

4. Ohhh wait that is precisely what SVD is if we are finding $U$ in $U*S*V^T$

5. I see we can use SVD to reduce dimensionality of data

But people seem to understand SVD in some capacity which makes them see dimensionality reduction directly as a consequence of SVD. Which i dont quite understand. Can somebody help me understand how without knowing that the eigenvectors of covariance matrix are the directions of principal axis, you get to see dimensionality reduction as something you can do from SVD

The SVD can be linked to dimensionality reduction from the standpoint of low rank matrix approximation.

SVD for low rank matrix approximation

Suppose we have a matrix $X$ and want to approximate it with a rank $r$ matrix $\hat{X}$, where $r < \text{rank}(X)$. The approximation error is measured by the Frobenius norm (which is equivalent to the square root of the squared error). The problem is then:

$$\min_\hat{X} \ \|X - \hat{X}\|_F \quad s.t. \ \text{rank}(\hat{X}) = r$$

The Eckart-Young theorem states that the solution is given by the truncated SVD of $X$:

$$\hat{X} = \tilde{U} \tilde{S} \tilde{V}^T$$

Where $X = U S V^T$ is the SVD of $X$, and $\tilde{U}, \tilde{S}, \tilde{V}$ are truncated versions of $U, S, V$--the bottom singular values and corresponding singular vectors have been discarded and only the top $r$ are retained.

Connection to dimensionality reduction

The rank of a data matrix indicates the number of dimensions spanned by the data points, i.e. the dimensionality of the linear (sub)space in which the points lie. If $X$ is a data matrix and $\hat{X}$ is a low rank approximation computed as above, this means that $\hat{X}$ is an approximation of $X$ where the points have been squashed into a lower dimensional subspace--specifically, an $r$-dimensional subspace. Hence, the truncated SVD performs dimensionality reduction.

Suppose rows correspond to data points and columns to dimensions. Then $\tilde{U} \tilde{S}$ (which has $r$ columns) gives low dimensional representations of the data. Multiplying by $\tilde{V}^T$ projects these low dimensional points back into the high dimensional space to approximate the original data: $X \approx \tilde{U} \tilde{S} \tilde{V}^T$

Connection to PCA

The relationship between SVD and PCA is often explained via eigendecomposition of the covariance matrix (as reviewed thoroughly here). But, there's also an alternative explanation based on the approximation error.

As above, the truncated SVD gives low dimensional representations that approximate the original data when projected back into the high dimensional space. This minimizes the approximation error as measured by the Frobenius norm, which is equivalent to minimizing the squared error. That is, it minimizes the squared distance between each data point and its reconstruction from the low dimensional representation.

This corresponds exactly to a description of PCA. PCA is commonly described as finding the directions of maximum variance, but it can be described equivalently as minimizing the squared approximation error, as above (e.g. see Tipping and Bishop 1999). Thus, SVD of the data matrix is equivalent to PCA. Note that this holds when the data matrix is centered. Otherwise, SVD corresponds to non-centered PCA (which can be expressed in terms of an eigendecomposition of $X^T X$ rather than the covariance matrix).

References

Eckart and Young (1936). The approximation of one matrix by another of lower rank.

Tipping and Bishop (1999). Probabilistic principal component analysis.

SVD is a generalization of PCA in the following sense. If one apples the singular value decomposition to a covariance matrix, then one gets the pca decomposition of that matrix. Viewing the matrix as a linear transformation, the matrix takes an orthonormal vector to a linear subspace spanned by one of the orthonormal vectors in the target space. What both results state is that if we consider a matrix as a linear transformation from one vector space to another, then there are orthonomal (perpendicular and of unit length) basis in both spaces such that the matrix takes a vector in one basis to the one dimensional space spanned by a vector in the other basis. In the case of a symmetric matrix one can take both vector spaces to be the same and there is only one basis. In either case once you have an orthonormal basis, , all the linear transformation can do is take a orthonormal vector to a multiple of a member of the orthonormal basis in the other. That scalar multiplication in the target space is a diagonal matrix in the case of pca,and in the case of a svd, it is a pseudo diagonal matrix. In words, with the right basis any linear transformation is just scaling the basis.

Once one has the last statement, the dimension reduction statement is, it seems to me, clear. If one has a diagonal matrix, what is the one dimensional matrix that is closest to it ? It is the diagonal matrix with all zeros except that it agrees with the original diagonal on the element of largest absolute value.