Abstract
The Fast Johnson–Lindenstrauss Transform (FJLT) was recently discovered by Ailon and Chazelle as a novel technique for performing fast dimension reduction with small distortion from ℓ d2 to ℓ k2 in time O(max {dlog d,k 3}). For k in [Ω(log d),O(d 1/2)], this beats time O(dk) achieved by naive multiplication by random dense matrices, an approach followed by several authors as a variant of the seminal result by Johnson and Lindenstrauss (JL) from the mid 1980s. In this work we show how to significantly improve the running time to O(dlog k) for k=O(d 1/2−δ), for any arbitrary small fixed δ. This beats the better of FJLT and JL. Our analysis uses a powerful measure concentration bound due to Talagrand applied to Rademacher series in Banach spaces (sums of vectors in Banach spaces with random signs). The set of vectors used is a real embedding of dual BCH code vectors over GF(2). We also discuss the number of random bits used and reduction to ℓ 1 space.
The connection between geometry and discrete coding theory discussed here is interesting in its own right and may be useful in other algorithmic applications as well.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. Contemp. Math. 26, 189–206 (1984)
Ailon, N., Chazelle, B.: Approximate nearest neighbors and the fast Johnson–Lindenstrauss transform. In: Proceedings of the 38st Annual Symposium on the Theory of Compututing (STOC), pp. 557–563. Seattle, WA (2006)
Frankl, P., Maehara, H.: The Johnson–Lindenstrauss lemma and the sphericity of some graphs. J. Combin. Theory Ser. A 44, 355–362 (1987)
Indyk, P., Motwani, R.: Approximate nearest neighbors: Towards removing the curse of dimensionality. In: Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC), pp. 604–613 (1998)
Matousek, J.: On variants of the Johnson–Lindenstrauss lemma. Private communication (2006)
Kushilevitz, E., Ostrovsky, R., Rabani, Y.: Efficient search for approximate nearest neighbor in high dimensional spaces. SIAM J. Comput. 30(2), 457–474 (2000)
Littlestone, N.: Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Mach. Learn. 2(4), 285–318 (1988)
Arriaga, R.I., Vempala, S.: An algorithmic theory of learning: Robust concepts and random projection. In: FOCS ’99: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p. 616. Washington, DC, USA, IEEE Computer Society (1999)
Indyk, P.: On approximate nearest neighbors in non-Euclidean spaces. In: Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 148–155 (1998)
Vempala, S.: The Random Projection Method. DIMACS Series in Discrete Mathematics and Theoretical Computer Science (2004)
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)
Har-Peled, S.: A replacement for Voronoi diagrams of near linear size. In: Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 94–103. Las Vegas, Nevada, USA (2001)
Alon, N.: Problems and results in extremal combinatorics I. Discrete Math. 273(1–3), 31–53 (2003)
Sudan, M.: Essential coding theory (class notes)
Khot, S.: Hardness of approximating thee shortest vector problem in lattices. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS) (2004)
Ailon, N., Chazelle, B.: Lower bounds for linear degeneracy testing. J. ACM 52(2), 157–171 (2005)
Razborov, A.A.: Expander codes and somewhat Euclidean sections in ℓ n1 . ECCC (2007)
Indyk, P.: Uncertainty principles, extractors, and explicit embeddings of l2 into l1. In: Proceedings of the 39th Annual ACM Symposium on the Theory of Computing (2007)
Artstein-Avidan, S., Milman, V.: Logarithmic reduction of the level of randomness in some probabilistic geometric constructions. SIAM J. Comput. 1(34), 67–88 (2004)
Frieze, A.M., Kannan, R., Vempala, S.: Fast Monte-Carlo algorithms for finding low-rank approximations. In: IEEE Symposium on Foundations of Computer Science, pp. 370–378 (1998)
Drineas, P., Kannan, R.: Fast Monte-Carlo algorithms for approximate matrix multiplication. In: IEEE Symposium on Foundations of Computer Science, pp. 452–459 (2001)
Drineas, P., Kannan, R., Mahoney, M.: Fast Monte Carlo algorithms for matrices II: Computing a low-rank approximation to a matrix (2004)
Drineas, P., Kannan, R., Mahoney, M.: Fast Monte Carlo algorithms for matrices III: Computing a compressed approximate matrix decomposition (2004)
Woolfe, F., Liberty, E., Rokhlin, V., Tygert, M.: A fast randomized algorithm for the approximation of matrices. Yale Computer Science Technical Reports, YALE/DCS/TR1380 (2007)
Drineas, P., Mahoney, M.W., Muthukrishnan, S., Sarlos, T.: Faster least squares approximation. http://arxiv.org/abs/0710.1435 (2007)
Bergh, J., Lofstrom, J.: Interpolation Spaces. Springer, Berlin (1976)
Ledoux, M., Talagrand, M.: Probability in Banach Spaces: Isoperimetry and Processes. Springer, Berlin (1991)
MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error Correcting Codes. North-Holland, Amsterdam (1983)
König, C.S.H., Jaegermann, N.T.: Projection constants of symmetric spaces and variants of Khintchine’s inequality. J. Reine Angew. Math. 511, 1–42 (1999)
Author information
Authors and Affiliations
Corresponding author
Additional information
N. Ailon supported by the National Science Foundation under agreement No. DMS-0111298P.
E. Liberty supported by AFOSR, and NGA.
Rights and permissions
About this article
Cite this article
Ailon, N., Liberty, E. Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes. Discrete Comput Geom 42, 615–630 (2009). https://doi.org/10.1007/s00454-008-9110-x
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-008-9110-x