Sharp recovery bounds for convex demixing, with applications
From MaRDI portal
(Redirected from Publication:404302)
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.
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
Cites work
- scientific article; zbMATH DE number 1266748 (Why is no real title available?)
- scientific article; zbMATH DE number 1534289 (Why is no real title available?)
- scientific article; zbMATH DE number 873911 (Why is no real title available?)
- scientific article; zbMATH DE number 3244470 (Why is no real title available?)
- A unified framework for high-dimensional analysis of M-estimators with decomposable regularizers
- An analog scrambling scheme which does not expand bandwidth, Part I: Discrete time
- An analog scrambling scheme which does not expand bandwidth, Part II: Continuous time
- An asymptotic estimate of the average number of steps of the parametric simplex method
- Analysis versus synthesis in signal priors
- Analyzing Weighted $\ell_1$ Minimization for Sparse Recovery With Nonuniform Sparse Models
- Atomic Decomposition by Basis Pursuit
- Compressed sensing
- Compressed sensing with coherent and redundant dictionaries
- Compressive principal component pursuit
- Corrupted Sensing: Novel Guarantees for Separating Structured Signals
- Counting faces of randomly projected polytopes when the projection radically lowers dimension
- Counting the faces of randomly-projected hypercubes and orthants, with applications
- Dense Error Correction Via \ell^1-Minimization
- Elliptically contoured distributions
- Exact Recoverability From Dense Corrupted Observations via $\ell _{1}$-Minimization
- Exponential Bounds Implying Construction of Compressed Sensing Matrices, Error-Correcting Codes, and Neighborly Polytopes by Random Sampling
- Graph implementations for nonsmooth convex programs
- Graßmann angles of convex polytopes
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- High-dimensional centrally symmetric polytopes with neighborliness proportional to dimension
- How to generate random matrices from the classical compact groups
- Image decomposition via the combination of sparse representations and a variational approach
- Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting
- Integrable KP coupling and its exact solution
- Intrinsic volumes of symmetric cones and applications in convex programming
- Linear Inversion of Band-Limited Reflection Seismograms
- Living on the edge: phase transitions in convex programs with random data
- Morphological Diversity and Sparsity in Blind Source Separation
- NIST handbook of mathematical functions
- Near Minimax Line Spectral Estimation
- Neighborliness of randomly projected simplices in high dimensions
- Non-linear angle-sum relations for polyhedral cones and polytopes
- Nonlinear methods of approximation
- Observed universality of phase transitions in high-dimensional geometry, with implications for modern data analysis and signal processing
- On the geometrical moments of skew-regular simplices in hyperspherical space, with some applications in geometry and mathematical statistics
- On the linear independence of spikes and sines
- Precise Stability Phase Transitions for \ell₁ Minimization: A Unified Geometric Framework
- Probabilistic Recovery Guarantees for Sparsely Corrupted Signals
- Probability of unique integer solution to a system of linear equations
- Random projections of regular polytopes
- Random projections of regular simplices
- Rank-Sparsity Incoherence for Matrix Decomposition
- Recovery of Sparsely Corrupted Signals
- Restricted strong convexity and weighted matrix completion: optimal bounds with noise
- Robust PCA via Outlier Pursuit
- Robust principal component analysis?
- Robust smoothed analysis of a condition number for linear programming
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Separation Properties of Convex Cones
- Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
- Signal Recovery on Incoherent Manifolds
- Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA)
- Some remarks on greedy algorithms
- Sparse solutions to linear inverse problems with multiple measurement vectors
- Stochastic and Integral Geometry
- The convex geometry of linear inverse problems
- Two proposals for robust PCA using semidefinite programming
- Uncertainty Principles and Signal Recovery
- Uncertainty principles and ideal atomic decomposition
- Universality in polytope phase transitions and message passing algorithms
Cited in
(17)- Super-resolution of point sources via convex programming
- Living on the edge: phase transitions in convex programs with random data
- Intersection probabilities and kinematic formulas for polyhedral cones
- Conic support measures
- Signal Decomposition Using Masked Proximal Operators
- Stable low-rank matrix recovery via null space properties
- A convex program for mixed linear regression with a recovery guarantee for well-separated data
- Sparse recovery from extreme eigenvalues deviation inequalities
- Uniform recovery guarantees for quantized corrupted sensing using structured or generative priors
- Robust recovery of sparse non-negative weights from mixtures of positive-semi-definite matrices
- A proximal-based algorithm for piecewise sparse approximation with application to scattered data fitting
- Robust non-parametric regression via incoherent subspace projections
- Concentration of the intrinsic volumes of a convex body
- Sparse blind deconvolution and demixing through \(\ell_{1,2}\)-minimization
- A Rice method proof of the null-space property over the Grassmannian
- Discrete uncertainty principles and sparse signal processing
- Painless breakups -- efficient demixing of low rank matrices
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)
