Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices

DOI10.1073/pnas.1219540110zbMath1292.94007OpenAlexW2168537135WikidataQ36567958 ScholiaQ36567958MaRDI QIDQ5170951

Unnamed Author, David L. Donoho, Sina Jafarpour, Matan Gavish, Hatef Monajemi

Publication date: 25 July 2014

Published in: Proceedings of the National Academy of Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1073/pnas.1219540110

Mathematics Subject Classification ID

Estimation in multivariate analysis (62H12) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Image processing (compression, reconstruction, etc.) in information and communication theory (94A08) Detection theory in information and communication theory (94A13) Random matrices (algebraic aspects) (15B52) Sampling theory in information and communication theory (94A20)

Related Items

Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery, On the universality of noiseless linear estimation with respect to the measurement matrix, Performance comparisons of greedy algorithms in compressed sensing, Universality of approximate message passing with semirandom matrices, Bipolar measurement matrix using chaotic sequence, The restricted isometry property for random block diagonal matrices, Reducing effects of bad data using variance based joint sparsity recovery, Joint Sparse Recovery Based on Variances, Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices, The phase transition of matrix recovery from Gaussian measurements matches the minimax MSE of matrix denoising, CoverBLIP: accelerated and scalable iterative matched-filtering for magnetic resonance fingerprint reconstruction*, Uniform recovery from subgaussian multi-sensor measurements, Empirical average-case relation between undersampling and sparsity in X-ray CT

Uses Software

• CVXOPT
• CVX
• Mosek
• SPGL1

Cites Work

• Unnamed Item
• Unnamed Item
• A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
• The road to deterministic matrices with the restricted isometry property
• Explicit constructions of RIP matrices and related problems
• On the linear independence of spikes and sines
• Near-ideal model selection by \(\ell _{1}\) minimization
• On the conditioning of random subdictionaries
• Chirp sensing codes: Deterministic compressed sensing measurements for fast recovery
• Grassmannian frames with applications to coding and communication
• Universality in polytope phase transitions and message passing algorithms
• Counting the faces of randomly-projected hypercubes and orthants, with applications
• High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension
• Uncertainty Principles and Signal Recovery
• The finite harmonic oscillator and its associated sequences
• Counting faces of randomly projected polytopes when the projection radically lowers dimension
• Decoding by Linear Programming
• Probing the Pareto Frontier for Basis Pursuit Solutions
• Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
• Atomic Decomposition by Basis Pursuit
• Convex Polytopes
• Uncertainty principles and ideal atomic decomposition
• Deterministic matrices matching the compressed sensing phase transitions of Gaussian random matrices
• Sparse nonnegative solution of underdetermined linear equations by linear programming
• Neighborliness of randomly projected simplices in high dimensions
• Compressed sensing
• Noiselets