In a recent stream of papers, authors Liberty, Martinsson,
Rokhlin, Tygert and Woolfe28, 35, 38 design and analyze fast
algorithms for low-dimensional approximation algorithms of
matrices, and demonstrate their application to the evaluation
of the SVD of numerically low-rank matrices. Their schemes
are based on randomized transformations akin to FJLT.
4. Be YonD fJLt
The FJLT result gives rise to the following question: What is
a lower bound, as a function of n, d and e, on the complexity
of computing a JL-like random linear mapping? By this we
mean a mapping that distorts pairwise Euclidean distances
among any set of n points in d dimension by at most 1 ± e.
The underlying model of computation can be chosen as a
linear circuit, 32 manipulating complex-valued intermediates by either adding two or multiplying one by (random)
constants, and designating n as input and k = O(e − 2 log n) as
output (say, for p = 2). It is worth observing that any lower
bound in W(e − 2 log n min{d, log2 n}) would imply a similar lower bound on the complexity of computing a Fourier
transform. Such bounds are known only in a very restricted
model31 where constants are of bounded magnitude.
As a particular case of interest, we note that, whenever
k = O(d1/3), the running time of FJLT is O(d log d). In a more
recent paper, Ailon and Liberty3 improved this bound and
showed that it is possible to obtain a JL-like random mapping
in time O(d log d) for k = O(d 1/2 −d ) and any d > 0. Their transformation borrows the idea of preconditioning a Fourier
transform with a random diagonal matrix from FJLT, but
uses it differently and takes advantage of stronger measure
concentration bounds and tools from error correcting codes
over fields of characteristic 2. The same authors together
with Singer consider the following inverse problem4: Design
randomized linear time computable transformations that
require the mildest assumptions possible on data to ensure
successful dimensionality reduction.
1. achlioptas, D. Database-friendly
random projections: Johnson–
Lindenstrauss with binary coins.
J. Comput. Syst. Sci. 66, 4 (2003),
671–687.
2. ailon, N., chazelle, b. approximate
nearest neighbors and the fast
Johnson-Lindenstrauss transform.
SIAM J. Comput. 39, 1 (2009),
302–322.
3. ailon, N., Liberty, E. Fast dimension
reduction using rademacher series
on dual bch codes. Discrete and
Computational Geometry (2008).
4. ailon, N., Liberty, E., Singer, a.
Dense fast random projections and
lean walsh transforms.
APPROX-RANDOM, 2008, 512–522.
5. alon, N. Problems and results in
extremal combinatorics–i. Discrete
Math. 273, 1–3 (2003), 31–53.
6. alon, N., Spencer, J. The Probabilistic
Method. John Wiley, 2nd edition, 2000.
7. arora, S. Polynomial time
approximation schemes for euclidean
traveling salesman and other
geometric problems. J. ACM 45, 5
(1998), 753–782.
8. arya, S., Mount, D.M. approximate
nearest neighbor queries in fixed
dimensions. in Proceedings of the 4th
Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA) (austin,
tX, United States, 1993), 271–280.
28. Liberty, E., Woolfe, F., Martinsson, P.-g.,
rokhlin, V., tygert, M. randomized
algorithms for the low-rank
approximation of matrices. Proc. Natl.
Acad. Sci. (PNAS) 104, 51 (2007),
20167–20172.
29. Linial, N., London, E., rabinovich, y.
the geometry of graphs and some
of its algorithmic applications.
Combinatorica 15, 2 (1995), 215–245.
30. Mitchell, J.S.b. guillotine subdivisions
approximate polygonal subdivisions:
a simple new method for the
geometric k-MSt problem. SIAM J.
Comput. 28, 4 (1999), 1298–1309.
31. Morgenstern, J. Note on a lower
bound on the linear complexity of the
fast fourier transform. J. ACM 20, 2
(1973), 305–306.
32. Morgenstern, J. the linear complexity
of computation. J. ACM 22, 2 (1975),
184–194.
33. Muthukrishnan, S., Sahinalp, S.c.
Simple and practical sequence
nearest neighbors with block
operations. in Proceedings of the 13th
Annual Symposium on Combinatorial
Pattern Matching (CPM) (2002),
262–278.
34. Papadimitriou, c., raghavan, P.,
tamaki, h., Vempala, S. Latent
semantic indexing: a probabilistic
analysis. in Proceedings of the 17th
Annual Symposium of Database
Systems (1998), 159–168.
35. rokhlin, V., tygert, M. a fast
randomized algorithm for
overdetermined linear least-squares
regression. Proceedings of the
National Academy of Science (PNAS)
105, 36 (2008), 13212–13217.
36. Sarlós, t. improved approximation
algorithms for large matrices via
random projections. in Proceedings
of the 47th Annual IEEE Symposium
on Foundations of Computer Science
(FOCS) (berkeley, ca, 2006).
37. Schulman, L. clustering for edge-cost
minimization. in Proceedings of the
32nd Annual Symposium on Theory of
Computing (S TOC) (2000), 547–555.
38. Woolfe, F., Liberty, E., rokhlin,
V., tygert, M. a fast randomized
algorithm for the approximation of
matrices. Appl. Comput. Harmon.
Anal. 25 (2008), 335–366.
39. yianilos, P.N. Data structures and
algorithms for nearest neighbor
search in general metric spaces.
in Proceedings of the 4th Annual
ACM-SIAM Symposium on Discrete
Algorithms (SODA) (1993), 311–321.
40. yianilos, P.N. Locally lifting the
curse of dimensionality for nearest
neighbor search (extended abstract).
in Proceedings of the 11th Annual
ACM-SIAM Symposium on Discrete
Algorithms (SODA) (2000),
361–370.
nir Ailon ( nailon@gmail.com), google
research.
Bernard chazelle (chazelle@cs.
princeton.edu), Department of computer
Science, Princeton University.
© 2010 acM 0001-0782/10/0200 $10.00