New Constructions of RIP Matrices with Fast Multiplication and Fewer Rows

 Title: New Constructions of RIP Matrices with Fast Multiplication and Fewer Rows Author: Nelson, Jelani; Price, Eric; Wootters, Mary Note: Order does not necessarily reflect citation order of authors. Citation: Nelson, Jelani, Eric Price, and Mary Wootters. 2014. "New Constructions of RIP Matrices with Fast Multiplication and Fewer Rows." In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, January 5-7, Portland, Oregon: 1515-1528. Philadelphia, PA: Society for Industrial and Applied Mathematics. Full Text & Related Files: riphash.pdf (458.8Kb; PDF) Abstract: In this paper, we present novel constructions of matrices with the restricted isometry property (RIP) that support fast matrix-vector multiplication. Our guarantees are the best known, and can also be used to obtain the best known guarantees for fast Johnson Lindenstrauss transforms. In compressed sensing, the restricted isometry property is a sufficient condition for the efficient reconstruction of a nearly k-sparse vector $$x \in \mathbb{C}^d$$ from m linear measurements $$\Phi x$$. It is desirable for m to be small, and further it is desirable for $$\Phi$$ to support fast matrix-vector multiplication. Among other applications, fast multiplication improves the runtime of iterative recovery algorithms which repeatedly multiply by $$\Phi$$ or $$\Phi^*$$. The main contribution of this work is a novel randomized construction of RIP matrices $$\Phi \in \mathbb{C}^{m×d}$$, preserving the $$\ell_2$$ norms of all k-sparse vectors with distortion $$1 + \epsilon$$, where the matrix-vector multiply $$\Phi x$$ can be computed in nearly linear time. The number of rows m is on the order of $$\epsilon^{−2}klogd log^2(klogd)$$, an improvement on previous analyses by a logarithmic factor. Our construction, together with a connection between RIP matrices and the Johnson-Lindenstrauss lemma in [Krahmer-Ward, SIAM. J. Math. Anal. 2011], also implies fast Johnson-Lindenstrauss embeddings with asymptotically fewer rows than previously known. Our construction is actually a recipe for improving any existing family of RIP matrices. Briefly, we apply an appropriate sparse hash matrix with sign flips to any suitable family of RIP matrices. We show that the embedding properties of the original family are maintained, while at the same time improving the number of rows. The main tool in our analysis is a recent bound for the supremum of certain types of Rademacher chaos processes in [Krahmer-Mendelson-Rauhut, Comm. Pure Appl. Math. to appear]. Published Version: doi:10.1137/1.9781611973402.111 Other Sources: http://arxiv.org/abs/1211.0986 Terms of Use: This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA Citable link to this page: http://nrs.harvard.edu/urn-3:HUL.InstRepos:13820495 Downloads of this work: