Understanding Truncated SVD (2023)

By Chema Guerra

In a previous discussion, I explored Principal Component Analysis (PCA). To recap: PCA achieves data reduction by linearly shifting data into a new coordinate system. This allows the majority of the data's variance to be captured using fewer dimensions than the original set. Technically, this process relies on the eigen-decomposition of the covariance matrix.

What is SVD?

Singular Value Decomposition (SVD) is a method of matrix factorization. It breaks down a real matrix M into three distinct matrices: U, Σ (Sigma), and V, expressed by the following LaTeX formula:

$M = U \Sigma V^T$

Matrix Properties

• U and V are orthonormal.
• Σ is a rectangular-diagonal matrix containing non-negative coefficients.

The relationship between SVD and PCA is intimate but distinct. While they are similar, the primary difference lies in what is being factored:

Note: The diagonal elements of Σ are the singular values of M. These are typically sorted in descending order. The total number of non-zero singular values determines the rank of matrix M.

The SVD-PCA Connection

1. The columns of V represent the principal axes (or eigenvectors).
2. The singular values in Σ are directly related to the eigenvalues of the covariance matrix.

---

The Concept of Truncated SVD

As noted via Wikipedia, let's apply this to a $1024 \times 1024$ grayscale image of the moon. We can view this image as a collection of 1024 vectors, each with 1024 components. Performing SVD results in three $1024 \times 1024$ matrices.

Truncated SVD is the process of keeping all coefficients keeping only the top $n$ coefficients in the top-left of Σ and setting all others to zero.

By reconstructing the matrix as $M' = U' \Sigma' V'^T$, we get an approximation of the original. The more coefficients we retain, the closer $M'$ is to $M$. However, due to the nature of SVD, a small fraction of the top coefficients often captures nearly all the essential information.

Case Study: Reconstructing the Moon

To visualize this, we can sweep $n$ across its entire range. In the resulting analysis, the left side shows the reconstructed image $M'$, while a yellow graph tracks the Mean Squared Error (MSE).

The Efficiency of Reduction

Consider the case where $n = 32$:

• Original size: $1024 \times 1024$
• Truncated factors: U' ($1024 \times 32$), Σ' ($32$ values), V' ($1024 \times 32$).
• Result: A 16x reduction in data, yet the image is still clearly the moon.

The error graph drops precipitously, proving that the initial components hold the bulk of the information. The remaining components merely contain low-amplitude, high-frequency details.

Comparison to Signal Processing

This behavior is similar to the Fourier Transform (FT) or Cosine Transform (CT). While FT/CT deal with frequency duality, SVD/PCA are driven by variance. Both, however, restructure information so the most "important" parts are easily accessible. This is the foundation of compression formats like .jpeg and .mp3, which leverage the fact that human perception is more sensitive to luminance than certain high-frequency details.

---

Handling "Harder" Cases

Matrix factorization can be seen as a change of basis to a space where rows are linearly dependent. If a matrix has a low rank, it can be reconstructed perfectly with very few coefficients.

Example: The Centered Square For a simple centered box, a single coefficient ($n=1$) is often enough because the rows and columns are identical.

• Side note: A box is essentially a separable convolution filter.

The Rotation Problem When the shape is rotated, the reconstruction struggles. Even though SVD can detect basis changes, we are working with discrete pixels. Rotation introduces "pixelation," making the decomposition numerically impure. In early reconstruction frames, the algorithm often "insists" on rendering an unrotated square.

Practical Applications & Implementation

Beyond general data analysis, truncated SVD is useful for:

• Data Compression: Used in PBR texture set compression (see Bart Wronski's work).
• BCn Texture Compression: Based on dimensionality reduction.
• Low-Rank Convolution: (A topic for a future post).

Technical Implementation

I previously utilized a C++ implementation from the Maverick API for these experiments:

// Conceptual old implementation
xsvd_c svd_solver;
svd_solver.decompose(image_matrix, U, Sigma, V);
svd_solver.truncate(n);

However, after reviewing a post by Atrix256, I am considering replacing my xsvd_c class with the Eigen library for better performance and reliability.