Fast Algorithms for Demixing Sparse Signals From Nonlinear Observations

DOI10.1109/TSP.2017.2706181zbMATH Open1414.94578arXiv1608.01234OpenAlexW2487980609MaRDI QIDQ4621799FDOQ4621799

Authors: Mohammad Reza Soltani, Chinmay Hegde 

Publication date: 8 February 2019

Published in: IEEE Transactions on Signal Processing (Search for Journal in Brave)

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,ldots,m$, where $x=Phiw+Psiz$ denotes the superposition signal, $Phi$ and $Psi$ are orthonormal bases in $mathbb{R}^n$, and $w,zinmathbb{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}inmathbb{R}^n$ is the $i$-th row of the measurement matrix, $Ainmathbb{R}^{mimesn}$. 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.

Full work available at URL: https://arxiv.org/abs/1608.01234

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (3)

• Algorithms for fast multidimensional signal extraction
• Fast nonlinear autocorrelation algorithm for source separation
• Title not available (Why is that?)

This page was built for publication: Fast Algorithms for Demixing Sparse Signals From Nonlinear Observations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4621799)