Dense Fast Random Projections and Lean Walsh Transforms

Edo Liberty, Nir Ailon, Amit Singer

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


Random projection methods give distributions over k×d matrices such that if a matrix Ψ (chosen according to the distribution) is applied to a finite set of vectors xi∈ℝd the resulting vectors Ψxi∈ℝk approximately preserve the original metric with constant probability. First, we show that any matrix (composed with a random ±1 diagonal matrix) is a good random projector for a subset of vectors in ℝd. Second, we describe a family of tensor product matrices which we term Lean Walsh. We show that using Lean Walsh matrices as random projections outperforms, in terms of running time, the best known current result (due to Matousek) under comparable assumptions.

Original languageEnglish (US)
Pages (from-to)34-44
Number of pages11
JournalDiscrete and Computational Geometry
Issue number1
StatePublished - Jan 2011

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


  • Dimension reduction
  • Fast random projections
  • Johnson-Lindenstrauss
  • Lean Walsh matrices


Dive into the research topics of 'Dense Fast Random Projections and Lean Walsh Transforms'. Together they form a unique fingerprint.

Cite this