Difference between revisions of "Open Problems:24"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
(Created page with "{{DISPLAYTITLE:Problem 24: “Ultimate” Deterministic Sparse Recovery}} {{Infobox |label1 = Proposed by |data1 = Piotr Indyk |label2 = Source |data2 = [[Workshops:Ka...")
 
(Workaround to fix a weird parsing/rendering problem.)
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
{{DISPLAYTITLE:Problem 24: “Ultimate” Deterministic Sparse Recovery}}
+
{{Header
{{Infobox
+
|source=kanpur09
|label1 = Proposed by
+
|who=Piotr Indyk
|data1 = Piotr Indyk
 
|label2 = Source
 
|data2 = [[Workshops:Kanpur_2009|Kanpur 2009]]
 
|label3 = Short link
 
|data3 = http://sublinear.info/24
 
 
}}
 
}}
 
We say that a vector $v \in \mathbb R^n$ is ''$k$-sparse'' for some $k \in \{0,\ldots,n\}$ if there are no more than $k$ non-zero coordinates in $v$. The goal in the problem being considered is to  
 
We say that a vector $v \in \mathbb R^n$ is ''$k$-sparse'' for some $k \in \{0,\ldots,n\}$ if there are no more than $k$ non-zero coordinates in $v$. The goal in the problem being considered is to  
 
design an $m \times n$ matrix $A$ such that for any $x \in R^n$, one can recover from
 
design an $m \times n$ matrix $A$ such that for any $x \in R^n$, one can recover from
$Ax$ a vector $x^* \in \mathbb R^n$ that satisfies the following “$L_2$/$L_1$”
+
$Ax$ a vector $x^* \in \mathbb R^n$ that satisfies the following “$L_2/L_1$”
 
approximation guarantee:\[  \left\|x^*-x\right\|_2 \leq \min_{k\text{-sparse}\,x'\in\mathbb R^n}  \frac{C}{\sqrt{k}}  \left\|x'-x\right\|_1,\]where $C>0$ is a constant.
 
approximation guarantee:\[  \left\|x^*-x\right\|_2 \leq \min_{k\text{-sparse}\,x'\in\mathbb R^n}  \frac{C}{\sqrt{k}}  \left\|x'-x\right\|_1,\]where $C>0$ is a constant.
  
Line 19: Line 14:
 
It is known that one can achieve ''either'' (a) ''or'' (b) (see,
 
It is known that one can achieve ''either'' (a) ''or'' (b) (see,
 
e.g., {{cite|NeedellT-10}}). It is also possible to achieve both (a) and (b), but with
 
e.g., {{cite|NeedellT-10}}). It is also possible to achieve both (a) and (b), but with
a different “$L_1$/$L_1$” approximation guarantee, where  $\|x^*-x\|_1 \leq \min_{k\text{-sparse}\,x'}  C \|x'-x\|_1$ {{cite|IndykR-08|BerindeIR-08}}.
+
a different “$L_1/L_1$” approximation guarantee, where  $\|x^*-x\|_1 \leq \min_{k\text{-sparse}\,x'}  C \|x'-x\|_1$ {{cite|IndykR-08|BerindeIR-08}}.

Latest revision as of 22:33, 25 September 2016

Suggested by Piotr Indyk
Source Kanpur 2009
Short link https://sublinear.info/24

We say that a vector $v \in \mathbb R^n$ is $k$-sparse for some $k \in \{0,\ldots,n\}$ if there are no more than $k$ non-zero coordinates in $v$. The goal in the problem being considered is to design an $m \times n$ matrix $A$ such that for any $x \in R^n$, one can recover from $Ax$ a vector $x^* \in \mathbb R^n$ that satisfies the following “$L_2/L_1$” approximation guarantee:\[ \left\|x^*-x\right\|_2 \leq \min_{k\text{-sparse}\,x'\in\mathbb R^n} \frac{C}{\sqrt{k}} \left\|x'-x\right\|_1,\]where $C>0$ is a constant.

We conjecture that there is a solution that (a) uses $m=O(k \log (n/k))$ and (b) supports recovery algorithms running in time $O(n \operatorname{polylog} n)$.

Background[edit]

It is known that one can achieve either (a) or (b) (see, e.g., [NeedellT-10]). It is also possible to achieve both (a) and (b), but with a different “$L_1/L_1$” approximation guarantee, where $\|x^*-x\|_1 \leq \min_{k\text{-sparse}\,x'} C \|x'-x\|_1$ [IndykR-08,BerindeIR-08].