Sharp recovery bounds for convex demixing, with applications
From MaRDI portal
Publication:404302
DOI10.1007/S10208-014-9191-2zbMATH Open1312.94016arXiv1205.1580OpenAlexW2051237969MaRDI QIDQ404302FDOQ404302
Authors: Michael B. McCoy, Joel A. Tropp 
Publication date: 4 September 2014
Published in: Foundations of Computational Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1205.1580
Recommendations
- Super-resolution of point sources via convex programming
- Sparse blind deconvolution and demixing through \(\ell_{1,2}\)-minimization
- Painless breakups -- efficient demixing of low rank matrices
- Rapid, robust, and reliable blind deconvolution via nonconvex optimization
- Regularized gradient descent: a non-convex recipe for fast joint blind deconvolution and demixing
Convex programming (90C25) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Geometric probability and stochastic geometry (60D05)
Cites Work
- NIST handbook of mathematical functions
- Atomic Decomposition by Basis Pursuit
- Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
- A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers
- Robust principal component analysis?
- How to generate random matrices from the classical compact groups
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- Dense Error Correction Via $\ell^1$-Minimization
- Restricted strong convexity and weighted matrix completion: Optimal bounds with noise
- Rank-Sparsity Incoherence for Matrix Decomposition
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Compressed sensing
- Title not available (Why is that?)
- Graph implementations for nonsmooth convex programs
- Stochastic and Integral Geometry
- Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
- Title not available (Why is that?)
- Uncertainty principles and ideal atomic decomposition
- Precise Stability Phase Transitions for $\ell_1$ Minimization: A Unified Geometric Framework
- Sparse solutions to linear inverse problems with multiple measurement vectors
- Neighborliness of randomly projected simplices in high dimensions
- Nonlinear methods of approximation
- Some remarks on greedy algorithms
- Robust PCA via Outlier Pursuit
- Random projections of regular simplices
- Two proposals for robust PCA using semidefinite programming
- High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension
- Uncertainty Principles and Signal Recovery
- Compressive principal component pursuit
- The convex geometry of linear inverse problems
- Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA)
- Near Minimax Line Spectral Estimation
- Probabilistic Recovery Guarantees for Sparsely Corrupted Signals
- Image decomposition via the combination of sparse representations and a variational approach
- Living on the edge: phase transitions in convex programs with random data
- Analysis versus synthesis in signal priors
- Counting faces of randomly projected polytopes when the projection radically lowers dimension
- Exponential Bounds Implying Construction of Compressed Sensing Matrices, Error-Correcting Codes, and Neighborly Polytopes by Random Sampling
- Separation Properties of Convex Cones
- Probability of unique integer solution to a system of linear equations
- Counting the faces of randomly-projected hypercubes and orthants, with applications
- Intrinsic volumes of symmetric cones and applications in convex programming
- Graßmann angles of convex polytopes
- Non-linear angle-sum relations for polyhedral cones and polytopes
- Title not available (Why is that?)
- Title not available (Why is that?)
- Compressed sensing with coherent and redundant dictionaries
- Universality in polytope phase transitions and message passing algorithms
- Corrupted Sensing: Novel Guarantees for Separating Structured Signals
- Linear Inversion of Band-Limited Reflection Seismograms
- Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting
- Elliptically contoured distributions
- Random projections of regular polytopes
- On the geometrical moments of skew-regular simplices in hyperspherical space, with some applications in geometry and mathematical statistics
- Exact Recoverability From Dense Corrupted Observations via $\ell _{1}$-Minimization
- Signal Recovery on Incoherent Manifolds
- Morphological Diversity and Sparsity in Blind Source Separation
- An asymptotic estimate of the average number of steps of the parametric simplex method
- An analog scrambling scheme which does not expand bandwidth, Part II: Continuous time
- An analog scrambling scheme which does not expand bandwidth, Part I: Discrete time
- Analyzing Weighted $\ell_1$ Minimization for Sparse Recovery With Nonuniform Sparse Models
- Integrable KP Coupling and Its Exact Solution
- Recovery of Sparsely Corrupted Signals
- Robust smoothed analysis of a condition number for linear programming
- On the linear independence of spikes and sines
Cited In (12)
- Super-resolution of point sources via convex programming
- Signal Decomposition Using Masked Proximal Operators
- Stable low-rank matrix recovery via null space properties
- Intersection probabilities and kinematic formulas for polyhedral cones
- Conic support measures
- Concentration of the Intrinsic Volumes of a Convex Body
- Sparse recovery from extreme eigenvalues deviation inequalities
- Uniform recovery guarantees for quantized corrupted sensing using structured or generative priors
- A proximal-based algorithm for piecewise sparse approximation with application to scattered data fitting
- Robust non-parametric regression via incoherent subspace projections
- A Rice method proof of the null-space property over the Grassmannian
- Discrete uncertainty principles and sparse signal processing
Uses Software
This page was built for publication: Sharp recovery bounds for convex demixing, with applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q404302)
