Singular Value Decomposition

Singular Value Decomposition
Georg-Johann · CC BY-SA 3.0 · source
Name	Singular Value Decomposition
Field	Linear algebra
Introduced	19th century
Notable	Eugenio Beltrami, Camille Jordan, James Joseph Sylvester

Singular Value Decomposition Singular Value Decomposition is a fundamental matrix factorization in linear algebra used across science and engineering. It expresses a matrix as a product of orthogonal (or unitary) operators and a diagonal matrix of singular values, underpinning techniques in statistics, signal processing, and numerical analysis. The decomposition has connections to work by mathematicians such as Eugenio Beltrami, Camille Jordan, James Joseph Sylvester, and later developments in computational methods by researchers associated with institutions like Bell Labs and IBM Research.

Definition and basic properties

For any m×n real or complex matrix A, there exist unitary or orthogonal matrices U and V and a diagonal matrix Σ such that A = U Σ V*, where V* denotes the conjugate transpose; this representation generalizes diagonalization results considered by Augustin-Louis Cauchy, Arthur Cayley, and Carl Friedrich Gauss. The diagonal entries of Σ, the singular values, are nonnegative and ordered, relating to eigenvalues of A*A and AA* studied in the context of spectral theory by figures like John von Neumann and Issai Schur. Uniqueness results tie to multiplicity properties investigated by Émile Picard and later formalized in texts influenced by David Hilbert and Erhard Schmidt. Orthogonal invariance links to results used in work at Princeton University and Harvard University in multivariate statistics by researchers such as Harold Hotelling.

Computation and algorithms

Numerical computation of the decomposition relies on algorithmic frameworks developed at institutions including Bell Labs, Courant Institute, and Los Alamos National Laboratory. Classical approaches use bidiagonalization via Householder transformations attributed to methods from John Householder, followed by iterative diagonalization using variants of the QR algorithm associated with John G. F. Francis and Nikolai Krylov techniques. Modern large-scale algorithms exploit randomized methods popularized by researchers at Massachusetts Institute of Technology and Stanford University, and parallel implementations optimized on hardware from Intel Corporation and NVIDIA Corporation. Software packages implementing robust routines include libraries originating at Netlib and commercial systems from MathWorks and IBM.

Mathematical theory and proofs

Proofs of existence and properties draw on spectral theory developed by David Hilbert and John von Neumann and matrix analysis consolidated by Roger A. Horn and Charles R. Johnson. The SVD can be constructed from eigen-decompositions of A*A and AA*, invoking variational characterizations such as the Courant–Fischer theorem connected to work by Richard Courant and Gustav Fischer. Perturbation bounds and inequalities involve contributions by Ky Fan, Marcel Riesz, and later refinements in matrix perturbation theory referenced in studies linked to Alfred Tarski and researchers at ETH Zurich. Compact operator theory on Hilbert spaces, developed in part by John von Neumann and Stefan Banach, provides infinite-dimensional generalizations and rigorous functional-analytic proofs.

Applications

SVD underlies principal component analysis in statistics advanced by Karl Pearson and Harold Hotelling, and it appears in signal processing systems designed at Bell Labs and used in technologies by AT&T. In machine learning, SVD is a foundation for latent semantic analysis in projects at Bellcore and for recommender systems adopted by firms such as Netflix; it also supports dimensionality reduction methods used at Google and Microsoft Research. In computational physics and engineering, SVD is used in model reduction workflows developed at NASA and Los Alamos National Laboratory, and in medical imaging techniques implemented at institutions like Mayo Clinic and Johns Hopkins University. SVD is central to image compression standards influenced by work at International Telecommunication Union and to control theory formulations studied at California Institute of Technology.

Numerical stability and conditioning

Conditioning of singular values is studied with tools from numerical analysis developed by Nicholas Higham and classical stability theory from Alan Turing and John von Neumann. Backward stability of SVD algorithms is a key result established in literature tied to Gene H. Golub and William Kahan, whose analyses informed high-performance libraries at Netlib and Lawrence Berkeley National Laboratory. Sensitivity of singular subspaces to perturbations involves Davis–Kahan theorems related to work by Chandler Davis and William Kahan and has practical implications for large-scale computations carried out on architectures by IBM and Intel.

Generalizations and related decompositions

Generalizations include the compact SVD used in functional analysis traced to Stefan Banach and operator theory, and tensor decompositions such as the higher-order SVD developed in multilinear algebra research at Rice University and University of California, Berkeley. Related matrix factorizations include the eigen-decomposition prominent in studies by Leonhard Euler and Joseph-Louis Lagrange, the polar decomposition linked to work by Adrien-Marie Legendre and Carl Gustav Jacob Jacobi, and QR and LU factorizations with algorithmic history at Bell Labs and Mathematica developers. Recent advances in randomized linear algebra and streaming algorithms are driven by research groups at Massachusetts Institute of Technology, Stanford University, and industrial labs like Google Research.

Category:Linear algebra