13  Vector and Matrix Norms

Foundations for measuring approximation errors and convergence.

13.1 Vector Norms

NoteDefinition: Vector Norm

\(\|\cdot\| : \fR^n \to \fR\) satisfies:

  1. Definiteness: \(\|\bx\| \geq 0\), with equality iff \(\bx = \bzero\).

  2. Homogeneity: \(\|c\bx\| = |c|\|\bx\|\).

  3. Triangle Inequality: \(\|\bx + \by\| \leq \|\bx\| + \|\by\|\).

NoteDefinition: \(\ell^p\) Norms

\(\|\bx\|_p = (\sum |x_i|^p)^{1/p}\).

  • \(\ell_1\): \(\sum |x_i|\) (Sparsity).

  • \(\ell_2\): \(\sqrt{\bx^T\bx}\) (Energy).

  • \(\ell_\infty\): \(\max |x_i|\) (Tolerance).

NoteTheorem: Fundamental Inequalities

  • Cauchy-Schwarz: \(|\bx^T\by| \leq \|\bx\|_2 \|\by\|_2\).

  • Hölder: \(|\bx^T\by| \leq \|\bx\|_p \|\by\|_q\) where \(1/p + 1/q = 1\).

Tip

Equivalence: On \(\fR^n\), all norms are equivalent: \(c_1 \|\bx\|_\beta \leq \|\bx\|_\alpha \leq c_2 \|\bx\|_\beta\). Convergence in one implies convergence in all.

WarningExercise

  1. Prove the triangle inequality for \(\|\cdot\|_2\) using Cauchy-Schwarz.

  2. Show that \(\|\bx\|_\infty = \lim_{p\to\infty} \|\bx\|_p\).

13.2 Matrix Norms

Measure how much a matrix amplifies vectors.

NoteDefinition: Induced (Operator) Norm

\(\|\bA\| = \max_{\bx \neq \bzero} \frac{\|\bA\bx\|}{\|\bx\|}\).

  • \(\|\bA\|_1\): Max absolute column sum.

  • \(\|\bA\|_\infty\): Max absolute row sum.

  • \(\|\bA\|_2\) (Spectral): \(\sigma_{\max}(\bA) = \sqrt{\lambda_{\max}(\bA^T\bA)}\).

NoteDefinition: Frobenius Norm

\(\|\bA\|_F = \sqrt{\sum a_{ij}^2} = \sqrt{\text{Tr}(\bA^T\bA)}\).

  • Relation: \(\|\bA\|_2 \leq \|\bA\|_F \leq \sqrt{\text{rank}(\bA)} \|\bA\|_2\).
Tip

Consistency and Submultiplicativity: Matrix norms are useful when they satisfy \(\|\bA\bx\| \leq \|\bA\|\|\bx\|\). All induced norms are additionally submultiplicative: \(\|\bA\bB\| \leq \|\bA\|\|\bB\|\).

WarningExercise

  1. Compute \(\|\bA\|_1, \|\bA\|_\infty, \|\bA\|_2, \|\bA\|_F\) for \(\bA = \begin{pmatrix} 1 & -2 \\ -3 & 4 \end{pmatrix}\).

  2. Low-Rank Approximation: The Frobenius norm is central to the Eckart-Young-Mirsky theorem. How is it related to singular values?

  3. Find a \(2 \times 2\) example where the max norm (\(\max|a_{ij}|\)) is not submultiplicative.