Title :
Fast and efficient dimensionality reduction using Structurally Random Matrices
Author :
Do, Thong T. ; Gan, Lu ; Chen, Yi ; Nguyen, Nam ; Tran, Trac D.
Author_Institution :
Dept. of Electr. & Comput. Eng., Johns Hopkins Univ., Baltimore, MD
Abstract :
Structurally random matrices (SRM) are first proposed in 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, 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 epsi, provided that the projection dimension is on the order of O(epsi-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.
Keywords :
computational complexity; matrix algebra; random processes; signal processing; Johnson-Lindenstrauss lemma; computational complexity; dimensionality reduction transform; large scale compressed sensing applications; measurement operators; structurally random matrices; suboptimal Johnson-Lindenstrauss; Bridges; Compressed sensing; Computational complexity; Design engineering; Discrete cosine transforms; Distortion measurement; Gallium nitride; Large-scale systems; Random variables; Vectors; Johnson-Lindenstrauss; Low-distortion embedding; compressed sensing; dimensionality reduction; machine learning;
Conference_Titel :
Acoustics, Speech and Signal Processing, 2009. ICASSP 2009. IEEE International Conference on
Conference_Location :
Taipei
Print_ISBN :
978-1-4244-2353-8
Electronic_ISBN :
1520-6149
DOI :
10.1109/ICASSP.2009.4959960