Fast Random Projections Using Lean Walsh Transforms
YALE UNIV NEW HAVEN CT DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
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.
- Numerical Mathematics