The Singular Value Decomposition

For a real m-by-n matrix A, the full singular value decomposition is A = U Sigma V^T. U is m-by-m and V is n-by-n. Both are orthogonal, so their transposes are their inverses. Sigma is m-by-n with nonnegative diagonal entries and zeros elsewhere. The diagonal entries are singular values, listed largest first. The orthogonal changes can include reflections as well as rotations.

The largest singular value is max ||Ax|| over inputs with ||x|| = 1. Here ||x|| means Euclidean length. Each right singular vector is an input direction; a positive singular value sends it to that value times its matching left singular vector. A zero singular value has a right singular direction sent to zero. These are stretch factors measured using unit inputs.

Form A^T A and find its eigenvalues. The product is symmetric. Also x^T A^T A x = ||Ax||^2, which is nonnegative. If A^T A v = lambda v with v nonzero, then lambda ||v||^2 = ||Av||^2. Since ||v||^2 is positive, lambda cannot be negative. Take nonnegative square roots of these eigenvalues to obtain the singular values, with the rectangular convention below.

The usual list has p = min(m, n) singular values, including zeros when needed. A^T A has n eigenvalues; A A^T has m. Their positive eigenvalues agree with multiplicity, but their zero counts may differ. For n > m, omit n - m extra zeros from A^T A's eigenvalue list before taking square roots for the p-entry list. A wide matrix can collapse input directions even when all listed singular values are positive.

Rank counts positive singular values. Orthogonal U and V are invertible, so replacing either by another orthogonal factor does not change rank. Replacing a positive entry of Sigma by zero lowers rank; replacing it by another positive entry does not. For a tall m-by-n matrix with n positive singular values, every input coordinate has a positive scale, so no nonzero input is sent to zero.

Write A as layers sigma_i u_i v_i^T, using matching left and right singular vectors. Keeping the first k layers gives A_k. For 0 <= k < p, this is a best approximation among matrices of rank at most k in both Frobenius and spectral norm. Keeping a single positive layer gives rank one. Keeping every positive layer reproduces A exactly. Tied singular values can make the best approximation nonunique.

The Frobenius norm squared is the sum of squared entries. It also equals the sum of squared singular values. The spectral norm is the greatest output length for a unit input. For A - A_k, the squared Frobenius error is the sum of squares of discarded singular values. Take its square root for the Frobenius error. The spectral error is the largest discarded singular value.

The eigenvalue recipe uses A^T A, not A A. Real symmetry is a sufficient condition for equality: A^T = A gives A^T A = A^2. Other square matrices need not work. For a quarter-turn matrix, A^2 = -I but A^T A = I. Using A^2 would give negative eigenvalues instead of squared stretches. A numerical result can still agree by coincidence without symmetry.

Before watching the linked Visual Kernel SVD video, note: full rank does not make all eigenvectors of a symmetric matrix perpendicular. For B = 4I, (1, 0) and (1, 2) are independent eigenvectors with dot product 1, although B has full rank. Distinct eigenvalues force perpendicularity. Within a repeated eigenspace, Gram-Schmidt preserves the span: keep a unit q, subtract (q dot w)q from the next vector w, then divide the remainder by its length.

Choose V from an orthonormal eigenbasis of A^T A, using Gram-Schmidt within repeated eigenspaces. For positive sigma_i, set u_i = Av_i/sigma_i. Then u_i dot u_j = (v_i^T A^T A v_j)/(sigma_i sigma_j), which is 0 for distinct i and j and 1 when i = j. Complete these vectors to an orthonormal basis for U when needed. This division formula cannot be used for a zero singular value.