3.6 Summary

Review

Last time we proved that for each $k\le c_0\frac{n}{logN/n}$ , there exists an $n\times N$ matrix $\Phi$ and a decoder $\Delta$ such that

• (a)

  $\parallel x-\Delta \Phi \left(x\right){\parallel }_{{\ell }_1}\le c_0{\sigma }_k(x{)}_{{\ell }_1}$

• (b)

  $\parallel x-\Delta \Phi \left(x\right){\parallel }_{{\ell }_2}\le c_0\frac{{\sigma }_k(x{)}_{{\ell }_1}}{\sqrt{k}}$

Deficiencies

Decoding is not implementable

Our decoding “algorithm” is:

We cannot generate such φ

The construction of a $\Phi$ from realizations of Gaussian random variables is guaranteed to work with high probability.However, we would like to know, given a particular instance of $\Phi$ , do (a) and (b) still hold. Unfortunately, this is impossible to check (since, to show that $\Phi$ satisfies the MRIP for $k$ , we need to consider all possible submatrices of $\Phi$ ). Furthermore, we would like to build $\Phi$ that can be implemented in circuits. We also might wantfast decoders $\Delta$ for these $\Phi$ . Thus we also may need to be more restrictive in building $\Phi$ . Two possible approaches that move in this direction are as follows:

• Find $\Phi$ that we can build such that we can prove instance optimality in ${\ell }_1$ for a smaller range of $k$ , i.e.,
  $$\parallel x-\Delta \Phi \left(x\right){\parallel }_{{\ell }_1}\le c_0{\sigma }_k(x{)}_{{\ell }_1}$$
  for $k<K$ . If we are willing to sacrifice and let $K$ be smaller than before, for example, $K\approx \sqrt{n}$ , then we might be able to prove that ${\Phi }_T^t{\Phi }_T$ is diagonally dominant for all $T$ such that $♯T=2k$ , which would ensure that $\Phi$ satisfies the MRIP.
• Consider $\Phi \left(\omega \right)$ where $\omega$ is a random seed that generates a $\Phi$ . It is possible to show that give $x$ , with high probability, $\Phi \left(\omega \right)\left(x\right)=y$ encodes $x$ in an ${\ell }_2$ -instance optimal fashion:
  $$\parallel x-\overline{x}{\parallel }_{{\ell }_2}\le 2{\sigma }_k(x{)}_{{\ell }_2}$$
  for $k\le c_0\frac{n}{(logN/n{)}^{5/2}}$ . Thus, by generating many such matrices we can recover any $x$ with high probability.

Encoding signals

Another practical problem is that of encoding the measurements $y$ . In a real system these measurements must be quantized. This problem was addressed by Candes, Romberg,and Tao in their paper Stable Signal Recovery from Incomplete and Inaccurate Measurements. They prove that if $y$ is quantized to $\overline{y}$ , and if $x\in U\left({\ell }_p\right)$ for $p\le 1$ , then we get optimal performance in terms the number of bits requiredfor a given accuracy. Notice that their result applies only to the case where $p\le 1$ . One might expect that this argument could be extended to $p$ between 1 and 2, but a warning is in order at this stage:

Fix $1<p\le 2$ . Then there exist $\Phi$ and $\Delta$ satisfying

Examples:

• $p=1$ , we get our original results
• $p=2$ , we do not get instance optimal for $k=1$ unless $n\approx N$
• $p=\frac{3}{2}$ , we only get instance optimal if $k\le c_0{N}^{-2}{\left(\frac{n}{logN/n}\right)}^3$