Open Problems:51 - Revision history

Krzysztof Onak: updated header

2013-03-07T01:59:45Z

updated header

Krzysztof Onak at 04:37, 12 December 2012

2012-12-12T04:37:01Z

Andoni at 02:28, 12 December 2012

2012-12-12T02:28:09Z

Andoni at 01:25, 12 December 2012

2012-12-12T01:25:12Z

Andoni at 01:24, 12 December 2012

2012-12-12T01:24:55Z

Andoni: 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,..."

2012-12-12T01:22:17Z

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,..."

New page

{{Header
|title=``For all'' guarantee for computationally bounded adversaries
|source=dortmund12
|who=Martin Strauss
}}

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.

@@ Line 1: / Line 1: @@
 {{Header
 |source=dortmund12
 |who=Martin Strauss

@@ Line 1: / Line 1: @@
 {{Header
-|title="For all" guarantee for computationally bounded adversaries
+|title=&ldquo;For All&rdquo; Guarantee for Computationally Bounded Adversaries
 |source=dortmund12
 |who=Martin Strauss
@@ Line 7: / Line 7: @@
 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 "worlds" are incomparable: the first one works
+In some sense the two &ldquo;worlds&rdquo; 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
+'''Question:''' How can we get the best of both worlds (&ldquo;for all&rdquo; 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$?
+Once we require &ldquo;for all&rdquo;, it is provably impossible to obtain $\ell_2/\ell_2$ guarantee. But what if Mallory has bounded computational resources to construct a &ldquo;bad&rdquo; $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