[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Nonnegative rank factorization—a heuristic approach via rank reduction

  • Original Paper
  • Published:
Numerical Algorithms Aims and scope Submit manuscript

Abstract

Given any nonnegative matrix \(A \in \mathbb{R}^{m \times n}\), it is always possible to express A as the sum of a series of nonnegative rank-one matrices. Among the many possible representations of A, the number of terms that contributes the shortest nonnegative rank-one series representation is called the nonnegative rank of A. Computing the exact nonnegative rank and the corresponding factorization are known to be NP-hard. Even if the nonnegative rank is known a priori, no simple procedure exists presently that is able to perform the nonnegative factorization. Based on the Wedderburn rank reduction formula, this paper proposes a heuristic approach to tackle this difficult problem numerically. Starting with A, the idea is to recurrently extrat, whenever possible, a rank-one nonnegative portion from the previous matrix while keeping the residual nonnegative and lowering its rank by one. With a slight modification for symmetry, the method can equally be applied to another important class of completely positive matrices. No convergence can be guaranteed, but repeated restart might help alleviate the difficulty. Extensive numerical testing seems to suggest that the proposed algorithm might serve as a first-step numerical means for exploring the intriguing problem of nonnegative rank factorization.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bárány, I.: Sylvester’s question: the probability that n points are in convex position. Ann. Probab. 27(4), 2020–2034 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  2. Barioli, F., Berman, A.: The maximal cp-rank of rank k completely positive matrices. Linear Algebra Appl. 363, 17–33 (2003). Special issue on nonnegative matrices, M-matrices and their generalizations (Oberwolfach 2000)

    Article  MATH  MathSciNet  Google Scholar 

  3. Beasley, L.B., Laffey, T.J.: Real rank versus nonnegative rank. Linear Algebra Appl. 431(12), 2330–2335 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  4. Berman, A., Plemmons, R.J.: Nonnegative Matrices in the Mathematical Sciences, Classics in Applied Mathematics, vol. 9. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1994). Revised Reprint of the 1979 Original

    Book  Google Scholar 

  5. Berman, A., Rothblum, U.G.: A note on the computation of the CP-rank. Linear Algebra Appl. 419(1), 1–7 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  6. Berman, A., Shaked-Monderer, N.: Completely Positive Matrices. World Scientific Publishing Co. Inc., River Edge (2003)

    Book  MATH  Google Scholar 

  7. Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999)

    Google Scholar 

  8. 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)

    Article  MATH  MathSciNet  Google Scholar 

  9. Bro, R., de Jong, S.: A fast non-negativity-constrained least squares algorithm. J. Chemom. 11(5), 393–401 (1997)

    Article  Google Scholar 

  10. Campbell, S.L., Poole, G.D.: Computing nonnegative rank factorizations. Linear Algebra Appl. 35, 175–182 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  11. Chu, M.T., Diele, F., Plemmons, R.J., Ragni, S.: Optimality, computation and interpretation of nonnegative matrix factorizations. Available online at http://www4.ncsu.edu/mtchu/Research/Papers/nnmf.ps (2005)

  12. Chu, M.T., Funderlic, R.E., Golub, G.H.: A rank-one reduction formula and its applications to matrix factorizations. SIAM Rev. 37(4), 512–530 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  13. Chu, M.T., Funderlic, R.E., Golub, G.H.: Rank modifications of semidefinite matrices associated with a secant update formula. SIAM J. Matrix Anal. Appl. 20, 428–436 (1999, electronic)

    Article  MathSciNet  Google Scholar 

  14. Chu, M.T., Lin, M.M.: Low-dimensional polytope approximation and its applications to nonnegative matrix factorization. SIAM J. Sci. Comput. 30(3), 1131–1155 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  15. Cline, R.E., Funderlic, R.E.: The rank of a difference of matrices and associated generalized inverses. Linear Algebra Appl. 24, 185–215 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  16. Cohen, J.E., Rothblum, U.G.: Nonnegative ranks, decompositions, and factorizations of nonnegative matrices. Linear Algebra Appl. 190, 149–168 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  17. Donoho, D., Stodden, V.: When does nonnegative matrix factorization give a correct decomposition into parts? In: Proc. 17th Ann. Conf. Neural Information Processing Systems. NIPS, Stanford University, Stanford, CA (2003)

    Google Scholar 

  18. Elsner, L., Nabben, R., Neumann, M.: Orthogonal bases that lead to symmetric nonnegative matrices. Linear Algebra Appl. 271, 323–343 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  19. Gillis, N.: Nonnegative matrix factorization: complexity, algorithms and applications. Ph.D. thesis, Université catholique de Louvain (2011)

  20. Gillis, N., Glineur, F.: On the geometric interpretation of the nonnegative rank. Linear Algebra Appl. 437(11), 2685–2712 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  21. Goemans, M.X.: Smallest compact formulation for the permutahedron (2009, preprint)

  22. Hannah, J., Laffey, T.J.: Nonnegative factorization of completely positive matrices. Linear Algebra Appl. 55, 1–9 (1983)

    Article  MATH  MathSciNet  Google Scholar 

  23. Hopke, P.K.: Receptor Modeling for Air Quality Management. Elsevier, Amsterdam (1991)

    Google Scholar 

  24. Householder, A.S.: The Theory of Matrices in Numerical Analysis. Dover Publications Inc., New York (1975). Reprint of 1964 edition

    MATH  Google Scholar 

  25. Hoyer, P.O.: Nonnegative sparse coding. In: Proc. IEEE Workshop Neural Networks for Signal Processing. Martigny (2002)

  26. Hoyer, P.O.: Non-negative matrix factorization with sparseness constraints. J. Mach. Learn. Res. 5, 1457–1469 (2004)

    MATH  MathSciNet  Google Scholar 

  27. Hubert, L., Meulman, J., Heiser, W.: Two purposes for matrix factorization: a historical appraisal. SIAM Rev. 42(1), 68–82 (2000, electronic)

    Article  MATH  MathSciNet  Google Scholar 

  28. Jain, S.K., Tynan, J.: Nonnegative rank factorization of a nonnegative matrix A with \(A\sp \dagger A\geq 0\). Linear Multilinear Algebra 51(1), 83–95 (2003)

    Article  MathSciNet  Google Scholar 

  29. Jeter, M.W., Pye, W.C.: A note on nonnegative rank factorizations. Linear Algebra Appl. 38, 171–173 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  30. Jeter, M.W., Pye, W.C.: Some nonnegative matrices without nonnegative rank factorizations. Ind. Math. 32(1), 37–41 (1982)

    MATH  MathSciNet  Google Scholar 

  31. Kawamoto, T., Hotta, K., Mishima, T., Fujiki, J., Tanaka, M., Kurita, T.: Estimation of single tones from chord sounds using non-negative matrix factorization. Neural Netw World 3, 429–436 (2000)

    Google Scholar 

  32. Kim, H., Park, H.: Nonnegative matrix factorization based on alternating nonnegativity constrained least squares and active set method. SIAM J. Matrix Anal. Appl. 30(2), 713–730 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  33. Klain, D.A., Rota, G.C.: Introduction to Geometric Probability. Lezioni Lincee. [Lincei Lectures]. Cambridge University Press, Cambridge (1997)

    Google Scholar 

  34. Lawson, C.L., Hanson, R.J.: Solving Least Squares Problems, Classics in Applied Mathematics, vol. 15. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1995). Revised Reprint of the 1974 Original

    Book  Google Scholar 

  35. Lee, D.D., Seung, H.S.: Learning the parts of objects by non-negative matrix factorization. Nature 401, 788–791 (1999)

    Article  Google Scholar 

  36. Lee, D.D., Seung, H.S.: Algorithms for non-negative matrix factorization. In: Advances in Neural Information Processing Systems, vol. 13, pp. 556–562 (2001)

  37. Levin, B.: On calculating maximum rank one underapproximations for positive arrays. Tech. rep., Division of Biostatistics, Columbia University, New York (1985)

    Google Scholar 

  38. Lin, M.M., Chu, M.T.: On the nonnegative rank of Euclidean distance matrices. Linear Algebra Appl. 433(3), 681–689 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  39. Paatero, P.: The multilinear engine—a table-driven, least squares program for solving multilinear problems, including the n-way parallel factor analysis model. J. Comput. Graph. Stat. 8(4), 854–888 (1999)

    MathSciNet  Google Scholar 

  40. Paatero, P., Tapper, U.: Positive matrix factorization: a non-negative factor model with optimal utilization of error. Environmetrics 5, 111–126 (1994)

    Article  Google Scholar 

  41. Shaked-Monderer, N.: Minimal cp-matrices. ELA 8, 140–157 (2001)

    MATH  MathSciNet  Google Scholar 

  42. Shaked-Monderer, N.: A note on the cp-rank of matrices generated by a soules matrix. ELA 12, 2–5 (2004)

    MathSciNet  Google Scholar 

  43. Sra, S., Dhillon, I.S.: Nonnegative matrix approximation: algorithms and applications. Tech. rep., Department of Computer Sciences, University of Texas at Austin (2006)

  44. Sylvester, J.J.: On a special class of questions on the theory of probabilities. Birmingham British Assoc. Rept., pp. 8–9 (1865)

  45. Thomas, L.B.: Solution to problem 73-14: rank factorization of nonnegative matrices by A. Berman and R. J. Plemmons. SIAM Rev. 16(3), 393–394 (1974)

    Article  Google Scholar 

  46. Vavasis, S.A.: On the complexity of nonnegative matrix factorization. SIAM. J. Optim. 20(3), 1364–1377 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  47. Wedderburn, J.H.M.: Lectures on Matrices. Dover Publications Inc., New York (1964)

    MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Dalian University of Technology, Dalian, Liaoning, 116024, China

    Bo Dong

  2. Department of Mathematics, National Chung Cheng University, Chia-Yi, 621, Taiwan

    Matthew M. Lin

  3. Department of Mathematics, North Carolina State University, Raleigh, NC, 27695-8205, USA

    Moody T. Chu

Authors
  1. Bo Dong
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Matthew M. Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Moody T. Chu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Matthew M. Lin.

Additional information

Bo Dong’s research was supported in part by the National Natural Science Foundation of China (Grant No. 11101067 and 11171051), TianYuan Special Funds of the National Natural Science Foundation of China (Grant No. 11026164) and the Fundamental Research Funds for the Central Universities.

Matthew M. Lin’s research was supported in part by the National Science Council of Taiwan under grant 101-2115-M-194-007-MY3.

Moody T. Chu’s research was supported in part by the National Science Foundation under grant DMS-1014666.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Dong, B., Lin, M.M. & Chu, M.T. Nonnegative rank factorization—a heuristic approach via rank reduction. Numer Algor 65, 251–274 (2014). https://doi.org/10.1007/s11075-013-9704-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11075-013-9704-0

Keywords

Mathematics Subject Classifications (2010)

Search

Navigation