Difference between revisions of "Open Problems:50"
| 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:''' the best bound on $m$ known is $m = O(k \log(n / k) / \log \log (n / k))$ {{cite|IndykR-13}}. If one insists | + | '''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}}). | (building on {{cite|BaraniukCDH-10}}). | ||
Revision as of 17:29, 17 April 2013
| Suggested by | Piotr Indyk |
|---|---|
| Source | Bertinoro 2011 |
| Short link | https://sublinear.info/50 |
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: the best bound on $m$ known is $m = O(k \log(n / k) / \log \log (n / k))$ [IndykR-13]. If one insists on having $m = O(k)$, then the best $C$ we know how to achieve is $O(\sqrt{\log n})$ [IndykP-11] (building on [BaraniukCDH-10]).
