Robust non-negative matrix factorization

Abstract

Non-negative matrix factorization (NMF) is a recently popularized technique for learning partsbased, linear representations of non-negative data. The traditional NMF is optimized under the Gaussian noise or Poisson noise assumption, and hence not suitable if the data are grossly corrupted. To improve the robustness of NMF, a novel algorithm named robust nonnegative matrix factorization (RNMF) is proposed in this paper. We assume that some entries of the data matrix may be arbitrarily corrupted, but the corruption is sparse. RNMF decomposes the non-negative data matrix as the summation of one sparse error matrix and the product of two non-negative matrices. An efficient iterative approach is developed to solve the optimization problem of RNMF. We present experimental results on two face databases to verify the effectiveness of the proposed method.

Keywords

robust non-negative matrix factorization (RNMF) / convex optimization / dimensionality reduction

References

[1] Duda R O, Hart P E, Stork D G. Pattern Classification. New York: Wiley-Interscience Publication, 2000

[2] Hastie T, Tibshirani R, Friedman J. The Elements of Statistical Learning. Springer Series in Statistics. New York: Springer, 2009

[3] Fodor I K. A survey of dimension reduction techniques. Center for Applied Scientific Computing, Lawrence Livermore National Laboratory, Technical report, 2002

[4] Bishop C M. Pattern Recognition and Machine Learning (Information Science and Statistics). New York: Springer, 2007

[5] Deerwester S, Dumais S T, Furnas G W, Landauer T K, Harshman R. Indexing by latent semantic analysis. Journal of the American Society for Information Science, 1990, 41: 391-407

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

[7] Kalman D. A singularly valuable decomposition: the svd of a matrix. The College Mathematics Journal, 1996, 27(1): 2-23

[8] Xu W, Liu X, Gong Y. Document clustering based on nonnegative matrix factorization. In: Proceedings of the 26th annual international ACM SIGIR Conference on Research and development in informaion retrieval. 2003, 267-273

[9] Cai D, He X, Wu X, Han J. Non-negative matrix factorization on manifold. In: Proceedings of the 8th IEEE International Conference on Data Mining. 2008, 63-72

[10] Guillamet D, Vitrià J. Non-negative matrix factorization for face recognition. In: Escrig M, Toledo F, Golobardes E, eds. Topics in Artificial Intelligence. Lecture Notes in Computer Science, 2002, 2504: 336-344

[11] Brunet J P, Tamayo P, Golub T R, Mesirov J P. Metagenes and molecular pattern discovery using matrix factorization. Proceedings of the National Academy of Sciences of the United States of America, 2004, 101(12): 4164-4169

[12] Carmona-Saez P, Pascual-Marqui R D, Tirado F, Carazo J, Pascual-Montano A. Biclustering of gene expression data by non-smooth non-negative matrix factorization. BMC Bioinformatics, 2006, 7(1): 78

[13] Lee D D, Seung H S. Algorithms for non-negative matrix factorization. Advances in Neural Information Processing Systems, 2001, 13(2): 556-562

[14] Cichocki A, Zdunek R, Amari S I. Csiszár’s divergences for non-negative matrix factorization: Family of new algorithms. In: Proceedings of the International Conference on Independent Component Analysis and Blind Signal Separation. Lecture Notes in Computer Science. Charleston: Springer, 2006, 3889: 32-39

[15] Wright J, Ganesh A, Rao S, Peng Y, Ma Y. Robust principal component analysis: Exact recovery of corrupted lowrank matrices via convex optimization. Advances in Neural Information Processing Systems, 2009, 22: 2080-2088

[16] Sha F, Lin Y, Saul L K, Lee D D. Multiplicative updates for nonnegative quadratic programming. Neural Computation, 2007, 19(8): 2004-2031

[17] Hale E T, Yin W, Zhang Y. Fixed-point continuation for l₁-minimization: methodology and convergence. SIAM Journal on Optimization, 2008, 19(3): 1107-1130

[18] Martínez A M, Benavente R. The ar face database. Computer Vision Center. Technical Report 24, 1998

[19] Martínez A M, Kak A C. Pca versus lda. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2001, 23(2): 228-233

[20] Lováz L, Plummern M D. Matching Theory. Amsterdam: North-Holland, 1986

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg