Home/Notes/SVD

Singular Value Decomposition of a Matrix

Construction, the low-rank approximation theorem, and a worked example.

Abstract

The singular value decomposition (SVD) factors any real matrix into two orthogonal matrices and a diagonal matrix of non-negative singular values. It is the most important matrix factorization in numerical linear algebra: it exposes the rank, the four fundamental subspaces, and the exact sense in which a matrix is close to a low-rank one. This note states the decomposition, proves its existence constructively from the eigendecomposition of the Gram matrix \( A^{\mathsf T}A \), interprets the singular vectors as the axes along which the linear map acts by pure scaling, and derives the Eckart-Young-Mirsky theorem that makes the truncated SVD the optimal low-rank approximation in every unitarily invariant norm. A fully worked \( 2 \times 2 \) example is carried through by hand. The note closes with the two-way flow stress application, in which the leading singular value decides whether a decoupled (Johnson-Cook type) equation is legitimate for a given material, and points to the tensor generalization (CP / NN-CP) for three-way data.

Keywords: singular value decomposition; low-rank approximation; Eckart-Young theorem; principal component analysis; matrix rank

1. Introduction

Given a rectangular matrix of measurements, two questions recur throughout data-driven modeling: how many independent trends does the data actually contain, and what is the best approximation of the data by a simpler object of a chosen complexity. The singular value decomposition answers both exactly. Introduced for real square matrices by Beltrami and Jordan in the 1870s and extended to the rectangular case by Eckart and Young [1], it is today the computational core of principal component analysis, latent semantic indexing, image compression, and model-order reduction [2,3].

For the flow stress work on this site, the SVD plays a specific role. A two-way flow stress dataset, stress measured over strain and strain rate at a fixed temperature, is a matrix. A decoupled Johnson-Cook-type equation, in which the strain part and the strain-rate part multiply, is exactly a rank-1 matrix. The SVD therefore turns the qualitative question of whether such an equation is legitimate into the quantitative one of how much of the data the first singular value already explains. The three-way case (adding temperature) needs the tensor generalization treated in the CP and NN-CP notes.

2. Definition

Let \( A \in \mathbb{R}^{m \times n} \) with \( m \ge n \). The singular value decomposition of \( A \) is

\[ A = U \Sigma V^{\mathsf{T}} = \sum_{i=1}^{r} \sigma_i\, u_i\, v_i^{\mathsf{T}} \tag{1} \]

where \( U = [u_1,\dots,u_m] \in \mathbb{R}^{m \times m} \) and \( V = [v_1,\dots,v_n] \in \mathbb{R}^{n \times n} \) are orthogonal (\( U^{\mathsf T}U = I \), \( V^{\mathsf T}V = I \)), and \( \Sigma \in \mathbb{R}^{m \times n} \) is zero except for the ordered non-negative diagonal entries

\[ \sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_r > 0 = \sigma_{r+1} = \cdots = \sigma_n \tag{2} \]

The \( \sigma_i \) are the singular values, the \( u_i \) the left singular vectors, the \( v_i \) the right singular vectors, and \( r \) is the rank of \( A \). The right-hand sum in Eq. (1) writes \( A \) as a sum of \( r \) rank-1 matrices \( \sigma_i u_i v_i^{\mathsf T} \) ordered by importance. This is the exact matrix counterpart of the rank-1 sum in the CP tensor model; the difference is that here the summands are forced to be mutually orthogonal.

3. Existence and Construction

The decomposition always exists, and the standard constructive proof also gives the recipe used to compute it for small matrices. The matrix \( A^{\mathsf T}A \in \mathbb{R}^{n \times n} \) is symmetric and positive semi-definite, so by the spectral theorem it has an orthonormal set of eigenvectors \( v_1,\dots,v_n \) with real eigenvalues \( \mu_1 \ge \cdots \ge \mu_n \ge 0 \):

\[ A^{\mathsf{T}}A\, v_i = \mu_i\, v_i, \qquad \mu_i \ge 0 \tag{3} \]

Define the singular values as \( \sigma_i = \sqrt{\mu_i} \). For each \( i \) with \( \sigma_i > 0 \), define the left singular vector by

\[ u_i = \frac{1}{\sigma_i}\, A\, v_i \tag{4} \]

These \( u_i \) are orthonormal, because \( u_i^{\mathsf T} u_j = \dfrac{1}{\sigma_i \sigma_j} v_i^{\mathsf T} A^{\mathsf T} A v_j = \dfrac{\mu_j}{\sigma_i \sigma_j} v_i^{\mathsf T} v_j = \delta_{ij} \). Completing \( \{u_i\} \) to an orthonormal basis of \( \mathbb{R}^m \) and assembling \( U, \Sigma, V \) gives Eq. (1), since \( A v_i = \sigma_i u_i \) for all \( i \) is precisely the column-by-column statement of \( AV = U\Sigma \). This shows existence and, at the same time, that the right singular vectors diagonalize \( A^{\mathsf T}A \) and the left singular vectors diagonalize \( AA^{\mathsf T} \), with shared eigenvalues \( \sigma_i^2 \).

Geometrically, Eq. (4) says the linear map \( x \mapsto Ax \) sends the orthonormal right-singular directions \( v_i \) to the orthonormal left-singular directions \( u_i \), stretched by \( \sigma_i \). Every linear map is, in suitable orthonormal coordinates, a pure axis-aligned scaling: the SVD is the statement that a rotation, a scaling, and another rotation is all a matrix ever does. The singular vectors also read off the four fundamental subspaces: \( \{v_1,\dots,v_r\} \) span the row space, \( \{v_{r+1},\dots,v_n\} \) the null space, \( \{u_1,\dots,u_r\} \) the column space, and \( \{u_{r+1},\dots,u_m\} \) the left null space.

4. Low-Rank Approximation: the Eckart-Young-Mirsky Theorem

Truncating the sum in Eq. (1) after \( k < r \) terms gives the rank-\( k \) matrix

\[ A_k = \sum_{i=1}^{k} \sigma_i\, u_i\, v_i^{\mathsf{T}} \tag{5} \]

The Eckart-Young theorem [1], extended to all unitarily invariant norms by Mirsky [4], states that \( A_k \) is the best rank-\( k \) approximation of \( A \): among all matrices \( B \) of rank at most \( k \),

\[ \min_{\operatorname{rank}(B)\le k} \| A - B \|_2 = \| A - A_k \|_2 = \sigma_{k+1}, \qquad \min_{\operatorname{rank}(B)\le k} \| A - B \|_F = \| A - A_k \|_F = \sqrt{\sum_{i=k+1}^{r}\sigma_i^2} \tag{6} \]

The error of the optimal rank-\( k \) approximation is thus governed entirely by the discarded singular values. A convenient relative measure of how much a rank-\( k \) truncation captures is the energy ratio

\[ \alpha_k = \frac{\|A - A_k\|_F^2}{\|A\|_F^2} = \frac{\sum_{i>k}\sigma_i^2}{\sum_{i}\sigma_i^2} \tag{7} \]

A rapid decay of the singular values means the matrix is close to low rank and can be compressed with little loss; a slow decay means every direction carries comparable information. This is the precise sense in which the SVD tells you how many independent trends a dataset contains.

5. Relation to PCA

Principal component analysis is the SVD of a mean-centered data matrix. If the rows of \( A \) are observations and the columns are variables, and each column has had its mean removed, then the right singular vectors \( v_i \) are the principal directions, the columns of \( U\Sigma \) are the principal component scores, and \( \sigma_i^2/(m-1) \) is the variance explained by the \( i \)-th component. Computing PCA through the SVD of \( A \) is numerically preferable to forming and diagonalizing the covariance matrix \( A^{\mathsf T}A/(m-1) \), because squaring the data doubles the dynamic range and can lose small singular values to round-off [2].

6. Worked Example

Take the \( 2 \times 2 \) matrix

\[ A = \begin{bmatrix} 3 & 0 \\ 4 & 5 \end{bmatrix} \]

Form the Gram matrix and find its eigenvalues:

\[ A^{\mathsf{T}}A = \begin{bmatrix} 25 & 20 \\ 20 & 25 \end{bmatrix}, \qquad \det(A^{\mathsf T}A - \mu I) = (25-\mu)^2 - 400 = 0 \;\Rightarrow\; \mu = 45,\; 5 \]

Hence the singular values are \( \sigma_1 = \sqrt{45} = 3\sqrt5 \approx 6.708 \) and \( \sigma_2 = \sqrt5 \approx 2.236 \). The eigenvectors of \( A^{\mathsf T}A \) are \( v_1 = \tfrac{1}{\sqrt2}(1,1) \) for \( \mu = 45 \) and \( v_2 = \tfrac{1}{\sqrt2}(1,-1) \) for \( \mu = 5 \). Using Eq. (4),

\[ u_1 = \frac{1}{\sigma_1} A v_1 = \frac{1}{3\sqrt5}\begin{bmatrix} 3 \\ 9 \end{bmatrix}\frac{1}{\sqrt2} = \frac{1}{\sqrt{10}}\begin{bmatrix} 1 \\ 3 \end{bmatrix}, \qquad u_2 = \frac{1}{\sigma_2} A v_2 = \frac{1}{\sqrt5}\begin{bmatrix} 3 \\ -1 \end{bmatrix}\frac{1}{\sqrt2} = \frac{1}{\sqrt{10}}\begin{bmatrix} 3 \\ -1 \end{bmatrix} \]

so that

\[ A = U\Sigma V^{\mathsf T} = \frac{1}{\sqrt{10}}\begin{bmatrix} 1 & 3 \\ 3 & -1 \end{bmatrix} \begin{bmatrix} 3\sqrt5 & 0 \\ 0 & \sqrt5 \end{bmatrix} \frac{1}{\sqrt2}\begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} \]

The best rank-1 approximation is \( A_1 = \sigma_1 u_1 v_1^{\mathsf T} = \tfrac{3}{2}\left[\begin{smallmatrix} 1 & 1 \\ 3 & 3 \end{smallmatrix}\right] = \left[\begin{smallmatrix} 1.5 & 1.5 \\ 4.5 & 4.5 \end{smallmatrix}\right] \), with error \( \|A - A_1\|_2 = \sigma_2 = \sqrt5 \), exactly as Eq. (6) predicts. The energy ratio of Eq. (7) is \( \alpha_1 = \sigma_2^2/(\sigma_1^2+\sigma_2^2) = 5/50 = 0.10 \), so a rank-1 model captures 90% of this matrix. Read as a legitimacy test, a 10% residual would be judged too large if the acceptance threshold were, say, 1%, and a rank-2 (fully coupled) description would be required.

7. Use in the Flow Stress Work

Where this is used. A two-way flow stress matrix, stress over strain and strain rate, is decomposed by SVD. A decoupled Johnson-Cook-type equation is a rank-1 matrix, so the rank-1 energy ratio \( \alpha_1 \) of Eq. (7) becomes a quantitative legitimacy criterion: the decoupled form is accepted for a material only when the rank-1 approximation error stays below a preset threshold. Where it does not, the higher singular values quantify exactly how much coupling the data demands. For three-way data that also varies with temperature, the orthogonality that SVD imposes is no longer natural, and the model is replaced by the essentially unique, non-orthogonal CP decomposition. See Constitutive Modeling for the research context, and the IJIE 2023 paper for the criterion in use.

8. Conclusions

  1. Every real matrix factors as \( A = U\Sigma V^{\mathsf T} \) with orthogonal \( U, V \) and ordered non-negative singular values on \( \Sigma \); the construction follows from the eigendecomposition of \( A^{\mathsf T}A \).
  2. The singular vectors are the orthonormal axes along which the map acts by pure scaling, and they read off the rank and the four fundamental subspaces.
  3. By the Eckart-Young-Mirsky theorem, truncating the SVD after \( k \) terms gives the optimal rank-\( k \) approximation in every unitarily invariant norm, with error set by the discarded singular values.
  4. The decay of the singular values measures how many independent trends a dataset carries; a dominant first singular value is the matrix statement that a decoupled, rank-1 model suffices.

References

  1. Eckart, C., & Young, G. (1936). The approximation of one matrix by another of lower rank. Psychometrika, 1(3), 211-218.
  2. Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.
  3. Trefethen, L. N., & Bau, D. (1997). Numerical Linear Algebra. SIAM.
  4. Mirsky, L. (1960). Symmetric gauge functions and unitarily invariant norms. Quarterly Journal of Mathematics, 11(1), 50-59.
  5. Golub, G. H., & Reinsch, C. (1970). Singular value decomposition and least squares solutions. Numerische Mathematik, 14(5), 403-420.
  6. Jolliffe, I. T. (2002). Principal Component Analysis (2nd ed.). Springer.
  7. Kolda, T. G., & Bader, B. W. (2009). Tensor decompositions and applications. SIAM Review, 51(3), 455-500.

Back to Technical Notes