Name
Abstract | ||
|---|---|---|
The problems of random projections and sparse reconstruction have much in
common and individually received much attention. Surprisingly, until now they
progressed in parallel and remained mostly separate. Here, we employ new tools
from probability in Banach spaces that were successfully used in the context of
sparse reconstruction to advance on an open problem in random pojection. In
particular, we generalize and use an intricate result by Rudelson and Vershynin
for sparse reconstruction which uses Dudley's theorem for bounding Gaussian
processes. Our main result states that any set of $N = \exp(\tilde{O}(n))$ real
vectors in $n$ dimensional space can be linearly mapped to a space of dimension
$k=O(\log N\polylog(n))$, while (1) preserving the pairwise distances among the
vectors to within any constant distortion and (2) being able to apply the
transformation in time $O(n\log n)$ on each vector. This improves on the best
known $N = \exp(\tilde{O}(n^{1/2}))$ achieved by Ailon and Liberty and $N =
\exp(\tilde{O}(n^{1/3}))$ by Ailon and Chazelle.
The dependence in the distortion constant however is believed to be
suboptimal and subject to further investigation. For constant distortion, this
settles the open question posed by these authors up to a $\polylog(n)$ factor
while considerably simplifying their constructions. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2483699.2483701 | ACM Transactions on Algorithms (TALG) - Special Issue on SODA'11 |
Keywords | Field | DocType |
constant distortion,intricate result,open problem,johnson-lindenstrauss transform,almost optimal unrestricted fast,n log n,sparse reconstruction,n dimensional space,banach space,n polylog,open question,optimal unrestricted fast johnson-lindenstrauss,main result state,compressed sensing | Discrete mathematics,Binary logarithm,Combinatorics,Open problem,Upper and lower bounds,Banach space,Gaussian process,Time complexity,Distortion,Compressed sensing,Mathematics | Journal |
Volume | Issue | ISSN |
9 | 3 | 1549-6325 |
ISBN | Citations | PageRank |
978-1-61197-251-1 | 55 | 2.11 |
References | Authors | |
17 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nir Ailon | 1 | 1114 | 70.74 |
| Edo Liberty | 2 | 397 | 24.83 |