nips nips2012 nips2012-64 nips2012-64-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Tingni Sun, Cun-hui Zhang
Abstract: This paper concerns the problem of matrix completion, which is to estimate a matrix from observations in a small subset of indices. We propose a calibrated spectrum elastic net method with a sum of the nuclear and Frobenius penalties and develop an iterative algorithm to solve the convex minimization problem. The iterative algorithm alternates between imputing the missing entries in the incomplete matrix by the current guess and estimating the matrix by a scaled soft-thresholding singular value decomposition of the imputed matrix until the resulting matrix converges. A calibration step follows to correct the bias caused by the Frobenius penalty. Under proper coherence conditions and for suitable penalties levels, we prove that the proposed estimator achieves an error bound of nearly optimal order and in proportion to the noise level. This provides a unified analysis of the noisy and noiseless matrix completion problems. Simulation results are presented to compare our proposal with previous ones. 1
[1] ACM SIGKDD and Netflix. Proceedings of KDD Cup and workshop. 2007.
[2] E. Candes and B. Recht. Exact matrix completion via convex optimization. Found. Comput. Math., 9:717–772, 2009.
[3] E. J. Cand` s and T. Tao. The power of convex relaxation: Near-optimal matrix completion. e IEEE Trans. Inform. Theory, 56(5):2053–2080, 2009.
[4] D. Gross. Recovering low-rank matrices from few coefficients in any basis. abs/0910.1879, 2009. CoRR,
[5] R. H. Keshavan, A. Montanari, and S. Oh. Matrix completion from a few entries. IEEE Transactions on Information Theory, 56(6):2980–2998, 2010.
[6] R. H. Keshavan, A. Montanari, and S. Oh. Matrix completion from noisy entries. Journal of Machine Learning Research, 11:2057–2078, 2010.
[7] V. Koltchinskii, K. Lounici, and A. B. Tsybakov. Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion. The Annals of Statistics, 39:2302–2329, 2011.
[8] R. Mazumder, T. Hastie, and R. Tibshirani. Spectral regularization algorithms for learning large incomplete matrices. Journal of Machine Learning Research, 11:2287–2322, 2010.
[9] S. Negahban and M. J. Wainwright. Restricted strong convexity and weighted matrix completion: Optimal bounds with noise. 2010.
[10] R. I. Oliveira. Concentration of the adjacency matrix and of the laplacian in random graphs with independent edges. Technical Report arXiv:0911.0600, arXiv, 2010.
[11] B. Recht. A simpler approach to matrix completion. Journal of Machine Learning Research, 12:3413–3430, 2011.
[12] J. A. Tropp. User-friendly tail bounds for sums of random matrices. Found. Comput. Math. doi:10.1007/s10208-011-9099-z., 2011.
[13] P.-A. Wedin. Perturbation bounds in connection with singular value decomposition. BIT, 12:99–111, 1972.
[14] C.-H. Zhang and T. Zhang. A general framework of dual certificate analysis for structured sparse recovery problems. Technical report, arXiv: 1201.3302v1, 2012.
[15] H. Zou and T. Hastie. Regularization and variable selection via the elastic net. J. R. Statist. Soc. B, 67:301–320, 2005. 9