Norms and Inequalities

\(\newcommand{\abs}[1]{\left\lvert#1\right\rvert}\) \(\newcommand{\norm}[1]{\left\lVert#1\right\rVert}\) \(\newcommand{\inner}[1]{\left\langle#1\right\rangle}\) \(\DeclareMathOperator*{\argmin}{arg\,min}\) \(\DeclareMathOperator*{\argmax}{arg\,max}\) \(\DeclareMathOperator*{\E}{\mathbb{E}}\) \(\DeclareMathOperator*{\V}{\mathbb{V}}\)

D

efinitions and the standard inequalities for vector and matrix norms: the $\ell_p$ ordering, duality, and submultiplicativity. Everything here is deterministic and finite-dimensional.

Vector Norms

A norm on a real vector space $V$ is a function

that satisfies the following axioms for all $x,y\in V$ and all scalars $\lambda\in\mathbb{R}$:

1. Non-negativity:

   \[\norm{x} \ge 0,\]

   and
   positive definiteness:

   \[\norm{x} = 0 \quad \iff \quad x = 0.\]

2. Absolute homogeneity:

   \[\norm{\lambda x} = |\lambda|\,\norm{x}.\]

3. Triangle inequality (subadditivity):

   \[\norm{x + y} \le \norm{x} + \norm{y}.\]

For $\mathrm{x} = (x_i)_{i=1}^n \in \mathbb{R}^n$:

• General $\ell_p$-norm: $\norm{\mathrm{x}}_p = \left(\sum _{i=1}^n \abs{x_i}^p\right)^{1/p}$, $p \in [1,\infty)$
• Manhattan $\ell_1$-norm: $\norm{\mathrm{x}}_1 = \sum _{i=1}^n \abs{x_i}$
• Euclidean $\ell_2$-norm: $\norm{\mathrm{x}}_2 = \left(\sum _{i=1}^n x_i^2\right)^{1/2}$
• Maximum $\ell_\infty$-norm: $\norm{\mathrm{x}}_\infty = \max_i \abs{x_i}$
• $\ell_0$ “norm”: Count of nonzero entries.

In practice, $\ell_2$ is the default for distances, $\ell_1$ for sparsity, and $\ell_\infty$ for worst-case bounds.

• $\ell _0$ is not a true norm but is standard shorthand for sparsity.
• $\ell _\infty$ arises as the limit of $\ell _p$ as $p \to \infty$.
• In finite dimensions, all $\ell _p$ norms are equivalent up to constants.

Dual Norm

Given any norm \(\norm{\cdot}_{\ell_p}\) on $\mathbb{R}^n$, its dual norm $\norm{\cdot}_*$ is defined by

So $\norm{\mathbf{y}}_*$ is the largest value the inner product with $\mathbf{y}$ can take over the unit ball of the original (primal) norm, i.e. the operator norm of the linear functional $\mathbf{x}\mapsto\mathbf{x}^\top\mathbf{y}$.

Vector Inequalities

For example:

Hölder’s inequality bounds the inner product,

which implies Cauchy-Schwarz inequality when $p=q=2$,

and implies another interesting special case when $p=1, q=\infty$,

By Hölder’s inequality, the dual norm associated with \(\|\cdot\|_p\) coincides with the $\ell _q$ norm, where $1/p + 1/q = 1$.

Minkowski inequality is a triangle inequality for $L^p$ spaces,

As a direct consequence, one also has

That is, the direct distance from $\mathrm{x}$ to $\mathrm{y}$ is never longer than the detour through the origin.

Jensen’s inequality states that for a convex function, the function of an average is less than or equal to the average of the function,

Matrix Norms

A matrix norm is a norm on the vector space $\mathbb{R}^{m\times n}$; that is, a function \(\|\cdot\|:\mathbb{R}^{m\times n}\to[0,\infty)\) satisfying the same axioms as a vector norm.

Matrix norms may be defined either as induced norms from vector norms or directly in terms of the entries or singular values of the matrix.

For $A \in \mathbb{R}^{m\times n}$, let $k=\min(m,n)$ and let the singular values be $s_1(A)\ge \cdots \ge s_k(A)\ge 0$ (with $s_{r}>0$ and $s_{r+1}=\cdots=s_k=0$ if $\mathrm{rank}(A)=r$). Write $s(A)=(s_1(A),\ldots,s_k(A))$.

• Spectral (operator) norm ($2\to 2$ norm):

  \[\norm{A} _2 = \max _{x\neq 0}\frac{\norm{Ax} _2}{\norm{x} _2} = \max _{\norm{x} _2=1}\norm{Ax} _2 = \max _{\norm{x} _2=1,\ \norm{y} _2=1} y^\top A x = s_1(A) = \norm{s(A)} _\infty.\]

• Induced (operator) $p$-norm:

  \[\norm{A} _p := \max _{x\neq 0}\frac{\norm{Ax} _p}{\norm{x} _p}, \qquad p\in[1,\infty].\]

Special cases:

• Frobenius (Hilbert-Schmidt) norm:

  \[\norm{A} _F = \sqrt{\sum _{i=1}^m\sum _{j=1}^n |A_{ij}|^2} = \sqrt{\mathrm{tr}(A^\top A)} = \sqrt{\langle A,A\rangle}, \qquad \langle A,B\rangle := \mathrm{tr}(A^\top B),\]

Equivalently:

• Nuclear norm:

  \[\norm{A} _* = \sum _{i=1}^k s_i(A) = \norm{s(A)} _1.\]

• Schatten $p$-norms (unifies spectral/Frobenius/nuclear):

  \[\norm{A} _{S,p} := \norm{s(A)} _p, \qquad p\in[1,\infty].\]

In particular,

Matrix Inequalities

Throughout, let $A\in\mathbb{R}^{m\times n}$ and $B\in\mathbb{R}^{n\times k}$.

Submultiplicativity (induced norms)

For any induced matrix norm,

In particular, for the spectral norm,

Operator norm ordering

For induced (operator) norms,

Also,

Mixed Frobenius and spectral norm bounds

With the spectral norm on one factor and the Frobenius norm on the other,

Frobenius norm submultiplicativity (weaker form)

Although $\norm{\cdot}_F$ is not an induced norm, it satisfies

Singular value (Schatten norm) inequalities

Let $s(A)$ denote the vector of singular values.

• Hölder inequality for Schatten norms:

  \[\norm{AB} _{S,r} \le \norm{A} _{S,p}\,\norm{B} _{S,q}, \qquad \frac{1}{p}+\frac{1}{q}=\frac{1}{r}.\]

• In particular,

  \[\norm{AB} _* \le \norm{A} _2\,\norm{B} _*, \qquad \norm{AB} _* \le \norm{A} _*\,\norm{B} _2.\]

Trace inequalities

For compatible matrices $A,B$,

The same Hölder argument with the nuclear and spectral norms in place of two Frobenius norms gives

Rank-dependent norm comparisons

If $\mathrm{rank}(A)=r$, then

and

These inequalities are matrix analogues of norm equivalence in finite dimensions.