The Library
Living on the edge : phase transitions in convex programs with random data
Tools
Tools
Tools
Amelunzen, D., Lotz, Martin, McCoy, M. B. and Tropp, J. A. (2014) Living on the edge : phase transitions in convex programs with random data. Information and Inference, 3 (3). pp. 224-294. doi:10.1093/imaiai/iau005
|
PDF
WRAP-living-edge-phase-transitions-convex-programs-random-data-Lotz-2014.pdf - Accepted Version - Requires a PDF viewer. Download (2290Kb) | Preview |
Official URL: http://dx.doi.org/10.1093/imaiai/iau005
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: | Journal Article | |||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | |||||||||||||||||||||||||||
| Divisions: | Faculty of Science > Mathematics | |||||||||||||||||||||||||||
| Library of Congress Subject Headings (LCSH): | Convex functions, Conic sections, Mathematical optimization , Functions of complex variables | |||||||||||||||||||||||||||
| Journal or Publication Title: | Information and Inference | |||||||||||||||||||||||||||
| Publisher: | Oxford University Press | |||||||||||||||||||||||||||
| ISSN: | 2049-8764 | |||||||||||||||||||||||||||
| Official Date: | 30 June 2014 | |||||||||||||||||||||||||||
| Dates: |
|
|||||||||||||||||||||||||||
| Volume: | 3 | |||||||||||||||||||||||||||
| Number: | 3 | |||||||||||||||||||||||||||
| Page Range: | pp. 224-294 | |||||||||||||||||||||||||||
| DOI: | 10.1093/imaiai/iau005 | |||||||||||||||||||||||||||
| Status: | Peer Reviewed | |||||||||||||||||||||||||||
| Publication Status: | Published | |||||||||||||||||||||||||||
| Publisher Statement: | This is a pre-copyedited, author-produced version of an article accepted for publication in Information and Inference following peer review. The version of record Dennis Amelunxen, Martin Lotz, Michael B. McCoy, Joel A. Tropp, Living on the edge: phase transitions in convex programs with random data, Information and Inference: A Journal of the IMA, Volume 3, Issue 3, September 2014, Pages 224–294, https://doi.org/10.1093/imaiai/iau005 is available online at: https://doi.org/10.1093/imaiai/iau005 | |||||||||||||||||||||||||||
| Access rights to Published version: | Open Access | |||||||||||||||||||||||||||
| RIOXX Funder/Project Grant: |
|
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
