New constructions of RIP matrices with fast multiplication and fewer rows
From MaRDI portal
Publication:5384073
DOI10.1137/1.9781611973402.111zbMath1423.94022arXiv1211.0986OpenAlexW2138473013MaRDI QIDQ5384073
Mary Wootters, Jelani Nelson, Eric Price
Publication date: 20 June 2019
Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1211.0986
Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Randomized algorithms (68W20) Orthogonal matrices (15B10)
Related Items
Derandomizing restricted isometries via the Legendre symbol, Performance of Johnson--Lindenstrauss Transform for $k$-Means and $k$-Medians Clustering, Simple Analyses of the Sparse Johnson-Lindenstrauss Transform., An Introduction to Compressed Sensing, Discrete uncertainty principles and sparse signal processing, Toward a unified theory of sparse dimensionality reduction in Euclidean space, Real-valued embeddings and sketches for fast distance and similarity estimation, Fast and RIP-optimal transforms, Optimal fast Johnson-Lindenstrauss embeddings for large data sets, Robust Width: A Characterization of Uniformly Stable and Robust Compressed Sensing
