Fast Algorithms for Demixing Sparse Signals from Nonlinear Observations

Abstract

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^{T}x)+e_i,i=1,\dots ,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: (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. We also provide a range of numerical simulations to illustrate the performance of the proposed algorithms on both real and synthetic signals and images.

References in corpus (19)

• Sparsity and Incoherence in Compressive Sampling
• From Theory to Practice: Sub-Nyquist Sampling of Sparse Wideband Analog Signals
• Rank-Sparsity Incoherence for Matrix Decomposition
• Compressed Sensing and Redundant Dictionaries
• Latent variable graphical model selection via convex optimization
• A Unified Framework for High-Dimensional Analysis of M-Estimators with Decomposable Regularizers
• The LASSO with Non-linear Measurements is Equivalent to One With Linear Measurements
• Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization
• High Dimensional Low Rank plus Sparse Matrix Decomposition
• On Iterative Hard Thresholding Methods for High-dimensional M-Estimation
• Efficient Learning of Generalized Linear and Single Index Models with Isotonic Regression
• High-dimensional estimation with geometric constraints
• Convexity in source separation: Models, geometry, and algorithms
• Compressed Sensing with Coherent and Redundant Dictionaries
• Sparse Nonlinear Regression: Parameter Estimation and Asymptotic Inference
• Screen Content Image Segmentation Using Sparse-Smooth Decomposition
• Learning Single Index Models in High Dimensions
• Optimal linear estimation under unknown nonlinear transform
• Matrix Completion Under Monotonic Single Index Models

Cited by in corpus (5)

• Spatial Random Sampling: A Structure-Preserving Data Sketching Tool
• Iterative Thresholding for Demixing Structured Superpositions in High Dimensions
• Learning Generative Models of Structured Signals from Their Superposition Using GANs with Application to Denoising and Demixing
• Learning Illumination Patterns for Coded Diffraction Phase Retrieval
• Provably Convergent Algorithms for Solving Inverse Problems Using Generative Models