Accession Number:

ADA478655

Title:

Fast Random Projections Using Lean Walsh Transforms

Descriptive Note:

Corporate Author:

YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

2007-12-01

Pagination or Media Count:

10.0

Abstract:

We present a kappa x d random projection matrix that is applicable to vectors x belongs to Rexp d in Od operations if d greater than or equal to kexp 2 delta-prime . Here, kappa is the minimal Johnson Lindenstrauss dimension and delta is arbitrarily small. The projection succeeds, with probability 1-1n, in preserving vector lengths, up to distortion epsilon, for all vectors such that x sub infinity less than or equal to x sub 2kexp -12dexp -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.

Subject Categories:

  • Numerical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE