Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

[img]
Preview
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

Request Changes to record.

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, Engineering and Medicine > 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:
DateEvent
30 June 2014Published
25 April 2014Accepted
Volume: 3
Number: 3
Page Range: pp. 224-294
DOI: 10.1093/imaiai/iau005
Status: Peer Reviewed
Publication Status: Published
Reuse Statement (publisher, data, author rights): 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:
Project/Grant IDRIOXX Funder NameFunder ID
AM386/1-1[DFG] Deutsche Forschungsgemeinschafthttp://dx.doi.org/10.13039/501100001659
AM386/1-2[DFG] Deutsche Forschungsgemeinschafthttp://dx.doi.org/10.13039/501100001659
R41617Leverhulme Trusthttp://dx.doi.org/10.13039/501100000275
Seggie Brown FellowshipUniversity Of Edinburghhttp://dx.doi.org/10.13039/501100000848
N00014-08-1-0883Office of Naval Researchhttp://dx.doi.org/10.13039/100000006
N00014-11-1002Office of Naval Researchhttp://dx.doi.org/10.13039/100000006
FA9550-09-1-0643 Air Force Office of Scientific ResearchUNSPECIFIED
Sloan Research FellowshipAlfred P. Sloan Foundationhttp://dx.doi.org/10.13039/100000879

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us