|
Abstract:
We present a kappa * d random projection matrix that is applicable to vectors chi epsilon R(exp d) in O(d) operations if d >kappa(exp 2+delta) . 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 || chi || infinity < || chi ||(sub 2)kappa(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 || chi || infinity that is strongly dependant on d. Our method overcomes these shortcomings by rapidly applying dense tensor power matrices to incoming vectors.
| Limitations: |
 APPROVED FOR PUBLIC RELEASE |
| Pages: |
10 |
| Report Date: |
DEC 2007 |
| Report Number: |
A556874 |
|
|
|
|
|
Keywords relating to this report:
Email This Abstract
