nips nips2012 nips2012-254 nips2012-254-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Matthew Coudron, Gilad Lerman
Abstract: We estimate the rate of convergence and sample complexity of a recent robust estimator for a generalized version of the inverse covariance matrix. This estimator is used in a convex algorithm for robust subspace recovery (i.e., robust PCA). Our model assumes a sub-Gaussian underlying distribution and an i.i.d. sample from it. Our main result shows with high probability that the norm of the difference between the generalized inverse covariance of the underlying distribution and its estimator from an i.i.d. sample of size N is of order O(N −0.5+ ) for arbitrarily small > 0 (affecting the probabilistic estimate); this rate of convergence is close to the one of direct covariance estimation, i.e., O(N −0.5 ). Our precise probabilistic estimate implies for some natural settings that the sample complexity of the generalized inverse covariance estimation when using the Frobenius norm is O(D2+δ ) for arbitrarily small δ > 0 (whereas the sample complexity of direct covariance estimation with Frobenius norm is O(D2 )). These results provide similar rates of convergence and sample complexity for the corresponding robust subspace recovery algorithm. To the best of our knowledge, this is the only work analyzing the sample complexity of any robust PCA algorithm. 1
[1] A. Agarwal, S. Negahban, and M. Wainwright. Fast global convergence of gradient methods for high-dimensional statistical recovery. Technical Report arXiv:1104.4824, Apr 2011.
[2] A. Agarwal, S. Negahban, and M. Wainwright. Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions. In ICML, pages 1129–1136, 2011.
[3] T. T. Cai, C.-H. Zhang, and H. H. Zhou. Optimal rates of convergence for covariance matrix estimation. Ann. Statist., 38(4):2118–2144, 2010.
[4] E. J. Cand` s, X. Li, Y. Ma, and J. Wright. Robust principal component analysis? J. ACM, e 58(3):11, 2011.
[5] V. Chandrasekaran, S. Sanghavi, P. A. Parrilo, and A. S. Willsky. Rank-sparsity incoherence for matrix decomposition. Arxiv, 02139:1–24, 2009.
[6] C. Davis and W. M. Kahan. The rotation of eigenvectors by a perturbation. iii. SIAM J. on Numerical Analysis, 7:1–46, 1970.
[7] D. Hsu, S. Kakade, and T. Zhang. Robust matrix decomposition with sparse corruptions. Information Theory, IEEE Transactions on, 57(11):7221 –7234, nov. 2011.
[8] P. J. Huber and E. Ronchetti. Robust statistics. Wiley series in probability and mathematical statistics. Probability and mathematical statistics. Wiley, 2009.
[9] G. Lerman, M. McCoy, J. A. Tropp, and T. Zhang. Robust computation of linear models, or How to find a needle in a haystack. ArXiv e-prints, Feb. 2012.
[10] R. A. Maronna, R. D. Martin, and V. J. Yohai. Robust statistics: Theory and methods. Wiley Series in Probability and Statistics. John Wiley & Sons Ltd., Chichester, 2006.
[11] M. McCoy and J. Tropp. Two proposals for robust PCA using semidefinite programming. Elec. J. Stat., 5:1123–1160, 2011.
[12] P. Ravikumar, M. J. Wainwright, G. Raskutti, and B. Yu. High-dimensional covariance estimation by minimizing 1 -penalized log-determinant divergence. Electron. J. Stat., 5:935–980, 2011.
[13] A. J. Rothman, P. J. Bickel, E. Levina, and J. Zhu. Sparse permutation invariant covariance estimation. Electron. J. Stat., 2:494–515, 2008.
[14] P. J. Rousseeuw and A. M. Leroy. Robust regression and outlier detection. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. John Wiley & Sons Inc., New York, 1987.
[15] J. Shawe-taylor, C. Williams, N. Cristianini, and J. Kandola. On the eigenspectrum of the Gram matrix and the generalisation error of kernel PCA. IEEE Transactions on Information Theory, 51(1):2510–2522, 2005.
[16] L. G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134–1142, Nov. 1984.
[17] R. Vershynin. How close is the sample covariance matrix to the actual covariance matrix? to appear.
[18] R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Y. C. Eldar and G. Kutyniok, editors, Compressed Sensing: Theory and Applications. Cambridge Univ Press, to appear.
[19] H. Xu, C. Caramanis, and S. Sanghavi. Robust pca via outlier pursuit. In NIPS, pages 2496– 2504, 2010.
[20] H. Xu, C. Caramanis, and S. Sanghavi. Robust pca via outlier pursuit. Information Theory, IEEE Transactions on, PP(99):1, 2012.
[21] T. Zhang and G. Lerman. A novel m-estimator for robust pca. Submitted, available at arXiv:1112.4863.
[22] T. Zhang and H. Zou. Sparse precision matrix estimation via positive definite constrained minimization of 1 penalized d-trace loss. Personal Communication, 2012. 9