Vector Norms

Our interest is in operators mapping vectors from a model space \(\mathbb{C}^n\) to a data space \(\mathbb{C}^m\).

There are some simple and useful results on relationships between different \(p\)-norms listed in this section. We also discuss some interesting properties of \(l_1\)-norm specifically.

Definition

Let \(v \in \mathbb{C}^n\). Let the entries in \(v\) be represented as

(1)\[v_i = r_i \exp (j \theta_i)\]

where \(r_i = | v_i |\) with the convention that \(\theta_i = 0\) whenever \(r_i = 0\).

The sign vector for \(v\) denoted by \(\sgn(v)\) is defined as

(2)\[\begin{split}\sgn(v) = \begin{bmatrix}\sgn(v_1) \\ \vdots \\ \sgn(v_N) \end{bmatrix}\end{split}\]

where

(3)\[\begin{split}\sgn(v_i) = \left\{ \begin{array}{ll} \exp (j \theta_i) & \mbox{if $r_i \neq 0$ };\\ 0 & \mbox{if $r_i = 0$ }. \end{array} \right.\end{split}\]

Lemma

For any \(v \in \mathbb{C}^n\) :

(4)\[\| v \|_1 = \sgn(v)^H v = \langle v , \sgn(v) \rangle.\]

Proof

(5)\[\| v \|_1 = \sum_{i=1}^n r_i = \sum_{i=1}^n \left [r_i e^{j \theta_i} \right ] e^{- j \theta_i} = \sum_{i=1}^n v_i e^{- j \theta_i} = \sgn(v)^H v.\]

Note that whenever \(v_i = 0\), corresponding \(0\) entry in \(\sgn(v)\) has no effect on the sum.

Lemma

Suppose \(v \in \mathbb{C}^n\). Then

(6)\[\| v \|_2 \leq \| v\|_1 \leq \sqrt{n} \| v \|_2.\]

Proof

For the lower bound, we go as follows

(7)\[\| v \|_2^2 = \sum_{i=1}^n | v_i|^2 \leq \left ( \sum_{i=1}^n | v_i|^2 + 2 \sum_{i, j, i \neq j} | v_i | | v_j| \right ) = \left ( \sum_{i=1}^n | v_i| \right )^2 = \| v \|_1^2.\]

This gives us

(8)\[\| v \|_2 \leq \| v \|_1.\]

We can write \(l_1\) norm as

(9)\[\| v \|_1 = \langle v, \sgn (v) \rangle.\]

By Cauchy-Schwartz inequality we have

(10)\[\langle v, \sgn (v) \rangle \leq \| v \|_2 \| \sgn (v) \|_2\]

Since \(\sgn(v)\) can have at most \(n\) non-zero values, each with magnitude 1,

(11)\[\| \sgn (v) \|_2^2 \leq n \implies \| \sgn (v) \|_2 \leq \sqrt{n}.\]

Thus, we get

(12)\[\| v \|_1 \leq \sqrt{n} \| v \|_2.\]

Lemma

Let \(v \in \mathbb{C}^n\). Then

(13)\[\| v \|_2 \leq \sqrt{n} \| v \|_{\infty}\]

Proof

(14)\[\| v \|_2^2 = \sum_{i=1}^n | v_i |^2 \leq n \underset{1 \leq i \leq n}{\max} ( | v_i |^2) = n \| v \|_{\infty}^2.\]

Thus

(15)\[\| v \|_2 \leq \sqrt{n} \| v \|_{\infty}.\]

Lemma

Let \(v \in \mathbb{C}^n\). Let \(1 \leq p, q \leq \infty\). Then

(16)\[\| v \|_q \leq \| v \|_p \text{ whenever } p \leq q.\]

Lemma

Let \(\OneVec \in \mathbb{C}^n\) be the vector of all ones i.e. \(\OneVec = (1, \dots, 1)\). Let \(v \in \mathbb{C}^n\) be some arbitrary vector. Let \(| v |\) denote the vector of absolute values of entries in \(v\). i.e. \(|v|_i = |v_i| \Forall 1 \leq i \leq n\). Then

(17)\[\| v \|_1 = \OneVec^T | v | = \OneVec^H | v |.\]

Proof

(18)\[\OneVec^T | v | = \sum_{i=1}^n | v |_i = \sum_{i=1}^n | v_i | = \| v \|_1.\]

Finally since \(\OneVec\) consists only of real entries, hence its transpose and Hermitian transpose are same.

Lemma

Let \(\OneMat \in \CC^{n \times n}\) be a square matrix of all ones. Let \(v \in \mathbb{C}^n\) be some arbitrary vector. Then

(19)\[|v|^T \OneMat | v | = \| v \|_1^2.\]

Proof

We know that

(20)\[\OneMat = \OneVec \OneVec^T\]

Thus,

(21)\[|v|^T \OneMat | v | = |v|^T \OneVec \OneVec^T | v | = (\OneVec^T | v | )^T \OneVec^T | v | = \| v \|_1 \| v \|_1 = \| v \|_1^2.\]

We used the fact that \(\| v \|_1 = \OneVec^T | v |\).

Theorem

\(k\)-th largest (magnitude) entry in a vector \(x \in \mathbb{C}^n\) denoted by \(x_{(k)}\) obeys

(22)\[| x_{(k)} | \leq \frac{\| x \|_1}{k}\]

Proof

Let \(n_1, n_2, \dots, n_N\) be a permutation of \(\{ 1, 2, \dots, n \}\) such that

(23)\[|x_{n_1} | \geq | x_{n_2} | \geq \dots \geq | x_{n_N} |.\]

Thus, the \(k\)-th largest entry in \(x\) is \(x_{n_k}\). It is clear that

(24)\[\| x \|_1 = \sum_{i=1}^n | x_i | = \sum_{i=1}^n |x_{n_i} |\]

Obviously

(25)\[|x_{n_1} | \leq \sum_{i=1}^n |x_{n_i} | = \| x \|_1.\]

Similarly

(26)\[k |x_{n_k} | = |x_{n_k} | + \dots + |x_{n_k} | \leq |x_{n_1} | + \dots + |x_{n_k} | \leq \sum_{i=1}^n |x_{n_i} | \leq \| x \|_1.\]

Thus

(27)\[|x_{n_k} | \leq \frac{\| x \|_1}{k}.\]