Dense fast random projections and lean Walsh transforms

Edo Liberty, Nir Ailon, Amit Singer

Research output: Chapter in Book/Report/Conference proceedingConference contribution

24 Scopus citations

Abstract

Random projection methods give distributions over k × d matrices such that if a matrix Ψ (chosen according to the distribution) is applied to a vector x ∈ ℝd the norm of the resulting vector, Ψ x ∈ ℝk, is up to distortion ε equal to the norm of x w.p. at least 1 - δ. The Johnson Lindenstrauss lemma shows that such distributions exist over dense matrices for k (the target dimension) in O(log(1/δ)/fε2). Ailon and Chazelle and later Matousek showed that there exist entry-wise i.i.d. distributions over sparse matrices Ψ which give the same guaranties for vectors whose ℓ is bounded away from their ℓ2 norm. This allows to accelerate the mapping x → Ψx. We claim that setting Ψ as any column normalized deterministic dense matrix composed with random ±1 diagonal matrix also exhibits this property for vectors whose ℓp (for any p > 2) is bounded away from their ℓ2 norm. We also describe a specific tensor product matrix which we term lean Walsh. It is applicable to any vector in in O(d) operations and requires a weaker ℓ bound on x then the best current result, under comparable running times, using sparse matrices due to Matousek.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings
Pages512-522
Number of pages11
DOIs
StatePublished - Sep 22 2008
Externally publishedYes
Event11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008 - Boston, MA, United States
Duration: Aug 25 2008Aug 27 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5171 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008
CountryUnited States
CityBoston, MA
Period8/25/088/27/08

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Dimension reduction
  • Johnson Lindenstrauss
  • Random projections
  • lean Walsh transforms

Fingerprint Dive into the research topics of 'Dense fast random projections and lean Walsh transforms'. Together they form a unique fingerprint.

  • Cite this

    Liberty, E., Ailon, N., & Singer, A. (2008). Dense fast random projections and lean Walsh transforms. In Approximation, Randomization and Combinatorial Optimization: Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings (pp. 512-522). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5171 LNCS). https://doi.org/10.1007/978-3-540-85363-3_40