Demixing Structured Signal form their Nonlinear Superposition

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,m$, where $x = \Phi w+\Psi z$ denotes the superposition signal, $\Phi$ and $\Psi$ are orthonormal bases in $\mathbb{R}^n$, and $w, z\in\mathbb{R}^n$ are sparse coefficient vectors of the constituent signals, and $e_i$ represents the noise. Moreover, $g$ represents a nonlinear *link* function, and $a_i\in\mathbb{R}^n$ is the $i$-th row of the measurement matrix, $A\in\mathbb{R}^{m\times n}$. Problems of this nature arise in several applications ranging from astronomy, computer vision, and machine learning. We make some concrete algorithmic progress for the above demixing problem. Specifically, we consider two scenarios: (i) the case when the demixing procedure has no knowledge of the link function, and (ii) the case when the demixing algorithm has perfect knowledge of the link function. In both cases, we provide fast algorithms for recovery of the constituents $w$ and $z$ from the observations. Moreover, we support these algorithms with a rigorous theoretical analysis, and derive (nearly) tight upper bounds on the sample complexity of the proposed algorithms for achieving stable recovery of the component signals.

  1. M. Soltani and C. Hegde, Fast Algorithms for Demixing Sparse Signals from Nonlinear Observations, IEEE Transactions on Signal Processing, vol. 65, no. 16, p4209-4222, Aug 2017. [Paper]

  2. M. Soltani and C. Hegde, Stable Recovery from Random Sinusoidal Feature Maps, International Conference on Acoustics, Speech, and Signal Processing (ICASSP), March 2017 [Paper]

  3. M. Soltani and C. Hegde, Iterative Thresholding for Demixing Structured Superpositions in High Dimensions, NIPS Workshop on Learning in High Dimensions with Structure (LHDS), December 2016. [Paper]

  4. M. Soltani and C. Hegde, A Fast iterative Algorithm for Demixing Sparse Signals from Nonlinear Observations, IEEE GlobalSIP Symposium on Compressed Sensing and Deep Learning, Dec 2016. [Paper]


Mohammadreza Soltani
(PhD'19, Postdoc at Duke.)
Chinmay Hegde
Assistant Professor, ECPE