Fast and efficient dimensionality reduction using Structurally Random Matrices

摘要

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