Sparse Vectors

In this section we explore some useful properties of \(\Sigma_k\), the set of \(k\)-sparse signals in standard basis for \(\mathbb{C}^n\).

We recall that

(1)\[\Sigma_k = \{ x \in \mathbb{C}^n : \| x \|_0 \leq k \}.\]

This set is a union of \(\binom{n}{k}\) subspaces of \(\mathbb{C}^n\) each of which is is constructed by an index set \(\Lambda \subset \{1, \dots, n \}\) with \(| \Lambda | = k\) choosing \(k\) specific dimensions of \(\mathbb{C}^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

(2)\[\frac{\| u\|_1}{\sqrt{k}} \leq \| u \|_2 \leq \sqrt{k} \| u \|_{\infty}.\]

Proof

We can write \(l_1\) norm as

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

By Cauchy-Schwartz inequality we have

(4)\[\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

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

Thus we get the lower bound

(6)\[\| 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

(7)\[\| 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:

(8)\[\| u \|_2 \leq \sqrt{k} \| u \|_{\infty}\]