Problem 51: “For All” Guarantee for Computationally Bounded Adversaries

Suggested by	Martin Strauss
Source	Dortmund 2012
Short link	https://sublinear.info/51

There are two types of compressed sensing guarantees, illustrated using two players:

For all: Charlie constructs the sensing matrix $\phi$, and then Mallory constructs the signal $x=x(\phi)$ as a function of $\phi$. The Compressed Sensing question is to recover the approximate signal $\tilde x$ from the measurement $\phi x$. The best guarantee possible is the following $\ell_2/\ell_1$ guarantee: $$ ||\tilde x - x||_2 \le \epsilon/\sqrt{k} ||x_{opt} - x||_1. $$

For each: Charlie construct a distribution $D$ over sensing matrices $\phi$. Then Mallory constructs a vector $x=x(D)$ dependent on the distribution only. Finally, a sensing matrix $\phi$ is sampled from the distribution $D$. The goal is again to recover $\tilde x$, with good probability over the choice of $\phi$. It turns out a stronger guarantee, termed $\ell_2/\ell_2$, is possible: $$ ||\tilde x - x||_2 \le (1+\epsilon)||x_{opt} - x||_2 $$

In some sense the two "worlds" are incomparable: the first one works for all $x$ but obtains weaker error guarantee, and the second one works for each $x$ with some probability but gets better error guarantee.

Question is: How can we get the best of both worlds ("for all" with $\ell_2/\ell_2$ error) ?

Once we require "for all", it is provably impossible to obtain $\ell_2/\ell_2$ guarantee. But what if Mallory has bounded computational resources to construct a "bad" $x$?

A preliminary result considers the following setting. Mallory sees $\phi$ and writes down a sketch of $\phi$ (in bounded space). Then Mallory produces $x$ from this sketch only. Then $\ell_2/\ell_2$ is possible for such $x$'s.

Generally, we would like to allow Mallory to be probabilistic polynomial time, and have a $\phi$ so that Mallory still cannot find an input $x=x(\phi)$ that breaks the recovery algorithm.