Name
Abstract | ||
|---|---|---|
Random projection methods give distributions over k×dmatrices such that if a matrix 茂戮驴(chosen according to the distribution) is applied to a vector the norm of the resulting vector, , is up to distortion 茂戮驴equal to the norm of xw.p. at least 1 茂戮驴 茂戮驴. The Johnson Lindenstrauss lemma shows that such distributions exist over densematrices for k(the target dimension) in . Ailon and Chazelle and later Matousek showed that there exist entry-wise i.i.d. distributions over sparsematrices 茂戮驴which give the same guaranties for vectors whose 茂戮驴茂戮驴is bounded away from their 茂戮驴2norm. This allows to accelerate the mapping x茂戮驴茂戮驴x. We claim that setting 茂戮驴as any column normalized deterministic densematrix composed with random ±1 diagonal matrix also exhibits this property for vectors whose 茂戮驴p(for any p 2) is bounded away from their 茂戮驴2norm. 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 xthen the best current result, under comparable running times, using sparse matrices due to Matousek. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/s00454-010-9309-5 | Discrete and Computational Geometry |
Keywords | Field | DocType |
Fast random projections,Dimension reduction,Lean Walsh matrices,Johnson-Lindenstrauss | Tensor product,Random projection,Discrete mathematics,Combinatorics,Matrix (mathematics),Norm (mathematics),Diagonal matrix,Sparse matrix,Mathematics,Johnson–Lindenstrauss lemma,Bounded function | Journal |
Volume | Issue | ISSN |
45 | 1 | 0179-5376 |
Citations | PageRank | References |
24 | 1.85 | 21 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Edo Liberty | 1 | 397 | 24.83 |
| Nir Ailon | 2 | 1114 | 70.74 |
| A. Singer | 3 | 695 | 52.77 |