Sparse Hanson-Wright inequalities for subgaussian quadratic forms. (English) Zbl 1466.60036

Zhou, Shuheng

Bernoulli 25, No. 3, 1603-1639 (2019).

Summary: In this paper, we provide a proof for the Hanson-Wright inequalities for sparse quadratic forms in subgaussian random variables. This provides useful concentration inequalities for sparse subgaussian random vectors in two ways. Let \(X=(X_{1},\dots,X_{m})\in\mathbb{R}^{m}\) be a random vector with independent subgaussian components, and \(\xi=(\xi_{1},\dots,\xi_{m})\in\{0,1\}^{m}\) be independent Bernoulli random variables. We prove the large deviation bound for a sparse quadratic form of \((X\circ\xi)^{T}A(X\circ\xi)\), where \(A\in\mathbb{R}^{m\times m}\) is an \(m\times m\) matrix, and random vector \(X\circ\xi\) denotes the Hadamard product of an isotropic subgaussian random vector \(X\in\mathbb{R}^{m}\) and a random vector \(\xi\in\{0,1\}^{m}\) such that \((X\circ\xi)_{i}=X_{i}\xi_{i}\), where \(\xi_{1},\dots,\xi_{m}\) are independent Bernoulli random variables. The second type of sparsity in a quadratic form comes from the setting where we randomly sample the elements of an anisotropic subgaussian vector \(Y=HX\) where \(H\in\mathbb{R}^{m\times m}\) is an \(m\times m\) symmetric matrix; we study the large deviation bound on the \(\ell_{2}\)-norm \(\lVert D_{\xi}Y\rVert_{2}^{2}\) from its expected value, where for a given vector \(x\in\mathbb{R}^{m}\), \(D_{x}=\operatorname{diag}(x)\) denotes the diagonal matrix whose main diagonal entries are the entries of \(x\). This form arises naturally from the context of covariance estimation.

MSC:

60E15	Inequalities; stochastic orderings
60F10	Large deviations
62H12	Estimation in multivariate analysis

Keywords:

Hanson-Wright inequality; sparse quadratic forms; subgaussian concentration

References:

[1]	Adamczak, R. and Wolff, P. (2015). Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order. Probab. Theory Related Fields162 531-586. · Zbl 1323.60033 · doi:10.1007/s00440-014-0579-3
[2]	Dawid, A.P. (1981). Some matrix-variate distribution theory: Notational considerations and a Bayesian application. Biometrika68 265-274. · Zbl 0464.62039 · doi:10.1093/biomet/68.1.265
[3]	de la Peña, V.H. and Giné, E. (1999). Decoupling: From Dependence to Independence: Randomly Stopped Processes. \(U\)-Statistics and Processes. Martingales and Beyond. Probability and Its Applications (New York). New York: Springer. · Zbl 0918.60021
[4]	de la Peña, V.H. and Montgomery-Smith, S.J. (1995). Decoupling inequalities for the tail probabilities of multivariate \(U\)-statistics. Ann. Probab.23 806-816. · Zbl 0827.60014
[5]	Diakonikolas, I., Kane, D.M. and Nelson, J. (2010). Bounded independence fools degree-2 threshold functions. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science—FOCS 2010 11-20. Los Alamitos, CA: IEEE Computer Soc.
[6]	Foucart, S. and Rauhut, H. (2013). A Mathematical Introduction to Compressive Sensing. Applied and Numerical Harmonic Analysis. New York: Birkhäuser/Springer. · Zbl 1315.94002
[7]	Gupta, A.K. and Varga, T. (1992). Characterization of matrix variate normal distributions. J. Multivariate Anal.41 80-88. · Zbl 0745.62052
[8]	Hanson, D.L. and Wright, F.T. (1971). A bound on tail probabilities for quadratic forms in independent random variables. Ann. Math. Stat.42 1079-1083. · Zbl 0216.22203 · doi:10.1214/aoms/1177693335
[9]	Horn, R.A. and Johnson, C.R. (1991). Topics in Matrix Analysis. Cambridge: Cambridge Univ. Press. · Zbl 0729.15001
[10]	Hsu, D., Kakade, S.M. and Zhang, T. (2012). Tail inequalities for sums of random matrices that depend on the intrinsic dimension. Electron. Commun. Probab.17 Art. ID 14. · Zbl 1243.60007
[11]	Latała, R. (2006). Estimates of moments and tails of Gaussian chaoses. Ann. Probab.34 2315-2331. · Zbl 1119.60015
[12]	Rudelson, M. (2016). On the complexity of the set of unconditional convex bodies. Discrete Comput. Geom.55 185-202. · Zbl 1343.53070
[13]	Rudelson, M. and Vershynin, R. (2013). Hanson-Wright inequality and sub-Gaussian concentration. Electron. Commun. Probab.18 Art. ID 82. · Zbl 1329.60056
[14]	Talagrand, M. (1995). Sections of smooth convex bodies via majorizing measures. Acta Math.175 273-300. · Zbl 0917.46006
[15]	Vershynin, R. (2011). A simple decoupling inequality in probability theory. Available at http://www-personal.umich.edu/ romanv/papers/papers.html.
[16]	Vershynin, R. (2012). Introduction to the non-asymptotic analysis of random matrices. In Compressed Sensing 210-268. Cambridge: Cambridge Univ. Press.
[17]	Wright, F.T. (1973). A bound on tail probabilities for quadratic forms in independent random variables whose distributions are not necessarily symmetric. Ann. Probab.1 1068-1070. · Zbl 0271.60033
[18]	Zhou, S. (2014). Gemini: Graph estimation with matrix variate normal instances. Ann. Statist.42 532-562. · Zbl 1301.62054
[19]	Zhou, S. (2014). Supplement to “Gemini: Graph estimation with matrix variate normal instances”. Ann. Statist.DOI:10.1214/13-AOS1187SUPP. · Zbl 1301.62054