• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
  •   BIRD Home
  • CEREMADE (UMR CNRS 7534)
  • CEREMADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Rank optimality for the Burer-Monteiro factorization

Waldspurger, Irène; Waters, Alden (2020), Rank optimality for the Burer-Monteiro factorization, SIAM Journal on Optimization, 30, 3, p. 2577-2602. 10.1137/19M1255318

View/Open
matrices.pdf (629.0Kb)
Type
Article accepté pour publication ou publié
Date
2020
Journal name
SIAM Journal on Optimization
Volume
30
Number
3
Publisher
SIAM - Society for Industrial and Applied Mathematics
Pages
2577-2602
Publication identifier
10.1137/19M1255318
Metadata
Show full item record
Author(s)
Waldspurger, Irène
CEntre de REcherches en MAthématiques de la DEcision [CEREMADE]
Waters, Alden
Bernoulli Institute for Mathematics and Computer Science and Artificial Intelligence
Abstract (EN)
When solving large-scale semidefinite programs that admit a low-rank solution, an efficient heuristic is the Burer--Monteiro factorization: instead of optimizing over the full matrix, one optimizes over its low-rank factors. This reduces the number of variables to optimize but destroys the convexity of the problem, thus possibly introducing spurious second-order critical points. The article [N. Boumal, V. Voroninski, and A. S. Bandeira, Deterministic Guarantees for Burer-Monteiro Factorizations of Smooth Semidefinite Programs, https://arxiv.org/abs/1804.02008, 2018] shows that when the size of the factors is of the order of the square root of the number of linear constraints, this does not happen: for almost any cost matrix, second-order critical points are global solutions. In this article, we show that this result is essentially tight: for smaller values of the size, second-order critical points are not generically optimal, even when the global solution is rank 1.
Subjects / Keywords
semidefinite programming; Burer-Monteiro factorization

Related items

Showing items related by title and author.

  • Thumbnail
    Lecture notes on non-convex algorithms for low-rank matrix recovery 
    Waldspurger, Irène (2021) Document de travail / Working paper
  • Thumbnail
    Phase retrieval for the Cauchy wavelet transform 
    Mallat, Stéphane; Waldspurger, Irène (2015) Article accepté pour publication ou publié
  • Thumbnail
    Phase retrieval for wavelet transforms 
    Waldspurger, Irène (2017) Article accepté pour publication ou publié
  • Thumbnail
    A system dynamics model for supporting decision-makers in irrigation water management 
    Pluchinotta, Irene; Pagano, Alessandro; Giordano, Raffaele; Tsoukiàs, Alexis (2018) Article accepté pour publication ou publié
  • Thumbnail
    Multi-Agent Modelling for Distributed Intelligent Decision in Water Management 
    Pluchinotta, Irene (2015-03) Thèse
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo