zbMATH — the first resource for mathematics

Algorithms for positive semidefinite factorization. (English) Zbl 1427.90270
Summary: 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,\dots ,A^m\}\) and \(\{B^1,\dots ,B^n\}\) such that \(X_{i,j}=\mathrm {trace}(A^iB^j)\) for \(i=1,\dots ,m\), and \(j=1,\dots ,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+ \lceil\log _2(n)\rceil \) 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\)).

90C30 Nonlinear programming
Full Text: DOI
[1] Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific, Singapore (2003) · Zbl 1030.15022
[2] Burer, S; Monteiro, R, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Math. Program., 95, 329-357, (2003) · Zbl 1030.90077
[3] Cardano, G.: Ars Magna or the Rules of Algebra. Dover Publications, Mineola (1968) · Zbl 0191.27704
[4] Cichocki, A; Phan, AH, Fast local algorithms for large scale nonnegative matrix and tensor factorizations, IEICE Trans. Fundam. Electron., E92-A, 708-721, (2009)
[5] Cichocki, A., Zdunek, R., Amari, S.i.: Hierarchical ALS algorithms for nonnegative matrix and 3D tensor factorization. In: International Conference on Independent Component Analysis and Signal Separation, pp. 169-176. Springer (2007) · Zbl 1172.94390
[6] Fawzi, H; Gouveia, J; Parrilo, P; Robinson, R; Thomas, R, Positive semidefinite rank, Math. Program., 153, 133-177, (2015) · Zbl 1327.90174
[7] Fawzi, H; Gouveia, J; Robinson, R, Rational and real positive semidefinite rank can be different, Oper. Res. Lett., 44, 59-60, (2016) · Zbl 1408.15016
[8] Fiorini, S., Massar, S., Pokutta, S., Tiwary, H., de Wolf, R.: Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In: Proceedings of the 44th Annual ACM Symposium on Theory of Computing, pp. 95-106. ACM (2012) · Zbl 1286.90125
[9] Fiorini, S; Rothvoss, T; Tiwary, H, Extended formulations for polygons, Discrete Comput. Geom., 48, 658-668, (2012) · Zbl 1290.68122
[10] Gillis, N; Suykens, J (ed.); Signoretto, M (ed.); Argyriou, A (ed.), The why and how of nonnegative matrix factorization, (2014), Boca Raton
[11] Gillis, N; Glineur, F, Accelerated multiplicative updates and hierarchical ALS algorithms for nonnegative matrix factorization, Neural Comput., 24, 1085-1105, (2012)
[12] Goucha, A; Gouveia, J; Silva, P, On ranks of regular polygons, SIAM J. Discrete Math., 31, 2612-2625, (2017) · Zbl 1384.52004
[13] Gouveia, J; Parrilo, P; Thomas, R, Lifts of convex sets and cone factorizations, Math. Oper. Res., 38, 248-264, (2013) · Zbl 1291.90172
[14] Gouveia, J; Robinson, R; Thomas, R, Worst-case results for positive semidefinite rank, Math. Program., 153, 201-212, (2015) · Zbl 1344.90046
[15] Gribling, S; Laat, D; Laurent, M, Matrices with high completely positive semidefinite rank, Linear Algebra Appl., 513, 122-148, (2017) · Zbl 1349.15091
[16] Grippo, L; Sciandrone, M, On the convergence of the block nonlinear Gauss-Seidel method under convex constraints, Oper. Res. Lett., 26, 127-136, (2000) · Zbl 0955.90128
[17] Ho, N.D.: Nonnegative matrix factorization algorithms and applications. Ph.D. thesis, Univertsité catholique de Louvain (2008)
[18] Hsieh, C.J., Dhillon, I.: Fast coordinate descent methods with variable selection for non-negative matrix factorization. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1064-1072. ACM (2011)
[19] Kaibel, V, Extended formulations in combinatorial optimization, Optima, 85, 2-7, (2011)
[20] Kuang, D; Yun, S; Park, H, Symnmf: nonnegative low-rank approximation of a similarity matrix for graph clustering, J. Glob. Optim., 62, 545-574, (2015) · Zbl 1326.90080
[21] Kubjas, K., Robeva, E., Robinson, R.: Positive semidefinite rank and nested spectrahedra. Linear Multilinear Algebra. 1-23 (2017) · Zbl 1395.14041
[22] Lee, T., Theis, D.O.: Support-based lower bounds for the positive semidefinite rank of a nonnegative matrix. (2012). arXiv preprint arXiv:1203.3961
[23] Löfberg, J.: Yalmip: A toolbox for modeling and optimization in matlab. In: IEEE International Symposium on Computer Aided Control Systems Design, 2004, pp. 284-289. IEEE (2004)
[24] Nesterov, Y, A method of solving a convex programming problem with convergence rate 0(1/k2), Sov. Math. Dokl., 27, 372-376, (1983) · Zbl 0535.90071
[25] Prakash, A., Sikora, J., Varvitsiotis, A., Wei, Z.: Completely positive semidefinite rank. Math. Program. 1-35 (2016) · Zbl 1400.15004
[26] Shitov, Y, The complexity of positive semidefinite matrix factorization, SIAM J. Optim., 27, 1898-1909, (2017) · Zbl 1370.15013
[27] Sturm, JF, Using sedumi 1.02, a Matlab toolbox for optimization over symmetric cones, Optim. Methods Softw., 11, 625-653, (1999) · Zbl 0973.90526
[28] Vandaele, A; Gillis, N; Glineur, F, On the linear extension complexity of regular n-gons, Linear Algebra Appl., 521, 217-239, (2017) · Zbl 1360.52025
[29] Vandaele, A; Gillis, N; Glineur, F; Tuyttens, D, Heuristics for exact nonnegative matrix factorization, J. Glob. Optim., 65, 369-400, (2016) · Zbl 1341.65057
[30] Vandaele, A; Gillis, N; Lei, Q; Zhong, K; Dhillon, I, Efficient and non-convex coordinate descent for symmetric nonnegative matrix factorization, IEEE Trans. Signal Process., 64, 5571-5584, (2016)
[31] Wright, S, Coordinate descent algorithms, Math. Program., 151, 3-34, (2015) · Zbl 1317.49038
[32] Yannakakis, M, Expressing combinatorial optimization problems by linear programs, J. Comput. Syst. Sci., 43, 441-466, (1991) · Zbl 0748.90074
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.