Local Minima and Convergence in Low-Rank Semidefinite Programming

By S. Burer, Renato D. C. Monteiro. 2005

421 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computational Theory and Mathematics

In Numerical Analysis

Citations in the corpus

Spectral Regularization Algorithms for Learning Large Incomplete Matrices (2010, background): “[ BM05 , RS05] that bi-convex methods used in the optimization of (6) get stuck in suboptimal local minima if the rank r is small.”
Parallel stochastic gradient algorithms for large-scale matrix completion (2013, background): “3.2 Epochs Computing a solution to desired tolerance typically requires several passes over the data set.”
Relaxations for inference in restricted Boltzmann machines (2013, background): “Extensive properties of LRPk are studied in Burer & Monteiro (2005).”
Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization (2007, methodology): “As a consequence of the work in [9], it will follow that for values of r larger than the rank of the true optimal solution, the local minima of (5.”
Blind Deconvolution Using Convex Programming (2012, background): “Burer and Monteiro showed that provided r is bigger than the rank of the optimal solution of (8), all of the local minima of (19) were global minima of (8) [30].”
Global Optimality of Local Search for Low Rank Matrix Recovery (2016, background): “It was also shown that (under mild conditions) any rank deficient local minima is a global minima [4, 16], providing a post-hoc verifiable sufficient condition for global optimality.”
Fixed point and Bregman iterative methods for matrix rank minimization (2009, background): “7) is due to Burer and Monte iro [6; 7], (see also Rennie and Srebro [33; 36]).”
Primal-dual first-order methods with $${\mathcal {O}(1/\epsilon)}$$ iteration-complexity for cone programming (2011, methodology): “The latter termination criterion is used when comparing the variant of Nesterov’s method with Burer and Monteiro’s low-rank method which, being a primal-only method, generates only x and a dual estimate y based on x. 5.2 Comparisons of three first-order methods for LP In this subsection, we compare ”
The three R's of computer vision: Recognition, reconstruction and reorganization (2016, positive): “For each trajectory cluster, we first complete the 2D trajectory matrix using low-rank matrix completion, as in [9,11] .”
Dropping Convexity for Faster Semi-definite Optimization (2015, methodology): “Burer and Monteiro [15, 16] popularized the idea of solving classic SDPs by representing the solution as a product of two factor matrices.”
Matrix Completion and Low-Rank SVD via Fast Alternating Least Squares (2014, background): “Similarly, following the above steps for the B -update we have: Adding (81) and (82) we get (37) concluding the proof of the lemma.”
An Overview of Low-Rank Matrix Recovery From Incomplete Observations (2016, methodology): “A ( LR T ) is a combination of products of unknowns — there are assurances that the local minima in (10) are also global minima if the rank of the true solution is smaller than R [17].”
Fast and Accurate Matrix Completion via Truncated Nuclear Norm Regularization (2013, methodology): “It has been observed empirically and theoretically [35], [32] that biconvex methods used in the optimization of (5) get stuck in suboptimal local minimum if the rank r is small.”
Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees (2015, background): “The seminal work in [12] studies the problem of obtaining low-rank solutions to SDPs using gradient descent on the factor space.”