Nuit Blanche: Fast Algorithms for Demixing Sparse Signals from Nonlinear Observations / Fast recovery from a union of subspaces

Tuesday, August 09, 2016

Fast Algorithms for Demixing Sparse Signals from Nonlinear Observations / Fast recovery from a union of subspaces

Fast Algorithms for Demixing Sparse Signals from Nonlinear Observations by Mohammadreza Soltani, Chinmay Hegde

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
T

i
x)+
ei
, i=1,…,m

, where
x=Φw+Ψz

denotes the superposition signal, Φ

and Ψ

are orthonormal bases in Rn

, and
w,z∈
Rn

are sparse coefficient vectors of the constituent signals, and ei

represents the noise. Moreover,
g

represents a nonlinear link function, and ai
∈
Rn

is the i

-th row of the measurement matrix,
A∈
Rm×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.

and earlier:
Fast recovery from a union of subspaces by Chinmay Hegde, Piotr Indyk, Ludwig Schmidt

Abstract We address the problem of recovering a high-dimensional but structured vector from linear observations in a general setting where the vector can come from an arbitrary union of subspaces. This setup includes well-studied problems such as compressive sensing and low-rank matrix recovery. We show how to design more efficient algorithms for the union-of-subspace recovery problem by using approximate projections. Instantiating our general framework for the lowrank matrix recovery problem gives the fastest provable running time for an algorithm with optimal sample complexity. Moreover, we give fast approximate projections for 2D histograms, another well-studied low-dimensional model of data. We complement our theoretical results with experiments demonstrating that our framework also leads to improved time and sample complexity empirically.