Linear Algebra › Section G · Symmetric matrices and quadratic forms › Topic G.5
Applications to images, statistics, and data
Photographs, survey results and film ratings are all stored as matrices, and the singular value decomposition finds the few patterns that carry most of their information. This topic shows how that idea compresses images, powers principal component analysis and sits inside modern data science.
Data as matrices
A greyscale photograph is a matrix of brightness values, one entry per pixel. A survey of 500 people answering 20 questions is a \(20 \times 500\) matrix. A streaming service's ratings form a matrix with one row per viewer and one column per film. Such matrices are large but rarely random: neighbouring pixels are similar, answers are correlated, and tastes fall into a few broad types. The singular value decomposition measures that hidden structure. Large singular values mark strong patterns; small ones mark detail or noise.
Best low-rank approximation
Multiplying out \(A = U\Sigma V^T\) column by row writes any matrix of rank \(r\) as a sum of rank-1 pieces:
Keeping only the first \(k\) terms gives a matrix \(A_k\) of rank \(k\). The Eckart-Young theorem, published in 1936 and extended by Leon Mirsky in 1960, says no rank-\(k\) matrix is closer to \(A\). The error is \(\sigma_{k+1}\) in the matrix 2-norm, and \(\sqrt{\sigma_{k+1}^2 + \cdots + \sigma_r^2}\) in the Frobenius norm, the square root of the sum of the squared entries. When the singular values fall off quickly, a few terms are almost as good as the whole matrix.
Worked example: a rank-1 approximation
The \(3 \times 2\) matrix \(A\) with rows \((1, 1)\), \((0, 1)\), \((1, 0)\) has \(\sigma_1 = \sqrt{3}\), \(\sigma_2 = 1\), \(\mathbf{u}_1 = (2, 1, 1)/\sqrt{6}\) and \(\mathbf{v}_1 = (1, 1)/\sqrt{2}\). 1. \(A_1 = \sqrt{3}\,\mathbf{u}_1\mathbf{v}_1^T\) has rows \((1, 1)\), \((0.5, 0.5)\), \((0.5, 0.5)\). 2. The error \(A - A_1\) has rows \((0, 0)\), \((-0.5, 0.5)\), \((0.5, -0.5)\). 3. Its Frobenius norm is \(\sqrt{4 \times 0.25} = 1\), exactly the discarded \(\sigma_2\), as the theorem predicts.
Compressing an image
Storing an \(m \times n\) image takes \(mn\) numbers. Storing \(A_k\) takes only \(k\) singular values, \(k\) vectors \(\mathbf{u}_i\) of length \(m\) and \(k\) vectors \(\mathbf{v}_i\) of length \(n\), that is \(k(m + n + 1)\) numbers. For a \(512 \times 512\) image, \(k = 40\) needs \(40 \times 1025 = 41{,}000\) numbers instead of 262,144, about 16% of the original. Photographs usually have rapidly decaying singular values, so such an approximation often looks close to the original, while very small \(k\) gives a blurred picture. JPEG uses a different change of basis, the discrete cosine transform, in which most of an image's information also sits in a few coefficients.
Mean-deviation form and the covariance matrix
Suppose \(N\) observations of \(p\) variables are stored as the columns \(\mathbf{x}_1, \dots, \mathbf{x}_N\) of a \(p \times N\) matrix. Many software packages store observations as rows instead, which simply transposes everything. Compute the sample mean \(\mathbf{m} = \frac{1}{N}(\mathbf{x}_1 + \cdots + \mathbf{x}_N)\) and subtract it from each column to get the mean-deviation matrix \(B\). The sample covariance matrix is
It is \(p \times p\) and symmetric. Its diagonal entry \(s_{jj}\) is the variance of variable \(j\), its off-diagonal entry \(s_{ij}\) is the covariance of variables \(i\) and \(j\), and its trace is the total variance.
Worked example: a covariance matrix
Four observations of two variables are \((1, 2)\), \((3, 4)\), \((5, 8)\) and \((7, 6)\). 1. The mean is \(\mathbf{m} = (16/4, 20/4) = (4, 5)\). 2. Subtracting it gives the deviations \((-3, -3)\), \((-1, -1)\), \((1, 3)\), \((3, 1)\), the columns of \(B\). 3. The entries of \(BB^T\): \(9 + 1 + 1 + 9 = 20\), cross term \(9 + 1 + 3 + 3 = 16\), and \(9 + 1 + 9 + 1 = 20\). 4. Divide by \(N - 1 = 3\):
5. Each variable has variance \(20/3 \approx 6.67\), the covariance \(16/3\) is positive because the variables rise together, and the total variance is \(40/3 \approx 13.33\).
Principal component analysis
Principal component analysis (PCA), introduced by Karl Pearson in 1901 and developed by Harold Hotelling in 1933, looks for new perpendicular axes that line up with the spread of the data. Orthogonally diagonalise \(S = PDP^T\), with eigenvalues \(\lambda_1 \ge \cdots \ge \lambda_p \ge 0\). The unit eigenvectors, the columns of \(P\), are the principal components, and the new variables are \(\mathbf{y} = P^T\mathbf{x}\) for each mean-deviation observation \(\mathbf{x}\). The variance of \(y_1 = \mathbf{u}_1^T\mathbf{x}\) is \(\mathbf{u}_1^TS\mathbf{u}_1 = \lambda_1\), and by "Constrained optimization" no other unit direction does better. The new variables are uncorrelated, and the fraction of the total variance carried by component \(j\) is \(\lambda_j / (\lambda_1 + \cdots + \lambda_p)\).
Worked example: reducing two variables to one
Continue with the covariance matrix from the previous example. 1. Its eigenvalues are \((20 \pm 16)/3\), that is 12 and \(4/3\), with unit eigenvectors \((1, 1)/\sqrt{2}\) and \((1, -1)/\sqrt{2}\). 2. The first principal component is \(y_1 = (x_1 + x_2)/\sqrt{2}\), in mean-deviation form. 3. It carries \(12 / (40/3) = 90\%\) of the total variance. 4. Check directly: the four deviations give \(y_1 = -3\sqrt{2}, -\sqrt{2}, 2\sqrt{2}, 2\sqrt{2}\), whose squares sum to \(18 + 2 + 8 + 8 = 36\), and \(36/3 = 12\). 5. So replacing each two-number observation by the single number \(y_1\) keeps 90% of the variation, the idea behind dimension reduction for data with dozens or thousands of variables.
PCA through the SVD
In practice PCA is computed from the SVD of \(B\), not from \(S\). Since \(BB^T = U\Sigma\Sigma^TU^T\), the left singular vectors of \(B\) are the principal components, and the eigenvalues of \(S\) are \(\sigma_i^2/(N - 1)\). In the example, \(B\) has singular values 6 and 2, and \(36/3 = 12\) and \(4/3\) match. Working from \(B\) avoids forming \(BB^T\), which squares the condition number and loses accuracy. Multichannel satellite images use PCA to concentrate most of the variation of many wavelength bands into a few component images. When the variables have different units, they are usually standardised first, or the variable with the largest numbers dominates.
Recommendations and modern data
In a ratings matrix, a low-rank approximation models each viewer and each film by a few hidden taste factors, and its entries predict ratings not yet given; the Netflix Prize competition, run from 2006 to 2009, made such matrix factorisation methods famous. Suppose a ratings matrix has singular values 12, 5 and 0.6. Keeping two terms gives a relative Frobenius error of \(0.6/\sqrt{144 + 25 + 0.36} \approx 4.6\%\). More broadly, regression is least squares, text analysis applies the SVD to word-document matrices, and machine-learning systems represent words and images as vectors called embeddings, compared by cosine similarity, a normalised dot product.
Common mistakes to avoid
First, forgetting to centre the data: PCA needs the mean-deviation matrix \(B\), not the raw observations. Second, dividing by \(N\) instead of \(N - 1\) for the sample covariance. Third, mixing conventions: if observations are rows, the covariance matrix is \(B^TB/(N - 1)\) and the principal components are right singular vectors. Fourth, reporting a principal component as an eigenvector of the data matrix itself; it is an eigenvector of \(S\), or a singular vector of \(B\). Fifth, using singular values of \(B\) as variances without squaring them and dividing by \(N - 1\).
Key takeaways
Keeping the first k rank-1 pieces σᵢuᵢvᵢᵀ of the SVD gives the best rank-k approximation (Eckart-Young, 1936); its Frobenius error is the square root of the sum of the discarded σᵢ². A rank-k image needs k(m + n + 1) numbers. For data, subtract the mean to get B; then S = BBᵀ/(N − 1), whose trace is the total variance. The principal components are unit eigenvectors of S; component j carries the fraction λⱼ/(total variance). They are computed stably as left singular vectors of B, with λᵢ = σᵢ²/(N − 1). Low-rank models also power recommendations.
Flashcards
Flashcard
A = σ₁u₁v₁ᵀ + ⋯ + σᵣuᵣvᵣᵀ
Test your understanding
Question 1 of 5
A matrix has singular values 10, 4, 2 and 1. What is the Frobenius-norm error of its best rank-2 approximation?
Question 2 of 5
How many numbers are needed to store a rank-20 approximation of a 300 × 400 image?
Question 3 of 5
Three observations of two variables are (2, 1), (4, 5) and (6, 3). What is the sample covariance of the two variables?
Question 4 of 5
A covariance matrix has eigenvalues 30, 15 and 5. What fraction of the total variance does the first principal component carry?
Question 5 of 5
A mean-deviation matrix B for N = 11 observations has largest singular value 20. What is the variance of the first principal component?
