Difference between revisions of "Open Problems:51"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m (updated header)
 
(2 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
{{Header
 
{{Header
|title="For all" guarantee for computationally bounded adversaries
 
 
|source=dortmund12
 
|source=dortmund12
 
|who=Martin Strauss
 
|who=Martin Strauss
Line 7: Line 6:
 
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 "worlds" are incomparable: the first one works
+
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 is''': How can we get the best of both worlds ("for all" with
+
'''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 "for all", it is provably impossible to obtain
+
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 "bad" $x$?
 
  
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.