Sublinear Time, Approximate Model-based Sparse Recovery For All

2012/03/21 by Anastasios Kyrillidis, Volkan Cevher, Kyrillidis, Anastasios +1
Computer Science · Engineering · #FOS: Computer and information sciences #Information Theory (cs.IT) #Microwave Imaging and Scattering Analysis #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1203.4746

openalex publication_date 2012/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We describe a probabilistic, \it sublinear runtime, measurement-optimal system for model-based sparse recovery problems through dimensionality reducing, \em dense random matrices. Specifically, we obtain a linear sketch u∈ \R^M of a vector \bestsignal∈ \R^N in high-dimensions through a matrix Φ∈ \R^{M× N} (M

Citations

• Sparse Approximate Solutions to Linear Systems
• CoSaMP: Iterative signal recovery from incomplete and inaccurate samples

Related

• Sublinear Time, Measurement-Optimal, Sparse Recovery For All
• On the Performance of Sparse Recovery via L_p-minimization (0<=p <=1)
• The exact recovery with sub-exponential measurement matrix
• Simple Bounds for Recovering Low-complexity Models
• Semi-Random Sparse Recovery in Nearly-Linear Time