\(\newcommand{\abs}[1]{\left\lvert#1\right\rvert}\) \(\newcommand{\norm}[1]{\left\lVert#1\right\rVert}\) \(\newcommand{\inner}[1]{\left\langle#1\right\rangle}\) \(\DeclareMathOperator*{\argmin}{arg\,min}\) \(\DeclareMathOperator*{\argmax}{arg\,max}\) \(\DeclareMathOperator*{\E}{\mathbb{E}}\) \(\DeclareMathOperator*{\V}{\mathbb{V}}\)
T
he decompositions that keep coming up in dimension reduction and spectral methods, together with the variational characterizations that connect them to optimization. Everything here is deterministic linear algebra.
Spectral Decomposition (Symmetric Matrices)
Let $A\in\mathbb{R}^{n\times n}$ be symmetric. Then $A$ admits the spectral decomposition
\[A = \sum_{i=1}^n \lambda_i v_i v_i^\top,\]where $\lambda_1\ge\cdots\ge\lambda_n$ are real eigenvalues and ${v_i}_{i=1}^n$ is an orthonormal basis of $\mathbb{R}^n$.
This is the decomposition behind PCA, covariance matrices, and quadratic forms.
Singular Value Decomposition (SVD)
For any matrix $A\in\mathbb{R}^{m\times n}$ with rank $r$,
\[A = \sum_{i=1}^r s_i\,u_i v_i^\top,\]where $s_1\ge\cdots\ge s_r>0$ are singular values, $u_i\in\mathbb{R}^m$ and $v_i\in\mathbb{R}^n$ are orthonormal vectors.
The singular values satisfy
\[s_i^2 = \lambda_i(A^\top A).\]Equivalently, $A = U\Sigma V^\top$, where $\Sigma=\mathrm{diag}(s_1,\ldots,s_r)$.
For symmetric positive semidefinite $A$, the SVD and the spectral decomposition coincide.
Courant-Fischer Min-Max Theorem
Let $A\in\mathbb{R}^{n\times n}$ be symmetric with eigenvalues $\lambda_1\ge\cdots\ge\lambda_n$.
The largest eigenvalue admits the variational characterization
\[\lambda_1 = \max_{\|z\|_2=1} z^\top A z.\]More generally, the $k$-th largest eigenvalue satisfies
\[\lambda_k = \min_{\dim(S)=n-k+1}\; \max_{z\in S,\ \|z\|_2=1} z^\top A z.\]Semidefinite Programming Formulation
An equivalent formulation of the top eigenvalue problem is the SDP
\[\max_{Z\succeq 0,\ \mathrm{tr}(Z)=1} \ \mathrm{tr}(AZ).\]The maximum is attained at $Z = v_1 v_1^\top$, which is why the two formulations agree. Adding an $\ell_1$ bound on the entries of $Z$ gives the standard convex relaxation of sparse PCA (d’Aspremont et al., 2007).
Eckart-Young-Mirsky Theorem
Let $A=\sum_{i=1}^r s_i u_i v_i^\top$ be the SVD of $A$. For any $k<r$, define the truncated SVD
\[A_k = \sum_{i=1}^k s_i u_i v_i^\top.\]Then $A_k$ solves
\[\min_{\mathrm{rank}(B)\le k} \|A-B\|_F \quad\text{and}\quad \min_{\mathrm{rank}(B)\le k} \|A-B\|_2.\]So the truncated SVD is the best rank-$k$ approximation in both norms at once.
Polar Decomposition
Any matrix $A\in\mathbb{R}^{m\times n}$ with $m\ge n$ admits the polar decomposition
\[A = QH,\]where $Q$ has orthonormal columns and
\[H = (A^\top A)^{1/2}\]is symmetric positive semidefinite.
The name comes from the complex case $z = e^{i\theta}r$: $Q$ plays the role of the phase and $H$ the role of the modulus.
QR Decomposition
For $A\in\mathbb{R}^{m\times n}$ with $m\ge n$, there exists a decomposition
\[A = QR,\]where $Q\in\mathbb{R}^{m\times n}$ has orthonormal columns and $R\in\mathbb{R}^{n\times n}$ is upper triangular.
QR is the standard route to least squares: solve $Rx = Q^\top b$ instead of forming $A^\top A$.
Schur Decomposition
For any square matrix $A\in\mathbb{R}^{n\times n}$, there exists a unitary matrix $Q\in\mathbb{C}^{n\times n}$ such that
\[A = QTQ^*,\]where $T$ is upper triangular with the eigenvalues of $A$ on its diagonal. If $A$ has complex eigenvalues, $Q$ and $T$ are complex. The real Schur form keeps $Q$ real orthogonal at the price of $2\times 2$ blocks on the diagonal of $T$, one for each complex-conjugate pair.
Schur is the stable replacement for an eigendecomposition when $A$ is not symmetric: it always exists and never needs an ill-conditioned eigenvector basis.
- The spectral decomposition needs symmetry; the SVD works for any matrix.
- Truncated SVD, PCA, and low-rank denoising are all Eckart-Young applied to a different matrix.
- Courant-Fischer and the SDP form turn eigenvalue problems into optimization problems, and that is where constraints like sparsity get added.