Liangda Li
ABSTRACT
Non-negative matrix factorization (NMF) provides a lower rank approximation of a matrix. Due to nonnegativity imposed on the factors, it gives a latent structure that is often more physically meaningful than other lower rank approximations such as singular value decomposition (SVD). Most of the algorithms proposed in literature for NMF have been based on minimizing the Frobenius norm. This is partly due to the fact that the minimization problem based on the Frobenius norm provides much more flexibility in algebraic manipulation than other divergences. In this paper we propose a fast NMF algorithm that is applicable to general Bregman divergences. Through Taylor series expansion of the Bregman divergences, we reveal a relationship between Bregman divergences and Euclidean distance. This key relationship provides a new direction for NMF algorithms with general Bregman divergences when combined with the scalar block coordinate descent method. The proposed algorithm generalizes several recently proposed methods for computation of NMF with Bregman divergences and is computationally faster than existing alternatives. We demonstrate the effectiveness of our approach with experiments conducted on artificial as well as real world data.
Supplemental Material
- http://www.cl.cam.ac.uk/research/dtg/attarchive /facedatabase.html.Google Scholar
- A. Banerjee. Optimal bregman prediction and jensen's equality. In In Proc. International Symposium on Information Theory (ISIT), page 2004, 2004.Google ScholarCross Ref
- A. Banerjee, S. Merugu, I. S. Dhillon, and J. Ghosh. Clustering with bregman divergences. J. Mach. Learn. Res., 6:1705--1749, December 2005. Google ScholarCross Ref
- P. Breheny and J. Huang. Coordinate descent algorithms for nonconvex penalized regression, with applications to biological feature selection. Annals of Applied Statistics, 5(1):232--253, 2011.Google ScholarCross Ref
- A. Cichocki and A.-H. Phan. Fast local algorithms for large scale nonnegative matrix and tensor factorizations. IEICE Transactions on Fundamentals of Electronics, 92:708--721, 2009.Google ScholarCross Ref
- A. Cichocki and R. Zdunek. Nmflab for signal and image processing. In tech. rep, Laboratory for Advanced Brain Signal Processing, Saitama, Japan, 2006. BSI, RIKEN.Google Scholar
- A. Cichocki, R. Zdunek, and S. A. A.-H. Phan. Nonnegative matrix and tensor factorizations: Applications to exploratory multi-way data analysis and blind source separation. New York, USA, 2009. Wiley. Google ScholarDigital Library
- I. S. Dhillon and S. Sra. Generalized nonnegative matrix approximations with bregman divergences. In Neural Information Proc. Systems, pages 283--290, 2005.Google Scholar
- C. Ding, T. Li, and W. Peng. On the equivalence between non-negative matrix factorization and probabilistic latent semantic indexing. Comput. Stat. Data Anal., 52:3913--3927, April 2008. Google ScholarDigital Library
- J. Fan and R. Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American Statistical Association, 96(456).Google Scholar
- C. Fevotte, N. Bertin, and J.-L. Durrieu. Nonnegative matrix factorization with the itakura-saito divergence: With application to music analysis. Neural Comput., 21:793--830, March 2009. Google ScholarDigital Library
- M. Figueiredo, R. Nowak, and S. J. Wright. Gradient projection for sparse reconstruction: Application to compressed sensing and other inverse problems. IEEE J. of Selected Topics in Signal Proc, 1:586--598, 2007.Google ScholarCross Ref
- J. Friedman, T. Hastie, and R. Tibshirani. Regularization paths for generalized linear models via coordinate descent. Journal of Statistical Software, 33(1), 1 2010.Google ScholarCross Ref
- N. Gillis and F. Glineur. Accelerated multiplicative updates and hierarchical als algorithms for nonnegative matrix factorization. Neural Comput., 24(4):1085--1105, 4 2012. Google ScholarDigital Library
- M. R. Hestenes and E. Stiefel. Methods of conjugate gradients for solving linear systems. Journal of Research of the National Bureau of Standards, 49(6), 1952.Google ScholarCross Ref
- T. Hofmann. Probabilistic latent semantic indexing. In SIGIR '99, pages 50--57, New York, NY, USA, 1999. ACM. Google ScholarDigital Library
- C.-J. Hsieh and I. S. Dhillon. 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, KDD '11, pages 1064--1072, New York, NY, USA, 2011. ACM. Google ScholarDigital Library
- C.-J. Hsieh, M. A. Sustik, I. S. Dhillon, and P. Ravikumar. Sparse inverse covariance matrix estimation using quadratic approximation. In Advances in Neural Information Processing Systems 24, pages 2330--2338, 2011.Google Scholar
- H. Kim and H. Park. Sparse non-negative matrix factorizations via alternating non-negativity-constrained least squares for microarray data analysis. Bioinformatics, 23:1495--1502, June 2007. Google ScholarDigital Library
- H. Kim and H. Park. Nonnegative matrix factorization based on alternating nonnegativity constrained least squares and active set method. SIAM J. Matrix Anal. Appl., 30:713--730, July 2008. Google ScholarDigital Library
- J. Kim, Y. He, and H. Park. Algorithms for nonnegative matrix and tensor factorizations: A unified view based on block coordinate descent framework. Under review.Google Scholar
- J. Kim and H. Park. Toward faster nonnegative matrix factorization: A new algorithm and comparisons. IEEE International Conference on Data Mining, 0:353--362, 2008. Google ScholarDigital Library
- J. Kim and H. Park. Fast nonnegative matrix factorization: An active-set-like method and comparisons. In SIAM Journal on Scientific Computing, 2011. Google ScholarDigital Library
- G. Lebanon. Axiomatic geometry of conditional models. Information Theory, IEEE Transactions, 51:1283--1294, April 2005. Google ScholarDigital Library
- D. D. Lee and H. S. Seung. Algorithms for non-negative matrix factorization. In NIPS, pages 556--562. MIT Press, 2000.Google ScholarDigital Library
- Y. Li and S. Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Probl. Imaging, 3(3).Google Scholar
- C.-J. Lin. Projected gradient methods for non-negative matrix factorization. Neural Computation, 19:2756--2779, October 2007. Google ScholarDigital Library
- C. Y. Lin and E. Hovy. Automatic evaluation of summaries using n-gram co-occurrence statistics. In NAACL, pages 71--78, Morristown, NJ, USA, 2003. Association for Computational Linguistics. Google ScholarDigital Library
- R. Mazumder, J. Friedman, and T. Hastie. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American Statistical Association, 106(495).Google Scholar
- S. D. Pietra, V. D. Pietra, and J. Lafferty. Duality and auxiliary functions for bregman distances. Technical report, School of Computer Science, Carnegie Mellon University, 2002.Google Scholar
- A. P. Singh and G. J. Gordon. A unified view of matrix factorization models. In Proceedings of the European conference on Machine Learning and Knowledge Discovery in Databases - Part II, ECML PKDD '08, pages 358--373, Berlin, Heidelberg, 2008. Springer-Verlag. Google ScholarDigital Library
- S. Wang and D. Schuurmans. Learning continuous latent variable models with bregman divergences. In In Proc. IEEE International Conference on Algorithmic Learning Theory, page 2004, 2003.Google ScholarCross Ref
- T. Wu and K. Lange. Coordinate descent algorithms for lasso penalized regression. The Annals of Applied Statistics, 2(1):224--244, 2008.Google ScholarCross Ref
- S. Yun and K.-C. Toh. A coordinate gradient descent method for l1-regularized convex minimization. Computational Optimization and Applications, 48(2). Google ScholarDigital Library
Index Terms
- Fast bregman divergence NMF using taylor expansion and coordinate descent
Recommendations
Fast coordinate descent methods with variable selection for non-negative matrix factorization
KDD '11: Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data miningNonnegative Matrix Factorization (NMF) is an effective dimension reduction method for non-negative dyadic data, and has proven to be useful in many areas, such as text mining, bioinformatics and image processing. NMF is usually formulated as a ...
Generalized Fisher Kernel with Bregman Divergence
Hybrid Artificial Intelligent SystemsAbstractThe Fisher kernel has good statistical properties. However, from a practical point of view, the necessary distributional assumptions complicate the applicability. We approach the solution to this problem with the NMF (Non-negative Matrix ...
Feature Nonlinear Transformation Non-Negative Matrix Factorization with Kullback-Leibler Divergence
Highlights- A new non-negative matrix factorization decomposition model is proposed.
- A new ...
AbstractThis paper introduces a Feature Nonlinear Transformation Non-Negative Matrix Factorization with Kullback-Leibler Divergence (FNTNMF-KLD) for extracting the nonlinear features of a matrix in standard NMF. This method uses a nonlinear ...
Comments