### 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 language | English (US) |
---|---|

Title of host publication | Approximation, Randomization and Combinatorial Optimization |

Subtitle of host publication | Algorithms and Techniques - 11th International Workshop, APPROX 2008 and 12th International Workshop, RANDOM 2008, Proceedings |

Pages | 512-522 |

Number of pages | 11 |

DOIs | |

State | Published - Sep 22 2008 |

Externally published | Yes |

Event | 11th 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 2008 → Aug 27 2008 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 5171 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 11th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2008 and 12th International Workshop on Randomization and Computation, RANDOM 2008 |
---|---|

Country | United States |

City | Boston, MA |

Period | 8/25/08 → 8/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

*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