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(+)+e i, i=1,,m, with m n, incoherent orthonormal bases,, 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 sigma sqrt s (n)/m that hold at every localized stationary point, an oracle rate sigma sqrt s/m free of 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 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.