Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Efficient Rank-one Residue Approximation Method for Graph Regularized Non-negative Matrix Factorization

  • Conference paper

Part of the book series:Lecture Notes in Computer Science ((LNAI,volume 8189))

Abstract

Nonnegative matrix factorization (NMF) aims to decompose a given data matrixX into the product of two lower-rank nonnegative factor matricesUVT . Graph regularized NMF (GNMF) is a recently proposed NMF method that preserves the geometric structure ofX during such decomposition. Although GNMF has been widely used in computer vision and data mining, its multiplicative update rule (MUR) based solver suffers from both slow convergence and non-stationarity problems. In this paper, we propose a new efficient GNMF solver called rank-one residue approximation (RRA). Different from MUR, which updates both factor matrices (U andV) as a whole in each iteration round, RRA updates each of their columns by approximating the residue matrix by their outer product. Since each column of both factor matrices is updated optimally in an analytic formulation, RRA is theoretical and empirically proven to converge rapidly to a stationary point. Moreover, since RRA needs neither extra computational cost nor parametric tuning, it enjoys a similar simplicity to MUR but performs much faster. Experimental results on real-world datasets show that RRA is much more efficient than MUR for GNMF. To confirm the stationarity of the solution obtained by RRA, we conduct clustering experiments on real-world image datasets by comparing with the representative solvers such as MUR and NeNMF for GNMF. The experimental results confirm the effectiveness of RRA.

Similar content being viewed by others

Keywords

References

  1. Bertsekas, D.P.: Nonlinear programming. Athena Scientific (1999)

    Google Scholar 

  2. Cai, D., He, X., Han, J., Huang, T.S.: Graph regularized nonnegative matrix factorization for data representation. IEEE Transactions on Pattern Analysis and Machine Intelligence 33(8), 1548–1560 (2011)

    Article  Google Scholar 

  3. Cai, D., He, X., Wu, X., Han, J.: Non-negative matrix factorization on manifold. In: Eighth IEEE International Conference on Data Mining (ICDM 2008), pp. 63–72. IEEE (2008)

    Google Scholar 

  4. Chung, F.R.: Spectral graph theory. In: CBMS Regional Conference Series in Mathematics, vol. 92 (1997)

    Google Scholar 

  5. Cichocki, A., Zdunek, R., Amari, S.-I.: Hierarchical als algorithms for nonnegative matrix and 3d tensor factorization. In: Davies, M.E., James, C.J., Abdallah, S.A., Plumbley, M.D. (eds.) ICA 2007. LNCS, vol. 4666, pp. 169–176. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  6. Gu, Q., Zhou, J.: Neighborhood preserving nonnegative matrix factorization. In: Proc. 20th British Machine Vision Conf. (2009)

    Google Scholar 

  7. Guan, N., Tao, D., Luo, Z., Yuan, B.: Manifold regularized discriminative nonnegative matrix factorization with fast gradient descent. IEEE Transactions on Image Processing 20(7), 2030–2048 (2011)

    Article MathSciNet  Google Scholar 

  8. Guan, N., Tao, D., Luo, Z., Yuan, B.: Nenmf: an optimal gradient method for nonnegative matrix factorization. IEEE Transactions on Signal Processing 60(6), 2882–2898 (2012)

    Article MathSciNet  Google Scholar 

  9. Ho, N.D., Van Dooren, P., Blondel, V.D.: Descent methods for nonnegative matrix factorization. In: Numerical Linear Algebra in Signals, Systems and Control, pp. 251–293. Springer (2011)

    Google Scholar 

  10. Lin, C.J.: On the convergence of multiplicative update algorithms for nonnegative matrix factorization. IEEE Transactions on Neural Networks 18(6), 1589–1596 (2007)

    Article  Google Scholar 

  11. Lin, C.J.: Projected gradient methods for nonnegative matrix factorization. Neural Computation 19(10), 2756–2779 (2007)

    Article MathSciNet MATH  Google Scholar 

  12. Nene, S.A., Nayar, S.K., Murase, H.: Columbia object image library (coil-20). Technical Report CUS-005-96, Columbia Univ. USA (1996)

    Google Scholar 

  13. Shen, B., Si, L.: Nonnegative matrix factorization clustering on multiple manifolds. In: Proceedings of the 24th AAAI Conference on Artificial Intelligence, pp. 575–580 (2010)

    Google Scholar 

  14. Sim, T., Baker, S., Bsat, M.: The cmu pose, illumination, and expression database. IEEE Transactions on Pattern Analysis and Machine Intelligence 25(12), 1615–1618 (2003)

    Article  Google Scholar 

  15. Woodbury, M.A.: Inverting modified matrices. Memorandum Report 42, 106 (1950)

    MathSciNet  Google Scholar 

  16. Xu, D., Yan, S., Tao, D., Lin, S., Zhang, H.-J.: Marginal fisher analysis and its variants for human gait recognition and content-based image retrieval. IEEE Transactions on Image Processing 16(11), 2811–2821 (2007)

    Article MathSciNet  Google Scholar 

  17. Yang, J., Yang, S., Fu, Y., Li, X., Huang, T.: Non-negative graph embedding. In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 1–8. IEEE (2008)

    Google Scholar 

  18. Zhang, T., Fang, B., Tang, Y.Y., He, G., Wen, J.: Topology preserving non-negative matrix factorization for face recognition. IEEE Transactions on Image Processing 17(4), 574–584 (2008)

    Article MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science and Engineering, The Hong Kong University of Science and Technology, Hong Kong

    Qing Liao & Qian Zhang

Authors
  1. Qing Liao

    You can also search for this author inPubMed Google Scholar

  2. Qian Zhang

    You can also search for this author inPubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Computer Science, Katholieke Universiteit Leuven, Celestijnenlaan 200A, 3001, Leuven, Belgium

    Hendrik Blockeel

  2. Fraunhofer IAIS, Department of Knowledge Discovery, Schloss Birlinghoven, University of Bonn, 53754, Sankt Augustin, Germany

    Kristian Kersting

  3. LIACS, Universiteit Leiden, Niels Bohrweg 1, 2333, Leiden, CA, The Netherlands

    Siegfried Nijssen

  4. Department of Computer Science and Engineering, Czech Technical University, Technicka 2, 16627, Prague 6, Czech Republic

    Filip Železný

Rights and permissions

Copyright information

© 2013 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Liao, Q., Zhang, Q. (2013). Efficient Rank-one Residue Approximation Method for Graph Regularized Non-negative Matrix Factorization. In: Blockeel, H., Kersting, K., Nijssen, S., Železný, F. (eds) Machine Learning and Knowledge Discovery in Databases. ECML PKDD 2013. Lecture Notes in Computer Science(), vol 8189. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40991-2_16

Download citation

Publish with us

[8]ページ先頭
©2009-2025 Movatter.jp