Difference between revisions of "Open Problems:51"
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |title= | + | |title=“For All” Guarantee for Computationally Bounded Adversaries |
|source=dortmund12 | |source=dortmund12 | ||
|who=Martin Strauss | |who=Martin Strauss | ||
| Line 7: | Line 7: | ||
using two players: | 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 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_{\rm 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.$$ | + | * ''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_{\rm opt} - x||_2.$$ |
| − | In some sense the two | + | In some sense the two “worlds” are incomparable: the first one works |
for all $x$ but obtains weaker error guarantee, and the second one | for all $x$ but obtains weaker error guarantee, and the second one | ||
works for each $x$ with some probability but gets better error guarantee. | works for each $x$ with some probability but gets better error guarantee. | ||
| − | '''Question | + | '''Question:''' How can we get the best of both worlds (“for all” with |
$\ell_2/\ell_2$ error) ? | $\ell_2/\ell_2$ error) ? | ||
| − | Once we require | + | 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 | 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 | ||
Revision as of 04:37, 12 December 2012
| 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_{\rm 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_{\rm 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: 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.
