Difference between revisions of "Open Problems:51"
(Created page with "{{Header |title=``For all'' guarantee for computationally bounded adversaries |source=dortmund12 |who=Martin Strauss }} There are two types of compressed sensing guarantees,...") |
m (updated header) |
||
| (4 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
{{Header | {{Header | ||
| − | |||
|source=dortmund12 | |source=dortmund12 | ||
|who=Martin Strauss | |who=Martin Strauss | ||
}} | }} | ||
| − | |||
| − | |||
There are two types of compressed sensing guarantees, illustrated | There are two types of compressed sensing guarantees, illustrated | ||
using two players: | using two players: | ||
| − | ''For all'': Charlie constructs the sensing matrix $\phi$, and then | + | * ''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.$$ |
| − | 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 | + | * ''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.$$ |
| − | 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 | + | 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$? |
| − | $\ell_2/\ell_2$ guarantee. But what if Mallory has bounded | ||
| − | computational resources to construct a | ||
| − | A preliminary result considers the following setting. Mallory sees | + | 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 |
| − | $\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. | possible for such $x$'s. | ||
| − | Generally, we would like to allow Mallory to be probabilistic | + | 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. |
| − | polynomial time, and have a $\phi$ so that Mallory still cannot find | ||
| − | an input $x=x(\phi)$ that breaks the recovery algorithm. | ||
Latest revision as of 01:59, 7 March 2013
| 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.
