Fast dimension reduction using Rademacher series on dual BCH codes

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 ℓ^d₂ to ℓ^d₂ in time O(max{d log d,k³}). 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 80's. In this work we show how to significantly improve the running time to O(d log 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 ℓ₁ 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.

REFERENCES

• 1: W. B. Johnson and J. Lindenstrauss. Extensions of Lipschitz mappings into a Hilbert space. Contemporary Mathematics, 26:189--206, 1984.
• 2: Nir Ailon , Bernard Chazelle, Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132597]
• 3: P. Frankl , H. Maehara, The Johnson-Lindenstrauss Lemma and the sphericity of some graphs, Journal of Combinatorial Theory Series A, v.44 n.3, p.355-362, June 1987
• 4: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 5: J. Matousek. On variants of the Johnson-Lindenstrauss lemma. Private communication, 2006.
• 6: Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces, SIAM Journal on Computing, v.30 n.2, p.457-474, 2000 [doi>10.1137/S0097539798347177]
• 7: Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm, Machine Learning, v.2 n.4, p.285-318, April 1988 [doi>10.1023/A:1022869011914]
• 8: Rosa I. Arriaga , Santosh Vempala, An Algorithmic Theory of Learning: Robust Concepts and Random Projection, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.616, October 17-18, 1999
• 9: P. Indyk, On Approximate Nearest Neighbors in Non-Euclidean Spaces, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.148, November 08-11, 1998
• 10: Santosh Vempala. The Random Projection Method. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. 2004.
• 11: Tamas Sarlos, Improved Approximation Algorithms for Large Matrices via Random Projections, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.143-152, October 21-24, 2006 [doi>10.1109/FOCS.2006.37]
• 12: S. Har-Peled, A Replacement for Voronoi Diagrams of Near Linear Size, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.94, October 14-17, 2001
• 13: Noga Alon. Problems and results in extremal combinatorics-I. Discrete Mathematics, 273(1-3):31--53, 2003.
• 14: Madhu Sudan. Essential coding theory (class notes).
• 15: Subhash Khot, Hardness of Approximating the Shortest Vector Problem in Lattices, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.126-135, October 17-19, 2004 [doi>10.1109/FOCS.2004.31]
• 16: Nir Ailon , Bernard Chazelle, Lower bounds for linear degeneracy testing, Journal of the ACM (JACM), v.52 n.2, p.157-171, March 2005 [doi>10.1145/1059513.1059515]
• 17: A. A. Razborov. Expander codes and somewhat Euclidean sections in ℓⁿ₁. ECCC, 2007.
• 18: Piotr Indyk, Uncertainty principles, extractors, and explicit embeddings of l2 into l1, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250881]
• 19: S. Artstein-Avidan and V. Milman. Logarithmic reduction of the level of randomness in some probabilistic geometric constructions. SIAM Journal on Computing, 1(34):67--88, 2004.
• 20: Alan Frieze , Ravi Kannan , Santosh Vempala, Fast Monte-Carlo Algorithms for finding low-rank approximations, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.370, November 08-11, 1998
• 21: P. Drineas , R. Kannan, Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.452, October 14-17, 2001
• 22: P. Drineas, R. Kannan, and M. Mahoney. Fast monte carlo algorithms for matrices ii: Computing a low-rank approximation to a matrix, 2004.
• 23: P. Drineas, R. Kannan, and M. Mahoney. Fast monte carlo algorithms for matrices iii: Computing a compressed approximate matrix decomposition, 2004.
• 24: Franco Woolfe, Edo Liberty, Vladimir Rokhlin, and Mark Tygert. A fast randomized algorithm for the approximation of matrices. Yale Computer Science Technical Reports, YALE/DCS/TR1380, 2007.
• 25: P. Drineas, M. w. Mahoney, S. Muthukrishnan, and T. Sarlos. Faster least squares approximation. http://arxiv.org/abs/0710.1435, 2007.
• 26: J. Bergh and J. Lofstrom. Interpolation Spaces. Springer-Verlag, 1976.
• 27: M. Ledoux and M. Talagrand. Probability in Banach Spaces: Isoperimetry and Processes. Springer-Verlag, 1991.
• 28: F. J. MacWilliams and N. J. A. Sloane. The Theory of Error Correcting Codes. North-Holland, 1983.
• 29: Carsten Schütt Hermann König and Nicole Tomczak Jaegermann. Projection constants of symmetric spaces and variants of khintchine's inequality. J. Reine Angew. Math, 511:1--42, 1999.

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms, Design, Theory