×

Heuristics for exact nonnegative matrix factorization. (English) Zbl 1341.65057

Summary: The exact nonnegative matrix factorization (exact NMF) problem is the following: given an \(m\)-by-\(n\) nonnegative matrix \(X\) and a factorization rank \(r\), find, if possible, an \(m\)-by-\(r\) nonnegative matrix \(W\) and an \(r\)-by-\(n\) nonnegative matrix \(H\) such that \(X = WH\). In this paper, we propose two heuristics for exact NMF, one inspired from simulated annealing and the other from the greedy randomized adaptive search procedure. We show empirically that these two heuristics are able to compute exact nonnegative factorizations for several classes of nonnegative matrices (namely, linear Euclidean distance matrices, slack matrices, unique-disjointness matrices, and randomly generated matrices) and as such demonstrate their superiority over standard multi-start strategies. We also consider a hybridization between these two heuristics that allows us to combine the advantages of both methods. Finally, we discuss the use of these heuristics to gain insight on the behavior of the nonnegative rank, i.e., the minimum factorization rank such that an exact NMF exists. In particular, we disprove a conjecture on the nonnegative rank of a Kronecker product, propose a new upper bound on the extension complexity of generic \(n\)-gons and conjecture the exact value of (i) the extension complexity of regular \(n\)-gons and (ii) the nonnegative rank of a submatrix of the slack matrix of the correlation polytope.

MSC:

65Y05 Parallel numerical computation
15A23 Factorization of matrices
90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
15B48 Positive matrices and their generalizations; cones of matrices

Software:

QEPCAD
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Arora, S., Ge, R., Kannan, R., Moitra, A.: Computing a nonnegative matrix factorization—provably. in Proceedings of the 44th Symposium on Theory of Computing, STOC ’12, pp. 145-162, (2012) · Zbl 1286.15014
[2] Beasley, L., Laffey, T.: Real rank versus nonnegative rank. Linear Algebra Appl. 431(12), 2330-2335 (2009) · Zbl 1185.15002 · doi:10.1016/j.laa.2009.02.034
[3] Beasley, L., Lee, T., Klauck, H., Theis, D.: Dagstuhl report 13082: communication complexity, linear optimization, and lower bounds for the nonnegative rank of matrices (2013). arXiv:1305.4147
[4] Ben-Tal, A., Nemirovski, A.: On polyhedral approximations of the second-order cone. Math. Oper. Res. 26(2), 193-205 (2001) · Zbl 1082.90133 · doi:10.1287/moor.26.2.193.10561
[5] Bocci, C., Carlini, E., Rapallo, F.: Perturbation of matrices and nonnegative rank with a view toward statistical models. SIAM J. Matrix Anal. Appl. 32(4), 1500-1512 (2011) · Zbl 1242.15031 · doi:10.1137/110825455
[6] Boutsidis, C., Gallopoulos, E.: SVD based initialization: a head start for nonnegative matrix factorization. Pattern Recognit. 41(4), 1350-1362 (2008) · Zbl 1131.68084 · doi:10.1016/j.patcog.2007.09.010
[7] Brown, C.W.: Qepcad b: a program for computing with semi-algebraic sets using cads. ACM SIGSAM Bull. 37(4), 97-108 (2003) · Zbl 1083.68148 · doi:10.1145/968708.968710
[8] Carlini, E., Rapallo, F.: Probability matrices, non-negative rank, and parameterization of mixture models. Linear Algebra Appl. 433, 424-432 (2010) · Zbl 1196.15034 · doi:10.1016/j.laa.2010.03.010
[9] Cichocki, A., Amari, S.-I., Zdunek, R., Phan, A.: Non-negative Matrix and Tensor Factorizations: Applications to Exploratory Multi-way Data Analysis and Blind Source Separation. Wiley, London (2009) · doi:10.1002/9780470747278
[10] Cichocki, A., Phan, A.H.: Fast local algorithms for large scale nonnegative matrix and tensor factorizations. IEICE Trans. Fundam. Electron. E92-A(3), 708-721 (2009) · doi:10.1587/transfun.E92.A.708
[11] Cichocki, A., Zdunek, R., Amari, S.-i.: Hierarchical ALS Algorithms for Nonnegative Matrix and 3D Tensor Factorization. Lecture notes in computer science (Springer, 2007), pp. 169-176 · Zbl 1172.94390
[12] Cohen, J., Rothblum, U.: Nonnegative ranks, decompositions and factorization of nonnegative matrices. Linear Algebra Appl. 190, 149-168 (1993) · Zbl 0784.15001 · doi:10.1016/0024-3795(93)90224-C
[13] Conforti, M., Cornuéjols, G., Zambelli, G.: Extended formulations in combinatorial optimization. 4OR A Q.J. Oper. Res. 10(1), 1-48 (2010) · Zbl 1219.90193 · doi:10.1007/s10288-010-0122-z
[14] de Caen, D., Gregory, D.A., Pullman, N.J.: The boolean rank of zero-one matrices. in Proceedings of Third Caribbean Conference on Combinatorics and Computing (Barbados), pp. 169-173 (1981) · Zbl 0496.20052
[15] Fawzi, H., Gouveia, J., Parrilo, P., Robinson, R., Thomas, R.: Positive Semidefinite Rank (2014). arXiv:1407.4095
[16] Fiorini, S., Kaibel, V., Pashkovich, K., Theis, D.: Combinatorial bounds on nonnegative rank and extended formulations. Discret. Math. 313(1), 67-83 (2013) · Zbl 1259.90111 · doi:10.1016/j.disc.2012.09.015
[17] Fiorini, S., Massar, S., Pokutta, S., Tiwary, H., de Wolf, R.: Linear Versus Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds. in Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, ACM, pp. 95-106, (2012) · Zbl 1286.90125
[18] Fiorini, S., Rothvoss, T., Tiwary, H.: Extended formulations for polygons. Discret. Comput. Geom. 48(3), 658-668 (2012) · Zbl 1290.68122 · doi:10.1007/s00454-012-9421-9
[19] Gillis, N.: Sparse and unique nonnegative matrix factorization through data preprocessing. J. Mach. Learn. Res. 13(Nov), 3349-3386 (2012) · Zbl 1436.15013
[20] Gillis, N.; Suykens, J. (ed.); Signoretto, M. (ed.); Argyriou, A. (ed.), The why and how of nonnegative matrix factorization (2014), London
[21] Gillis, N., Glineur, F.: Using underapproximations for sparse nonnegative matrix factorization. Pattern Recognit. 43(4), 1676-1687 (2010) · Zbl 1191.68783 · doi:10.1016/j.patcog.2009.11.013
[22] Gillis, N., Glineur, F.: Accelerated multiplicative updates and hierarchical ALS algorithms for nonnegative matrix factorization. Neural Comput. 24(4), 1085-1105 (2012) · doi:10.1162/NECO_a_00256
[23] Gillis, N., Glineur, F.: On the geometric interpretation of the nonnegative rank. Linear Algebra Appl. 437(11), 2685-2712 (2012) · Zbl 1258.65039 · doi:10.1016/j.laa.2012.06.038
[24] Gillis, N., Vavasis, S.: Semidefinite programming based preconditioning for more robust near-separable nonnegative matrix factorization. SIAM J.Optim. 25, 677-698 (2015) · Zbl 1316.15015 · doi:10.1137/130940670
[25] Goemans, M.: Smallest Compact Formulation for the Permutahedron (2009). http://math.mit.edu/ goemans/PAPERS/permutahedron · Zbl 1322.90048
[26] Gouveia, J.: Personnal Comunication (2014) · Zbl 1232.65068
[27] Gouveia, J., Fawzi, H., Robinson, R.: Rational and Real Positive Srank can be Different (2014). arXiv:1404.4864 · Zbl 1408.15016
[28] Gouveia, J., Parrilo, P., Thomas, R.: Lifts of convex sets and cone factorizations. Math. Oper. Res. 38(2), 248-264 (2013) · Zbl 1291.90172 · doi:10.1287/moor.1120.0575
[29] Gouveia, J., Robinson, R., Thomas, R.: Worst-case Results for Positive Semidefinite Rank (2013). arXiv:1305.4600 · Zbl 1344.90046
[30] Gregory, D.A., Pullman, N.J.: Semiring rank: boolean rank and nonnegative rank factorizations. J. Combin. Inform. Syst. Sci. 8(3), 223-233 (1983) · Zbl 0622.15007
[31] Hrubeš, P.: On the nonnegative rank of distance matrices. Inf. Process. Lett. 112(11), 457-461 (2012) · Zbl 1243.15003 · doi:10.1016/j.ipl.2012.02.009
[32] Janecek, A., Tan, Y.: Iterative improvement of the multiplicative update NMF algorithm using nature-inspired optimization. in Seventh International Conference on Natural Computation vol. 3 (2011), pp. 1668-1672 · Zbl 1131.68084
[33] Janecek, A., Tan, Y.: Swarm intelligence for non-negative matrix factorization. Int. J. Swarm Intell. Res. 2(4), 12-34 (2011) · doi:10.4018/jsir.2011100102
[34] Janecek, A., Tan, Y.: Using population based algorithms for initializing nonnegative matrix factorization. Adv. Swarm Intell. 6729, 307-316 (2011) · Zbl 1305.65135
[35] Kaibel, V.: Extended formulations in combinatorial optimization. Optima 85, 2-7 (2011)
[36] Kaibel, V., Weltge, S.: A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially (2013). arXiv:1307.3543 · Zbl 1315.52021
[37] Kim, J., He, Y., Park, H.: Algorithms for nonnegative matrix and tensor factorizations: a unified view based on block coordinate descent framework. J. Global Optim. 58(2), 285-319 (2014) · Zbl 1321.90129 · doi:10.1007/s10898-013-0035-4
[38] Kim, J., Park, H.: Fast nonnegative matrix factorization: an active-set-like method and comparisons. SIAM J. Sci. Comput. 33(6), 3261-3281 (2011) · Zbl 1232.65068 · doi:10.1137/110821172
[39] Lee, D., Seung, H.: Learning the parts of objects by nonnegative matrix factorization. Nature 401, 788-791 (1999) · Zbl 1369.68285 · doi:10.1038/44565
[40] Lee, D., Seung, H.: Algorithms for non-negative matrix factorization. In: Advances in Neural Information Processing Systems, vol. 13, pp. 556-562 (2001)
[41] Lee, T., Shraibman, A.: Lower Bounds in Communication Complexity. Found. Trends Theor. Comput. Sci. 3(4), 263-399 (2007) · Zbl 1193.94002
[42] Moitra, A.: An Almost Optimal Algorithm for Computing Nonnegative Rank. in Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA ’13), pp. 1454-1464 (2013) · Zbl 1422.68130
[43] Oelze, M., Vandaele, A., Weltge, S.: Computing the Extension Complexities of all 4-Dimensional 0/1-polytopes (2014). arXiv:1406.4895
[44] Padrol, A., Pfeifle, J.: Polygons as Slices of Higher-Dimensional Polytopes (2014). arXiv:1404.2443 · Zbl 1312.52008
[45] Pirlot, M.: General local search methods. Eur. J. Oper. Res. 92(3), 493-511 (1996) · Zbl 0914.90227 · doi:10.1016/0377-2217(96)00007-0
[46] Rothvoss, T.: The Matching Polytope has Exponential Extension Complexity (2013). arXiv:1311.2369 · Zbl 1315.90038
[47] Shitov, Y.: Sublinear Extensions of Polygons (2014). arXiv:1412.0728
[48] Shitov, Y.: An upper bound for nonnegative rank. J. Combin. Theory Ser. A 122, 126-132 (2014) · Zbl 1316.52020 · doi:10.1016/j.jcta.2013.10.004
[49] Shitov, Y.: Nonnegative Rank Depends on the Field (2015). arXiv:1505.01893 · Zbl 1465.15044
[50] Takahashi, N., Hibi, R.: Global convergence of modified multiplicative updates for nonnegative matrix factorization. Comput. Optim. Appl. 57(2), 417-440 (2014) · Zbl 1305.65135 · doi:10.1007/s10589-013-9593-0
[51] Thomas, L.: Rank factorization of nonnegative matrices. SIAM Rev. 16(3), 393-394 (1974) · doi:10.1137/1016064
[52] Vandaele, A., Gillis, N., Glineur, F.: On the Linear Extension Complexity of Regular n-gons (2015). arXiv:1505.08031 · Zbl 1360.52025
[53] Vavasis, S.: On the complexity of nonnegative matrix factorization. SIAM J. Optim. 20(3), 1364-1377 (2010) · Zbl 1206.65130 · doi:10.1137/070709967
[54] Watson, T.: Sampling Versus Unambiguous Nondeterminism in Communication Complexity (2014). http://www.cs.toronto.edu/ thomasw/papers/nnr · Zbl 1191.68783
[55] Yannakakis, M.: Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43(3), 441-466 (1991) · Zbl 0748.90074 · doi:10.1016/0022-0000(91)90024-Y
[56] Zdunek, R.: Initialization of nonnegative matrix factorization with vertices of convex polytope. In: Artificial Intelligence and Soft Computing, vol. 7267, pp. 448-455. Lecture Notes in Computer Science (2012) · Zbl 1369.68285
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.