## Abstract

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 x_{i}∈ℝ^{d} the resulting vectors Ψx_{i}∈ℝ^{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 language | English (US) |
---|---|

Pages (from-to) | 34-44 |

Number of pages | 11 |

Journal | Discrete and Computational Geometry |

Volume | 45 |

Issue number | 1 |

DOIs | |

State | Published - Jan 2011 |

## All Science Journal Classification (ASJC) codes

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

## Keywords

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