Open Problems:50 - Revision history

Krzysztof Onak at 22:15, 11 October 2013

2013-10-11T22:15:44Z

24.218.75.233 at 04:25, 11 October 2013

2013-10-11T04:25:51Z

Krzysztof Onak at 19:00, 19 April 2013

2013-04-19T19:00:58Z

192.54.222.27 at 17:29, 17 April 2013

2013-04-17T17:29:45Z

192.54.222.27 at 17:20, 17 April 2013

2013-04-17T17:20:30Z

Krzysztof Onak: updated header

2013-03-07T01:56:20Z

updated header

Krzysztof Onak: Created page with "{{Header |title=Sparse Recovery for Tree Models |source=bertinoro11 |who=Piotr Indyk }} For any $n=2^{h}-1$, we can identify the coordinates of a vector $v \in \mathbb R^n$ w..."

2012-12-06T23:53:07Z

Created page with "{{Header |title=Sparse Recovery for Tree Models |source=bertinoro11 |who=Piotr Indyk }} For any $n=2^{h}-1$, we can identify the coordinates of a vector $v \in \mathbb R^n$ w..."

New page

{{Header
|title=Sparse Recovery for Tree Models
|source=bertinoro11
|who=Piotr Indyk
}}
For any $n=2^{h}-1$, we can identify the coordinates of a vector $v \in \mathbb R^n$ with the nodes of a full binary tree $B_h$ of height $h$ and root $1$. We define a ''$k$-sparse tree model'' ${\mathcal T}_k$ to be a set of all $T \subset [n]$ of size $k$ which form a connected subtree in $B_h$ rooted at $1$.

We want to
design an $m \times n$ matrix $A$ such that for any $x \in \mathbb R^n$, one can recover from
$Ax$ a vector $x^* \in \mathbb R^n$ such that:

\[ \left\|x^*-x\right\|_1 \leq \min_{x'\in\mathbb R^n,\ \operatorname{supp}(x') \subset T \mbox{ for some } T \in {\mathcal T}_k } C \left\|x'-x\right\|_1,
\]
where $\operatorname{supp}(x')$ is the set of non-zero coefficients of $x'$, and $C>0$ is a constant.

'''Question:''' Is it possible to achieve $m=O(k)$ for some constant $C>0$?

'''Background:''' It is known that a weaker bound of $m=O(k \log(n/k))$ is possible to achieve even if ${\mathcal T}_k$ is replaced by the set of all $k$-subsets of $[n]$ {{cite|CandesRT-06a}}. However, since $|{\mathcal T}_k | =\exp(O(k))$, one can expect a better bound for ${\mathcal T}_k$. By using ''model-based compressive sensing'' framework of {{cite|BaraniukCDH-10}} (cf. {{cite|IndykP-11}}), one can achieve the desired bound of $m=O(k)$ but with ''superconstant'' $C$.

← Older revision		Revision as of 22:15, 11 October 2013
Line 18:		Line 18:

	==Update==		==Update==
−	Indyk and Razenshteyn {{cite\|IndykR-13}} improved the bound on $m$ to $O(k \log(n / k) / \log \log (n / k))$ for constant $C$. In a follow-up paper {{cite\|BahBC-14}} ~~Bah et al.~~ presented an ''efficient'' recovery algorithm for this number of measurements.	+	Indyk and Razenshteyn {{cite\|IndykR-13}} improved the bound on $m$ to $O(k \log(n / k) / \log \log (n / k))$ for constant $C$. In a follow-up paper, Bah et al. {{cite\|BahBC-14}} presented an ''efficient'' recovery algorithm for this number of measurements.

← Older revision		Revision as of 04:25, 11 October 2013
Line 18:		Line 18:

	==Update==		==Update==
−	Indyk and Razenshteyn {{cite\|IndykR-13}} improved the bound on $m$ to $O(k \log(n / k) / \log \log (n / k))$ for constant $C$.	+	Indyk and Razenshteyn {{cite\|IndykR-13}} improved the bound on $m$ to $O(k \log(n / k) / \log \log (n / k))$ for constant $C$. In a follow-up paper {{cite\|BahBC-14}} Bah et al. presented an ''efficient'' recovery algorithm for this number of measurements.

@@ Line 15: / Line 15: @@
 '''Question:''' Is it possible to achieve $m=O(k)$ for some constant $C>0$?
-'''Background:''' the best bound on $m$ known is $m = O(k \log(n / k) / \log \log (n / k))$ {{cite|IndykR-13}}. If one insists on having $m = O(k)$, then the best $C$ we know how to achieve is $O(\sqrt{\log n})$ {{cite|IndykP-11}}
+'''Background:''' It is possible to achieve a weaker bound of $m=O(k \log(n/k))$ even if ${\mathcal T}_k$ is replaced by the set of all $k$-subsets of $[n]$ {{cite|CandesRT-06a}}. However, since $|{\mathcal T}_k | =\exp(O(k))$, one can expect a better bound for ${\mathcal T}_k$. The best $C$ we know how to achieve for $m = O(k)$ is $O(\sqrt{\log n})$ {{cite|IndykP-11}} (building on {{cite|BaraniukCDH-10}}).
 (building on {{cite|BaraniukCDH-10}}).

@@ Line 15: / Line 15: @@
 '''Question:''' Is it possible to achieve $m=O(k)$ for some constant $C>0$?
-'''Background:''' the best bound on $m$ known is $m = O(k \log(n / k) / \log \log (n / k))$ {{cite|IndykR-13}}. If one insists of having $m = O(k)$, then the best $C$ we know how to achieve is $O(\sqrt{\log n})$ {{cite|IndykP-11}}
+'''Background:''' the best bound on $m$ known is $m = O(k \log(n / k) / \log \log (n / k))$ {{cite|IndykR-13}}. If one insists on having $m = O(k)$, then the best $C$ we know how to achieve is $O(\sqrt{\log n})$ {{cite|IndykP-11}}
 (building on {{cite|BaraniukCDH-10}}).

← Older revision		Revision as of 17:20, 17 April 2013
Line 15:		Line 15:
	'''Question:''' Is it possible to achieve $m=O(k)$ for some constant $C>0$?		'''Question:''' Is it possible to achieve $m=O(k)$ for some constant $C>0$?

−	'''Background:''' It is ~~known that a weaker bound of~~ $m=O(k \log(n/k)~~)$ is possible to achieve even if ${~~\~~mathcal T}_k$ is replaced by the set of all $~~k~~$-subsets of $[n]~~$ {{cite\|~~CandesRT~~-~~06a~~}}. ~~However, since~~ $~~\|{\mathcal T}_k \|~~ =~~\exp(~~O(k))$, ~~one can expect a better bound for~~ ${\~~mathcal T~~}_k$~~. By using ''model-based compressive sensing'' framework of~~ {{cite\|~~BaraniukCDH~~-10}} (~~cf.~~ {{cite\|~~IndykP~~-11}})~~, one can achieve the desired bound of $m=O(k)$ but with ''superconstant'' $C$~~.	+	'''Background:''' the best bound on $m$ known is $m = O(k \log(n / k) / \log \log (n / k))$ {{cite\|IndykR-13}}. If one insists of having $m = O(k)$, then the best $C$ we know how to achieve is $O(\sqrt{\log n})$ {{cite\|IndykP-11}}
		+	(building on {{cite\|BaraniukCDH-10}}).

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