Demixing 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, 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 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 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.