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

DOI10.1016/J.JCO.2013.08.001zbMATH Open1294.65045arXiv1302.5936OpenAlexW2086190841MaRDI QIDQ2252137FDOQ2252137

Authors: M. A. Iwen 

Publication date: 16 July 2014

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

Abstract: A compressed sensing method consists of a rectangular measurement matrix, $Minmathbbm{R}^{mimesN}$ with $mllN$, together with an associated recovery algorithm, $mathcalA:mathbbm{R}^{m}ightarrowmathbbm{R}^N$. Compressed sensing methods aim to construct a high quality approximation to any given input vector $$ using only $$ as input. In particular, we focus herein on instance optimal nonlinear approximation error bounds for $M$ and $mathcalA$ of the form $$ for $$, where $$ is the best possible $k$-term approximation to $$. In this paper we develop a compressed sensing method whose associated recovery algorithm, $mathcalA$, runs in $O((klogk)logN)$-time, matching a lower bound up to a $O(logk)$ factor. This runtime is obtained by using a new class of sparse binary compressed sensing matrices of near optimal size in combination with sublinear-time recovery techniques motivated by sketching algorithms for high-volume data streams. The new class of matrices is constructed by randomly subsampling rows from well-chosen incoherent matrix constructions which already have a sub-linear number of rows. As a consequence, fewer random bits than previously required are needed in order to select the rows utilized by the fast reconstruction algorithms considered herein.

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

Recommendations

• Combinatorial Algorithms for Compressed Sensing
• Sublinear time, measurement-optimal, sparse recovery for all
• Nearly linear-time model-based compressive sensing
• Approximate sparse recovery: optimizing time and measurements
• Approximate sparse recovery: optimizing time and measurements

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)

Cites Work

• Stable signal recovery from incomplete and inaccurate measurements
• Compressed sensing
• Iterative hard thresholding for compressed sensing
• Compressed sensing and best \(k\)-term approximation
• A mathematical introduction to compressive sensing
• An improved data stream summary: the count-min sketch and its applications
• Improved approximation guarantees for sublinear-time Fourier algorithms
• Title not available (Why is that?)
• Deterministic constructions of compressed sensing matrices
• Title not available (Why is that?)
• Approximate sparse recovery: optimizing time and measurements
• Title not available (Why is that?)
• Combinatorial Algorithms for Compressed Sensing
• Lower bounds for sparse recovery
• Title not available (Why is that?)
• Title not available (Why is that?)
• Efficient and Robust Compressed Sensing Using Optimized Expander Graphs
• On the design of deterministic matrices for fast recovery of Fourier compressible functions
• (1 + eps)-Approximate Sparse Recovery

Cited In (13)

• Sparse recovery properties of discrete random matrices
• Construction of sparse binary sensing matrices using set systems
• Fast Phase Retrieval from Local Correlation Measurements
• Approximate sparse recovery: optimizing time and measurements
• Nearly linear-time model-based compressive sensing
• Derandomized compressed sensing with nonuniform guarantees for \(\ell_1\) recovery
• Sparse harmonic transforms: a new class of sublinear-time algorithms for learning functions of many variables
• Lower Memory Oblivious (Tensor) Subspace Embeddings with Fewer Random Bits: Modewise Methods for Least Squares
• Efficiently decodable compressed sensing by list-recoverable codes and recursion
• Sparse harmonic transforms. II: Best \(s\)-term approximation guarantees for bounded orthonormal product bases in sublinear-time
• Combinatorial Algorithms for Compressed Sensing
• Robust sparse phase retrieval made easy
• Sublinear time, measurement-optimal, sparse recovery for all

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

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