Rank penalized estimators for high-dimensional matrices. (English) Zbl 1274.62489

Summary: In this paper we consider the trace regression model. Assume that we observe a small set of entries or linear combinations of entries of an unknown matrix \(A_{0}\) corrupted by noise. We propose a new rank penalized estimator of \(A_{0}\). For this estimator we establish general oracle inequality for the prediction error both in probability and in expectation. We also prove upper bounds for the rank of our estimator. Then, we apply our general results to the problems of matrix completion and matrix regression. In these cases our estimator has a particularly simple form: it is obtained by hard thresholding of the singular values of a matrix constructed from the observations.


62J99 Linear inference, regression
62H12 Estimation in multivariate analysis
60B20 Random matrices (probabilistic aspects)
60G15 Gaussian processes
Full Text: DOI arXiv Euclid


[1] Argyriou, A., Evgeniou, T. and Pontil, M. (2008) Convex multi-task feature learning., Mach. Learn. , 73 , 243-272.
[2] Argyriou, A., Micchelli, C.A. and Pontil, M. (2010) On spectral learning., J. Mach. Learn. Res. , 11 , 935-953. · Zbl 1242.68201
[3] Argyriou, A., Micchelli, C.A., Pontil, M. and Ying, Y. (2007) A spectral regularization framework for multi-task structure learning. In, NIPS .
[4] Bach, F.R. (2008) Consistency of trace norm minimization., J. Mach. Learn. Res. , 9 , 1019-1048. · Zbl 1225.68146
[5] Bunea, F., She, Y. and Wegkamp, M. (2011) Optimal selection of reduced rank estimators of high-dimensional matrices., Annals of Statistics , 39 , 1282-1309. · Zbl 1216.62086 · doi:10.1214/11-AOS876
[6] Candès, E.J. and Plan, Y. (2009). Matrix completion with noise., Proceedings of IEEE .
[7] Candès, E.J. and Plan, Y. (2010) Tight oracle bounds for low-rank matrix recovery from a minimal number of random measurements., · Zbl 1366.90160
[8] Candès, E.J. and Recht, B. (2009) Exact matrix completion via convex optimization., Fondations of Computational Mathematics , 9(6) , 717-772. · Zbl 1219.90124 · doi:10.1007/s10208-009-9045-5
[9] Gaïffas, S. and Lecué, G. (2010) Sharp oracle inequalities for the prediction of a high-dimensional matrix., IEEE Transactions on Information Theory , · Zbl 1365.62137
[10] Giraud, C. (2011) Low rank Multivariate regression., Electronic Journal of Statistics , 5 , 775-799. · Zbl 1274.62434 · doi:10.1214/11-EJS625
[11] Gross, D. Recovering low-rank matrices from few coefficients in any basis. (2011)., IEEE Transactions , 57(3) , 1548-1566. · Zbl 1366.94103 · doi:10.1109/TIT.2011.2104999
[12] Keshavan, R.H., Montanari, A. and Oh, S. (2010) Matrix completion from noisy entries., Journal of Machine Learning Research , 11 , 2057-2078. · Zbl 1242.62069
[13] Koltchinskii, V., Lounici, K. and Tsybakov, A. Nuclear norm penalization and optimal rates for noisy low rank matrix completion., Annals of Statistics , · Zbl 1231.62097 · doi:10.1214/11-AOS894
[14] Negahban, S. and Wainwright, M.J. (2011). Estimation of (near) low-rank matrices with noise and high-dimensional scaling., Annals of Statistics , 39 , 1069-1097. · Zbl 1216.62090 · doi:10.1214/10-AOS850
[15] Recht, B. (2009) A simpler approach to matrix completion., Journal of Machine Learning Research , · Zbl 1280.68141
[16] Reinsel, G.C. and Velu, R.P., Multivariate Reduced-Rank Regression: Theory and Applications . Springer, 1998. · Zbl 0909.62066
[17] Rohde, A. and Tsybakov, A. (2011) Estimation of High-Dimensional Low-Rank Matrices., Annals of Statistics , 39 , 887-930. · Zbl 1215.62056 · doi:10.1214/10-AOS860
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.