Low-Rank Optimization on the Cone of Positive Semidefinite Matrices

DOI10.1137/080731359zbMATH Open1215.65108arXiv0807.4423OpenAlexW2117198760MaRDI QIDQ3083289FDOQ3083289

P.-A. Absil, Rodolphe Sepulchre, Michel Journée, Francis Bach

Publication date: 21 March 2011

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: We propose an algorithm for solving nonlinear convex programs defined in terms of a symmetric positive semidefinite matrix variable $X$. This algorithm rests on the factorization $X=Y{Y}^T$, where the number of columns of Y fixes the rank of $X$. It is thus very effective for solving programs that have a low rank solution. The factorization $X=Y{Y}^T$ evokes a reformulation of the original problem as an optimization on a particular quotient manifold. The present paper discusses the geometry of that manifold and derives a second order optimization method. It furthermore provides some conditions on the rank of the factorization to ensure equivalence with the original problem. The efficiency of the proposed algorithm is illustrated on two applications: the maximal cut of a graph and the sparse principal component analysis problem.

Full work available at URL: https://arxiv.org/abs/0807.4423

zbMATH Keywords

convergencesparse principal component analysisnonconvex programslarge-scale algorithmscone of symmetric positive definite matriceslow-rank constraintsmaximum-cut algorithmsRiemannian quotient manifold

Mathematics Subject Classification ID

Factor analysis and principal components; correspondence analysis (62H25) Numerical mathematical programming methods (65K05) Convex programming (90C25) Nonconvex programming, global optimization (90C26) Combinatorial optimization (90C27) Nonlinear programming (90C30) Semidefinite programming (90C22)

Cited In (64)

• Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization
• A Riemannian dimension-reduced second-order method with application in sensor network localization
• A feasible method for general convex low-rank SDP problems
• Which constraints of a numerical problem cause ill-conditioning?
• An equivalent nonlinear optimization model with triangular low-rank factorization for semidefinite programs
• Benign landscapes of low-dimensional relaxations for orthogonal synchronization on general graphs
• The effect of smooth parametrizations on nonconvex optimization landscapes
• Loraine – an interior-point solver for low-rank semidefinite programming
• Operator-valued formulas for Riemannian gradient and Hessian and families of tractable metrics in Riemannian optimization
• Solving PhaseLift by Low-Rank Riemannian Optimization Methods for Complex Semidefinite Constraints
• Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization
• Convergence Results for Projected Line-Search Methods on Varieties of Low-Rank Matrices Via Łojasiewicz Inequality
• Mini-workshop: Computational optimization on manifolds. Abstracts from the mini-workshop held November 15--21, 2020 (online meeting)
• Rank Optimality for the Burer--Monteiro Factorization
• Finding graph embeddings by incremental low-rank semidefinite programming
• Flexible low-rank statistical modeling with missing data and side information
• Restricted Riemannian geometry for positive semidefinite matrices
• Solutions to 18 constrained optimization problems on the rank and inertia of the linear matrix function
• Low-rank multi-parametric covariance identification
• On critical points of quadratic low-rank matrix optimization problems
• Balanced Truncation for Parametric Linear Systems Using Interpolation of Gramians: A Comparison of Algebraic and Geometric Approaches
• Riemannian preconditioning
• Mahalanobis Distance Learning for Person Re-identification
• A survey on conic relaxations of optimal power flow problem
• Scalable incremental nonconvex optimization approach for phase retrieval
• Fast certifiable relative pose estimation with gravity prior
• A brief introduction to manifold optimization
• Adaptive Low-Nonnegative-Rank Approximation for State Aggregation of Markov Chains
• Adaptive regularization with cubics on manifolds
• On the Landscape of Synchronization Networks: A Perspective from Nonconvex Optimization
• Low rank approximation of the symmetric positive semidefinite matrix
• Fenchel Duality and a Separation Theorem on Hadamard Manifolds
• Memory-Efficient Structured Convex Optimization via Extreme Point Sampling
• Title not available (Why is that?)
• A hierarchy of spectral relaxations for polynomial optimization
• The problem of semidefinite least squares with low rank
• On the Burer-Monteiro method for general semidefinite programs
• Computational Approaches to Max-Cut
• Forbidden minor characterizations for low-rank optimal solutions to semidefinite programs over the elliptope
• Global Registration of Multiple Point Clouds Using Semidefinite Programming
• Local minima and convergence in low-rank semidefinite programming
• A Decomposition Augmented Lagrangian Method for Low-Rank Semidefinite Programming
• A Riemannian symmetric rank-one trust-region method
• Normal Cones Intersection Rule and Optimality Analysis for Low-Rank Matrix Optimization with Affine Manifolds
• Scalable Low-Rank Semidefinite Programming for Certifiably Correct Machine Perception
• Accelerated method for optimization over density matrices in quantum state estimation
• Quotient Geometry with Simple Geodesics for the Manifold of Fixed-Rank Positive-Semidefinite Matrices
• An alternative to EM for Gaussian mixture models: batch and stochastic Riemannian optimization
• Approximation bounds for sparse principal component analysis
• Title not available (Why is that?)
• Matrix optimization over low-rank spectral sets: stationary points and local and global minimizers
• Finding Low-Rank Solutions via Nonconvex Matrix Factorization, Efficiently and Provably
• Optimization on low rank nonconvex structures
• Nonconvex weak sharp minima on Riemannian manifolds
• Title not available (Why is that?)
• Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs
• A survey on rank and inertia optimization problems of the matrix-valued function \(A+BXB^\ast\)
• SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances
• The geometry of algorithms using hierarchical tensors
• Tangent and normal cones for low-rank matrices
• Manifold Optimization-Assisted Gaussian Variational Approximation
• Title not available (Why is that?)
• Tightness of the maximum likelihood semidefinite relaxation for angular synchronization
• Title not available (Why is that?)

Uses Software

• SDPLR
• DSPCA

This page was built for publication: Low-Rank Optimization on the Cone of Positive Semidefinite Matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3083289)