Living on the edge: A geometric theory of phase transitions in convex optimization

Mike McCoy just sent me the following: 

Hello Igor,

My collaborators and I have a paper, hot off the press, that explains the ubiquity of phase transitions in convex optimization programs with random constraints. I expect it will be interesting to your readers that are curious about foundational aspects of compressed sensing, and I know you are keen on phase transitions yourself. I'd be grateful if you would advertise this on your website.

The paper can be found here, here, and on the arXiv. [Detailed info below.]

Thanks very much,

Mike McCoy

Thanks Mike, as you noted phase transition is of interest on both the theoretical side but also of primal interest when designing compressive sensors. Without further due here is the paper: Living on the edge: A geometric theory of phase transitions in convex optimization by Dennis Amelunxen  Martin Lotz  Michael B. McCoy  and Joel Tropp. The abstract reads:

Recent empirical 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 l1 minimization method for identifying a sparse vector from random linear samples. Indeed, this approach succeeds with high probability when the number of samples 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.

These applications depend on foundational research in conic geometry. This paper introduces a new 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 conic intrinsic volumes of a convex cone concentrates sharply near the statistical dimension. This fact leads to an approximate version of the conic kinematic formula that gives bounds on the probability that a randomly oriented cone shares a ray with a fixed cone.

An earlier paper of interest: M.B. McCoy and J.A. Tropp, Sharp bounds for convex deconvolution, with applications.. 2012.preprint.

Credit: Aerosmith - Livin' On The Edge

Join the CompressiveSensing subreddit or the Google+ Community and post there !

Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.