Open Problems:24 - Revision history

Krzysztof Onak: Workaround to fix a weird parsing/rendering problem.

2016-09-25T22:33:24Z

Workaround to fix a weird parsing/rendering problem.

Krzysztof Onak: updated header

2013-03-07T01:49:24Z

updated header

Krzysztof Onak at 05:21, 16 November 2012

2012-11-16T05:21:29Z

Krzysztof Onak: 1 revision

2012-11-08T05:33:51Z

1 revision

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Problem 24: “Ultimate” Deterministic Sparse Recovery}} {{Infobox |label1 = Proposed by |data1 = Piotr Indyk |label2 = Source |data2 = [[Workshops:Ka..."

2012-10-17T18:58:14Z

Created page with "{{DISPLAYTITLE:Problem 24: “Ultimate” Deterministic Sparse Recovery}} {{Infobox |label1 = Proposed by |data1 = Piotr Indyk |label2 = Source |data2 = [[Workshops:Ka..."

New page

{{DISPLAYTITLE:Problem 24: “Ultimate” Deterministic Sparse Recovery}}
{{Infobox
|label1 = Proposed by
|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
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 ==
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
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}}.

@@ Line 1: / Line 1: @@
 {{Header
 |source=kanpur09
 |who=Piotr Indyk

@@ Line 1: / Line 1: @@
-{{DISPLAYTITLE:Problem 24: &ldquo;Ultimate&rdquo; Deterministic Sparse Recovery}}
+{{Header
-{{Infobox
+|title=&ldquo;Ultimate&rdquo; Deterministic Sparse Recovery
-|label1 = Proposed by
+|source=kanpur09
-|data1 = Piotr Indyk
+|who=Piotr Indyk
 }}
 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

@@ Line 5: / Line 5: @@
 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 &ldquo;$L_2$/$L_1$&rdquo;
+$Ax$ a vector $x^* \in \mathbb R^n$ that satisfies the following &ldquo;$L_2/L_1$&rdquo;
 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 14: / Line 14: @@
 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
-a different &ldquo;$L_1$/$L_1$&rdquo; approximation guarantee, where  $\|x^*-x\|_1 \leq \min_{k\text{-sparse}\,x'}  C \|x'-x\|_1$ {{cite|IndykR-08|BerindeIR-08}}.
+a different &ldquo;$L_1/L_1$&rdquo; approximation guarantee, where  $\|x^*-x\|_1 \leq \min_{k\text{-sparse}\,x'}  C \|x'-x\|_1$ {{cite|IndykR-08|BerindeIR-08}}.

← Older revision	Revision as of 05:33, 8 November 2012
(No difference)