Image Compression With Truncated SVD

From Pixels to a Matrix

A grayscale image assigns one intensity value to each pixel. If an image has \(m\) rows and \(n\) columns of pixels, place its intensities in a matrix \(\mathbf{A}\in\mathbb{R}^{m\times n}\), with \(a_{ij}\) the intensity at row \(i\), column \(j\). For example, an 8-bit image uses values from \(0\) to \(255\), where \(0\) is black and \(255\) is white. The matrix need not have any special algebraic form: the goal is to find a compact representation that preserves the important variation in its entries.

For a real matrix \(\mathbf{A}\), a singular value decomposition (SVD) writes it as a sum of rank-one matrices: \(\mathbf{A}=\sum_{i=1}^{r}\sigma_i\mathbf{u}_i\mathbf{v}_i^{\top}\). Here \(r=\operatorname{rank}\mathbf{A}\), the singular values satisfy \(\sigma_1\ge\cdots\ge\sigma_r>0\), and each of the lists \(\mathbf{u}_1,\dots,\mathbf{u}_r\) and \(\mathbf{v}_1,\dots,\mathbf{v}_r\) is orthonormal. A singular triplet consists of \((\sigma_i,\mathbf{u}_i,\mathbf{v}_i)\). Keeping the first \(k\) triplets gives a matrix that uses fewer factors than the full image matrix.

Each retained triplet stores \(m\) entries of \(\mathbf{u}_i\), \(n\) entries of \(\mathbf{v}_i\), and one singular value. Thus a direct factor representation uses \(k(m+n+1)\) real numbers, before accounting for any additional metadata or encoding. By contrast, storing every pixel as a matrix entry uses \(mn\) numbers. This comparison counts real values, not the bits required to encode them; practical image formats also use quantization and other coding choices.

Measuring the Reconstruction Error

The Frobenius norm of a matrix is the square root of the sum of the squares of all its entries: \(\|\mathbf{B}\|_F=\sqrt{\sum_{i,j}b_{ij}^2}\). For images, it measures the aggregate squared pixel difference between an original matrix and a reconstruction. The relative Frobenius error divides this difference by \(\|\mathbf{A}\|_F\), provided \(\mathbf{A}\ne\mathbf{O}\). The operator norm, written \(\|\mathbf{B}\|_2\), measures the largest singular value of \(\mathbf{B}\).

Proof. Write the discarded part as \(\mathbf{A}-\mathbf{A}_k=\sum_{i=k+1}^{r}\sigma_i\mathbf{u}_i\mathbf{v}_i^{\top}\). For matrices \(\mathbf{u}_i\mathbf{v}_i^{\top}\) and \(\mathbf{u}_j\mathbf{v}_j^{\top}\), their Frobenius inner product is \(\operatorname{tr}((\mathbf{u}_i\mathbf{v}_i^{\top})^{\top}\mathbf{u}_j\mathbf{v}_j^{\top})=(\mathbf{u}_i^{\top}\mathbf{u}_j)(\mathbf{v}_j^{\top}\mathbf{v}_i)\). Orthonormality makes this \(1\) when \(i=j\) and \(0\) otherwise. Therefore the squared Frobenius norm of the discarded sum is \(\sum_{i=k+1}^{r}\sigma_i^2\). Its nonzero singular values are precisely the discarded singular values, so its operator norm is the largest of them, \(\sigma_{k+1}\), when \(k<r\). If \(k=r\), the discarded sum is \(\mathbf{O}\), and both norms are zero. \(\square\)

The Eckart–Young theorem, established in the earlier material on low-rank approximation, says that \(\mathbf{A}_k\) achieves the smallest possible Frobenius error among all matrices of rank at most \(k\); it also minimizes the operator-norm error. The formula above quantifies the error for this optimal choice: the omitted singular values determine how much is lost. A small retained rank is useful when the tail of the singular-value list is small, not merely because the matrix has many entries.

A Reconstruction With Corrected Pixel Errors

When Does the Factor Representation Save Values?

Proof. The original matrix has \(m\) rows and \(n\) columns, hence \(mn\) entries. For each of the \(k\) triplets, the left vector has \(m\) entries, the right vector has \(n\) entries, and the singular value contributes one more. The factor storage count is therefore \(k(m+n+1)\). Comparing the two counts gives a storage reduction precisely when \(k(m+n+1)<mn\); equality means no reduction, and a larger factor count means the factor representation uses more values. \(\square\)

This count treats all values equally and excludes storage for dimensions, file headers, and the precision or coding of each value. It is a useful first test, not a guarantee about the size of a finished image file. The truncated SVD is most attractive when \(k\) is small relative to both image dimensions and the discarded singular values are small enough for the desired visual quality.

From the Mathematical Matrix to a Displayed Image

The SVD reconstruction is a real matrix, but a display or image file may require integer pixel values in a fixed range. A common practical step is to round each reconstructed entry and clip values below \(0\) to \(0\), and values above the allowed maximum to that maximum. Rounding and clipping can change the matrix and its error; the exact truncated-SVD error formulas apply to \(\mathbf{A}_k\) before these extra operations. If exact quality comparisons matter, calculate the pixel differences after the final rounding and clipping as well.

Another practical issue is that storing factors directly may not itself create a smaller file: factor entries may need many bits, and overhead can matter. The count \(k(m+n+1)\) answers a narrower, precise question—how many real values the two representations contain under the same counting convention. The error and storage measures together help select \(k\): compare the discarded singular-value energy with the number of values saved, rather than assuming that a lower rank is always a better compression choice.

Common Pitfall: Mixing Up Error Entries

When calculating \(\mathbf{A}-\mathbf{A}_k\), subtract each matrix entry from the entry in the same position, then count symmetric off-diagonal errors twice when summing squares over the whole matrix. In the \(4\times4\) example, the error at position \(12\) is \(17/4-5=-3/4\), not \(1/4\); the error at position \(14\) is \(11/4-3=-1/4\), not \(-5/4\). Using an incorrect error table can produce a plausible-looking but false norm. A reliable check is to form the full difference matrix and compare its squared Frobenius norm with the sum of the discarded squared singular values. Here both calculations give \(5\).