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: yi=g(innerbaibPhibw^ast+bPsibz^ast)+ei, i=1,dots,m, with mll n, incoherent orthonormal bases bPhi,bPsi, a scalar link g, and noise ei 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--Lojasiewicz 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 σ√slog(n)/m that hold at every localized stationary point, an oracle rate σ√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 ℓ1 demixing and greedy hard-thresholding baselines, a 35× accuracy advantage over squared-loss estimation under 5% gross outliers, and successful demixing of spike-plus-background signals observed through a saturating amplifier.