Lesson overview | Previous part | Next part

Matrix Norms and Condition Numbers: Part 10: Common Mistakes to Appendix I: Practice Problems and Solutions

10. Common Mistakes

---

11. Exercises

Exercise 1 * - Norm computation and verification

Let $A = \begin{pmatrix} 3 & 1 & 0 \\ 0 & 2 & -1 \\ 1 & 0 & 4 \end{pmatrix}$.

(a) Compute $\|A\|_F$ (Frobenius norm) by hand and verify using the SVD formula $\|A\|_F = \|\boldsymbol{\sigma}\|_2$.

(b) Compute $\|A\|_1$ (max absolute column sum) and $\|A\|_\infty$ (max absolute row sum). Verify $\|A^\top\|_1 = \|A\|_\infty$.

(c) Compute $\|A\|_2 = \sigma_1(A)$ numerically. Verify the inequalities $\|A\|_2 \leq \|A\|_F \leq \sqrt{3}\|A\|_2$.

(d) Compute $\|A\|_*$ (nuclear norm). Verify $\|A\|_* \leq \sqrt{3}\|A\|_F$ and $\|A\|_* \geq \|A\|_F$ (when checking your numbers!).

---

Exercise 2 * - Frobenius norm properties

(a) Prove that $\|A\|_F^2 = \operatorname{tr}(A^\top A)$.

(b) Show that the Frobenius inner product $\langle A, B\rangle_F = \operatorname{tr}(A^\top B)$ satisfies all inner product axioms.

(c) For $A = \mathbf{u}\mathbf{v}^\top$ (rank-1), show $\|A\|_F = \|\mathbf{u}\|_2\|\mathbf{v}\|_2 = \|A\|_2$. Verify numerically.

(d) Verify submultiplicativity $\|AB\|_F \leq \|A\|_F\|B\|_F$ for random matrices. Show it fails as equality for most pairs.

---

Exercise 3 * - Condition number analysis

(a) Construct a $3 \times 3$ matrix with condition number $\kappa_2 \approx 100$ and one with $\kappa_2 \approx 10^6$.

(b) For each matrix, solve $A\mathbf{x} = \mathbf{b}$ with $\mathbf{b} = A\mathbf{x}_0$ for known $\mathbf{x}_0 = [1,1,1]^\top$. Add noise $\delta\mathbf{b} = \epsilon \cdot \text{rand}$ with $\epsilon = 10^{-6}$. Measure the relative error $\|\hat{\mathbf{x}} - \mathbf{x}_0\| / \|\mathbf{x}_0\|$.

(c) Verify the bound: relative forward error $\leq \kappa(A) \cdot$ relative backward error.

(d) Apply Tikhonov regularization with $\lambda = 10^{-3}$ to the ill-conditioned matrix. Compute the new condition number and solution accuracy.

---

Exercise 4 ** - Nuclear norm and low-rank approximation

(a) Generate a random rank-3 matrix $A = UV^\top$ with $U \in \mathbb{R}^{8 \times 3}$, $V \in \mathbb{R}^{10 \times 3}$. Confirm $\|A\|_* = \sum_{i=1}^3 \sigma_i$ and $\operatorname{rank}(A) = 3$.

(b) Add Gaussian noise $E$ with $\|E\|_F = 0.1\|A\|_F$. Compute the best rank-$k$ approximations $\tilde{A}_k$ for $k = 1, 2, 3, 5, 8$. Plot $\|A - \tilde{A}_k\|_F$ vs $k$.

(c) Verify the Eckart-Young theorem: $\|A - \tilde{A}_k\|_F^2 = \sum_{i>k}\sigma_i^2$ and $\|A - \tilde{A}_k\|_2 = \sigma_{k+1}$.

(d) Implement the proximal operator for the nuclear norm (singular value soft-thresholding) and verify it on a $5 \times 5$ random matrix with threshold $\lambda = 2$.

---

Exercise 5 ** - Weyl's inequality and perturbation

(a) Verify Weyl's inequality: construct $A, E \in \mathbb{R}^{5 \times 5}$ and verify $|\sigma_i(A+E) - \sigma_i(A)| \leq \|E\|_2$ for all $i$.

(b) Show (numerically) that Weyl's bound is tight: construct $A$ and $E$ such that equality is achieved for $i=1$.

(c) For a non-symmetric matrix $A$, compute eigenvalues of $A + E$ for several random perturbations $\|E\|_2 = \epsilon$. Compare the eigenvalue scatter to the singular value scatter - demonstrate that eigenvalues of non-normal matrices are more sensitive.

(d) Bauer-Fike: compute $\kappa_2(P)$ where $P$ is the eigenvector matrix of your non-symmetric $A$. Verify the bound $\min_j|\tilde{\lambda} - \lambda_j| \leq \kappa_2(P)\|E\|_2$.

---

Exercise 6 ** - Dual norms and optimization

(a) Verify the duality $\|A\|_* = \max_{\|B\|_2 \leq 1}\operatorname{tr}(A^\top B)$ numerically for a random $4 \times 4$ matrix.

(b) The dual of $\|A\|_F$ is itself. Verify: $\|A\|_F = \max_{\|B\|_F \leq 1}\operatorname{tr}(A^\top B)$.

(c) The Ky Fan $k$-norm has a variational formula: $\|A\|_{(k)} = \max_{U_k, V_k \text{ orthonormal}}\operatorname{tr}(U_k^\top A V_k)$. Verify for $k=2$ on a $5 \times 5$ matrix.

(d) Write the subgradient of $\|A\|_*$ at a rank-2 matrix $A = \mathbf{u}_1\mathbf{v}_1^\top + \mathbf{u}_2\mathbf{v}_2^\top$. Verify it numerically by finite differences.

---

Exercise 7 *** - Spectral normalization for neural networks

Implement spectral normalization for a simple 2-layer network on a toy binary classification problem.

(a) Implement power iteration to estimate $\sigma_1(W)$ for a weight matrix. Compare to np.linalg.svd(W)[1][0]. Measure convergence rate.

(b) Train a 2-layer network with and without spectral normalization on a toy dataset. Track $\|W_l\|_2$ during training.

(c) Estimate the Lipschitz constant $\prod_l \|W_l\|_2$ during training. Compare the two settings.

(d) Demonstrate that spectral normalization stabilizes training: use a larger learning rate that causes instability without SN but converges with SN.

---

Exercise 8 *** - Implicit regularization in matrix factorization

(a) Solve $\min_{U,V} \|UV^\top - A\|_F^2$ for a random $6 \times 6$ matrix $A$ with gradient flow (small step gradient descent). Initialize $U, V$ close to zero.

(b) Track $\|UV^\top\|_*$ during optimization. Compare to the minimum nuclear norm completion $\min\{\|X\|_* : X = A\}$ (which equals $\|A\|_*$ if $A$ is full rank).

(c) Now let $A$ be rank-2. Show that gradient flow recovers the rank-2 structure even without explicit rank regularization: plot the singular values of $UV^\top$ over iterations.

(d) Compare the implicit nuclear norm regularization of matrix factorization to explicit nuclear norm minimization using the proximal gradient method (from Exercise 4(d)). Which finds a solution faster? Which has smaller $\|X\|_*$?

---

12. Why This Matters for AI (2026 Perspective)

---

13. Conceptual Bridge

Matrix norms are the measuring instruments of linear algebra. Without them, we cannot quantify stability, sensitivity, approximation quality, or regularization strength. Every major result in numerical linear algebra - condition number theory, perturbation bounds, error analysis - is stated in terms of matrix norms. And in machine learning, norms appear at every level: they define regularizers, measure approximation error, bound generalization, and determine convergence rates.

What came before. This section builds on the SVD (-> Singular Value Decomposition), which provides the singular values that define the spectral, Frobenius, nuclear, and Schatten norms. It uses eigenvalue theory (-> Eigenvalues and Eigenvectors) for the spectral norm of symmetric PSD matrices and for condition number of symmetric positive definite systems. It uses orthogonality (-> Orthogonality) for the unitary invariance of Schatten norms.

What comes after. Condition number analysis is essential for numerical methods in the next chapter. Matrix norm theory enables gradient analysis in optimization (-> Chapter 8: Optimization). The nuclear norm and low-rank regularization connect directly to dimensionality reduction (-> PCA) and the mathematical foundations of LoRA and other PEFT methods in the models chapters. Perturbation theory connects to the stability analysis of RNNs and LSTMs (-> RNN and LSTM Math).

MATRIX NORMS IN THE CURRICULUM
========================================================================

  02-Linear-Algebra-Basics              03-Advanced-Linear-Algebra
  -----------------------               ----------------------------

  +----------------------+             +-------------------------------+
  | 05-Matrix-Rank       |  ->  rank    | 01-Eigenvalues-Eigenvectors   |
  | 04-Determinants      |  ->  det     | 02-SVD  --+                   |
  +----------------------+             |           | singular values   |
                                       |           down                   |
                                       | +-------------------------+  |
                                       | |  06-Matrix-Norms  *     |  |
                                       | |                         |  |
                                       | |  - Frobenius (F-norm)   |  |
                                       | |  - Spectral (\sigma_1)        |  |
                                       | |  - Nuclear (\Sigma\sigma^i)        |  |
                                       | |  - Schatten (ell^p of \sigma)  |  |
                                       | |  - Condition number     |  |
                                       | |  - Perturbation theory  |  |
                                       | +-------------+-----------+  |
                                       |               |               |
                                       |               down               |
                                       | 07-Linear-Transformations     |
                                       | 08-Matrix-Decompositions      |
                                       +-------------------------------+
                                                       |
                                     +-----------------+----------------+
                                     down                 down                down
                              08-Optimization    ML-Applications    14-Specific
                              (gradient flow,   (LoRA, spectral    (RNN stability,
                               convergence)      normalization,     attention rank,
                                                 PAC-Bayes)        MLA compression)

========================================================================

The key insight unifying this section: matrix norms reduce questions about linear operators to scalar quantities. The spectral norm reduces Lipschitz analysis to a number. The nuclear norm reduces rank minimization to a convex program. The condition number reduces numerical stability to a ratio. This reduction from functional complexity to scalar measurement is the fundamental technical move that makes both theory and computation tractable.

---

Appendix A: Proofs and Derivations

A.1 Proof that $\|A\|_F = \sqrt{\operatorname{tr}(A^\top A)}$

Let $A \in \mathbb{R}^{m \times n}$. The $(j,k)$-entry of $A^\top A$ is:

$$(A^\top A)_{jk} = \sum_i (A^\top)_{ji} A_{ik} = \sum_i A_{ij} A_{ik}$$

The trace sums the diagonal ($j = k$):

$$\operatorname{tr}(A^\top A) = \sum_j (A^\top A)_{jj} = \sum_j \sum_i A_{ij}^2 = \sum_{i,j} a_{ij}^2 = \|A\|_F^2 \qquad \square$$

Corollary. For any unitary $U \in \mathbb{R}^{m \times m}$ and $V \in \mathbb{R}^{n \times n}$:

$$\|UAV\|_F^2 = \operatorname{tr}((UAV)^\top (UAV)) = \operatorname{tr}(V^\top A^\top U^\top UAV) = \operatorname{tr}(V^\top A^\top AV) = \operatorname{tr}(A^\top A) = \|A\|_F^2$$

using $U^\top U = I$ and cyclic invariance of the trace $\operatorname{tr}(VXV^\top) = \operatorname{tr}(X)$.

A.2 Proof of Submultiplicativity of the Frobenius Norm

We prove $\|AB\|_F \leq \|A\|_F \|B\|_F$.

Let $A \in \mathbb{R}^{m \times p}$ and $B \in \mathbb{R}^{p \times n}$. Denote the rows of $A$ as $\mathbf{a}_i^\top$ and columns of $B$ as $\mathbf{b}_j$. Then $(AB)_{ij} = \mathbf{a}_i^\top \mathbf{b}_j$.

By Cauchy-Schwarz: $|(AB)_{ij}|^2 \leq \|\mathbf{a}_i\|_2^2 \|\mathbf{b}_j\|_2^2$. Summing over all $i,j$:

$$\|AB\|_F^2 = \sum_{i,j} |(AB)_{ij}|^2 \leq \sum_{i,j} \|\mathbf{a}_i\|^2 \|\mathbf{b}_j\|^2 = \left(\sum_i \|\mathbf{a}_i\|^2\right)\left(\sum_j \|\mathbf{b}_j\|^2\right) = \|A\|_F^2 \|B\|_F^2 \qquad \square$$

A.3 Proof that the Matrix 1-Norm Equals Maximum Column Sum

Claim. $\|A\|_{1 \to 1} = \max_j \sum_i |a_{ij}|$.

Upper bound. For $\|\mathbf{x}\|_1 = 1$:

$$\|A\mathbf{x}\|_1 = \left\|\sum_j x_j \mathbf{a}_j\right\|_1 \leq \sum_j |x_j| \|\mathbf{a}_j\|_1 \leq \max_j \|\mathbf{a}_j\|_1 \cdot \sum_j |x_j| = \max_j \|\mathbf{a}_j\|_1$$

Attainment. Let $j^* = \arg\max_j \|\mathbf{a}_{j}\|_1$. Set $\mathbf{x} = \mathbf{e}_{j^*}$. Then $A\mathbf{x} = \mathbf{a}_{j^*}$, so $\|A\mathbf{x}\|_1 = \max_j\|\mathbf{a}_j\|_1$. $\square$

A.4 Proof of Weyl's Inequality

Theorem. For $A, E \in \mathbb{R}^{m \times n}$ with $m \geq n$, and all $i = 1, \ldots, n$:

$$|\sigma_i(A+E) - \sigma_i(A)| \leq \sigma_1(E) = \|E\|_2$$

Proof using the minimax characterization. By Courant-Fischer:

$$\sigma_i(A) = \min_{\substack{S \subseteq \mathbb{R}^n \\ \dim S = n-i+1}} \max_{\mathbf{x} \in S, \|\mathbf{x}\|=1} \|A\mathbf{x}\|$$

Let $S^*$ achieve the minimax for $\sigma_i(A)$. Then:

$$\sigma_i(A+E) \leq \max_{\mathbf{x} \in S^*, \|\mathbf{x}\|=1} \|(A+E)\mathbf{x}\| \leq \max_{\mathbf{x} \in S^*, \|\mathbf{x}\|=1} \left(\|A\mathbf{x}\| + \|E\mathbf{x}\|\right) \leq \sigma_i(A) + \|E\|_2$$

By symmetry (apply to $A+E$ with perturbation $-E$): $\sigma_i(A) \leq \sigma_i(A+E) + \|E\|_2$.

Combining both inequalities: $|\sigma_i(A+E) - \sigma_i(A)| \leq \|E\|_2$. $\square$

A.5 Proof that the Nuclear Norm is Dual to the Spectral Norm

Claim. $\|A\|_* = \max_{\|B\|_2 \leq 1} \operatorname{tr}(A^\top B)$.

Achieving the bound. Let $A = U\Sigma V^\top$ and set $B = UV^\top$. Then $\|B\|_2 = 1$ (product of unitary-like matrices with unit singular values) and:

$$\operatorname{tr}(A^\top B) = \operatorname{tr}(V\Sigma U^\top \cdot UV^\top) = \operatorname{tr}(V\Sigma V^\top) = \operatorname{tr}(\Sigma) = \sum_i \sigma_i = \|A\|_*$$

Upper bound for any $\|B\|_2 \leq 1$. By the Von Neumann trace inequality:

$$|\operatorname{tr}(A^\top B)| \leq \sum_i \sigma_i(A)\sigma_i(B) \leq \sum_i \sigma_i(A) \cdot 1 = \|A\|_*$$

(since $\sigma_i(B) \leq \|B\|_2 \leq 1$). Therefore $\max_{\|B\|_2\leq 1}\operatorname{tr}(A^\top B) = \|A\|_*$. $\square$

---

Appendix B: Advanced Topics

B.1 The Von Neumann Trace Inequality

A fundamental result connecting norms to the trace:

Theorem (Von Neumann, 1937). For $A, B \in \mathbb{R}^{m \times n}$:

$$|\operatorname{tr}(A^\top B)| \leq \sum_{i=1}^{\min(m,n)} \sigma_i(A)\sigma_i(B)$$

with equality when $A$ and $B$ share the same left and right singular vectors (i.e., $A$ and $B$ are simultaneously diagonalizable in the SVD sense).

Consequences:

1. Nuclear-spectral Holder: $|\langle A,B\rangle_F| \leq \|A\|_*\|B\|_2$
2. Cauchy-Schwarz (Frobenius): $|\langle A,B\rangle_F| \leq \|A\|_F\|B\|_F$ (using $\sigma_i(A)\sigma_i(B) \leq (\sigma_i(A)^2+\sigma_i(B)^2)/2$)
3. Duality: $\|A\|_* = \max_{\|B\|_2\leq 1}\operatorname{tr}(A^\top B)$ (proved in A.5 using this inequality)

For AI: This inequality bounds approximation errors in attention: $|\operatorname{tr}(\hat{S}^\top V^\top V)| \leq \|\hat{S}\|_* \|V\|_2^2$, connecting attention approximation quality to the nuclear norm of the approximate attention matrix.

B.2 Pseudo-Spectrum and Non-Normal Matrices

For a non-normal matrix $A$ ($AA^\top \neq A^\top A$), eigenvalues can be extremely sensitive to perturbation even when the matrix has bounded spectral norm. The $\epsilon$-pseudo-spectrum reveals this sensitivity:

$$\Lambda_\epsilon(A) = \{\lambda \in \mathbb{C} : \sigma_{\min}(A - \lambda I) \leq \epsilon\} = \{z : \|(A - zI)^{-1}\|_2 \geq \epsilon^{-1}\}$$

This is the set of complex numbers that are eigenvalues of some perturbation $A + E$ with $\|E\|_2 \leq \epsilon$.

Normal vs. non-normal. For normal matrices ($A^\top A = AA^\top$), $\Lambda_\epsilon(A) = \bigcup_j D(\lambda_j, \epsilon)$ - just disks of radius $\epsilon$ around each eigenvalue. For non-normal matrices, the pseudo-spectrum can extend far beyond these disks.

Example: Jordan block. $A = \begin{pmatrix}0&1\\0&0\end{pmatrix}$ has eigenvalue $0$ with multiplicity 2. Yet $\Lambda_\epsilon(A) \supset \{|z| < \sqrt{\epsilon}\}$ - a disk of radius $\sqrt{\epsilon}$, much larger than $\epsilon$ for small $\epsilon$.

For AI: Non-normal recurrent weight matrices $W_{hh}$ in RNNs can transiently amplify signals even when $\|W_{hh}\|_2 < 1$. The pseudo-spectrum shows why the simple criterion "$\|W_{hh}\|_2 < 1$ implies stability" is insufficient - transient growth can lead to effective instability in finite-depth computations (finite unrolling of time steps).

B.3 Stable Rank and Generalization

The stable rank of $A$ is:

$$\rho(A) = \frac{\|A\|_F^2}{\|A\|_2^2} = \frac{\sum_i \sigma_i^2}{\sigma_1^2} = \sum_i \left(\frac{\sigma_i}{\sigma_1}\right)^2$$

Properties:

• $1 \leq \rho(A) \leq \operatorname{rank}(A)$
• $\rho(A) = 1$ iff $A$ is rank-1
• $\rho(A) = r$ iff $A$ has $r$ equal nonzero singular values (flat singular value spectrum)
• $\rho(A)$ is continuous in $A$ (unlike rank, which is discontinuous)

Generalization bound. For a linear predictor $\mathbf{f}(\mathbf{x}) = W\mathbf{x}$ learned from $n$ samples:

$$\text{Generalization gap} \leq O\left(\sqrt{\frac{\rho(W)\|W\|_2^2}{n}}\right) = O\left(\sqrt{\frac{\|W\|_F^2}{n}}\right)$$

This shows that the Frobenius norm (not rank) controls generalization for linear models - justifying Frobenius regularization (weight decay).

For deep networks. Bartlett et al. (2017) proved:

$$\text{Generalization gap} \leq O\left(\frac{\prod_l \|W_l\|_2 \cdot \sqrt{\sum_l \rho(W_l)}}{\gamma\sqrt{n}}\right)$$

where $\gamma$ is the margin. The stable rank $\rho(W_l)$ of each layer's weight matrix appears, not its true rank.

B.4 Matrix Norms in Optimization: Proximal Methods

Many regularized optimization problems of the form:

$$\min_W \mathcal{L}(W) + \lambda R(W)$$

can be solved with proximal gradient descent:

$$W^{(t+1)} = \operatorname{prox}_{\alpha\lambda R}(W^{(t)} - \alpha \nabla \mathcal{L}(W^{(t)}))$$

The proximal operator $\operatorname{prox}_{\tau R}(V) = \arg\min_W \frac{1}{2}\|W-V\|_F^2 + \tau R(W)$ depends on the choice of $R$:

For AI: The proximal operator for nuclear norm regularization is singular value soft-thresholding (SVT), the key subroutine in matrix completion algorithms (Cai-Candes-Shen, 2010). Modern deep learning rarely uses explicit nuclear norm regularization because the factored parameterization in LoRA provides implicit nuclear norm regularization via the dynamics of gradient descent on $\min_{B,A}\mathcal{L}(W_0+BA)$.

B.5 Norm Balls and Geometry

The geometry of norm balls illuminates the differences between norms.

UNIT BALLS IN 2D (for matrix norms, visualized on singular value vectors)
========================================================================

  Spectral (ell\infty on \sigma)    Frobenius (ell^2 on \sigma)   Nuclear (ell^1 on \sigma)

    \sigma_2                     \sigma_2                     \sigma_2
    |                      |                      |
  1-+-------+            1-+    +---+           1-+
    |       |              |   /   \              |\
    |       |              |  |     |             |  \
    |       |              |  |     |             |    \
  --+-------+--\sigma_1       --+--+-----+--\sigma_1      --+-----+--\sigma_1
    |       1              |        1             |     1
    |                      |                      |
    + square               + circle               + diamond

  All \sigma \leq 1               \sigma_1^2+\sigma_2^2 \leq 1          \sigma_1+\sigma_2 \leq 1

========================================================================

The nuclear norm ball is a polytope in singular value space (it's the $\ell^1$ ball), making nuclear norm minimization a linear program in singular value space - hence solvable efficiently.

The spectral norm ball is a hypercube in singular value space ($\ell^\infty$ ball), with flat faces. This geometry means that spectral norm projection (projecting onto $\|W\|_2 \leq 1$) simply caps all singular values at 1.

For AI: The different geometries explain why nuclear norm regularization promotes low-rank solutions (the corners of the $\ell^1$ diamond are at axis-aligned points = rank-1 matrices) while Frobenius regularization does not (the smooth $\ell^2$ ball has no corners to attract the solution toward).

---

Appendix C: Computational Reference

C.1 NumPy/SciPy Norm API

import numpy as np
import scipy.linalg as la

A = np.random.randn(4, 5)   # example matrix

# Frobenius norm
np.linalg.norm(A, 'fro')           # direct
np.sqrt(np.sum(A**2))              # elementwise
np.sqrt(np.trace(A.T @ A))        # trace formula

# Spectral norm = sigma_1
np.linalg.norm(A, 2)               # direct (uses SVD internally)
la.svdvals(A)[0]                   # explicit first singular value

# Nuclear norm = sum of singular values
np.linalg.norm(A, 'nuc')           # direct
np.sum(la.svdvals(A))              # explicit sum

# Matrix 1-norm = max absolute column sum
np.linalg.norm(A, 1)               # induced 1-norm

# Matrix infinity-norm = max absolute row sum
np.linalg.norm(A, np.inf)          # induced inf-norm

# Condition number
np.linalg.cond(A)                  # spectral: sigma_1 / sigma_n
np.linalg.cond(A, 'fro')          # Frobenius-based
np.linalg.cond(A, 1)              # 1-norm condition number

C.2 Power Iteration for Spectral Norm

def spectral_norm_power_iter(A, n_iter=20, seed=42):
    """Estimate ||A||_2 = sigma_1(A) via power iteration."""
    rng = np.random.default_rng(seed)
    v = rng.standard_normal(A.shape[1])
    v /= np.linalg.norm(v)

    for _ in range(n_iter):
        u = A @ v;  u /= np.linalg.norm(u)
        v = A.T @ u
        sigma = np.linalg.norm(v)
        v /= sigma

    return sigma   # converges at rate (sigma_2 / sigma_1)^(2*n_iter)

This is used in spectral normalization: one step per training iteration is enough (the estimate from the previous step is a warm start).

C.3 Singular Value Soft-Thresholding

def svt(A, threshold):
    """Proximal operator of threshold * ||.||_* applied to A."""
    U, s, Vt = np.linalg.svd(A, full_matrices=False)
    s_thresh = np.maximum(s - threshold, 0)
    return U @ np.diag(s_thresh) @ Vt

# Returns argmin_X  (1/2)||X - A||_F^2 + threshold * ||X||_*
# Singular values below threshold are zeroed -> rank reduction

C.4 Stable Rank

def stable_rank(A):
    """Stable rank rho(A) = ||A||_F^2 / ||A||_2^2."""
    s = np.linalg.svd(A, compute_uv=False)
    return np.sum(s**2) / s[0]**2

# Always in [1, rank(A)]
# = 1 iff rank-1; = rank(A) iff flat singular value spectrum

C.5 Tikhonov Solution via SVD

def tikhonov_svd(A, b, lam):
    """Tikhonov-regularized least squares: min ||Ax-b||^2 + lam||x||^2.
    Uses SVD for numerical stability even when A is near-singular."""
    U, s, Vt = np.linalg.svd(A, full_matrices=False)
    d = s / (s**2 + lam)     # modified singular value filter
    return Vt.T @ (d * (U.T @ b))

# Condition number of regularized system: (s[0]^2 + lam) / (s[-1]^2 + lam)

---

Appendix D: Extended Examples and Worked Problems

D.1 A Complete Norm Taxonomy on One Matrix

Let $A = \begin{pmatrix} 4 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix}$ (diagonal with singular values $\sigma_1=4, \sigma_2=2, \sigma_3=1$).

All norms in one place:

Ordering verification: $\|A\|_2 = 4 \leq \|A\|_F \approx 4.58 \leq \|A\|_* = 7$ OK

For rank-$r$ bounds: $\|A\|_F \leq \sqrt{3}\|A\|_2$ gives $4.58 \leq 6.93$ OK and $\|A\|_* \leq \sqrt{3}\|A\|_F$ gives $7 \leq 7.94$ OK.

D.2 Worked Example: Spectral Norm via Power Iteration

Let $A = \begin{pmatrix} 3 & 1 \\ 2 & 4 \end{pmatrix}$.

Exact: The singular values satisfy $\sigma^2 = \text{eigenvalues of } A^\top A = \begin{pmatrix}13&11\\11&17\end{pmatrix}$.

$\text{tr}(A^\top A) = 30$, $\det(A^\top A) = 13\cdot17 - 121 = 221 - 121 = 100$.

Eigenvalues: $\lambda = (30 \pm \sqrt{900 - 400})/2 = (30 \pm \sqrt{500})/2 = 15 \pm 5\sqrt{5}$.

So $\sigma_1 = \sqrt{15 + 5\sqrt{5}} \approx \sqrt{26.18} \approx 5.12$ and $\|A\|_2 \approx 5.12$.

Power iteration (starting with $\mathbf{v}_0 = (1,0)^\top$):

Converging to $\sigma_1 \approx 5.12$ (the remaining gap is because we stopped early).

For AI: This is exactly how PyTorch implements torch.nn.utils.spectral_norm - one step of power iteration per training step, with the previous estimate $\mathbf{v}$ stored as a buffer.

D.3 Worked Example: Condition Number and Error Amplification

Consider the Hilbert matrix $H_n$ with $(H_n)_{ij} = 1/(i+j-1)$ - a canonical example of an ill-conditioned matrix.

For $n = 5$:

$$H_5 = \begin{pmatrix} 1 & 1/2 & 1/3 & 1/4 & 1/5 \\ 1/2 & 1/3 & 1/4 & 1/5 & 1/6 \\ 1/3 & 1/4 & 1/5 & 1/6 & 1/7 \\ 1/4 & 1/5 & 1/6 & 1/7 & 1/8 \\ 1/5 & 1/6 & 1/7 & 1/8 & 1/9 \end{pmatrix}$$

The condition number grows as $\kappa_2(H_n) \approx e^{3.5n}$:

• $\kappa_2(H_5) \approx 4.77 \times 10^5$
• $\kappa_2(H_{10}) \approx 1.60 \times 10^{13}$
• $\kappa_2(H_{12}) \approx 1.83 \times 10^{16}$ (at the limit of double precision!)

Error analysis. Solve $H_5 \mathbf{x} = \mathbf{b}$ where $\mathbf{b} = H_5 \mathbf{1}$ (exact solution $\mathbf{x}_0 = (1,1,1,1,1)^\top$). With $\mathbf{b}$ perturbed by machine epsilon $\epsilon \approx 10^{-16}$:

Relative forward error $\leq \kappa(H_5) \cdot 10^{-16} \approx 4.77 \times 10^5 \cdot 10^{-16} \approx 5 \times 10^{-11}$

So we lose about 5 decimal places of precision. For $H_{10}$, we'd lose 13 places - near total loss of information.

Tikhonov fix: With $\lambda = 10^{-5}$, $\kappa(H_5 + \lambda I) \approx 8 \times 10^4$ - a 6\times improvement at the cost of introducing systematic bias $\approx \lambda\|\mathbf{x}\|$.

D.4 The Spectral Norm of the Attention Matrix

In a transformer with sequence length $T = 512$, dimension $d_k = 64$, and queries and keys drawn from a standard Gaussian:

Expected spectral norm. For $Q, K \in \mathbb{R}^{T \times d_k}$ with i.i.d. $\mathcal{N}(0, 1/d_k)$ entries:

$$\mathbb{E}[\|QK^\top\|_2] \approx \frac{T + d_k}{d_k/T + 1} \cdot \frac{\sigma^2}{d_k}$$

More concretely, by random matrix theory (Marchenko-Pastur law), $\|QK^\top\|_2 \approx 2\sqrt{Td_k}/d_k \cdot \sqrt{d_k} = 2\sqrt{T}$.

The factor $1/\sqrt{d_k}$ in attention ($\text{softmax}(QK^\top/\sqrt{d_k})$) is a spectral normalization: it scales the attention logits so that $\|QK^\top/\sqrt{d_k}\|_2 \approx 2\sqrt{T/d_k}$ - preventing the softmax from collapsing to one-hot distributions when $T \gg d_k$.

Nuclear norm and attention rank. In trained models, attention matrices exhibit low stable rank. Dong et al. (2021) measured stable rank $\rho(A) = \|A\|_F^2/\|A\|_2^2$ averaging 4-8 in BERT's attention heads (out of possible 512), suggesting the effective attention rank is much lower than the sequence length.

D.5 LoRA Norm Analysis

LoRA fine-tuning adds $\Delta W = BA$ with $B \in \mathbb{R}^{d \times r}$, $A \in \mathbb{R}^{r \times d}$, typically $r \in \{4, 8, 16, 32\}$ vs. $d \in \{768, 1024, 4096\}$.

Norm bounds on $\Delta W$:

• $\|\Delta W\|_F = \|BA\|_F \leq \|B\|_F\|A\|_F$ (submultiplicativity)
• $\|\Delta W\|_2 = \|BA\|_2 \leq \|B\|_2\|A\|_2$
• $\|\Delta W\|_* = \|BA\|_* \leq \min(\|B\|_*\|A\|_2, \|B\|_2\|A\|_*)$

Implicit nuclear norm regularization. The factored parameterization $\Delta W = BA$ has at most $r$ nonzero singular values (since $\text{rank}(BA) \leq r$). The nuclear norm $\|BA\|_* = \sum_{i=1}^r \sigma_i(BA)$ is automatically bounded by:

$$\|BA\|_* \leq \sqrt{r}\|BA\|_F \leq \sqrt{r}\|B\|_F\|A\|_F$$

During optimization, gradient descent on $\min_{B,A}\mathcal{L}(W_0+BA)$ implicitly minimizes $\|BA\|_*$ - this is the Gunasekar et al. (2017) implicit regularization result.

DoRA (weight decomposition). DoRA (Liu et al., 2024) reparameterizes as $W = m\cdot(V+BA)/\|V+BA\|_{col}$ where $m$ controls the magnitude and $V+BA/\|...\|$ controls the direction. The column-wise normalization is related to the nuclear norm: $\|W\|_*$ is invariant to column-wise rescaling.

D.6 Gradient Flow and Norm Dynamics

During training, norms of weight matrices evolve. Understanding this evolution helps diagnose training pathologies.

Stable training. For a well-trained transformer layer with weight matrix $W \in \mathbb{R}^{4096 \times 4096}$:

• $\|W\|_2 \approx 1-5$ (spectral norm; bounded by weight decay + gradient clipping)
• $\|W\|_F \approx 30-100$ (Frobenius norm; $\approx \sqrt{d}\|W\|_2$ for flat spectrum)
• $\kappa(W) \approx 10^2-10^4$ (condition number; not too large for well-initialized models)
• $\rho(W) \approx 100-500$ (stable rank; much less than 4096)

Warning signs:

• $\|W\|_2$ growing rapidly -> potential gradient explosion; increase weight decay
• $\|W\|_2 \to 0$ -> vanishing gradients or overly aggressive weight decay
• $\kappa(W) \to 10^6$ -> poorly conditioned optimization; consider preconditioning
• $\rho(W) \to 1$ -> the layer is becoming rank-1 (mode collapse); increase model capacity

D.7 Norm-Based Pruning

Neural network pruning can be guided by matrix norms:

Magnitude pruning (Frobenius). Remove weight matrices (or rows/columns) with smallest Frobenius norm. The remaining error $\|W_{\text{pruned}} - W\|_F$ equals the Frobenius norm of the pruned components.

Spectral pruning. Prune singular value components below a threshold $\tau$: $\hat{W} = \sum_{\sigma_i > \tau} \sigma_i \mathbf{u}_i\mathbf{v}_i^\top$. Error: $\|W - \hat{W}\|_2 = \sigma_{k+1}$ (spectral) and $\|W-\hat{W}\|_F = \sqrt{\sum_{i>k}\sigma_i^2}$ (Frobenius).

Nuclear norm pruning. Regularize the fine-tuned model with $\lambda\|\Delta W\|_*$ during training, encouraging the weight update to use fewer singular value "directions." After training, prune near-zero singular values.

Comparison:

---

<- Back to Advanced Linear Algebra | Next: Linear Transformations ->

Appendix E: Connections to Other Fields

E.1 Matrix Norms in Statistics

Matrix norms appear throughout multivariate statistics.

Covariance matrices. For a sample covariance matrix $\hat{\Sigma} = \frac{1}{n}X^\top X$ (where $X \in \mathbb{R}^{n \times p}$):

• $\|\hat{\Sigma}\|_2 = \lambda_{\max}(\hat{\Sigma})$: the variance in the direction of maximum spread (principal component 1)
• $\|\hat{\Sigma}\|_*= \operatorname{tr}(\hat{\Sigma}) = \sum_j \hat{\sigma}_j^2$: total variance
• $\kappa(\hat{\Sigma}) = \lambda_{\max}/\lambda_{\min}$: measures how "spherical" the distribution is

Condition number and regression. For linear regression $\mathbf{y} = X\boldsymbol{\beta} + \boldsymbol{\epsilon}$:

$$\kappa(X^\top X) = \frac{\lambda_{\max}(X^\top X)}{\lambda_{\min}(X^\top X)} = \frac{\sigma_1(X)^2}{\sigma_p(X)^2} = \kappa(X)^2$$

Multicollinearity in $X$ gives large $\kappa(X^\top X)$, making OLS estimates numerically unstable. Ridge regression adds $\lambda I$ to improve conditioning: $\kappa((X^\top X + \lambda I)) = (\sigma_1^2 + \lambda)/(\sigma_p^2 + \lambda)$.

PCA error bounds. Truncating PCA at $k$ components introduces Frobenius error $\sqrt{\sum_{i>k}\lambda_i}$ where $\lambda_i$ are eigenvalues of $\hat{\Sigma}$. This is exactly the Eckart-Young theorem applied to the covariance matrix.

Sample covariance concentration. For $n$ samples from $\mathcal{N}(0, \Sigma)$:

$$\mathbb{E}\|\hat{\Sigma} - \Sigma\|_2 \lesssim \|\Sigma\|_2 \sqrt{\frac{p}{n}} \quad (p \leq n)$$

The spectral norm of the estimation error scales as $\|\Sigma\|_2\sqrt{p/n}$ - one needs $n \gg p$ samples to estimate $\Sigma$ well in spectral norm.

E.2 Matrix Norms in Control Theory

Control systems use matrix norms to quantify system gain and stability margins.

System norms. For a linear system $\dot{\mathbf{x}} = A\mathbf{x} + B\mathbf{u}$, $\mathbf{y} = C\mathbf{x}$:

• $H_\infty$ norm: $\|G\|_\infty = \sup_\omega \sigma_{\max}(G(i\omega))$ - worst-case gain over all frequencies; the spectral norm of the frequency response
• $H_2$ norm: $\|G\|_2 = \sqrt{\operatorname{tr}(B^\top P B)}$ where $P$ solves a Lyapunov equation; related to Frobenius norm in the frequency domain

Stability. A discrete-time system $\mathbf{x}_{t+1} = A\mathbf{x}_t$ is stable iff $\rho(A) < 1$ (spectral radius < 1). But for finite-time analysis, $\|A^t\|_2 \leq \|A\|_2^t$ - the spectral norm controls the growth of powers.

For AI: Recurrent networks are discrete-time dynamical systems with $\mathbf{h}_{t+1} = \sigma(W_{hh}\mathbf{h}_t + W_{xh}\mathbf{x}_t)$. The condition $\|W_{hh}\|_2 < 1$ (spectral normalization) guarantees contractivity: gradients decay as $\|W_{hh}\|_2^t$ through time - preventing explosion but also potentially causing vanishing gradients in long sequences.

E.3 Matrix Norms in Quantum Information

Quantum states are represented by density matrices $\rho$ (PSD, $\operatorname{tr}(\rho) = 1$). Operations are described by quantum channels. Matrix norms quantify distances between quantum states and operations.

Trace norm distance. The trace distance between quantum states $\rho, \sigma$:

$$D(\rho, \sigma) = \frac{1}{2}\|\rho - \sigma\|_* = \frac{1}{2}\sum_i |\lambda_i(\rho - \sigma)|$$

(For Hermitian matrices, the nuclear norm equals the sum of absolute eigenvalues, not singular values.)

Diamond norm. For quantum channels $\mathcal{E}, \mathcal{F}$:

$$\|\mathcal{E} - \mathcal{F}\|_\diamond = \max_\rho \|(\mathcal{E} \otimes I)(\rho) - (\mathcal{F} \otimes I)(\rho)\|_*$$

This is the quantum analog of the $2 \to 1$ norm - measuring the maximum distinguishability of the channels.

For AI: Large language models in principle implement quantum-inspired computations when trained on quantum data. More concretely, tensor network approximations of quantum states use matrix norms (Frobenius) to bound truncation error in tensor decompositions - the same mathematics as SVD-based model compression.

E.4 Matrix Norms in Graph Theory

For a graph $G$ on $n$ vertices with adjacency matrix $A \in \{0,1\}^{n \times n}$:

Spectral radius. $\|A\|_2 = \lambda_{\max}(A)$ (for symmetric $A$, since $\|A\|_2 = \rho(A)$ for symmetric PSD).

Graph conductance and mixing. The second eigenvalue $\lambda_2$ of the normalized Laplacian controls the mixing time of random walks. Small $\lambda_2$ means slow mixing (large $\kappa$).

Graph neural networks. A GNN layer applies $H^{(l+1)} = \sigma(\hat{A}H^{(l)}W^{(l)})$ where $\hat{A}$ is the normalized adjacency. The spectral norm $\|\hat{A}\|_2 \leq 1$ (by design of normalization) ensures the graph propagation is non-expansive - a Lipschitz constraint built into the architecture.

Over-smoothing and rank collapse. After many GNN layers, the representations $H^{(L)}$ converge to a low-rank matrix. The nuclear norm of $H^{(L)}$ decreases, reflecting that all nodes' features converge to the same value (weighted by PageRank). This is the GNN analog of the attention rank collapse phenomenon.

---

Appendix F: Historical Development

The theory of matrix norms developed in parallel with the needs of numerical analysis and functional analysis.

HISTORICAL TIMELINE: MATRIX NORMS
========================================================================

  1844  Cauchy introduces the "module" of a complex matrix - early norm idea

  1878  Frobenius studies bilinear forms; Frobenius norm implicit in his work

  1905  Hilbert introduces "Hilbert space" - inner product -> norm framework

  1929  Von Neumann: abstract operator theory in Hilbert space;
        nuclear operators (trace class) defined

  1937  Von Neumann trace inequality proved; singular values for operators

  1939  Ky Fan: Ky Fan k-norms, matrix inequalities

  1946  Eckart & Young: best low-rank approximation theorem (SVD)

  1950s Development of "matrix analysis" as a field (Bauer, Fike, etc.)
        Bauer-Fike theorem (1960): eigenvalue perturbation bound

  1960s Gershgorin circle theorem; norm-based stability conditions
        for numerical ODE solvers and control systems

  1970s  Numerical linear algebra matures (Golub, Van Loan)
        Condition number becomes central concept in floating-point analysis

  1988  Grothendieck's "resume" translated; connections to operator spaces

  1990s  Nuclear norm in matrix completion; compressed sensing foundations

  2004  Candes & Tao: compressed sensing; nuclear norm as convex
        proxy for rank in matrix recovery

  2010  Cai, Candes, Shen: singular value thresholding algorithm (SVT)
        for nuclear norm minimization

  2018  Miyato et al.: Spectral Normalization for GANs
        (ICLR 2018 paper)

  2021  Dong et al.: attention rank collapse analysis via matrix norms

  2021  Hu et al.: LoRA - implicit nuclear norm regularization via
        low-rank factored parameterization

  2024  DeepSeek MLA: explicit low-rank KV cache via nuclear norm
        motivated matrix compression

========================================================================

Key insight from the historical development. Matrix norms began as abstract tools in functional analysis (Von Neumann, Ky Fan) and numerical analysis (Frobenius, Bauer, Fike). Their entry into machine learning came through three channels:

1. Optimization theory (nuclear norm = convex proxy for rank, 2004-2010)
2. Generalization theory (Frobenius and spectral norms in PAC-Bayes bounds, 2017)
3. Architecture design (spectral normalization, LoRA, MLA, 2018-2024)

The mathematical tools developed over 80 years now routinely appear in the training pipelines of the largest language models.

---

Appendix G: Summary Tables

G.1 Complete Norm Reference Table

G.2 Norm Inequality Summary

For $A \in \mathbb{R}^{m \times n}$ with rank $r$ and singular values $\sigma_1 \geq \cdots \geq \sigma_r > 0$:

$$\|A\|_2 \leq \|A\|_F \leq \sqrt{r}\|A\|_2$$ $$\|A\|_F \leq \|A\|_* \leq \sqrt{r}\|A\|_F$$ $$\|A\|_2 \leq \|A\|_* \leq r\|A\|_2$$ $$\frac{1}{\sqrt{n}}\|A\|_1 \leq \|A\|_2 \leq \sqrt{m}\|A\|_1$$ $$\frac{1}{\sqrt{m}}\|A\|_\infty \leq \|A\|_2 \leq \sqrt{n}\|A\|_\infty$$ $$\|A\|_{\max} \leq \|A\|_2 \leq \sqrt{mn}\|A\|_{\max}$$

All inequalities are tight (achieved by appropriate matrices).

G.3 Which Norm to Use When

G.4 Condition Number Thresholds (Practical Guide)

In double precision arithmetic ($\epsilon_{\text{mach}} \approx 10^{-16}$), effective precision = $16 - \log_{10}\kappa$ digits.

---

Appendix H: Deep Dives

H.1 The Spectral Norm in Full Detail

The spectral norm $\|A\|_2 = \sigma_1(A)$ deserves extended treatment because it appears in so many different contexts.

Variational characterizations. All of the following equal $\sigma_1(A)$:

$$\sigma_1(A) = \max_{\|\mathbf{x}\|_2 = 1}\|A\mathbf{x}\|_2 \qquad \text{(definition)}$$ $$= \max_{\|\mathbf{x}\|_2 = \|\mathbf{y}\|_2 = 1} \mathbf{y}^\top A\mathbf{x} \qquad \text{(bilinear form)}$$ $$= \sqrt{\lambda_{\max}(A^\top A)} \qquad \text{(eigenvalue of Gram matrix)}$$ $$= \sqrt{\lambda_{\max}(AA^\top)} \qquad \text{(left Gram matrix)}$$ $$= \max_{\|B\|_* \leq 1}\langle A, B\rangle_F \qquad \text{(dual norm formula)}$$

Each characterization reveals a different aspect:

• The first shows it as maximum stretching
• The second shows it as maximum inner product over the unit sphere (bilinear)
• The third and fourth show it as square root of a largest eigenvalue
• The fifth shows it as dual of nuclear norm

Computing $\sigma_1$ for structured matrices:

For $A = \mathbf{u}\mathbf{v}^\top$ (rank-1): $\sigma_1 = \|\mathbf{u}\|\|\mathbf{v}\|$ (exact, no SVD needed).

For $A$ symmetric PSD: $\sigma_1 = \lambda_{\max}(A)$ (Lanczos iteration converges fast).

For $A$ sparse: Power iteration on $A^\top A$ with sparse matrix-vector products, $O(\text{nnz}(A) \cdot k)$ for $k$ iterations.

For $A$ a convolution matrix (CNN weights): The spectral norm equals the maximum frequency response $\|\hat{a}\|_\infty$ where $\hat{a}$ is the Fourier transform of the filter - computable in $O(n\log n)$ via FFT.

For AI: The "singular value of a convolution" insight means spectral normalization of CNN layers can be done in $O(n\log n)$ using FFT instead of $O(n^2)$ SVD. This is exploited in efficient implementations of spectral normalization for CNNs.

Spectral norm of attention. For scaled dot-product attention with keys $K \in \mathbb{R}^{T\times d_k}$, queries $Q \in \mathbb{R}^{T\times d_k}$, the attention logit matrix $S = QK^\top/\sqrt{d_k}$ satisfies:

$$\|S\|_2 \leq \|Q\|_2\|K\|_2/\sqrt{d_k}$$

In practice, if $Q, K$ are normalized (unit-norm rows), then $\|Q\|_2 \leq \sqrt{T}$ and $\|K\|_2 \leq \sqrt{T}$, giving $\|S\|_2 \leq T/\sqrt{d_k}$. The $1/\sqrt{d_k}$ factor prevents this from growing with $d_k$, maintaining bounded spectral norm for fixed $T$.

Spectral norm through training. In typical training of GPT-like models:

• At initialization (Xavier/Kaiming): $\|W\|_2 \approx \sqrt{2/d}$ (by design)
• After training without regularization: $\|W\|_2$ can grow by 10-100\times as features strengthen
• With weight decay $\lambda$: equilibrium at $\|W\|_2 \approx \|\nabla_W\mathcal{L}\|_2/\lambda$ (gradient norm divided by decay rate)
• With spectral normalization: $\|W\|_2 = 1$ exactly (enforced each step)

H.2 The Nuclear Norm in Full Detail

The nuclear norm $\|A\|_* = \sum_i\sigma_i$ has a rich structure worth examining closely.

Characterizations. All of the following equal $\|A\|_*$:

$$\|A\|_* = \operatorname{tr}(\sqrt{A^\top A}) = \operatorname{tr}(|A|)$$ $$= \min_{A = UV^\top} \frac{1}{2}(\|U\|_F^2 + \|V\|_F^2) \qquad \text{(factorization formula)}$$ $$= \max_{\|B\|_2 \leq 1}\operatorname{tr}(A^\top B) \qquad \text{(duality)}$$ $$= \min_{\substack{A = B + C \\ B\text{ rank-1}}} \|B\|_* + \|C\|_* \qquad \text{(triangle inequality applied optimally)}$$

The factorization formula $\|A\|_* = \min_{A=UV^\top}\frac{1}{2}(\|U\|_F^2+\|V\|_F^2)$ is particularly useful:

It shows that the nuclear norm equals half the squared Frobenius norm at the optimal factorization - the one where the singular values split evenly: $U = U_0\Sigma^{1/2}$ and $V = V_0\Sigma^{1/2}$ in the SVD $A = U_0\Sigma V_0^\top$.

For AI: This is exactly why LoRA works. The optimization $\min_{B,A}\mathcal{L}(W_0 + BA)$ with $B \in \mathbb{R}^{d\times r}$ and $A \in \mathbb{R}^{r\times d}$ implicitly minimizes $\|BA\|_* = \min_{\Delta W = BA}\|BA\|_*$ over rank-$r$ weight increments. The factored form is the "unfolded" version of nuclear norm minimization.

Nuclear norm SDP representation. The nuclear norm can be computed via semidefinite programming:

$$\|A\|_* = \min_{W_1, W_2} \frac{1}{2}(\operatorname{tr}(W_1) + \operatorname{tr}(W_2)) \quad\text{s.t.}\quad \begin{pmatrix}W_1 & A \\ A^\top & W_2\end{pmatrix} \succeq 0$$

This shows nuclear norm minimization is a semidefinite program (SDP) - solvable in polynomial time (in principle). For large-scale problems, proximal methods (using SVT) are much faster than interior-point SDP solvers.

Subdifferential. The subdifferential of $\|\cdot\|_*$ at $A$ with compact SVD $A = U_r\Sigma_r V_r^\top$ (only positive singular values) is:

$$\partial\|A\|_* = \{U_r V_r^\top + P_\perp W P_\perp : \|W\|_2 \leq 1\}$$

where $P_\perp = I - U_rU_r^\top$ projects onto the orthogonal complement of the column space. The unique subgradient when all singular values are distinct is $U_r V_r^\top$ - the "direction matrix."

H.3 Condition Number and Optimization Landscape

The condition number of the Hessian $H = \nabla^2\mathcal{L}$ at a critical point determines the local convergence rate of gradient-based methods.

Gradient descent convergence. For $\mathcal{L}$ with $L$-smooth and $\mu$-strongly convex Hessian ($\mu I \preceq H \preceq LI$):

$$\mathcal{L}(\mathbf{x}^{(t)}) - \mathcal{L}^* \leq \left(1 - \frac{\mu}{L}\right)^t (\mathcal{L}(\mathbf{x}^{(0)}) - \mathcal{L}^*)$$

The convergence rate $(1-\mu/L) = 1 - 1/\kappa(H)$ depends directly on the condition number. For $\kappa(H) = 1000$, we need $\sim 1000$ steps to reduce error by $1/e$.

Newton's method. Newton steps use the Hessian as a preconditioner: $\mathbf{x}^{(t+1)} = \mathbf{x}^{(t)} - H^{-1}\nabla\mathcal{L}$. This achieves quadratic convergence near the optimum, independent of $\kappa(H)$.

Adam as approximate preconditioning. Adam maintains estimates of $\mathbb{E}[g_i^2]$ for each parameter. Dividing the gradient by $\sqrt{\mathbb{E}[g_i^2]}$ approximates dividing by $\sqrt{H_{ii}}$ - a diagonal preconditioning. This reduces the effective condition number:

$$\kappa_{\text{eff}} = \frac{\max_i H_{ii}/\mathbb{E}[g_i^2]^{1/2}}{\min_i H_{ii}/\mathbb{E}[g_i^2]^{1/2}} \ll \kappa(H)$$

when $H$ is diagonally dominant. For non-diagonal $H$, Adam's approximation is crude, which is why Shampoo (full matrix preconditioning) converges faster.

Shampoo optimizer. Shampoo (Gupta et al., 2018) computes full matrix preconditioners:

$$G_{t+1} = G_t + \text{grad}_t \text{grad}_t^\top, \quad \hat{G}_t = G_t^{-1/4}$$

The preconditioned gradient $\hat{G}_t \text{grad}_t \hat{G}_t^\top$ (for a 2D weight matrix) approximates the natural gradient, achieving condition number $\kappa_{\text{eff}} \approx 1$ in the limit. The cost is computing $G_t^{-1/4}$ (matrix $p$-th root) periodically.

H.4 Norms in Transformer Architecture Design

Modern transformer architectures are designed with matrix norm considerations in mind.

Layer normalization. LayerNorm normalizes hidden representations $\mathbf{h}$ so that $\|\mathbf{h}\|_2 \approx \sqrt{d}$ (unit variance per coordinate). This bounds the spectral norm of the Jacobian of subsequent layers: if $\|\mathbf{h}\|_2 \leq \sqrt{d}$ and $\|W\|_F \leq C$, then $\|W\mathbf{h}\|_2 \leq \|W\|_2\|\mathbf{h}\|_2 \leq \|W\|_F\sqrt{d}$.

Residual connections. The residual architecture $\mathbf{h}_{l+1} = \mathbf{h}_l + F_l(\mathbf{h}_l)$ has Jacobian $I + J_{F_l}$. The spectral norm:

$$\|I + J_{F_l}\|_2 \leq 1 + \|J_{F_l}\|_2$$

This prevents extreme gradient flow: even if $\|J_{F_l}\|_2$ is large, the identity term stabilizes backward propagation. Empirically, $\|J_{F_l}\|_2 \approx 0.5-2$ in trained transformers.

Pre-norm vs. post-norm. In pre-norm transformers (LayerNorm before the sublayer), the effective Jacobian has better conditioning than post-norm. Specifically, pre-norm ensures $\|\mathbf{h}\|_2$ remains bounded before each attention/MLP, giving more stable Hessian conditioning.

RoPE (Rotary Position Embeddings). RoPE applies a position-dependent rotation to queries and keys:

$$\tilde{\mathbf{q}} = R_m \mathbf{q}, \quad \tilde{\mathbf{k}} = R_n \mathbf{k}$$

where $R_m$ is a rotation matrix depending on position $m$. Since $R_m$ is unitary ($\|R_m\|_2 = 1$), this preserves the spectral norm of the query/key vectors: $\|\tilde{\mathbf{q}}\|_2 = \|\mathbf{q}\|_2$. The inner product $\tilde{\mathbf{q}}^\top\tilde{\mathbf{k}} = \mathbf{q}^\top R_m^\top R_n \mathbf{k} = \mathbf{q}^\top R_{n-m}\mathbf{k}$ - only the relative position $n-m$ matters.

MLA (Multi-Head Latent Attention). DeepSeek's MLA compresses the KV cache from $2Td_{kv}$ to $Td_c$ (with $d_c \ll 2d_{kv}$) by decomposing:

$$K = C_{KV}W^K, \quad V = C_{KV}W^V$$

where $C_{KV} \in \mathbb{R}^{T\times d_c}$ is the "latent" KV. The approximation error (measured in nuclear norm) is bounded by the nuclear norm of the difference $\|KV^\top - \hat{K}\hat{V}^\top\|_*$ - exactly the type of bound from Eckart-Young applied to the KV product matrix.

---

Appendix I: Practice Problems and Solutions

I.1 Conceptual Checks

Check 1. Explain why $\|I_n\|_F = \sqrt{n}$ while $\|I_n\|_2 = 1$. What does this say about whether the Frobenius norm is induced?

Solution. $\|I_n\|_F = \sqrt{\sum_{i,j}\delta_{ij}^2} = \sqrt{n}$. Every induced norm must satisfy $\|I\| = 1$ (since $\|I\mathbf{x}\| = \|\mathbf{x}\|$ for all $\mathbf{x}$, so $\max_{\|\mathbf{x}\|=1}\|I\mathbf{x}\| = 1$). Since $\|I_n\|_F = \sqrt{n} \neq 1$ for $n > 1$, the Frobenius norm cannot be induced by any vector norm.

Check 2. A student claims: "Since $\|A\|_F \leq \sqrt{r}\|A\|_2$, I can upper bound the Frobenius norm by computing only the spectral norm." When is this bound tight and when is it loose?

Solution. The bound $\|A\|_F \leq \sqrt{r}\|A\|_2$ is tight when all $r$ singular values are equal ($\sigma_1 = \cdots = \sigma_r$), e.g., a scalar multiple of a unitary matrix. It is loose when singular values decay rapidly (e.g., $\sigma_i = \sigma_1/i$), in which case $\|A\|_F \approx \sigma_1\sqrt{\sum 1/i^2} \approx \sigma_1\cdot\pi/\sqrt{6}$ while the bound gives $\sigma_1\sqrt{r}$. For matrices with low stable rank, the bound is tight.

Check 3. Is the condition number invariant under matrix addition? I.e., does $\kappa(A+B) = \kappa(A) + \kappa(B)$?

Solution. No. Condition number is not additive. Consider $A = \text{diag}(100, 1)$ (so $\kappa(A) = 100$) and $B = \text{diag}(0, 99)$ (so $\kappa(B) = \infty$ since $B$ is singular). Then $A + B = \text{diag}(100, 100)$ with $\kappa(A+B) = 1$. The sum of two ill-conditioned matrices can be perfectly conditioned.

Check 4. Prove or disprove: $\|A+B\|_2 = \|A\|_2 + \|B\|_2$ implies $A$ and $B$ have the same top right singular vector.

Solution. True. The spectral norm satisfies the triangle inequality $\|A+B\|_2 \leq \|A\|_2 + \|B\|_2$ with equality iff $A$ and $B$ are "aligned" in the spectral sense. Specifically, equality holds iff there exist unit vectors $\mathbf{u}, \mathbf{v}$ such that $\mathbf{u}^\top A\mathbf{v} = \|A\|_2$ and $\mathbf{u}^\top B\mathbf{v} = \|B\|_2$ - meaning $\mathbf{v}$ is the top right singular vector of both $A$ and $B$, and $\mathbf{u}$ is the corresponding top left singular vector. (Same structure as Cauchy-Schwarz equality condition.)

I.2 Computational Exercises with Answers

Problem 1. Let $A = \begin{pmatrix}2 & 1 \\ 0 & 3\end{pmatrix}$.

(a) Find all five norms: $\|A\|_F$, $\|A\|_2$, $\|A\|_*$, $\|A\|_1$, $\|A\|_\infty$.

(b) Find $\kappa_2(A)$ and the condition number of the equation $A\mathbf{x} = \mathbf{b}$.

Solution.

First compute $A^\top A = \begin{pmatrix}4&2\\2&10\end{pmatrix}$. Eigenvalues: $\lambda = (14 \pm \sqrt{196-36-16})/2$... Let us directly:

$\det(A^\top A - \lambda I) = (4-\lambda)(10-\lambda) - 4 = \lambda^2 - 14\lambda + 36 = 0$

$\lambda = (14 \pm \sqrt{196-144})/2 = (14 \pm \sqrt{52})/2 = 7 \pm \sqrt{13}$

So $\sigma_1 = \sqrt{7+\sqrt{13}} \approx \sqrt{10.606} \approx 3.257$ and $\sigma_2 = \sqrt{7-\sqrt{13}} \approx \sqrt{3.394} \approx 1.842$.

(a) Results:

• $\|A\|_F = \sqrt{4+1+0+9} = \sqrt{14} \approx 3.742$
• $\|A\|_2 = \sigma_1 \approx 3.257$
• $\|A\|_* = \sigma_1 + \sigma_2 \approx 3.257 + 1.842 = 5.099$
• $\|A\|_1 = \max(|2|+|0|, |1|+|3|) = \max(2, 4) = 4$
• $\|A\|_\infty = \max(|2|+|1|, |0|+|3|) = \max(3, 3) = 3$

(b) $\kappa_2(A) = \sigma_1/\sigma_2 \approx 3.257/1.842 \approx 1.768$.

This is a well-conditioned matrix. For $A\mathbf{x}=\mathbf{b}$ with relative perturbation $\epsilon$ in $\mathbf{b}$, the relative error in $\mathbf{x}$ is at most $\kappa \epsilon \approx 1.77\epsilon$.

Problem 2. Rank-1 approximation.

For $A = \begin{pmatrix}1&2\\3&4\\5&6\end{pmatrix}$, find the best rank-1 approximation in the Frobenius norm and compute the approximation error.

Solution. Compute SVD. The singular values are $\sigma_1 \approx 9.525$ and $\sigma_2 \approx 0.514$. The best rank-1 approximation $A_1 = \sigma_1\mathbf{u}_1\mathbf{v}_1^\top$ has:

$$\|A - A_1\|_F = \sigma_2 \approx 0.514, \quad \|A - A_1\|_2 = \sigma_2 \approx 0.514$$

The approximation captures $\sigma_1^2/(\sigma_1^2+\sigma_2^2) = 90.7/91.0 \approx 99.7\%$ of the Frobenius-squared energy.

Problem 3. Tikhonov regularization effect on condition number.

Let $A = \text{diag}(10, 1, 0.01)$ (diagonal, well-structured). Compute $\kappa_2(A^\top A + \lambda I)$ for $\lambda \in \{0, 0.001, 0.01, 0.1, 1\}$ and observe the trade-off.

Solution. $A^\top A = \text{diag}(100, 1, 10^{-4})$, so $\kappa(A^\top A) = 10^6$.

$\kappa(A^\top A + \lambda I) = (100+\lambda)/(10^{-4}+\lambda)$:

Each decade of $\lambda$ improves $\kappa$ dramatically but increases bias. The optimal $\lambda$ balances condition improvement against solution bias.

I.3 Connection to Linear Programming

The nuclear norm can be computed via a semidefinite program (SDP) or, for special cases, via linear programming.

Ky Fan norm via LP. The Ky Fan $k$-norm has the dual representation:

$$\|A\|_{(k)} = \min\{k\mu + \operatorname{tr}(S) : S \succeq 0,\, S \geq 0,\, S + \mu I \geq \text{diag}(\boldsymbol{\sigma}),\, \mu \geq 0\}$$

(where the inequality is in the PSD sense on the diagonal). This is a semidefinite program in $(\mu, S)$.

Nuclear norm via SDP.

$$\|A\|_* = \min_{W_1,W_2}\frac{1}{2}(\operatorname{tr}(W_1)+\operatorname{tr}(W_2)) \quad \text{s.t.} \quad \begin{pmatrix}W_1&A\\A^\top&W_2\end{pmatrix} \succeq 0$$

This is a standard SDP with $O(m+n)$ variables. Interior-point methods solve it in $O((m+n)^3)$ time.

For AI: While these SDP representations are theoretically important (they prove polynomial solvability of nuclear norm problems), they are impractical for large matrices. Instead, proximal gradient descent with SVT (the practical algorithm) exploits the simple proximal operator structure.

---