Sparse Recovery with Linear and Nonlinear Observations: Dependent and Noisy Data
This work addresses sparse recovery challenges in machine learning and signal processing, offering theoretical insights for applications like regression, but it appears incremental as it builds on existing information-theoretic frameworks.
The paper tackles the problem of sparse support recovery under general observation models with dependent and noisy data, providing non-asymptotic bounds on recovery probability and a tight mutual information formula for sample complexity, with explicit improvements over prior work.
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.