New constructions of RIP matrices with fast multiplication and fewer rows

DOI10.1137/1.9781611973402.111zbMATH Open1423.94022arXiv1211.0986OpenAlexW2138473013MaRDI QIDQ5384073FDOQ5384073

Authors: Jelani Nelson, Eric Price, Mary Wootters 

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: In compressed sensing, the "restricted isometry property" (RIP) is a sufficient condition for the efficient reconstruction of a nearly k-sparse vector x in C^d from m linear measurements Phi x. It is desirable for m to be small, and for Phi to support fast matrix-vector multiplication. In this work, we give a randomized construction of RIP matrices Phi in C^{m x d}, preserving the L_2 norms of all k-sparse vectors with distortion 1+eps, where the matrix-vector multiply Phi x can be computed in nearly linear time. The number of rows m is on the order of eps^{-2}klog dlog^2(klog d). Previous analyses of constructions of RIP matrices supporting fast matrix-vector multiplies, such as the sampled discrete Fourier matrix, required m to be larger by roughly a log k factor. Supporting fast matrix-vector multiplication is useful for iterative recovery algorithms which repeatedly multiply by Phi or Phi^*. Furthermore, our construction, together with a connection between RIP matrices and the Johnson-Lindenstrauss lemma in [Krahmer-Ward, SIAM. J. Math. Anal. 2011], implies fast Johnson-Lindenstrauss embeddings with asymptotically fewer rows than previously known. Our approach is a simple twist on previous constructions. Rather than choosing the rows for the embedding matrix to be rows sampled from some larger structured matrix (such as the discrete Fourier transform or a random circulant matrix), we instead choose each row of the embedding matrix to be a linear combination of a small number of rows of the original matrix, with random sign flips as coefficients. The main tool in our analysis is a recent bound for the supremum of certain types of Rademacher chaos processes in [Krahmer-Mendelson-Rauhut, arXiv:1207.0235].

Full work available at URL: https://arxiv.org/abs/1211.0986

Recommendations

• Fast and RIP-optimal transforms
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Explicit constructions of RIP matrices and related problems
• An Improved Estimate in the Restricted Isometry Problem
• Explicit Construction of RIP Matrices Is Ramsey‐Hard

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Randomized algorithms (68W20) Orthogonal matrices (15B10)

Cited In (15)

• Compliant Ternary Matrices based on Restricted Isometry Property: Construction and Application to Image Retrieval
• Robust width: a characterization of uniformly stable and robust compressed sensing
• Derandomizing restricted isometries via the Legendre symbol
• Fast and RIP-optimal transforms
• Explicit Construction of RIP Matrices Is Ramsey‐Hard
• Breaking the k ² barrier for explicit RIP matrices
• Explicit constructions of RIP matrices and related problems
• An introduction to compressed sensing
• Explicit matrices with the restricted isometry property: breaking the square-root bottleneck
• Optimal fast Johnson-Lindenstrauss embeddings for large data sets
• Simple analyses of the sparse Johnson-Lindenstrauss transform
• Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering
• Real-valued embeddings and sketches for fast distance and similarity estimation
• Discrete uncertainty principles and sparse signal processing
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property

This page was built for publication: New constructions of RIP matrices with fast multiplication and fewer rows

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384073)