User menu

Heuristics for exact nonnegative matrix factorization

Bibliographic reference Vandaele, Arnaud ; Gillis, Nicolas ; Glineur, François ; Tuyttens, Daniel. Heuristics for exact nonnegative matrix factorization. In: Journal of Global Optimization, Vol. 65, no. 2, p. 369-400 (June 2016)
Permanent URL
  1. Arora Sanjeev, Ge Rong, Kannan Ravindran, Moitra Ankur, Computing a nonnegative matrix factorization -- provably, 10.1145/2213977.2213994
  2. Beasley LeRoy B., Laffey Thomas J., Real rank versus nonnegative rank, 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 Aharon, Nemirovski Arkadi, On Polyhedral Approximations of the Second-Order Cone, 10.1287/moor.
  5. Bocci Cristiano, Carlini Enrico, Rapallo Fabio, Perturbation of Matrices and Nonnegative Rank with a View toward Statistical Models, 10.1137/110825455
  6. Boutsidis C., Gallopoulos E., SVD based initialization: A head start for nonnegative matrix factorization, 10.1016/j.patcog.2007.09.010
  7. Brown Christopher W., QEPCAD B : a program for computing with semi-algebraic sets using CADs, 10.1145/968708.968710
  8. Carlini Enrico, Rapallo Fabio, Probability matrices, non-negative rank, and parameterization of mixture models, 10.1016/j.laa.2010.03.010
  9. Cichocki Andrzej, Zdunek Rafal, Phan Anh Huy, Amari Shun-Ichi, Nonnegative Matrix and Tensor Factorizations, ISBN:9780470747278, 10.1002/9780470747278
  10. CICHOCKI Andrzej, PHAN Anh-Huy, Fast Local Algorithms for Large Scale Nonnegative Matrix and Tensor Factorizations, 10.1587/transfun.e92.a.708
  11. Cichocki Andrzej, Zdunek Rafal, Amari Shun-ichi, Hierarchical ALS Algorithms for Nonnegative Matrix and 3D Tensor Factorization, Independent Component Analysis and Signal Separation ISBN:9783540744931 p.169-176, 10.1007/978-3-540-74494-8_22
  12. Cohen Joel E., Rothblum Uriel G., Nonnegative ranks, decompositions, and factorizations of nonnegative matrices, 10.1016/0024-3795(93)90224-c
  13. Conforti Michele, Cornuéjols Gérard, Zambelli Giacomo, Extended formulations in combinatorial optimization, 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)
  15. Fawzi, H., Gouveia, J., Parrilo, P., Robinson, R., Thomas, R.: Positive Semidefinite Rank (2014). arXiv:1407.4095
  16. Fiorini Samuel, Kaibel Volker, Pashkovich Kanstantsin, Theis Dirk Oliver, Combinatorial bounds on nonnegative rank and extended formulations, 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)
  18. Fiorini Samuel, Rothvoß Thomas, Tiwary Hans Raj, Extended Formulations for Polygons, 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)
  20. Gillis, N.: The why and how of nonnegative matrix factorization. In: Suykens, J., Signoretto, M., Argyriou, A. (eds.) Regularization, Optimization, Kernels, and Support Vector Machines. Machine Learning and Pattern Recognition Series. Chapman & Hall/CRC, London (2014)
  21. Gillis Nicolas, Glineur François, Using underapproximations for sparse nonnegative matrix factorization, 10.1016/j.patcog.2009.11.013
  22. Gillis Nicolas, Glineur François, Accelerated Multiplicative Updates and Hierarchical ALS Algorithms for Nonnegative Matrix Factorization, 10.1162/neco_a_00256
  23. Gillis Nicolas, Glineur François, On the geometric interpretation of the nonnegative rank, 10.1016/j.laa.2012.06.038
  24. Gillis Nicolas, Vavasis Stephen A., Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization, 10.1137/130940670
  25. Goemans, M.: Smallest Compact Formulation for the Permutahedron (2009).
  26. Gouveia, J.: Personnal Comunication (2014)
  27. Gouveia, J., Fawzi, H., Robinson, R.: Rational and Real Positive Srank can be Different (2014). arXiv:1404.4864
  28. Gouveia João, Parrilo Pablo A., Thomas Rekha R., Lifts of Convex Sets and Cone Factorizations, 10.1287/moor.1120.0575
  29. Gouveia, J., Robinson, R., Thomas, R.: Worst-case Results for Positive Semidefinite Rank (2013). arXiv:1305.4600
  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)
  31. Hrubeš Pavel, On the nonnegative rank of distance matrices, 10.1016/j.ipl.2012.02.009
  32. Janecek Andreas, Tan Ying, Iterative improvement of the Multiplicative Update NMF algorithm using nature-inspired optimization, 10.1109/icnc.2011.6022356
  33. Janecek Andreas, Tan Ying, Swarm Intelligence for Non-Negative Matrix Factorization : , 10.4018/jsir.2011100102
  34. Janecek Andreas, Tan Ying, Using Population Based Algorithms for Initializing Nonnegative Matrix Factorization, Lecture Notes in Computer Science (2011) ISBN:9783642215230 p.307-316, 10.1007/978-3-642-21524-7_37
  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
  37. Kim Jingu, He Yunlong, Park Haesun, Algorithms for nonnegative matrix and tensor factorizations: a unified view based on block coordinate descent framework, 10.1007/s10898-013-0035-4
  38. Kim Jingu, Park Haesun, Fast Nonnegative Matrix Factorization: An Active-Set-Like Method and Comparisons, 10.1137/110821172
  39. Seung H. Sebastian, Lee Daniel D., 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, 10.1561/0400000040
  42. Moitra Ankur, An Almost Optimal Algorithm for Computing Nonnegative Rank, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms (2013) ISBN:9781611972511 p.1454-1464, 10.1137/1.9781611973105.104
  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
  45. Pirlot Marc, General local search methods, 10.1016/0377-2217(96)00007-0
  46. Rothvoss, T.: The Matching Polytope has Exponential Extension Complexity (2013). arXiv:1311.2369
  47. Shitov, Y.: Sublinear Extensions of Polygons (2014). arXiv:1412.0728
  48. Shitov Yaroslav, An upper bound for nonnegative rank, 10.1016/j.jcta.2013.10.004
  49. Shitov, Y.: Nonnegative Rank Depends on the Field (2015). arXiv:1505.01893
  50. Takahashi Norikazu, Hibi Ryota, Global convergence of modified multiplicative updates for nonnegative matrix factorization, 10.1007/s10589-013-9593-0
  51. Thomas L. B., Rank Factorization of Nonnegative Matrices (A. Berman), 10.1137/1016064
  52. Vandaele, A., Gillis, N., Glineur, F.: On the Linear Extension Complexity of Regular n-gons (2015). arXiv:1505.08031
  53. Vavasis Stephen A., On the Complexity of Nonnegative Matrix Factorization, 10.1137/070709967
  54. Watson, T.: Sampling Versus Unambiguous Nondeterminism in Communication Complexity (2014).
  55. Yannakakis Mihalis, Expressing combinatorial optimization problems by Linear Programs, 10.1016/0022-0000(91)90024-y
  56. Zdunek Rafal, Initialization of Nonnegative Matrix Factorization with Vertices of Convex Polytope, Artificial Intelligence and Soft Computing (2012) ISBN:9783642293467 p.448-455, 10.1007/978-3-642-29347-4_52