Fast and RIP-optimal transforms

DOI10.1007/s00454-014-9632-3zbMath1309.15006arXiv1301.0878OpenAlexW2026408233MaRDI QIDQ2514234

Nir Ailon, Holger Rauhut

Publication date: 3 February 2015

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

Fourier transformorthogonal grouprandom matrixHadamard transformrandom walkcompressive sensingrestricted isometryJohnson-Lindenstrauss transformations

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Numerical methods for discrete and fast Fourier transforms (65T50) Random matrices (algebraic aspects) (15B52) Linear transformations, semilinear transformations (15A04)

Related Items

Tighter Fourier Transform Lower Bounds, Randomized algorithms for distributed computation of principal component analysis and singular value decomposition, Improved bounds for sparse recovery from subsampled random convolutions, Real-valued embeddings and sketches for fast distance and similarity estimation, Fast and memory-optimal dimension reduction using Kac's walk

Uses Software

• CoSaMP

Cites Work

• Unnamed Item
• Unnamed Item
• A mathematical introduction to compressive sensing
• Restricted isometries for partial random circulant matrices
• The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)
• Iterative hard thresholding for compressed sensing
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples
• A simple proof of the restricted isometry property for random matrices
• Uniform uncertainty principle for Bernoulli and subgaussian ensembles
• Fast dimension reduction using Rademacher series on dual BCH codes
• Database-friendly random projections: Johnson-Lindenstrauss with binary coins.
• One-Bit Compressed Sensing by Linear Programming
• Sparse Recovery Algorithms: Sufficient Conditions in Terms of Restricted Isometry Constants
• Suprema of Chaos Processes and the Restricted Isometry Property
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• On sparse reconstruction from Fourier and Gaussian measurements
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Compressive Sensing
• New constructions of RIP matrices with fast multiplication and fewer rows
• Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes
• Stable signal recovery from incomplete and inaccurate measurements
• Compressed sensing
• New concentration inequalities in product spaces