Living on the edge: Phase transitions in convex programs with random data
arXiv:1303.6672
Abstract
Recent research indicates that many convex optimization problems with random constraints exhibit a phase transition as the number of constraints increases. For example, this phenomenon emerges in the minimization method for identifying a sparse vector from random linear measurements. Indeed, the approach succeeds with high probability when the number of measurements exceeds a threshold that depends on the sparsity level; otherwise, it fails with high probability. This paper provides the first rigorous analysis that explains why phase transitions are ubiquitous in random convex optimization problems. It also describes tools for making reliable predictions about the quantitative aspects of the transition, including the location and the width of the transition region. These techniques apply to regularized linear inverse problems with random measurements, to demixing problems under a random incoherence model, and also to cone programs with random affine constraints. The applied results depend on foundational research in conic geometry. This paper introduces a summary parameter, called the statistical dimension, that canonically extends the dimension of a linear subspace to the class of convex cones. The main technical result demonstrates that the sequence of intrinsic volumes of a convex cone concentrates sharply around the statistical dimension. This fact leads to accurate bounds on the probability that a randomly rotated cone shares a ray with a fixed cone.
arXiv commentFirst version, 26 March 2013. This version, 24 April 2014. 52 pages, 12 figures, 3 tables
References in corpus (5)
- Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization
- Message Passing Algorithms for Compressed Sensing
- Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
- Universality in polytope phase transitions and message passing algorithms
- The Phase Transition of Matrix Recovery from Gaussian Measurements Matches the Minimax MSE of Matrix Denoising
Cited by in corpus (15)
- On risk bounds in isotonic and other shape restricted regression problems
- A new perspective on least squares under convex constraint
- High-dimensional estimation with geometric constraints
- Geometric Inference for General High-Dimensional Linear Inverse Problems
- Tight convex relaxations for sparse matrix factorization
- Asymptotic Analysis of LASSOs Solution Path with Implications for Approximate Message Passing
- The Gaussian min-max theorem in the Presence of Convexity
- Sharp MSE Bounds for Proximal Denoising
- Precise Error Analysis of Regularized M-estimators in High-dimensions
- Sparse Spikes Deconvolution on Thin Grids
- Learning Tensors in Reproducing Kernel Hilbert Spaces with Multilinear Spectral Penalties
- Asymptotically Exact Error Analysis for the Generalized -LASSO
- Sharp recovery bounds for convex demixing, with applications
- On the volume of tubular neighborhoods of real algebraic varieties
- Multireference Alignment using Semidefinite Programming