Norm Inequality
Published:
This post summarizes some useful inequalities between different norms.
Norm Equivalence
On any finite-dimensional vector space over $\mathbb{R}$ or $\mathbb{C}$, all norms are equivalent. This means that for any two norms $\Vert\cdot\Vert_a$ and $\Vert\cdot\Vert_b$, there exists $c_1\geq c_2>0$ such that $$c_1\Vert\cdot\Vert_b \leq \Vert\cdot\Vert_a \leq c_2\Vert\cdot\Vert_b $$ holds for any element in the space.
Useful Inequalities
| Domain | Inequality |
|---|---|
| Vector $x\in\mathbb{R}^n$ with $s=\Vert x\Vert_0\leq n$ | $\Vert x\Vert_{\infty}\leq \Vert x\Vert_{2} \leq \Vert x\Vert_{1} \leq \sqrt{s}\Vert x\Vert_{2} \leq s\Vert x\Vert_{\infty}$ |
| Spectral domain of Matrix $X\in\mathbb{R}^{n\times d}$ with $r=\text{rank}(X)\leq \min\{n,d\}$ | $\Vert X\Vert_{op}\leq \Vert X\Vert_{F} \leq \Vert X\Vert_{nuc} \leq \sqrt{r}\Vert X\Vert_{F} \leq r\Vert X\Vert_{op}$ |
| Matrix $X\in\mathbb{R}^{n\times d}$ | $\frac{1}{\sqrt{d}}\Vert X\Vert_\infty\leq\Vert X\Vert_{op}\leq \sqrt{n} \Vert X\Vert_\infty$ |
Note the matrix norms in the spectral domain have similar behaviors as the corresponding vector norms.
Miscellanies
- $\Vert X\Vert_{1} = \max_{1\leq j\leq d} \Vert X_j \Vert_1$
- $\Vert X\Vert_{2,\infty} = \max_{1\leq j\leq d} \Vert X_j \Vert_2$
- $\Vert X \Vert_{F} = ({\rm tr}(X^{\top}X))^{1/2}$
- $\Vert X \Vert_{nuc} = \Vert X \Vert_{\ast} = \Vert X \Vert_ = {\rm tr}((X^{\top}X)^{1/2})$
$|{\rm tr}(AB)| \leq \Vert A \Vert_{\rm op} \cdot \Vert B \Vert_{\rm tr} $
For positive semi-definite matrix $A$ and arbitrary $B$, we have $\lambda_n(B),{\rm tr}(A)\leq {\rm tr}(AB)\leq\lambda_1(B),{\rm tr}(A)$