The Early History of the Singular Value Decomposition (1993)

Abstract: The Singular Value Decomposition (SVD) is often viewed as a modern tool of numerical linear algebra. However, its roots extend deep into the 19th century. This article traces the evolution of the SVD from its early theoretical foundations to its emergence as a computational powerhouse.

---

1. Introduction to the SVD

The Singular Value Decomposition is a fundamental matrix factorization. For any matrix $A \in \mathbb{R}^{m \times n}$, the SVD expresses the matrix as:

$\mathbf{A} = \mathbf{U} \mathbf{\Sigma} \mathbf{V}^T$

Where:

• $\mathbf{U}$ is an $m \times m$ orthogonal matrix (left singular vectors).
• $\mathbf{\Sigma}$ is an $m \times n$ diagonal matrix containing non-negative real numbers $\sigma_i$ (singular values).
• $\mathbf{V}$ is an $n \times n$ orthogonal matrix (right singular vectors).

Unlike the Eigen-decomposition, which requires a square matrix, the SVD is universal—it applies to any rectangular matrix.

---

2. The Theoretical Genesis (19th Century)

The SVD did not appear as a single "eureka" moment but evolved through the study of quadratic forms and symmetric matrices.

2.1 Early Contributions

In the mid-1800s, mathematicians were preoccupied with the properties of symmetric matrices. The realization that any symmetric matrix could be diagonalized laid the groundwork.

• The 2x2 Case: Early explorations (some attributed to Euler) dealt with simple $2 \times 2$ transformations.
• The Generalization: By the 1870s, mathematicians like Camille Jordan and Eugenio Beltrami began exploring the decomposition of general linear transformations.

2.2 The Shift in Perspective

Initially, the SVD was seen as a theoretical curiosity. The mathematical community focused on:

1. Finding exact roots of polynomials.
2. Understanding the geometry of linear mappings.
3. The relationship between a matrix $A$ and the symmetric matrices $AA^T$ and $A^TA$.

---

3. The Path to Modernity (1900–1936)

As the 20th century began, the focus shifted toward the approximation of matrices and the concept of "best fit."

3.1 The Schmidt Contribution

Around 1907, Erhard Schmidt provided a more rigorous framework for what we now call the SVD, particularly in the context of operator theory. He recognized that the singular values represented the "principal axes" of the transformation.

3.2 The Eckart-Young Theorem (1936)

The most pivotal moment for the utility of the SVD came in 1936. Carl Eckart and J.Y. Young proved that the SVD provides the optimal low-rank approximation of a matrix.

The Theorem states: To find the best rank-$k$ approximation $A_k$ of a matrix $A$ (minimizing the Frobenius norm $\|A - A_k\|_F$), one simply keeps the $k$ largest singular values and sets the rest to zero.

$\min_{\text{rank}(B)=k} \|A - B\|_F = \sqrt{\sum_{i=k+1}^{\min(m,n)} \sigma_i^2}$

---

4. The Computational Revolution (1960s–1990s)

For decades, the SVD was a "pencil and paper" theory because calculating it for large matrices was computationally prohibitive. This changed with the advent of digital computers.

4.1 The Golub-Kahan Algorithm

In 1965, Gene Golub and William Kahan developed a numerically stable algorithm to compute the SVD. Instead of forming $A^TA$ (which squares the condition number and loses precision), they used a two-step process:

1. Bidiagonalization: Reducing $A$ to a bidiagonal form using Householder reflections.
2. Iterative Diagonalization: Using a variation of the QR algorithm to find the singular values.

4.2 Comparison: SVD vs. Eigen-decomposition

---

5. Visualizing the Process

The following diagram illustrates the conceptual flow of the SVD transformation:

---

6. Implementation and Application

Today, the SVD is implemented in almost every scientific computing library. Below is a conceptual example of how it is invoked in modern python using numpy:

import numpy as np

# Define a rectangular matrix A
A = np.array([[1, 2], [3, 4], [5, 6]])

# Perform Singular Value Decomposition
U, Sigma_diag, VT = np.linalg.svd(A)

# Sigma_diag is returned as a 1D array of singular values
Sigma = np.zeros((A.shape[0], A.shape[1]))
Sigma[:len(Sigma_diag), :len(Sigma_diag)] = np.diag(Sigma_diag)

print("Singular Values:\n", Sigma_diag)

6.1 Key Milestones Checklist

• Theoretical foundation (Jordan/Beltrami)
• Formalization of operators (Schmidt)
• Low-rank approximation proof (Eckart-Young)
• Stable numerical algorithm (Golub-Kahan)
• Integration into software (LAPACK/MATLAB)

---

7. Conclusion

The journey of the SVD from a niche 19th-century mathematical curiosity to the backbone of modern data science is a testament to the synergy between pure mathematics and computational engineering. By providing a way to identify the "dominant" structures within data, the SVD enables everything from image compression to latent semantic analysis.

Figure 1: Geometric interpretation of SVD as a rotation, scaling, and second rotation.