Name
Abstract | ||
|---|---|---|
Structurally Random Matrices (SRM) are first proposed in [1] as fast and highly efficient measurement operators for large scale compressed sensing applications. Motivated by the bridge between compressed sensing and the Johnson-Lindenstrauss lemma [2] , this paper introduces a related application of SRMs regarding to realizing a fast and highly efficient embedding. In particular, it shows that a SRM is also a promising dimensionality reduction transform that preserves all pairwise distances of high dimensional vectors within an arbitrarily small factor ∈, provided that the projection dimension is on the order of O(∈−2 log3 N), where N denotes the number of d-dimensional vectors. In other words, SRM can be viewed as the sub-optimal Johnson-Lindenstrauss embedding that, however, owns very low computational complexity O(d log d) and highly efficient implementation that uses only O(d) random bits, making it a promising candidate for practical, large scale applications where efficiency and speed of computation are highly critical. |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1109/ICASSP.2009.4959960 | ICASSP |
Keywords | Field | DocType |
efficient embedding,johnson-lindenstrauss lemma,efficient measurement operator,structurally random matrices,promising candidate,log3 n,promising dimensionality reduction,efficient implementation,sub-optimal johnson-lindenstrauss,large scale application,efficient dimensionality reduction,large scale,computational complexity,probability density function,random matrices,dimensionality reduction,signal processing,data mining,machine learning,compressed sensing,random variables,random processes,vectors,sparse matrices | Random variable,Mathematical optimization,Dimensionality reduction,Embedding,Computer science,Sparse matrix,Compressed sensing,Computational complexity theory,Johnson–Lindenstrauss lemma,Random matrix | Conference |
ISSN | Citations | PageRank |
1520-6149 | 6 | 0.72 |
References | Authors | |
4 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thong T. Do | 1 | 234 | 12.76 |
| Lu Gan | 2 | 96 | 6.31 |
| Yi Chen | 3 | 427 | 15.85 |
| Nam Nguyen | 4 | 26 | 4.16 |
| Trac D. Tran | 5 | 1507 | 108.22 |