Sparse Recovery with Linear and Nonlinear Observations: Dependent and Noisy Data
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.
Code (0)
등록된 구현이 없습니다.
Tasks
regressionSimilar Papers 제목 키워드 기반
Fast Algorithms for Demixing Sparse Signals from Nonlinear Observations
We study the problem of demixing a pair of sparse signals from noisy, nonlinear observations of their superposition. Mathematically, we consider a nonlinear signal observation model, $y_i = g(a_i^Tx) + e_i, \ i=1,\ldots,…
AstronomyDemixing Sparse Signals from Nonlinear Observations using Generalized Non-convex Regularization
We consider the recovery of a pair of sparse vectors from a limited number of nonlinear observations of their superposition: $y_i=g(\inner{\ba_i}{\bPhi\bw^\ast+\bPsi\bz^\ast})+e_i$, $i=1,\dots,m$, with $m\ll n$, incohere…
On the Identifiability of Quantized Factors
Disentanglement aims to recover meaningful latent ground-truth factors from the observed distribution solely, and is formalized through the theory of identifiability. The identifiability of independent latent factors is …
DisentanglementInductive BiasSparse Signal Processing with Linear and Nonlinear Observations: A Unified Shannon-Theoretic Approach
We derive fundamental sample complexity bounds for recovering sparse and structured signals for linear and nonlinear observation models including sparse regression, group testing, multivariate regression and problems wit…
regressionThe Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements
We consider the problem of support recovery for sparse binary signals from noisy linear measurements. For sparse Gaussian measurement matrices we identify sufficient conditions on the minimal sample size for maximum-like…