5 5 10 Compress Sensing

In this exercise, our goal is to compress efficiently sparse signals in $\mathbb{R}^p$. The strategy proposed by Candès, Romberg and Tao [48] and Donoho [67] is to multiply the signal by a matrix $A \in \mathbb{R}^{m \times p}$ with $m$ smaller than $p$. We have in mind that the signals are coordinate sparse, with at most $k$ non-zero entries. We will answer the two questions: - How can we decompress efficiently the signals?
- For which value of $m$ are we able to compress / decompress any $k$-sparse signal with no loss?

Let us formalize this problem. Let $x^* \in \mathbb{R}^p$ be a vector with at most $k$ nonzero entries. Write $\operatorname{supp}\left(x^*\right)=\left\{j: x_j^* \neq 0\right\}$ for the (unknown) support of $x^*$. Let $y=A x^*$ be the compressed siggnal and define the decompression algorithm

(1)

\begin{align} \hat{x} \in \underset{x \in \mathbb{R}^p: A x=y}{\operatorname{argmin}}|x|_1, \end{align}

with $|x|_1$ the $\ell^1$-norm of $x$.

A) Null Space Property

In this problem, for any set $S \subset\{1, \ldots, p\}$ and any vector $v \in \mathbb{R}^p$, we denote by $v_S$ the vector in $\mathbb{R}^p$ with entries

(2)

\begin{align} \left[v_S\right]_j=v_j \mathbf{1}_{j \in S}, \quad \text { for } j=1, \ldots, p . \end{align}

The matrix $A \in \mathbb{R}^{m \times p}$ is said to fulfill the null space property, $\operatorname{NSP}(k)$, if for any $v \in \operatorname{ker}(A) \backslash\{0\}$ and any $S \subset\{1, \ldots, p\}$ with cardinality $|S|=k$,

(3)

\begin{align} \text { we have }\left|v_S\right|_1<\left|v_{S^c}\right|_1 \text {. } \end{align}

1. We prove that if $A$ fulfills the nullspace property, then there is a unique solution to (1), which is $\hat{x}=x^*$.

Since $| \operatorname{supp} (x^*) | \leq k$, we can choose $S \subset \{ 1, \dots, p \}$ such that $| S | = k$ and $\operatorname{supp} (x^*) \subset S$. Let $z \in \mathbb{R}^p \backslash \{ x^* \}$ such that $Az = y$. Then $x^* - z \in \operatorname{ker} (A) \backslash \{0\}$ and because $A$ fulfills $\operatorname{NSP} (k)$:

(4)

\begin{align} | x^* |_1 = | x^*_S |_1 \leq_{\text{(Triangle inequality)}} | x^*_S - z_S |_1 + | z_S |_1 < | z_{S^c} |_1 + | z_S |_1 = | z |_1 \end{align}

This proves that $x^*$ is solution to (1) and that any other solution to $Ax = y$ has strictly higher $\ell^1$-norm, therefore $x^*$ is the unique solution to (1).

B) Restricted Isometry Property Enforces Null Space Property

Let $\delta \in(0,1)$. The matrix $A$ is said to fulfill the $(d, \delta)$-Restricted Isometry Property, abbreviated $(d, \delta)$-RIP, if $1-\delta \leq\|A u\|^2 \leq 1+\delta, \quad$ for all $u \in \mathbb{R}^p$ such that $|u|_0 \leq d$ and $\|u\|=1$,
where $\|u\|$ is the Euclidean norm of $u$ and $|u|_0=|\operatorname{supp}(u)|$. In this part, we will prove that the $(2 k, \delta)$-RIP property with $\delta<1 / 3$ enforces the Null Space Property (5.36).
Let $A$ be a matrix fulfilling the $(2 k, \delta)$-RIP property with $\delta<1 / 3$. Let $v \in \operatorname{ker}(A) \backslash$ $\{0\}$ and let

(5)

\begin{align} \left|v_{i_1}\right| \geq\left|v_{i_2}\right| \geq \ldots \geq\left|v_{i_p}\right| \end{align}

be the absolute values of the entries of $v$ ranked in decreasing order. Let $J$ denote the integer part of $p / k$ and define $S_j=\left\{i_{k j+1}, \ldots, i_{k(j+1)}\right\}$ for $j=0, \ldots, J-1$ and $S_J=\left\{i_{k J+1}, \ldots, i_p\right\}$.

1. For $j=0, \ldots, J$, let us set $\bar{v}_{S_j}=v_{S_j} /\left\|v_{S_j}\right\|$. Then, for $j=1, \ldots, J$:

(6)

\begin{align} \operatorname{supp} (\bar{v}_{S_0}) \cap \operatorname{supp} (\bar{v}_{S_j}) = \emptyset \quad \text{hence} \quad \langle \bar{v}_{S_0}, \bar{v}_{S_j} \rangle = 0 \quad \text{hence} \quad \|\bar{v}_{S_0} \pm \bar{v}_{S_j}\|^2 = \|\bar{v}_{S_0} \|^2 + \| \bar{v}_{S_j} \|^2 = 2 \end{align}

We deduce:

(7)

\begin{aligned} -\left\langle A \bar{v}_{S_0}, A \bar{v}_{S_j}\right\rangle &= \frac{1}{4} \left( \left\| A \left( \bar{v}_{S_0} - \bar{v}_{S_j} \right) \right\|^2 - \left\| A \left(\bar{v}_{S_0} + \bar{v}_{S_j} \right) \right\|^2 \right) \\ &= \frac{1}{2} \left( \left\| A u^-_j \right\|^2 - \left\| A u^+_j \right\|^2 \right) \leq \delta \end{aligned}

because $u^\pm_j := \frac{1}{\sqrt{2}} ( \bar{v}_{S_0} \pm \bar{v}_{S_j} )$ verifies $\| u^\pm_j \| = 1$ and $| u^\pm_j |_0 \leq | \bar{v}_{S_0} |_0 + | \bar{v}_{S_j} |_0 \leq 2k$.

2. Then we prove that:

(8)

\begin{aligned} \left\| A v_{S_0} \right\|^2 &= \left\langle A v_{S_0}, Av - \sum_{j=1}^J A v_{S_j} \right\rangle \\ &=_{(Av = 0)} - \sum_{j=1}^J \left\langle A v_{S_0}, A v_{S_j} \right\rangle \\ &= - \sum_{j=1}^J \left\langle A \bar{v}_{S_0}, A \bar{v}_{S_j} \right\rangle \left\| v_{S_0} \right\| \left\| v_{S_j} \right\| \\ &\leq_{\text{(Question 1)}} \delta \sum_{j=1}^J \left\| v_{S_0} \right\| \left\| v_{S_j} \right\| \end{aligned}

3. Now we check that:

(9)

\begin{align} \left\|v_{S_j}\right\| \leq \left| v_{S_j} \right|_0^{1/2} \left| v_{S_j} \right|_\infty \leq k^{1/2} \frac{1}{k} \left| v_{S_{j-1}} \right|_1 = k^{-1/2} \left| v_{S_{j-1}} \right|_1 \quad \text{for} \quad j=1, \ldots, J \end{align}

and by the Cauchy-Schwarz inequality (we define $\varepsilon$ the vector of the signs of $v$):

(10)

\begin{align} \left| v_{S_0} \right|_1 = \left\langle v_{S_0}, \varepsilon_{S_0} \right\rangle \leq \left\| \varepsilon_{S_0} \right\| \left\| v_{S_0} \right\| = \sqrt{k} \left\| v_{S_0} \right\| \end{align}

4. Putting pieces together, we derive the bound:

(11)

\begin{aligned} \delta \sum_{j=1}^J \left| v_{S_{j-1}} \right|_1 &\geq \delta k^{1/2} \sum_{j=1}^J \left\| v_{S_j} \right\| \\ &\geq k^{1/2} \frac{\left\| A v_{S_0} \right\|^2}{\left\| v_{S_0} \right\|} \\ &\geq \left| v_{S_0} \right|_1 \left\| A \bar{v}_{S_0} \right\|^2 \\ &\geq (1 - \delta) \left| v_{S_0} \right|_1 \end{aligned}

Therefore:

(12)

\begin{align} \left| v_{S_0} \right|_1 \leq \frac{\delta}{1 - \delta} \sum_{j=1}^J\left| v_{S_{j-1}} \right|_1 \end{align}

5. Finally, we prove that the null space property $\operatorname{NSP}(k)$ holds for any matrix $A$ fulfilling the $(2 k, \delta)$-RIP property with $\delta < 1/3$.

To do so, we transform a little last question's inequality:

(13)

\begin{align} \left| v_{S_0} \right|_1 \leq \frac{\delta}{1 - \delta} \left( \left| v_{S_0^c} \right|_1 - \left| v_{S_J} \right|_1 + \left| v_{S_0} \right|_1 \right) \end{align}

which implies:

(14)

\begin{align} \left| v_{S_0} \right|_1 \leq \frac{\delta}{1 - 2 \delta} \left| v_{S_0^c} \right|_1 \end{align}

which, since $\delta < \frac{1}{3}$, in turn implies:

(15)

\begin{align} \left| v_{S_0} \right|_1 < \left| v_{S_0^c} \right|_1 \end{align}

To complete the proof, let us remember that we sorted the absolute coordinates of $v$ in descending order when partitioning $\{1, \dots, p \} = S_0 \coprod \dots \coprod S_J$, so that:

(16)

\begin{align} \left| v_{S_0} \right|_1 = \max_{S \subset \{1, \dots, p\}, |S| = k} \left| v_S \right|_1 \quad \text{and} \quad \left| v_{S_0^c} \right|_1 = \min_{S \subset \{1, \dots, p\}, |S| = k} \left| v_{S^c} \right|_1 \end{align}

C) RIP by Random Sampling

It remains to build a matrix $A$ fulfilling the $(2 k, \delta)$-RIP property with $\delta<1 / 3$. The goal of this part is to show that such a matrix can be obtained by random sampling. More precisely, let $B \in \mathbb{R}^{m \times p}$ be a matrix with entries $B_{i j}$ i.i.d. with $\mathscr{N}(0,1)$ Gaussian distribution. We will prove in this part, that for any $\delta \in(0,1 / 3)$ and any

(17)

\begin{align} m \geq \frac{9}{\delta^2} \left( \sqrt{d}+\sqrt{2 L+2 d \log (e p / d)} \right)^2, \quad \text { with } L \geq 0, \end{align}

the matrix $A=m^{-1 / 2} B$ fulfills the $(d, \delta)$-RIP property with probability at least $1-$ $2 e^{-L}$.

The first question below relies on the following bound (Lemma 8.3, page 163; see also Exercise 12.9.6, page 288): for $E \in \mathbb{R}^{d_1 \times d_2}$ with i.i.d. entries with $\mathscr{N}(0,1)$ Gaussian distribution, we have $\mathbb{E}\left[|E|_{\mathrm{op}}\right] \leq \sqrt{d_1}+\sqrt{d_2}$.

1. Let $S \subset\{1, \ldots, p\}$ with cardinality $|S|=d$. To prove that for any $t>0$

(18)

\begin{align} \mathbb{P}[\max \{\|B u\|:\|u\|=1, \operatorname{supp}(u) \subset S\} \geq \sqrt{m}+\sqrt{d}+\sqrt{2 t}] \leq e^{-t} \end{align}

we first rewrite the random variable as the operator norm of a random matrix $B_S = B P_S \in \mathbb{R}^{m \times d}$ where $P_S: \mathbb{R}^p \rightarrow \mathbb{R}^d$ is the semi-unitary matrix that represents the orthogonal projection onto $\operatorname{Vect} (S)$.

Then, using the Lemma 8.3, we get $\mathbb{E} [ |B_S|_{\mathrm{op}} ] \leq \sqrt{m} + \sqrt{d}$.

To conclude the proof, one need only justify that $|B_S|_{\mathrm{op}}$ is subgaussian $(1)$, which follows from the Gaussian concentration inequality (B.2), page 301, combined with the fact that $B \mapsto |B|_{\mathrm{op}} \leq |B|_F$ is $1$-Lipschitz.

2. Finally, let us fix $m$ fulfilling (5.38) and $L > 0$. Since we have $\delta \leq 3$, a simple derivative calculation gives:

(19)

\begin{align} \sqrt{1 + \delta} - 1 \geq \frac\delta3 \end{align}

Therefore, for $t = L + d \log \left( \frac{ep}{d} \right) > 0$:

(20)

\begin{aligned} \left( \sqrt{1 + \delta} - 1 \right) \sqrt m &\geq \sqrt d + \sqrt{2t} \\ \sqrt{1 + \delta}\, \sqrt m &\geq \sqrt m + \sqrt d + \sqrt{2t} \end{aligned}

Finally:

(21)

\begin{aligned} &\mathbb{P} \left[ \|A u\|^2 \leq 1 + \delta \quad \text{for all} \quad u \in \mathbb{R}^p \quad \text{such that} \quad |u|_0 \leq d \quad \text{and} \quad \|u\| = 1 \right] \\ &= \mathbb{P} \left[ \|B u\| \leq \sqrt{1 + \delta}\, \sqrt m \quad \text{for all} \quad u \in \mathbb{R}^p \quad \text{such that} \quad |u|_0 \leq d \quad \text{and} \quad \|u\| = 1 \right] \\ &\geq \mathbb{P} \left[ \|B u\| \leq \sqrt m + \sqrt d + \sqrt{2t} \quad \text{for all} \quad u \in \mathbb{R}^p \quad \text{such that} \quad |u|_0 \leq d \quad \text{and} \quad \|u\| = 1 \right] \\ &= 1 - \mathbb{P} \left[ \bigcup_{S \subset \{ 1, \dots, p \}, |S| = d} \overline{\Omega_{S, t}} \right] \quad \text{where}\ \Omega_{S, t} \ \text{is the event considered in the last question} \\ &\geq 1 - C_p^d \mathrm{e}^{-t} \\ &\geq 1 - \exp \left(d \log \left( \frac{ep}{d} \right) - t \right) = 1 - \mathrm{e}^{-L} \quad \text{by Lemma 2.1, page 36} \end{aligned}

The lower bound $\|A u\|^2 \geq 1-\delta$ can be proved in the same way.