Sparse Recovery with Linear and Nonlinear Observations: Dependent and Noisy Data

2014/03/12 by Cem Aksoylar, Venkatesh Saligrama, Aksoylar, Cem +1 · 1 citation
Computer Science · Earth and Planetary Sciences · Engineering · #FOS: Computer and information sciences #FOS: Mathematics #Image and Signal Denoising Methods #Information Theory (cs.IT) #Machine Learning (cs.LG) #Seismic Imaging and Inversion Techniques #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST)

paper · pdf · doi:10.48550/arxiv.1403.3109

openalex publication_date 2014/03/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We formulate sparse support recovery as a salient set identification problem and use information-theoretic analyses to characterize the recovery performance and sample complexity. We consider a very general model where we are not restricted to linear models or specific distributions. We state non-asymptotic bounds on recovery probability and a tight mutual information formula for sample complexity. We evaluate our bounds for applications such as sparse linear regression and explicitly characterize effects of correlation or noisy features on recovery performance. We show improvements upon previous work and identify gaps between the performance of recovery algorithms and fundamental information.

Cited by

• Sparse Nonlinear Regression: Parameter Estimation and Asymptotic Inference

Related

• Information-Theoretic Bounds for Adaptive Sparse Recovery
• Limits on Support Recovery with Probabilistic Models: An Information-Theoretic Framework
• Information-theoretic limits on sparse signal recovery: Dense versus sparse measurement matrices
• Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting
• Sparse Support Recovery with Non-smooth Loss Functions