Algorithms for positive semidefinite factorization

DOI10.1007/S10589-018-9998-XMaRDI QIDQ1790680zbMATH OpenOpenAlexFDO

Authors Arnaud Vandaele, François Glineur, Nicolas Gillis

Publication date 2 October 2018

Published in Computational Optimization and Applications (Search for Journal in Brave)

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

zbMATH Keywords

extended formulationsfast gradient methodpositive semidefinite factorizationcoordinate descent method

Mathematics Subject Classification ID

Nonlinear programming (90C30)

Abstract: This paper considers the problem of positive semidefinite factorization (PSD factorization), a generalization of exact nonnegative matrix factorization. Given an $m$-by-$n$ nonnegative matrix $X$ and an integer $k$, the PSD factorization problem consists in finding, if possible, symmetric $k$-by-$k$ positive semidefinite matrices $A^1,\mathrm{...},A^m$ and $B^1,\mathrm{...},B^n$ such that $X_{i,j}=exttrace(A^i{B}^j)$ for $i=1,\mathrm{...},m$, and $j=1,\mathrm{...}n$. PSD factorization is NP-hard. In this work, we introduce several local optimization schemes to tackle this problem: a fast projected gradient method and two algorithms based on the coordinate descent framework. The main application of PSD factorization is the computation of semidefinite extensions, that is, the representations of polyhedrons as projections of spectrahedra, for which the matrix to be factorized is the slack matrix of the polyhedron. We compare the performance of our algorithms on this class of problems. In particular, we compute the PSD extensions of size $k=1+lceillo{g}_2(n)ceil$ for the regular $n$-gons when $n=5$, $8$ and $10$. We also show how to generalize our algorithms to compute the square root rank (which is the size of the factors in a PSD factorization where all factor matrices $A^i$ and $B^j$ have rank one) and completely PSD factorizations (which is the special case where the input matrix is symmetric and equality $A^i=B^i$ is required for all $i$).

Recommendations

• Computing approximate PSD factorizations
• The complexity of positive semidefinite matrix factorization
• Some upper and lower bounds on PSD-rank
• Positive semidefinite rank
• Worst-case results for positive semidefinite rank

Cites work

• scientific article; zbMATH DE number 3850830 (Why is no real title available?)
• scientific article; zbMATH DE number 1933860 (Why is no real title available?)
• scientific article; zbMATH DE number 3303985 (Why is no real title available?)
• A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization
• Completely positive semidefinite rank
• Coordinate descent algorithms
• Efficient and Non-Convex Coordinate Descent for Symmetric Nonnegative Matrix Factorization
• Expressing combinatorial optimization problems by linear programs
• Extended formulations for polygons
• Heuristics for exact nonnegative matrix factorization
• Hierarchical ALS Algorithms for Nonnegative Matrix and 3D Tensor Factorization
• Lifts of Convex Sets and Cone Factorizations
• Linear vs. semidefinite extended formulations
• Matrices with high completely positive semidefinite rank
• On ranks of regular polygons
• On the convergence of the block nonlinear Gauss-Seidel method under convex constraints
• On the linear extension complexity of regular \(n\)-gons
• Positive semidefinite rank
• Positive semidefinite rank and nested spectrahedra
• Rational and real positive semidefinite rank can be different
• SymNMF: nonnegative low-rank approximation of a similarity matrix for graph clustering
• The complexity of positive semidefinite matrix factorization
• Using SeDuMi 1.02, A Matlab toolbox for optimization over symmetric cones
• Worst-case results for positive semidefinite rank

Cited in

(6)

• Further \(\exists{\mathbb{R}} \)-complete problems with PSD matrix factorizations
• Complexity analysis of interior-point methods for second-order stationary points of nonlinear semidefinite optimization problems
• Multiplicative updates for symmetric-cone factorizations
• Computing approximate PSD factorizations
• Lower bounds on matrix factorization ranks via noncommutative polynomial optimization
• A new algorithm for positive semidefinite matrix completion

Describes a project that uses

Uses Software

• SymNMF
• SDPLR
• YALMIP
• SeDuMi

This page was built for publication: Algorithms for positive semidefinite factorization

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