Perturbation bounds for eigenspaces under a relative gap condition

Jirak, Moritz; Wahl, Martin

doi:10.1090/proc/14714

Perturbation bounds for eigenspaces under a relative gap condition
HTML articles powered by AMS MathViewer

by Moritz Jirak and Martin Wahl

Proc. Amer. Math. Soc. 148 (2020), 479-494

DOI: https://doi.org/10.1090/proc/14714

Published electronically: September 20, 2019

PDF | Request permission

Abstract:

A basic problem in operator theory is to estimate how a small perturbation affects the eigenspaces of a self-adjoint compact operator. In this paper, we prove upper bounds for the subspace distance, tailored for relative perturbations. As a main example, we consider the empirical covariance operator and show that a sharp bound can be achieved under a relative gap condition. The proof is based on a novel contraction phenomenon, contrasting previous spectral perturbation approaches.

References

Radosław Adamczak, A note on the Hanson-Wright inequality for random vectors with dependencies, Electron. Commun. Probab. 20 (2015), no. 72, 13. MR 3407216, DOI 10.1214/ECP.v20-3829
T. W. Anderson, Asymptotic theory for principal component analysis, Ann. Math. Statist. 34 (1963), 122–148. MR 145620, DOI 10.1214/aoms/1177704248
Rajendra Bhatia, Matrix analysis, Graduate Texts in Mathematics, vol. 169, Springer-Verlag, New York, 1997. MR 1477662, DOI 10.1007/978-1-4612-0653-8
Stéphane Boucheron, Gábor Lugosi, and Pascal Massart, Concentration inequalities, Oxford University Press, Oxford, 2013. A nonasymptotic theory of independence; With a foreword by Michel Ledoux. MR 3185193, DOI 10.1093/acprof:oso/9780199535255.001.0001
T. Tony Cai, Zongming Ma, and Yihong Wu, Sparse PCA: optimal rates and adaptive estimation, Ann. Statist. 41 (2013), no. 6, 3074–3110. MR 3161458, DOI 10.1214/13-AOS1178
Françoise Chatelin, Spectral approximation of linear operators, Computer Science and Applied Mathematics, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York, 1983. With a foreword by P. Henrici; With solutions to exercises by Mario Ahués. MR 716134
J. Dauxois, A. Pousse, and Y. Romain, Asymptotic theory for the principal component analysis of a vector random function: some applications to statistical inference, J. Multivariate Anal. 12 (1982), no. 1, 136–154. MR 650934, DOI 10.1016/0047-259X(82)90088-4
Chandler Davis and W. M. Kahan, The rotation of eigenvectors by a perturbation. III, SIAM J. Numer. Anal. 7 (1970), 1–46. MR 264450, DOI 10.1137/0707001
Uwe Einmahl and Deli Li, Characterization of LIL behavior in Banach space, Trans. Amer. Math. Soc. 360 (2008), no. 12, 6677–6693. MR 2434306, DOI 10.1090/S0002-9947-08-04522-4
Peter Hall and Mohammad Hosseini-Nasab, Theory for high-order bounds in functional principal components analysis, Math. Proc. Cambridge Philos. Soc. 146 (2009), no. 1, 225–256. MR 2461880, DOI 10.1017/S0305004108001850
Lajos Horváth and Piotr Kokoszka, Inference for functional data with applications, Springer Series in Statistics, Springer, New York, 2012. MR 2920735, DOI 10.1007/978-1-4614-3655-3
Tailen Hsing and Randall Eubank, Theoretical foundations of functional data analysis, with an introduction to linear operators, Wiley Series in Probability and Statistics, John Wiley & Sons, Ltd., Chichester, 2015. MR 3379106, DOI 10.1002/9781118762547
Ilse C. F. Ipsen, Relative perturbation results for matrix eigenvalues and singular values, Acta numerica, 1998, Acta Numer., vol. 7, Cambridge Univ. Press, Cambridge, 1998, pp. 151–201. MR 1689433, DOI 10.1017/S0962492900002828
Ilse C. F. Ipsen, An overview of relative $\sin \Theta$ theorems for invariant subspaces of complex matrices, J. Comput. Appl. Math. 123 (2000), no. 1-2, 131–153. Numerical analysis 2000, Vol. III. Linear algebra. MR 1798523, DOI 10.1016/S0377-0427(00)00404-0
Moritz Jirak, Optimal eigen expansions and uniform bounds, Probab. Theory Related Fields 166 (2016), no. 3-4, 753–799. MR 3568039, DOI 10.1007/s00440-015-0671-3
Moritz Jirak and Martin Wahl, Relative perturbation bounds with applications to empirical covariance operators, https://arxiv.org/pdf/1802.02869, 2018.
Tosio Kato, Perturbation theory for linear operators, Classics in Mathematics, Springer-Verlag, Berlin, 1995. Reprint of the 1980 edition. MR 1335452, DOI 10.1007/978-3-642-66282-9
Vladimir Koltchinskii and Karim Lounici, Asymptotics and concentration bounds for bilinear forms of spectral projectors of sample covariance, Ann. Inst. Henri Poincaré Probab. Stat. 52 (2016), no. 4, 1976–2013 (English, with English and French summaries). MR 3573302, DOI 10.1214/15-AIHP705
Vladimir Koltchinskii and Karim Lounici, Concentration inequalities and moment bounds for sample covariance operators, Bernoulli 23 (2017), no. 1, 110–133. MR 3556768, DOI 10.3150/15-BEJ730
RafałLatała, Some estimates of norms of random matrices, Proc. Amer. Math. Soc. 133 (2005), no. 5, 1273–1282. MR 2111932, DOI 10.1090/S0002-9939-04-07800-1
André Mas and Frits Ruymgaart, High-dimensional principal projections, Complex Anal. Oper. Theory 9 (2015), no. 1, 35–63. MR 3300524, DOI 10.1007/s11785-014-0371-5
Sean O’Rourke, Van Vu, and Ke Wang, Random perturbation of low rank matrices: improving classical bounds, Linear Algebra Appl. 540 (2018), 26–59. MR 3739989, DOI 10.1016/j.laa.2017.11.014
Markus Reiß and Martin Wahl, Non-asymptotic upper bounds for the reconstruction error of PCA, Ann. Statist., to appear.
Bernhard Schölkopf, An introduction to support vector machines, Recent advances and trends in nonparametric statistics, Elsevier B. V., Amsterdam, 2003, pp. 3–17. MR 2498229, DOI 10.1016/B978-044451378-6/50001-6
Ramon van Handel, Structured random matrices, Convexity and concentration, IMA Vol. Math. Appl., vol. 161, Springer, New York, 2017, pp. 107–156. MR 3837269
Roman Vershynin, Introduction to the non-asymptotic analysis of random matrices, Compressed sensing, Cambridge Univ. Press, Cambridge, 2012, pp. 210–268. MR 2963170
Van Vu, Singular vectors under random perturbation, Random Structures Algorithms 39 (2011), no. 4, 526–538. MR 2846302, DOI 10.1002/rsa.20367
Y. Yu, T. Wang, and R. J. Samworth, A useful variant of the Davis-Kahan theorem for statisticians, Biometrika 102 (2015), no. 2, 315–323. MR 3371006, DOI 10.1093/biomet/asv008