Sharp recovery bounds for convex demixing, with applications
arXiv:1205.1580
Abstract
Demixing refers to the challenge of identifying two structured signals given only the sum of the two signals and prior information about their structures. Examples include the problem of separating a signal that is sparse with respect to one basis from a signal that is sparse with respect to a second basis, and the problem of decomposing an observed matrix into a low-rank matrix plus a sparse matrix. This paper describes and analyzes a framework, based on convex optimization, for solving these demixing problems, and many others. This work introduces a randomized signal model which ensures that the two structures are incoherent, i.e., generically oriented. For an observation from this model, this approach identifies a summary statistic that reflects the complexity of a particular signal. The difficulty of separating two structured, incoherent signals depends only on the total complexity of the two structures. Some applications include (i) demixing two signals that are sparse in mutually incoherent bases; (ii) decoding spread-spectrum transmissions in the presence of impulsive errors; and (iii) removing sparse corruptions from a low-rank matrix. In each case, the theoretical analysis of the convex demixing method closely matches its empirical behavior.
arXiv comment51 pages, 13 figures, 2 tables. This version accepted to J. Found. Comput. Math
References in corpus (13)
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
- Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
- Latent variable graphical model selection via convex optimization
- Universality in polytope phase transitions and message passing algorithms
- A framework to characterize performance of LASSO algorithms
- Various thresholds for -optimization in compressed sensing
- On the linear independence of spikes and sines
- The achievable performance of convex demixing
- Living on the edge: Phase transitions in convex programs with random data
- Near Minimax Line Spectral Estimation
- Sharp MSE Bounds for Proximal Denoising
- Intrinsic volumes of symmetric cones
Cited by in corpus (6)
- An Online Algorithm for Separating Sparse and Low-dimensional Signal Sequences from their Sum
- Sharp MSE Bounds for Proximal Denoising
- Recursive Sparse Recovery in Large but Structured Noise - Part 2
- Signal Recovery on Incoherent Manifolds
- A Correctness Result for Online Robust PCA
- Probabilistic Recovery Guarantees for Sparsely Corrupted Signals