nips nips2012 nips2012-125 nips2012-125-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Ben Recht, Christopher Re, Joel Tropp, Victor Bittorf
Abstract: This paper describes a new approach, based on linear programming, for computing nonnegative matrix factorizations (NMFs). The key idea is a data-driven model for the factorization where the most salient features in the data are used to express the remaining features. More precisely, given a data matrix X, the algorithm identifies a matrix C that satisfies X ≈ CX and some linear constraints. The constraints are chosen to ensure that the matrix C selects features; these features can then be used to find a low-rank NMF of X. A theoretical analysis demonstrates that this approach has guarantees similar to those of the recent NMF algorithm of Arora et al. (2012). In contrast with this earlier work, the proposed method extends to more general noise models and leads to efficient, scalable algorithms. Experiments with synthetic and real datasets provide evidence that the new approach is also superior in practice. An optimized C++ implementation can factor a multigigabyte matrix in a matter of minutes. 1
[1] docs.oracle.com/cd/B28359_01/datamine.111/b28129/algo_nmf.htm.
[2] lemurproject.org/clueweb09/.
[3] www.mathworks.com/help/toolbox/stats/nnmf.html.
[4] S. Arora, R. Ge, R. Kannan, and A. Moitra. Computing a nonnegative matrix factorization – provably. To appear in STOC 2012. Preprint available at \arxiv.org/abs/1111.0952, 2011.
[5] D. P. Bertsekas and J. N. Tsitsiklis. Parallel and Distributed Computation: Numerical Methods. Athena Scientific, Belmont, MA, 1997.
[6] V. Bittorf, B. Recht, C. R´ , and J. A. Tropp. Factoring nonnegative matrices with linear programs. Teche nical Report. Available at arxiv.org/1206.1270, 2012.
[7] E. D. Dolan and J. J. Mor´ . Benchmarking optimization software with performance profiles. Mathematie cal Programming, Series A, 91:201–213, 2002.
[8] D. Donoho and V. Stodden. When does non-negative matrix factorization give a correct decomposition into parts? In Advances in Neural Information Processing Systems, 2003.
[9] E. Elhamifar, G. Sapiro, and R. Vidal. See all by looking at a few: Sparse modeling for finding representative objects. In Proceedings of CVPR, 2012.
[10] E. Elhamifar and R. Vidal. Sparse subspace clustering. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2009.
[11] E. Esser, M. M¨ ller, S. Osher, G. Sapiro, and J. Xin. A convex model for non-negative matrix factorization o and dimensionality reduction on physical space. IEEE Transactions on Image Processing, 2012. To appear. Preprint available at arxiv.org/abs/1102.0844.
[12] R. Gaujoux and C. Seoighe. NMF: A flexible R package for nonnegative matrix factorization. BMC Bioinformatics, 11:367, 2010. doi:10.1186/1471-2105-11-367.
[13] N. Gillis. Robustness analysis of hotttopixx, a linear programming model for factoring nonnegative matrices. arxiv.org/1211.6687, 2012.
[14] M. Grant and S. Boyd. CVX: Matlab software for disciplined convex programming, version 1.21. http: //cvxr.com/cvx, May 2010.
[15] M. Gu and S. C. Eisenstat. Efficient algorithms for computing a strong rank-revealing QR factorization. SIAM Journal on Scientific Computing, 17:848–869, 1996.
[16] T. Hofmann. Probabilistic latent semantic indexing. In Proceedings of the 22nd Annual International SIGIR Conference on Research and Development in Information Retrieval, 1999.
[17] D. D. Lee and H. S. Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401:788–791, 1999.
[18] D. D. Lee and H. S. Seung. Algorithms for non-negative matrix factorization. In Advances in Neural Information Processing Systems, 2001.
[19] D. Lewis, Y. Yang, T. Rose, and F. Li. RCV1: A new benchmark collection for text categorization research. Journal of Machine Learning Research, 5:361–397, 2004.
[20] M. W. Mahoney and P. Drineas. CUR matrix decompositions for improved data analysis. Proceedings of the National Academy of Sciences, 106:697–702, 2009.
[21] F. Niu, B. Recht, C. R´ , and S. J. Wright. HOGWILD!: A lock-free approach to parallelizing stochastic e gradient descent. In Advances in Neural Information Processing Systems, 2011.
[22] L. D. Shapiro. Join processing in database systems with large main memories. ACM Transactions on Database Systems, 11(3):239–264, 1986.
[23] P. Smaragdis. Non-negative matrix factorization for polyphonic music transcription. In IEEE Workshop on Applications of Signal Processing to Audio and Acoustics, pages 177–180, 2003.
[24] M. Soltanolkotabi and E. J. Cand` s. A geometric analysis of subspace clustering with outliers. Preprint e available at arxiv.org/abs/1112.4258, 2011.
[25] L. B. Thomas. Problem 73-14, rank factorization of nonnegative matrices. SIAM Review, 16(3):393–394, 1974.
[26] K. C. Toh, M. Todd, and R. H. T¨ t¨ nc¨ . uu u SDPT3: ware package for semidefinite-quadratic-linear programming. http://www.math.nus.edu.sg/˜mattohkc/sdpt3.html. A MATLAB Available softfrom
[27] S. A. Vavasis. On the complexity of nonnegative matrix factorization. SIAM Joural on Optimization, 20(3):1364–1377, 2009. 9