nips nips2013 nips2013-179 nips2013-179-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Akshay Krishnamurthy, Aarti Singh
Abstract: We study low rank matrix and tensor completion and propose novel algorithms that employ adaptive sampling schemes to obtain strong performance guarantees. Our algorithms exploit adaptivity to identify entries that are highly informative for learning the column space of the matrix (tensor) and consequently, our results hold even when the row space is highly coherent, in contrast with previous analyses. In the absence of noise, we show that one can exactly recover a n ⇥ n matrix of rank r from merely ⌦(nr3/2 log(r)) matrix entries. We also show that one can recover an order T tensor using ⌦(nrT 1/2 T 2 log(r)) entries. For noisy recovery, our algorithm consistently estimates a low rank matrix corrupted with noise using ⌦(nr3/2 polylog(n)) entries. We complement our study with simulations that verify our theory and demonstrate the scalability of our algorithms. 1
[1] Dimitris Achlioptas and Frank Mcsherry. Fast computation of low-rank matrix approximations. Journal of the ACM (JACM), 54(2):9, 2007. 8
[2] Laura Balzano, Benjamin Recht, and Robert Nowak. High-dimensional matched subspace detection when data are missing. In Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on, pages 1638–1642. IEEE, 2010.
[3] Christos Boutsidis, Michael W Mahoney, and Petros Drineas. An improved approximation algorithm for the column subset selection problem. In Proceedings of the twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 968–977. Society for Industrial and Applied Mathematics, 2009.
[4] Jian-Feng Cai, Emmanuel J Cand` s, and Zuowei Shen. A singular value thresholding algorithm e for matrix completion. SIAM Journal on Optimization, 20(4):1956–1982, 2010.
[5] Emmanuel J Candes and Yaniv Plan. Matrix completion with noise. Proceedings of the IEEE, 98(6):925–936, 2010.
[6] Emmanuel J Cand` s and Benjamin Recht. Exact matrix completion via convex optimization. e Foundations of Computational mathematics, 9(6):717–772, 2009.
[7] Emmanuel J Cand` s and Terence Tao. The power of convex relaxation: Near-optimal matrix e completion. Information Theory, IEEE Transactions on, 56(5):2053–2080, 2010.
[8] Yudong Chen, Srinadh Bhojanapalli, Sujay Sanghavi, and Rachel Ward. Coherent matrix completion. arXiv preprint arXiv:1306.2979, 2013.
[9] Mark A Davenport and Ery Arias-Castro. Compressive binary search. In Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on, pages 1827–1831. IEEE, 2012.
[10] Amit Deshpande, Luis Rademacher, Santosh Vempala, and Grant Wang. Matrix approximation and projective clustering via volume sampling. Theory of Computing, 2:225–247, 2006.
[11] Silvia Gandy, Benjamin Recht, and Isao Yamada. Tensor completion and low-n-rank tensor recovery via convex optimization. Inverse Problems, 27(2):025010, 2011.
[12] Alex Gittens. The spectral norm error of the naive nystrom extension. arXiv preprint arXiv:1110.5305, 2011.
[13] David Gross. Recovering low-rank matrices from few coefficients in any basis. Information Theory, IEEE Transactions on, 57(3):1548–1566, 2011.
[14] Venkatesan Guruswami and Ali Kemal Sinop. Optimal column-based low-rank matrix reconstruction. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1207–1214. SIAM, 2012.
[15] Jarvis D Haupt, Richard G Baraniuk, Rui M Castro, and Robert D Nowak. Compressive distilled sensing: Sparse recovery using adaptivity in compressive measurements. In Signals, Systems and Computers, 2009 Conference Record of the Forty-Third Asilomar Conference on, pages 1551–1555. IEEE, 2009.
[16] Jun He, Laura Balzano, and John Lui. Online robust subspace tracking from partial information. arXiv preprint arXiv:1109.3827, 2011.
[17] Raghunandan H Keshavan, Andrea Montanari, and Sewoong Oh. Matrix completion from noisy entries. The Journal of Machine Learning Research, 99:2057–2078, 2010.
[18] Sanjiv Kumar, Mehryar Mohri, and Ameet Talwalkar. Sampling methods for the nystr¨ m o method. The Journal of Machine Learning Research, 98888:981–1006, 2012.
[19] B´ atrice Laurent and Pascal Massart. Adaptive estimation of a quadratic functional by model e selection. The annals of Statistics, 28(5):1302–1338, 2000.
[20] Sahand Negahban and Martin J Wainwright. Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. The Journal of Machine Learning Research, 2012.
[21] Benjamin Recht. A simpler approach to matrix completion. The Journal of Machine Learning Research, 7777777:3413–3430, 2011.
[22] Ryota Tomioka, Kohei Hayashi, and Hisashi Kashima. Estimation of low-rank tensors via convex optimization. arXiv preprint arXiv:1010.0789, 2010.
[23] Ryota Tomioka, Taiji Suzuki, Kohei Hayashi, and Hisashi Kashima. Statistical performance of convex tensor decomposition. In Advances in Neural Information Processing Systems, pages 972–980, 2011.
[24] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010. 9