CaltechAUTHORS
  A Caltech Library Service

Living on the edge: phase transitions in convex programs with random data

Amelunxen, Dennis and Lotz, Martin and McCoy, Michael B. and Tropp, Joel A. (2014) Living on the edge: phase transitions in convex programs with random data. Information and Inference, 3 (3). pp. 224-294. ISSN 2049-8772. http://resolver.caltech.edu/CaltechAUTHORS:20150422-120051110

[img] PDF - Submitted Version
See Usage Policy.

1740Kb
[img] Archive (ZIP) (Supplementary Data) - Supplemental Material
See Usage Policy.

4Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20150422-120051110

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 ℓ_1 minimization method for identifying a sparse vector from random linear measurements. Indeed, the ℓ_1 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.


Item Type:Article
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1093/imaiai/iau005DOIArticle
http://imaiai.oxfordjournals.org/content/3/3/224PublisherArticle
http://imaiai.oxfordjournals.org/content/3/3/224/suppl/DC1PublisherSupplementary Data
http://arxiv.org/abs/1303.6672arXivDiscussion Paper
Additional Information:Copyright © 2015 Institute of Mathematics and its Applications. Received on 27 January 2014; revised on 24 April 2014; accepted on 25 April 2014. The authors wish to thank Babak Hassibi and Samet Oymak for helpful discussions on the connection between phase transitions and minimax risk. Jared Tanner provided detailed information about contemporary research on phase transitions for random linear inverse problems. D.A. was supported by DFG grant AM 386/1-1 and 386/1-2. M.L. was supported by Leverhulme Trust grant R41617 and a Seggie Brown Fellowship of the University of Edinburgh. M.B.M. and J.A.T. aresupported by ONR awards N00014-08-1-0883 and N00014-11-1002, AFOSR award FA9550-09-1- 0643, and a Sloan Research Fellowship.
Funders:
Funding AgencyGrant Number
Deutsche Forschungsgemeinschaft (DFG)AM 386/1-1
Deutsche Forschungsgemeinschaft (DFG)386/1-2
Leverhulme TrustR41617
University of Edinburgh Seggie Brown FellowshipUNSPECIFIED
Office of Naval Research (ONR)N00014-08-1-0883
Office of Naval Research (ONR)N00014-11-1002
Air Force Office of Scientific Research (AFOSR)FA9550-09-1- 0643
Alfred P. Sloan FoundationUNSPECIFIED
Non-Subject Keywords:Convex optimization; phase transitions; integral geometry; conic geometry; compressed sensing; 1 minimization; nuclear norm minimization; morphological component analysis; rank-sparsity decomposition.
Record Number:CaltechAUTHORS:20150422-120051110
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20150422-120051110
Official Citation:Dennis Amelunxen, Martin Lotz, Michael B. McCoy, and Joel A. Tropp Living on the edge: phase transitions in convex programs with random data Information and Inference (2014) 3 (3): 224-294 first published online June 30, 2014 doi:10.1093/imaiai/iau005
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:56879
Collection:CaltechAUTHORS
Deposited By: Joy Painter
Deposited On:22 Apr 2015 19:28
Last Modified:22 Apr 2015 19:28

Repository Staff Only: item control page