1 Basic definitions and notation

1.1 Matrix factorization statement

Singular Value Decomposition (SVD) is a matrix factorization that represents any real \(m\times n\) matrix \(A\) in the form \[ A = U \Sigma V^T, \] where \(U\) is an \(m\times m\) orthogonal matrix, \(V\) is an \(n\times n\) orthogonal matrix, and \(\Sigma\) is an \(m\times n\) diagonal (rectangular diagonal) matrix with nonnegative entries on its “diagonal.” For complex matrices, the transpose \(V^T\) is replaced by the conjugate transpose \(V^*\), and \(U,V\) are unitary.

The number of nonzero singular values is equal to the rank of \(A\), and the singular values are ordered conventionally in nonincreasing order.

1.2 Singular values and singular vectors

The diagonal entries of \(\Sigma\), denoted \(\sigma_1,\sigma_2,\dots\), are the singular values of \(A\). They satisfy \[ \sigma_1 \ge \sigma_2 \ge \cdots \ge 0. \] Associated with each singular value \(\sigma_i\) are left and right singular vectors: vectors \(u_i\) (columns of \(U\)) and \(v_i\) (columns of \(V\)) such that \[ A v_i = \sigma_i u_i,\qquad A^T u_i = \sigma_i v_i \] for real matrices, and with conjugate transpose in the complex case.

These vectors form orthonormal bases for the relevant subspaces determined by \(A\).

1.3 Geometric interpretation of SVD

Geometrically, SVD expresses a linear map as three stages: rotation/reflection by \(V^T\), scaling along orthogonal directions by \(\Sigma\), and rotation/reflection by \(U\). In particular, \(A\) maps the right singular vectors \(v_i\) to scaled left singular vectors \(\sigma_i u_i\). Because the singular vectors are orthonormal, the action of \(A\) on different directions separates cleanly into independent scale factors.

This viewpoint makes SVD especially useful for understanding how a transformation stretches, compresses, or collapses space.

1.4 Relation to eigenvalues and eigenvectors

While \(A\) need not be diagonalizable, the symmetric positive semidefinite matrices \[ A^T A \quad \text{and} \quad A A^T \] are diagonalizable with orthonormal eigenvectors. Their eigenvalues are the squares of the singular values of \(A\): \[ A^T A v_i = \sigma_i^2 v_i,\qquad A A^T u_i = \sigma_i^2 u_i. \] Thus, the right singular vectors are eigenvectors of \(A^T A\), and the left singular vectors are eigenvectors of \(A A^T\). This relationship explains why SVD is a “square-root” extension of eigen-decomposition to rectangular and nonnormal matrices.

2 Computing SVD

2.1 Overview of numerical algorithms

In practice, SVD is computed using numerically stable algorithms designed for floating-point arithmetic. Most modern implementations follow a pipeline that reduces the problem to a simpler structured form and then computes singular values and vectors via iterative refinements.

2.1.1 Bidiagonalization and reduction steps

A common approach begins with bidiagonalization, transforming \(A\) into an upper (or lower) bidiagonal matrix \(B\) using orthogonal/unitary transformations from the left and right: \[ A = P B Q^T. \] Since \(B\) has nonzero entries only on its main diagonal and one adjacent diagonal, its structure is easier to exploit. The singular values of \(B\) match those of \(A\), and the singular vectors of \(A\) can be recovered by accumulating the transformations \(P\) and \(Q\).

This stage is crucial for numerical stability and sets up efficient subsequent computations.

2.1.2 Iterative methods and convergence considerations

Once bidiagonal form is obtained, algorithms such as the implicitly shifted QR method are used to compute the singular values and singular vectors of \(B\). Convergence depends on spectral gaps, scaling, and the presence of clustered singular values. Practical implementations include strategies to reduce numerical errors, such as careful shift selection and deflation when parts of the spectrum separate.

Iterative methods are designed to maintain orthogonality of computed vectors to within floating-point precision.

2.2 Handling rectangular and rank-deficient matrices

For rectangular matrices, SVD naturally accommodates differing dimensions: \(\Sigma\) is rectangular and includes singular values corresponding to the rank. When \(A\) is rank-deficient, some singular values are exactly or numerically zero, and the corresponding singular vectors span the null space components. Algorithms typically detect or mitigate loss of significance to ensure that near-zero singular values are treated consistently.

Robust handling of rank deficiency is central to using SVD in least-squares and inverse problems.

2.3 Complexity and practical performance notes

The computational cost of full SVD depends on \(m,n\). For dense matrices, the leading-order complexity is typically on the order of \(O(mn\min(m,n))\) for standard methods, though optimized routines can vary by constant factors and hardware. In many applications, partial or truncated SVD is preferable, especially when only the largest singular values and vectors are needed.

Performance in practice also depends on memory layout, whether the matrix is sparse or structured, and whether specialized solvers are used.

3 Properties of SVD

3.1 Orthogonality/unitarity properties

The factors \(U\) and \(V\) have orthonormal columns. In the real case, \(U^T U = I\) and \(V^T V = I\). In the complex case, \(U^*U=I\) and \(V^*V=I\). These properties ensure that norms and inner products are preserved under multiplication by \(U\) and \(V\), which simplifies analysis of \(A\) through its diagonal “core” \(\Sigma\).

As a consequence, many identities involving SVD reduce to straightforward statements about \(\Sigma\).

3.2 Invariance under orthogonal transformations

If \(Q_1\) and \(Q_2\) are orthogonal (or unitary) matrices of compatible sizes, then \[ A' = Q_1 A Q_2 \] has the same singular values as \(A\). The singular vectors transform accordingly, while the scaling factors in \(\Sigma\) remain unchanged. This invariance supports the geometric interpretation: rotations/reflections of input and output coordinates do not alter how strongly \(A\) stretches along orthogonal directions.

3.3 Best low-rank approximation

A central optimality property is the Eckart–Young–Mirsky theorem. For any target rank \(r\), the truncated SVD provides the best approximation of \(A\) among all matrices of rank at most \(r\), measured in either the spectral norm \(\|\cdot\|_2\) or Frobenius norm \(\|\cdot\|_F\). If

\[ A_r = \sum_{i=1}^r \sigma_i u_i v_i^T, \] then \[

\|A - A_r\|_2 = \sigma_{r+1},\qquad \|A - A_r\|_F^2 = \sum_{i=r+1}^{\min(m,n)} \sigma_i^2.

\] Thus, truncation has a precise meaning: it removes the “least energetic” singular directions.

3.4 Pseudoinverse from SVD

The Moore–Penrose pseudoinverse \(A^+\) can be expressed via SVD. If \(A=U\Sigma V^T\), then \[ A^+ = V \Sigma^+ U^T, \] where \(\Sigma^+\) is obtained by inverting each nonzero singular value and transposing the rectangular structure appropriately. Singular values that are zero remain zero after inversion. This formulation yields a stable method for constructing generalized inverses and is commonly used in least-squares solvers.

3.5 Norms, condition numbers, and stability

SVD provides direct access to operator norms. In particular, \[

\|A\|_2 = \sigma_1,\qquad \|A\|_F^2 = \sum_i \sigma_i^2.

\] The (2-norm) condition number is \[ \kappa_2(A)=\frac{\sigma_1}{\sigma_{\min\neq 0}}, \] and it quantifies sensitivity to perturbations. Because SVD exposes small singular values explicitly, it offers a clear diagnostic for ill-conditioning and guides regularization or truncation strategies.

4 Applications in applied mathematics

4.1 Least-squares and regression

4.1.1 Solving overdetermined systems

For an overdetermined system \(Ax \approx b\) with \(m>n\), least-squares seeks \(x\) minimizing \(\|Ax-b\|_2\). Using SVD, one can express the solution as

\[ x = A^+ b, \] which distributes contributions of \(b\) across the singular directions. Directions aligned with small singular values can amplify noise, so SVD-based computations often incorporate truncation or regularization when necessary.

This approach is widely used because it produces stable solutions even when \(A\) is nearly rank-deficient.

4.1.2 Solving underdetermined systems

For underdetermined problems (\(m<n\)), there are infinitely many solutions that fit the data exactly (when consistent). SVD identifies the minimum-norm solution, typically the one with smallest \(\|x\|_2\). The pseudoinverse formulation \(x=A^+b\) selects this minimum-norm element among all feasible vectors.

4.2 Principal Component Analysis (PCA)

4.2.1 Data centering and covariance connections

PCA begins by centering data so that the mean is removed. When one forms a data matrix \(X\) whose rows (or columns) represent observations, the covariance matrix is proportional to \(X^T X\) (or \(X X^T\)). Since SVD yields eigenvectors of these Gram matrices, the principal components correspond to singular vectors. The principal component variances relate to squared singular values.

This establishes a tight link between PCA and SVD: principal directions emerge from the same spectral structure.

4.2.2 Dimensionality reduction using truncated SVD

Truncated SVD reduces the data representation by keeping the first \(r\) singular values and vectors. The resulting approximation minimizes reconstruction error in Frobenius norm among rank-\(r\) reconstructions. In many workflows, this leads to faster downstream computation and mitigates noise by suppressing minor singular directions.

4.3 Image and signal processing

4.3.1 Denoising via truncated SVD

In denoising, an observed signal matrix is modeled as a low-rank structure plus noise. Truncating the SVD keeps dominant singular components believed to represent the underlying signal. Removing weaker components reduces noise power, often improving visual quality or signal interpretability.

4.3.2 Compression and reconstruction

Image compression leverages the fact that images can be approximated well by low-rank matrices. Storing only the largest singular values and corresponding singular vectors can significantly reduce memory. Reconstruction uses the truncated sum \(\sum_{i=1}^r \sigma_i u_i v_i^T\), trading fidelity for storage through the choice of \(r\).

4.4 Systems identification and model reduction

In engineering and scientific computation, one often seeks reduced-order models that mimic system behavior using fewer degrees of freedom. Data-driven techniques can collect snapshots of system states and use SVD to identify dominant modes. Keeping the leading singular components yields a lower-dimensional subspace for simulation and control design, improving efficiency while retaining essential dynamics.

4.5 Spectral methods and modal analysis

Spectral methods analyze operators by examining their action on basis functions or measured data. SVD assists in extracting dominant modes from data matrices derived from time series or spatial discretizations. In modal analysis, singular vectors can represent coherent patterns even when the underlying operator is not normal or when direct eigen-decomposition is unreliable.

5 Truncated and randomized SVD

5.1 Rank truncation and reconstruction error

Given singular values \(\sigma_1\ge \cdots\), the truncated rank-\(r\) approximation uses only the first \(r\) terms. Reconstruction error depends on the discarded tail. Under Frobenius norm, the error equals the square root of the sum of squares of omitted singular values. This provides a practical measure for selecting \(r\) based on desired accuracy or energy capture.

5.2 Choosing the target rank

Selecting \(r\) requires balancing approximation quality against computational cost. Common criteria include:

  • retaining enough singular value “energy” (e.g., a fixed percentage of \(\sum \sigma_i^2\)),
  • comparing \(\sigma_{r}\) and \(\sigma_{r+1}\) to detect spectral gaps,
  • cross-validation for predictive tasks,
  • and using stability-driven thresholds in the presence of noise.

In many applications, the singular value decay rate strongly influences the usefulness of truncation.

5.3 Randomized SVD workflow

5.3.1 Sketching and sampling strategies

Randomized SVD approximates leading singular components using random projections (“sketches”). One multiplies \(A\) by a random test matrix \(\Omega\) to obtain \(Y=A\Omega\), then orthonormalizes \(Y\) to form a basis \(Q\). The product \(B=Q^T A\) is smaller, and its SVD is computed directly. This reduces the cost when \(A\) is large and only leading singular values are needed.

Oversampling and power iterations are often used to improve accuracy, especially when singular values decay slowly.

5.3.2 Error estimation and refinement

Randomized methods typically include mechanisms to estimate approximation error from the sketch. Refinements such as additional power iterations or reweighting steps can improve spectral fidelity. The target is to ensure that the computed subspace captures the dominant singular directions with high probability, while keeping runtime feasible.

6.1 Connection to QR and eigenvalue decompositions

SVD relates to QR decomposition through shared geometric content: QR factorizes a matrix into an orthonormal basis and an upper triangular factor. While QR focuses on column spaces, SVD simultaneously characterizes both row and column spaces. In special cases where \(A\) is square and normal (commutes with its adjoint), eigen-decomposition aligns closely with SVD since singular values coincide with absolute eigenvalues. More generally, SVD can be used to connect nonnormal problems to eigen-structure of \(A^TA\) and \(AA^T\).

6.2 Economy/compact SVD variants

A full SVD uses full-sized \(U\) and \(V\). The compact (or economy) SVD keeps only the singular vectors corresponding to nonzero (or numerically significant) singular values. If \(r=\text{rank}(A)\), the compact form can be written as \[ A = U_r \Sigma_r V_r^T \] with \(U_r\in \mathbb{R}^{m\times r}\), \(V_r\in \mathbb{R}^{n\times r}\). This reduces storage and can speed up downstream computations, particularly when the rank is much smaller than \(\min(m,n)\).

6.3 Polar decomposition relation

Polar decomposition writes a matrix \(A\) as \(A=UH\), where \(U\) is orthogonal/unitary and \(H\) is symmetric positive semidefinite (or Hermitian). SVD provides an explicit link: \(H\) can be expressed using singular values and \(U\) corresponds to the singular-vector-based isometry. As a result, SVD can be used to compute polar factors and interpret \(A\) as a rotation/reflection combined with a stretching component.

6.4 Nonnegative matrix factorization (conceptual comparison)

Nonnegative matrix factorization (NMF) factors a nonnegative matrix into factors with nonnegative entries, often producing parts-based representations. Conceptually, NMF and SVD both perform low-rank approximations, but SVD allows arbitrary signs and typically yields orthogonal factors, whereas NMF imposes nonnegativity constraints for interpretability. Because NMF is generally nonconvex, it lacks the universal optimality guarantees associated with the SVD truncation in least-squares settings, though it can offer different interpretive advantages.

7 Interpretation and common pitfalls

7.1 Sign/phase ambiguity in singular vectors

Singular vectors are not uniquely determined: if \((u_i,v_i)\) corresponds to \(\sigma_i\), then \((-u_i,-v_i)\) also corresponds. For complex matrices, a common phase rotation \(e^{i\theta}\) applied consistently to the pair also preserves the decomposition. Consequently, comparing singular vectors across runs or datasets may require alignment of signs/phases, especially when using them as features.

7.2 Zero singular values and subspaces

When singular values are zero (or extremely small), the corresponding singular vectors span null-space-related components. Numerical computations may produce small but nonzero values due to finite precision. Interpretation should then be cautious: whether a direction is truly absent or merely suppressed depends on the tolerance used to distinguish “numerically zero” from “significant.”

7.3 Scaling effects and data preprocessing

SVD is sensitive to scaling of rows and columns because it depends on Euclidean geometry. In practice, data preprocessing steps such as normalization, centering, or scaling features can significantly change singular values and directions. For example, in PCA-like workflows, using the covariance-based formulation rather than raw data may be essential to avoid giving undue influence to variables with large units or variances.

7.4 Numerical issues (floating-point, conditioning)

Computations can suffer from rounding errors, especially for ill-conditioned matrices with rapidly decaying singular values. Although SVD is among the most stable decompositions, the choice of truncation threshold or regularization parameter can strongly affect results. Verifying residuals, monitoring condition numbers, and using reliable numerical libraries help reduce the risk of misleading conclusions.

8 Hands-on examples and workflows

8.1 Worked example: low-rank approximation

Consider a matrix \(A\) whose singular values decay quickly. Computing its SVD produces singular values \(\sigma_1,\sigma_2,\ldots\) and corresponding vectors. To form a rank-2 approximation, one constructs \[ A_2 = \sigma_1 u_1 v_1^T + \sigma_2 u_2 v_2^T. \]

One then evaluates approximation quality by computing \(\|A-A_2\|_F\) or by comparing \(\sigma_3\) to the leading values. If \(\sigma_3\) is much smaller than \(\sigma_1\) and \(\sigma_2\), the low-rank representation captures most structure.

This workflow is common in compressing images, summarizing correlated measurements, or modeling smooth patterns.

8.2 Worked example: least-squares via SVD

For a system \(Ax \approx b\), compute \(A=U\Sigma V^T\). The pseudoinverse solution is \[ x = V \Sigma^+ U^T b. \]

In implementation, \(\Sigma^+\) inverts only singular values above a chosen cutoff, while very small values may be left un-inverted to avoid noise amplification. After computing \(x\), one checks the residual \(\|Ax-b\|_2\) and, if needed, uses truncation to balance fit and stability.

This approach is often used when \(A\) is close to rank-deficient or when standard normal-equation methods are unreliable.

8.3 Practical guidance: selecting truncation parameters

A practical workflow for choosing a truncation rank or threshold includes:

  1. compute the singular values,
  2. inspect their decay and identify a knee point or gap,
  3. choose \(r\) (or a threshold \(\tau\)) based on desired error or stability,
  4. validate on held-out data for predictive tasks, or compare reconstruction error for descriptive tasks,
  5. document the cutoff rule, since results depend on it.

When singular values decay gradually, careful selection is more important because small changes in cutoff can alter the retained subspace.

9 Exercises and further reading

9.1 Suggested problem sets

A useful problem set typically includes:

  • verifying that eigenvalues of \(A^TA\) are squares of singular values of \(A\),
  • computing SVD for small matrices by hand and comparing with numerical results,
  • constructing truncated SVD approximations and measuring spectral/Frobenius errors,
  • solving least-squares problems and demonstrating the effect of truncation on stability,
  • exploring randomized SVD on synthetic low-rank matrices with controlled noise.

These exercises reinforce both the theoretical links and the practical considerations that drive correct usage.

9.2 Reference topics and standard texts

Further study often covers:

  • properties of matrix norms and unitarily invariant norms,
  • perturbation theory for singular values,
  • numerical linear algebra topics such as bidiagonalization and Golub–Kahan-type methods,
  • randomized numerical linear algebra and sketching theory,
  • and optimization or statistical interpretations connecting SVD to PCA and regularization methods.

Standard references in numerical linear algebra and applied matrix analysis provide background and proofs, while machine learning-oriented texts connect SVD to modern data workflows.