p-norms and sparse signals

l1 , l2 and max norms

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 \CC^N\). Let the entries in \(v\) be represented as

\[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

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

where

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

Lemma

For any \(v \in \CC^N\) :

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

Proof

\[\| 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 \CC^N\). Then

\[\| v \|_2 \leq \| v\|_1 \leq \sqrt{N} \| v \|_2.\]

Proof

For the lower bound, we go as follows

\[\| 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

\[\| v \|_2 \leq \| v \|_1.\]

We can write \(l_1\) norm as

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

By Cauchy-Schwartz inequality we have

\[\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,

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

Thus, we get

\[\| v \|_1 \leq \sqrt{N} \| v \|_2.\]

Lemma

Let \(v \in \CC^N\). Then

\[\| v \|_2 \leq \sqrt{N} \| v \|_{\infty}\]

Proof

\[\| 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

\[\| v \|_2 \leq \sqrt{N} \| v \|_{\infty}.\]

Lemma

Let \(v \in \CC^N\). Let \(1 \leq p, q \leq \infty\). Then

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

Proof

TBD

Lemma

Let \(\OneVec \in \CC^N\) be the vector of all ones i.e. \(\OneVec = (1, \dots, 1)\). Let \(v \in \CC^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

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

Proof

\[\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 \CC^N\) be some arbitrary vector. Then

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

Proof

We know that

\[\OneMat = \OneVec \OneVec^T\]

Thus,

\[|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 \CC^N\) denoted by \(x_{(k)}\) obeys

\[| 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

\[|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

\[\| x \|_1 = \sum_{i=1}^N | x_i | = \sum_{i=1}^N |x_{n_i} |\]

Obviously

\[|x_{n_1} | \leq \sum_{i=1}^N |x_{n_i} | = \| x \|_1.\]

Similarly

\[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

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

Sparse signals

In this section we explore some useful properties of \(\Sigma_K\), the set of \(K\)-sparse signals in standard basis for \(\CC^N\).

We recall that

\[\Sigma_K = \{ x \in \CC^N : \| x \|_0 \leq K \}.\]

We established before that this set is a union of \(\binom{N}{K}\) subspaces of \(\CC^N\) each of which is is constructed by an index set \(\Lambda \subset \{1, \dots, N \}\) with \(| \Lambda | = K\) choosing \(K\) specific dimensions of \(\CC^N\).

We first present some lemmas which connect the \(l_1\), \(l_2\) and \(l_{\infty}\) norms of vectors in \(\Sigma_K\).

Lemma

Suppose \(u \in \Sigma_K\). Then

\[\frac{\| u\|_1}{\sqrt{K}} \leq \| u \|_2 \leq \sqrt{K} \| u \|_{\infty}.\]

Proof

We can write \(l_1\) norm as

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

By Cauchy-Schwartz inequality we have

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

Since \(u \in \Sigma_K\), \(\sgn(u)\) can have at most \(K\) non-zero values each with magnitude 1. Thus, we have

\[\| \sgn (u) \|_2^2 \leq K \implies \| \sgn (u) \|_2 \leq \sqrt{K}\]

Thus we get the lower bound

\[\| u \|_1 \leq \| u \|_2 \sqrt{K} \implies \frac{\| u \|_1}{\sqrt{K}} \leq \| u \|_2.\]

Now \(| u_i | \leq \max(| u_i |) = \| u \|_{\infty}\). So we have

\[\| u \|_2^2 = \sum_{i= 1}^{N} | u_i |^2 \leq K \| u \|_{\infty}^2\]

since there are only \(K\) non-zero terms in the expansion of \(\| u \|_2^2\).

This establishes the upper bound:

\[\| u \|_2 \leq \sqrt{K} \| u \|_{\infty}\]