nips nips2011 nips2011-73 nips2011-73-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Lester W. Mackey, Michael I. Jordan, Ameet Talwalkar
Abstract: This work introduces Divide-Factor-Combine (DFC), a parallel divide-andconquer framework for noisy matrix factorization. DFC divides a large-scale matrix factorization task into smaller subproblems, solves each subproblem in parallel using an arbitrary base matrix factorization algorithm, and combines the subproblem solutions using techniques from randomized matrix approximation. Our experiments with collaborative filtering, video background modeling, and simulated data demonstrate the near-linear to super-linear speed-ups attainable with this approach. Moreover, our analysis shows that DFC enjoys high-probability recovery guarantees comparable to those of its base algorithm.
[1] A. Agarwal, S. Negahban, and M. J. Wainwright. Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions. In International Conference on Machine Learning, 2011.
[2] E. J. Cand` s, X. Li, Y. Ma, and J. Wright. Robust principal component analysis? Journal of the ACM, 58 e (3):1–37, 2011.
[3] E.J. Cand` s and Y. Plan. Matrix completion with noise. Proceedings of the IEEE, 98(6):925 –936, 2010. e
[4] V. Chandrasekaran, S. Sanghavi, P. A. Parrilo, and A. S. Willsky. Sparse and low-rank matrix decompositions. In Allerton Conference on Communication, Control, and Computing, 2009.
[5] Y. Chen, H. Xu, C. Caramanis, and S. Sanghavi. Robust matrix completion and corrupted columns. In International Conference on Machine Learning, 2011.
[6] P. Drineas, M. W. Mahoney, and S. Muthukrishnan. Relative-error CUR matrix decompositions. SIAM Journal on Matrix Analysis and Applications, 30:844–881, 2008.
[7] A. Frieze, R. Kannan, and S. Vempala. Fast Monte-Carlo algorithms for finding low-rank approximations. In Foundations of Computer Science, 1998.
[8] S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin. A theory of pseudoskeleton approximations. Linear Algebra and its Applications, 261(1-3):1 – 21, 1997.
[9] D. Gross and V. Nesme. Note on sampling without replacing from a finite collection of matrices. CoRR, abs/1001.2738, 2010.
[10] W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13–30, 1963.
[11] D. Hsu, S. M. Kakade, and T. Zhang. Dimension-free tail inequalities for sums of random matrices. arXiv:1104.1672v3[math.PR], 2011.
[12] R. H. Keshavan, A. Montanari, and S. Oh. Matrix completion from noisy entries. Journal of Machine Learning Research, 99:2057–2078, 2010.
[13] S. Kumar, M. Mohri, and A. Talwalkar. On sampling-based approximate spectral decomposition. In International Conference on Machine Learning, 2009.
[14] S. Kumar, M. Mohri, and A. Talwalkar. Ensemble Nystr¨ m method. In NIPS, 2009. o
[15] Z. Lin, A. Ganesh, J. Wright, L. Wu, M. Chen, and Y. Ma. Fast convex optimization algorithms for exact recovery of a corrupted low-rank matrix. UIUC Technical Report UILU-ENG-09-2214, 2009.
[16] S. Ma, D. Goldfarb, and L. Chen. Fixed point and bregman iterative methods for matrix rank minimization. Mathematical Programming, 128(1-2):321–353, 2011.
[17] K. Min, Z. Zhang, J. Wright, and Y. Ma. Decomposing background topics from keywords by principal component pursuit. In Conference on Information and Knowledge Management, 2010.
[18] M. Mohri and A. Talwalkar. Can matrix coherence be efficiently and accurately estimated? In Conference on Artificial Intelligence and Statistics, 2011.
[19] Y. Mu, J. Dong, X. Yuan, and S. Yan. Accelerated low-rank visual recovery by random projection. In Conference on Computer Vision and Pattern Recognition, 2011.
[20] S. Negahban and M. J. Wainwright. Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. arXiv:1009.2118v2[cs.IT], 2010.
[21] Y. Peng, A. Ganesh, J. Wright, W. Xu, and Y. Ma. Rasl: Robust alignment by sparse and low-rank decomposition for linearly correlated images. In Conference on Computer Vision and Pattern Recognition, 2010.
[22] B. Recht. A simpler approach to matrix completion. arXiv:0910.0651v2[cs.IT], 2009.
[23] K. Toh and S. Yun. An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. Pacific Journal of Optimization, 6(3):615–640, 2010.
[24] C.K. Williams and M. Seeger. Using the Nystr¨ m method to speed up kernel machines. In NIPS, 2000. o
[25] Z. Zhou, X. Li, J. Wright, E. J. Cand` s, and Y. Ma. Stable principal component pursuit. arXiv: e 1001.2363v1[cs.IT], 2010. 9