Difference between revisions of "Open Problems:46"
(Created page with "{{Header |title=Fast JL Transform for Sparse Vectors |source=bertinoro11 |who=Jelani Nelson }} Consider a distribution over linear mappings $A$ from $R^d$ to $R^k$, $k=O(\log...") |
|||
| Line 9: | Line 9: | ||
'''Question:''' Can we construct a distribution with this property such that the matrix-vector product $Ax$ can be evaluated in time $(s+k)\cdot \operatorname{polylog}(d)$ time given an $s$-sparse $x$? | '''Question:''' Can we construct a distribution with this property such that the matrix-vector product $Ax$ can be evaluated in time $(s+k)\cdot \operatorname{polylog}(d)$ time given an $s$-sparse $x$? | ||
| − | '''Background:''' Such an algorithm is not known even for $s=d$ (unless $k$ is larger {{cite|AilonL-11}}). | + | '''Background:''' Such an algorithm is not known even for $s=d$ (unless $k$ is larger {{cite|AilonL-11}}, {{cite|KrahmerW-11}}). |
| − | '''Question:''' Provide an explicit construction of a distribution with the $(\epsilon, P)$-JL property such that the random | + | '''Question:''' Provide an explicit construction of a distribution with the $(\epsilon, P)$-JL property such that the random matrix $A$ can be generated using $O(\log (d/P))$ bits. |
Revision as of 23:30, 12 December 2012
| Suggested by | Jelani Nelson |
|---|---|
| Source | Bertinoro 2011 |
| Short link | https://sublinear.info/46 |
Consider a distribution over linear mappings $A$ from $R^d$ to $R^k$, $k=O(\log (1/P)/\epsilon^2)$. We say that it has an $(\epsilon, P)$-JL property if for any vector $x \in R^d$ we have $$\|Ax\|_2 = (1 \pm \epsilon) \|x\|_2$$ with probability $1-P$.
Question: Can we construct a distribution with this property such that the matrix-vector product $Ax$ can be evaluated in time $(s+k)\cdot \operatorname{polylog}(d)$ time given an $s$-sparse $x$?
Background: Such an algorithm is not known even for $s=d$ (unless $k$ is larger [AilonL-11], [KrahmerW-11]).
Question: Provide an explicit construction of a distribution with the $(\epsilon, P)$-JL property such that the random matrix $A$ can be generated using $O(\log (d/P))$ bits.
