Phase transitions in semidefinite relaxations
Abstract
Modern data analysis requires solving hard optimization problems with a large number of parameters and a large number of constraints. A successful approach is to replace these hard problems by surrogate problems that are convex and hence tractable. Semidefinite programming relaxations offer a powerful method to construct such relaxations. In many instances it was observed that a semidefinite relaxation becomes very accurate when the noise level in the data decreases below a certain threshold. We develop a new method to compute these noise thresholds (or phase transitions) using ideas from statistical physics.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Mar 21, 2016
- Source ID
- 10.1073/pnas.1523097113
Entities
People
- Adel Javanmard
- Andrea Montanari
- Federico Ricci-tersenghi
Organizations
- Air Force Office of Scientific Research
- Istituto Nazionale di Fisica Nucleare
- National Science Foundation
- Sapienza University of Rome
- Stanford University
- University of Southern California