Open Problems:46 - Revision history

Krzysztof Onak: updated header

2013-03-07T01:55:27Z

updated header

Minilek at 23:30, 12 December 2012

2012-12-12T23:30:52Z

Krzysztof Onak: 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..."

2012-11-17T04:14:59Z

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..."

New page

{{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 (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 {{cite|AilonL-11}}).

'''Question:''' Provide an explicit construction of a distribution with the $(\epsilon, P)$-JL property such that the random variable $A$ can be generated using $O(\log (d/P))$ bits.

@@ Line 1: / Line 1: @@
 {{Header
 |source=bertinoro11
 |who=Jelani Nelson

@@ 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$?
-'''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 variable $A$ can be generated using $O(\log (d/P))$ bits.
+'''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.