Demixing Sparse Signals from Nonlinear Observations using Generalized Non-convex Regularization
2026-07-12 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study how to recover two sparse signals that are combined and observed through a complicated, nonlinear process with noise. They propose a method that uses a special type of loss function (Huberized) and advanced penalties (SCAD, MCP) to handle noise and sparsity, along with an algorithm that reliably converges to good solutions. They provide mathematical guarantees on the quality of the recovered signals, even when the noise is heavy-tailed and the link function is unknown. Their experiments show their approach works better than some standard methods, especially in noisy or corrupted data conditions.
sparse recoverynonlinear observationsHuber lossSCAD penaltyMCP penaltyproximal alternating algorithmrestricted strong convexityKurzykka–Łojasiewicz propertyheavy-tailed noisephase transition
Authors
Raziyeh Takbiri
Abstract
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$, incoherent orthonormal bases $\bPhi,\bPsi$, a scalar link $g$, and noise $e_i$ that may be heavy-tailed or contaminated. We propose a regularization-based framework combining a Huberized data fidelity with generalized folded-concave penalties (SCAD, MCP), and a two-block proximal alternating algorithm with backtracking (NLD-PALM) whose whole iterate sequence provably converges to critical points under the Kurdyka--Łojasiewicz property, with local linear rates. On the statistical side we establish restricted strong convexity of the Huberized nonlinear loss through an exact sign-definite decomposition, and derive estimation error bounds of order $σ\sqrt{s\log(n)/m}$ that hold at \emph{every} localized stationary point, an oracle rate $σ\sqrt{s/m}$ free of $\log n$ and shrinkage bias under a beta-min condition, and a co-equal recovery theorem for \emph{unknown} monotone links via a linear surrogate and a clipped Plan--Vershynin decoupling. The estimator requires no knowledge of the sparsity levels, and its guarantees hold under symmetric noise with only finite variance. Experiments at $n=512$ under a frozen data-driven regularization rule show an earlier phase transition than convex $\ell_1$ demixing and greedy hard-thresholding baselines, a $35\times$ accuracy advantage over squared-loss estimation under $5\%$ gross outliers, and successful demixing of spike-plus-background signals observed through a saturating amplifier.