Communications - February 2010

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),