Compressed sensing with sparse binary matrices: instance optimal error guarantees in near-optimal time

DOI10.1016/J.JCO.2013.08.001zbMath1294.65045arXiv1302.5936OpenAlexW2086190841MaRDI QIDQ2252137

Mark A. Iwen

Publication date: 16 July 2014

Published in: Journal of Complexity (Search for Journal in Brave)

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

zbMATH Keywords

sparse matricescompressed sensingrecovery algorithmsublinear-time algorithms

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Related Items (7)

Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery ⋮ Sparse recovery properties of discrete random matrices ⋮ Fast Phase Retrieval from Local Correlation Measurements ⋮ Robust sparse phase retrieval made easy ⋮ Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables ⋮ Construction of Sparse Binary Sensing Matrices Using Set Systems ⋮ Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A mathematical introduction to compressive sensing
• Iterative hard thresholding for compressed sensing
• Improved approximation guarantees for sublinear-time Fourier algorithms
• Deterministic constructions of compressed sensing matrices
• Approximate sparse recovery
• On the Design of Deterministic Matrices for Fast Recovery of Fourier Compressible Functions
• Compressed sensing and best 𝑘-term approximation
• Combinatorial Algorithms for Compressed Sensing
• An improved data stream summary: the count-min sketch and its applications
• Efficient and Robust Compressed Sensing Using Optimized Expander Graphs
• Lower Bounds for Sparse Recovery
• Stable signal recovery from incomplete and inaccurate measurements
• (1 + eps)-Approximate Sparse Recovery
• Compressed sensing

This page was built for publication: Compressed sensing with sparse binary matrices: instance optimal error guarantees in near-optimal time