NLA MT25, Vector and matrix norms
Flashcards
Vector norms
@State a result bounding the vector $\infty$-norm in terms of the vector $2$-norm.
@State a result bounding the vector $2$-norm in terms of the vector $1$-norm.
@State a result bounding the vector $\infty$-norm in terms of the vector $1$-norm.
@State a useful result about comparing $ \vert \vert x \vert \vert _ p$ and $ \vert \vert x \vert \vert _ q$.
For $p > q$, $ \vert \vert x \vert \vert _ p \le \vert \vert x \vert \vert _ q$.
@Prove that if $p > q$, then $ \vert \vert x \vert \vert _ p \le \vert \vert x \vert \vert _ q$.
By homogeneity, note that $ \vert \vert \alpha x \vert \vert _ p = \vert \alpha \vert \cdot \vert \vert x \vert \vert _ p$, so without loss of generality we may assume $ \vert \vert x \vert \vert _ p = 1$. Then
\[\begin{aligned} 1 &= \vert \vert x \vert \vert _ p^p \\ &= \sum^n _ {i = 1} \vert x _ i \vert ^p \\ &\le \sum^n _ {i = 1} \vert x _ i \vert ^q && (\ast)\\ &= \vert \vert x \vert \vert ^q _ q \end{aligned}\]where the nontrivial inequality $(\ast)$ comes from the fact that the entries of $x _ i$ are bounded by $1$.
Hence $ \vert \vert x \vert \vert ^q _ q \ge 1$, so $ \vert \vert x \vert \vert _ q \ge 1 = \vert \vert x \vert \vert _ p$.
Matrix norms
@Define the matrix $p$-norm $ \vert \vert A \vert \vert _ p$.
The matrix $p$-norm $ \vert \vert A \vert \vert _ p$ is normally defined via
\[ \vert \vert A \vert \vert _ p = \max _ x \frac{ \vert \vert Ax \vert \vert _ p}{ \vert \vert x \vert \vert _ p}\]
@State three alternative characterisations of the matrix $2$-norm, $1$-norm and $\infty$-norm.
- $2$-norm: $ \vert \vert A \vert \vert _ 2 = \sigma _ \max(A)$.
- $1$-norm: $ \vert \vert A \vert \vert _ 1 = \max _ i \sum^m _ {j = 1} \vert A _ {ji} \vert $, i.e. biggest column sum
- $\infty$-norm: $ \vert \vert A \vert \vert _ \infty = \max _ i \sum^n _ {j = 1} \vert A _ {ij} \vert $, i.e. biggest row sum
@Define the Frobenius norm $ \vert \vert A \vert \vert _ F$.
@Define the trace norm / nuclear norm $ \vert \vert A \vert \vert _ \ast$.
(note here that the trace norm is not just the trace of the matrix, since the trace is the sum of the eigenvalues and is only defined for square matrices).
Which of the following are unitarily invariant matrix norms (i.e. $ \vert \vert A \vert \vert = \vert \vert UAV \vert \vert $)?
- $2$-norm
- $1$-norm
- $\infty$-norm
- Frobenius norm
- Trace norm
- $2$-norm
- Frobenius norm
- Trace norm
@Define what it means for:
- a vector norm $ \vert \vert \cdot \vert \vert $ to be unitarily invariant
- a matrix norm $ \vert \vert \cdot \vert \vert $ to be unitarily invariant
- For any $x \in \mathbb C^n$ and any unitary $U$, $ \vert \vert Ux \vert \vert = \vert \vert x \vert \vert $.
- For any $A \in \mathbb C^{m \times n}$ and unitary matrices $U,V$, $ \vert \vert A \vert \vert = \vert \vert UAV \vert \vert $.
@Define what it means for a matrix norm $ \vert \vert \cdot\|$ to be submultiplicative.
@State a result about matrix $p$-norms in relation to $ \vert \vert AB \vert \vert _ p$.
Matrix $p$-norms are submultiplicative, i.e.
\[ \vert \vert AB \vert \vert _ p \le \vert \vert A \vert \vert _ p \vert \vert B \vert \vert _ p\]@Prove that matrix $p$-norms are submultiplicative, i.e.
\[ \vert \vert AB \vert \vert _ p \le \vert \vert A \vert \vert _ p \vert \vert B \vert \vert _ p\]
Suppose $B = 0$, then
\[ \vert \vert AB \vert \vert _ p = \sup _ {x\ne 0} \frac{ \vert \vert ABx \vert \vert _ p}{ \vert \vert x \vert \vert _ p} = 0 = \vert \vert A \vert \vert _ p \vert \vert B \vert \vert _ p\]as required. If $B \ne 0$, then
\[\begin{aligned} \vert \vert AB \vert \vert _ p &= \sup _ {x \ne 0} \frac{ \vert \vert ABx \vert \vert _ p}{ \vert \vert x \vert \vert _ p} \\ &= \sup _ {Bx \ne 0} \frac{ \vert \vert ABx \vert \vert _ p}{ \vert \vert Bx \vert \vert _ p} \cdot \frac{ \vert \vert Bx \vert \vert _ p}{ \vert \vert x \vert \vert _ p} \\ &\le \sup _ {x \ne 0} \frac{ \vert \vert Ax \vert \vert _ p}{ \vert \vert x \vert \vert _ p} \cdot \sup _ {x \ne 0} \frac{ \vert \vert Bx \vert \vert _ p}{ \vert \vert x \vert \vert _ p} \\ &= \vert \vert A \vert \vert _ p \vert \vert B \vert \vert _ p \end{aligned}\]@State a result which bounds the matrix $2$-norm in terms of the matrix $\infty$-norm.
Suppose $A \in \mathbb R^{m \times n}$. Then:
\[\frac{1}{\sqrt n} \vert \vert A \vert \vert _ \infty \le \vert \vert A \vert \vert _ 2 \le \sqrt m \vert \vert A \vert \vert _ \infty\]@State a result which bounds the matrix $2$-norm in terms of the matrix $1$-norm.
Suppose $A \in \mathbb R^{m \times n}$. Then:
\[\frac 1 {\sqrt m} \vert \vert A \vert \vert _ 1 \le \vert \vert A \vert \vert _ 2 \le \sqrt n \vert \vert A \vert \vert _ 1\]@State a result which bounds the Frobenius norm in terms of the matrix $2$-norm.
Suppose $A \in \mathbb R^{m \times n}$. Then:
\[ \vert \vert A \vert \vert _ 2 \le \vert \vert A \vert \vert _ F \le \sqrt{\min(m, n)} \vert \vert A \vert \vert _ 2\]Bite-sized
Cauchy-Schwarz inequality: for $x, y \in \mathbb R^n$, $ \vert x^\top y \vert \le $ $\ \vert x\ \vert _ 2 \ \vert y\ \vert _ 2$.
The Euclidean 2-norm is induced by the standard inner product: $\ \vert x\ \vert _ 2 = $ $\sqrt{x^\top x}$.
Frobenius norm via singular values: $\ \vert A\ \vert _ F = $ $\sqrt{\sum _ i \sigma _ i(A)^2}$. Via trace: $\ \vert A\ \vert _ F^2 = $ $\mathrm{Trace}(A^\top A)$.
Why is the 2-norm “unitarily invariant”?
$\|Ux\| _ 2 = \|x\| _ 2$ for any unitary (or orthogonal) $U$. Proof: $\|Ux\| _ 2^2 = (Ux)^\top (Ux) = x^\top U^\top U x = x^\top x = \|x\| _ 2^2$. The 2-norm is the unique vector $p$-norm with this property — neither the 1-norm nor the $\infty$-norm is unitarily invariant.
Spectral norm and trace norm as functions of singular values: $\ \vert A\ \vert _ 2 = $ $\sigma _ 1(A)$ (largest singular value); $\ \vert A\ \vert _ * = $ $\sum _ {i=1}^{\min(m,n)} \sigma _ i(A)$ (sum of singular values).
Strategy for proving matrix $p$-norms are submultiplicative, $\|AB\| _ p \le \|A\| _ p \|B\| _ p$ (∆matrix-p-norm-submultiplicative-proof).
The key trick is splitting the sup via multiply-and-divide by $\|Bx\| _ p$:
\[\|AB\| _ p = \sup _ {x \ne 0} \frac{\|ABx\| _ p}{\|x\| _ p} = \sup _ {Bx \ne 0} \frac{\|A(Bx)\| _ p}{\|Bx\| _ p} \cdot \frac{\|Bx\| _ p}{\|x\| _ p}.\]The first factor is bounded by $\sup _ {y \ne 0} \|Ay\| _ p / \|y\| _ p = \|A\| _ p$ (taking $y = Bx$, which ranges over a subset of nonzero vectors). The second factor is bounded by $\|B\| _ p$. Multiply. Handle $B = 0$ as a separate trivial case.