Fast Random Projections Using Lean Walsh Transforms

Abstract

We present a kappa x d random projection matrix that is applicable to vectors x belongs to R(exp d) in O(d) operations if d greater than or equal to k(exp 2 + delta-prime) . Here, kappa is the minimal Johnson Lindenstrauss dimension and delta is arbitrarily small. The projection succeeds, with probability 1-1/n, in preserving vector lengths, up to distortion epsilon, for all vectors such that || x ||(sub infinity) less than or equal to || x ||(sub 2)k(exp -1/2)d(exp -delta) (for arbitrary small delta). Sampling based approaches are either not applicable in linear time or require a bound on || x ||(sub infinity) that is strongly dependant on d. Our method overcomes these shortcomings by rapidly applying dense tensor power matrices to incoming vectors.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Dec 01, 2007
Accession Number
ADA478655

Entities

People

  • Amit Singer
  • Edo Liberty
  • Nir Ailon

Organizations

  • Yale University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Compressed Sensing
  • Computations
  • Computer Science
  • Construction
  • Equations
  • Information Operations
  • Linear Algebra
  • Mathematics
  • Numbers
  • Probability
  • Random Variables
  • Real Numbers
  • Skewness
  • Universities

Readers

  • Approximation Theory.
  • Graph Algorithms and Convex Optimization.