TY - JOUR

T1 - Fast Algorithms for Demixing Sparse Signals from Nonlinear Observations

AU - Soltani, Mohammadreza

AU - Hegde, Chinmay

N1 - Funding Information:
Manuscript received August 2, 2016; revised December 10, 2016 and March 1, 2017; accepted May 1, 2017. Date of publication May 18, 2017; date of current version June 16, 2017. The associate editor coordinating the review of this manuscript and approving it for publication was Dr. Tareq Alnaffouri. This work was supported by the National Science Foundation under the Grants CCF-1566281 and IIP-1632116. This paper was presented in part at the Annual Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA, USA, Nov. 2016 [1] and in part at the IEEE Global Conference Signal and Image Processing, Washington, DC, USA, Dec. 2016 [2]. (Corresponding author: Mohammadreza Soltani.) The authors are with the Department of Electrical and Computer Engineering, Iowa State University, Ames, IA 50010 USA (e-mail: msoltani@iastate.edu; chinmay@iastate.edu).

PY - 2017/8/15

Y1 - 2017/8/15

N2 - 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. In this paper, we make some concrete algorithmic progress for the above demixing problem. Specifically, we consider two scenarios: first, the case when the demixing procedure has no knowledge of the link function, and second is 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. We also provide a range of numerical simulations to illustrate the performance of the proposed algorithms on both real and synthetic signals and images.

AB - 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. In this paper, we make some concrete algorithmic progress for the above demixing problem. Specifically, we consider two scenarios: first, the case when the demixing procedure has no knowledge of the link function, and second is 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. We also provide a range of numerical simulations to illustrate the performance of the proposed algorithms on both real and synthetic signals and images.

KW - Demixing

KW - incoherence

KW - nonlinear measurements

KW - sparse recovery

UR - http://www.scopus.com/inward/record.url?scp=85028424144&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85028424144&partnerID=8YFLogxK

U2 - 10.1109/TSP.2017.2706181

DO - 10.1109/TSP.2017.2706181

M3 - Article

AN - SCOPUS:85028424144

VL - 65

SP - 4209

EP - 4222

JO - IEEE Transactions on Acoustics, Speech, and Signal Processing

JF - IEEE Transactions on Acoustics, Speech, and Signal Processing

SN - 1053-587X

IS - 16

M1 - 7931568

ER -