ZoomNotes for Linear Algebra

Part 7: Singular Values and Vectors: $Av = \sigma u$ and $A = U\Sigma V^T$

7.1 Singular Vectors in $U$, $V$ and Singular Values in $\Sigma$

The Singular Value Decomposition (SVD) exists for every matrix $A$ (size $m \times n$, any rank $r$):

$$A = U \Sigma V^T$$

Components:

• $U$: $m \times m$ orthogonal matrix. Columns are left singular vectors $u_1, \dots, u_m$ (span the column space and left nullspace)
• $V$: $n \times n$ orthogonal matrix. Columns are right singular vectors $v_1, \dots, v_n$ (span the row space and nullspace)
• $\Sigma$: $m \times n$ diagonal matrix with singular values $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0$ on the diagonal, and zeros elsewhere

Fundamental Equation:

$$A v_k = \sigma_k u_k \quad \text{for } k = 1, \dots, r$$

and for $k > r$, $A v_k = 0$ and $A^T u_k = 0$.

---

7.2 Reduced SVD / Full SVD / Construct $U\Sigma V^T$ from $A^T A$

Full SVD: $A = U_{m \times m} \Sigma_{m \times n} V_{n \times n}^T$

Reduced (Economy) SVD: $A = U_r \Sigma_r V_r^T$ where:

• $U_r$ is $m \times r$ (only the $r$ left singular vectors corresponding to nonzero singular values)
• $\Sigma_r$ is $r \times r$ diagonal
• $V_r$ is $n \times r$

Construction from $A^T A$:

1. Compute $A^T A$ (size $n \times n$), which is symmetric positive semidefinite
2. Find its eigenvalues $\sigma_1^2 \geq \sigma_2^2 \geq \cdots \geq \sigma_r^2 > 0$
3. The eigenvectors of $A^T A$ are the right singular vectors $v_1, \dots, v_r$
4. The singular values are $\sigma_k = \sqrt{\lambda_k(A^T A)}$
5. Compute the left singular vectors: $u_k = A v_k / \sigma_k$ for $k = 1, \dots, r$

Alternative from $AA^T$: Similarly, eigenvectors of $AA^T$ give the left singular vectors $u_k$ with the same eigenvalues $\sigma_k^2$.

---

7.3 The Geometry of the SVD: Rotate - Stretch - Rotate

The SVD reveals that every linear transformation decomposes into three geometric steps:

$$A = U \Sigma V^T$$

1. Rotate (or reflect) by $V^T$: $V^T$ maps the standard basis to the right singular vectors
2. Stretch by $\Sigma$: Scale each axis by $\sigma_k$ (and embed into $\mathbb{R}^m$ if $m \neq n$)
3. Rotate by $U$: Rotate from the stretched axes to the left singular vectors

Circle-to-Ellipse View: When $A$ is $2 \times 2$, the unit circle maps to an ellipse with semi-axes $\sigma_1 u_1$ and $\sigma_2 u_2$.

Four-Number SVD for 2x2: Any 2x2 matrix can be expressed as:

$$A = Q_\theta \, \Sigma \, Q_\phi$$

where $Q_\theta$ and $Q_\phi$ are rotation matrices by angles $\theta$ and $\phi$, and $\Sigma$ is diagonal with $\sigma_1, \sigma_2$.

---

7.4 $A_k$ is Closest to $A$: Principal Component Analysis (PCA)

Eckart-Young Theorem: The best rank-$k$ approximation to $A$ (in the Frobenius norm or spectral norm) is obtained by truncating the SVD:

$$A_k = U_k \Sigma_k V_k^T = \sum_{i=1}^k \sigma_i u_i v_i^T$$

where $U_k$, $V_k$ contain the first $k$ singular vectors, and $\Sigma_k$ contains the top $k$ singular values. This minimizes $\|A - B\|$ over all rank-$k$ matrices $B$.

PCA (Principal Component Analysis):

• Center the data: subtract the mean from each column of the data matrix $A$
• Compute the SVD of the centered data
• The first principal component $u_1$ is the direction of maximum variance
• The sample covariance matrix is $S = AA^T / (n-1)$
• Total variance = sum of eigenvalues of $S$ = $\sum \sigma_i^2$
• The fraction of variance captured by the first $k$ components is $(\sum_{i=1}^k \sigma_i^2) / (\sum_{i=1}^m \sigma_i^2)$

---

7.5 Computing Eigenvalues of $S$ and Singular Values of $A$

QR Algorithm (for eigenvalues):

1. Set $S_0 = S$ (symmetric)
2. For $k = 1, 2, \dots$:
   • Factor $S_{k-1} = Q_k R_k$
   • Set $S_k = R_k Q_k$
3. $S_k$ converges to a diagonal matrix containing the eigenvalues

The QR algorithm uses the fact that $S_k = Q_k^T S_{k-1} Q_k$, so all $S_k$ are similar and have the same eigenvalues.

Golub-Kahan Algorithm (for SVD): An efficient two-step process:

1. Reduce $A$ to bidiagonal form using Householder reflections
2. Apply an implicit QR iteration to the bidiagonal matrix to find the singular values

Modern numerical linear algebra computes SVD in $O(mn^2)$ or $O(m^2 n)$ operations.

---

7.6 Compressing Images by the SVD

An image can be represented as a matrix $A$ of pixel values. The SVD provides a natural compression scheme:

Truncated SVD Compression: Instead of storing all $m \times n$ entries, store only:

• $k$ singular values $\sigma_1, \dots, \sigma_k$
• $k$ left singular vectors $u_1, \dots, u_k$ (each length $m$)
• $k$ right singular vectors $v_1, \dots, v_k$ (each length $n$)

Total storage: $k(1 + m + n)$ instead of $mn$. When $k$ is small compared to the rank, this is a significant compression.

Example: A $1000 \times 1000$ image ($10^6$ pixels) might be well-approximated by $k=50$ singular values, storing only $50 \times (1 + 1000 + 1000) \approx 100,000$ numbers -- a 10x compression.

---

7.7 The Victory of Orthogonality

This chapter celebrates the fundamental role of orthogonality throughout linear algebra. Nine key properties:

1. $\|Qx\| = \|x\|$ -- Orthogonal matrices preserve length
2. Eigenvectors of symmetric matrices are orthogonal -- $S = Q\Lambda Q^T$
3. Singular vectors are orthogonal -- $A = U\Sigma V^T$ with $U^T U = I$, $V^T V = I$
4. Gram-Schmidt produces orthogonal bases from any independent set
5. Four fundamental subspaces come in orthogonal pairs -- Row space $\perp$ Nullspace, Column space $\perp$ Left nullspace
6. Fourier series uses orthogonal sines/cosines -- The Fourier basis is orthonormal
7. Projection matrices are symmetric and idempotent -- $P^T = P$, $P^2 = P$
8. Least squares minimizes error via orthogonality -- $A^T(b - A\hat{x}) = 0$
9. QR factorization combines Gram-Schmidt into matrix form

Polar Decomposition: Every matrix $A$ can be factored as:

$$A = Q S$$

where $Q$ is orthogonal and $S$ is symmetric positive semidefinite (or positive definite if $A$ is invertible). From the SVD: $Q = UV^T$ and $S = V\Sigma V^T$. This is the matrix analogue of $z = re^{i\theta}$ for complex numbers.