Hanson-Wright inequality and sub-gaussian concentration

Mark Rudelson (University of Michigan)
Roman Vershynin (University of Michigan)

Abstract


In this expository note, we give a modern proof of Hanson-Wright inequality for quadratic forms in sub-gaussian random variables.We deduce a useful concentration inequality for sub-gaussian random vectors.Two examples are given to illustrate these results: a concentration of distances between random vectors and subspaces, and a bound on the norms of products of random and deterministic matrices.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-9

Publication Date: October 23, 2013

DOI: 10.1214/ECP.v18-2865

References

  • R. Adamczak, P. Wolff, Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order, arXiv:1304.1826
  • Bourgain, Jean. Random points in isotropic convex sets. Convex geometric analysis (Berkeley, CA, 1996), 53--58, Math. Sci. Res. Inst. Publ., 34, Cambridge Univ. Press, Cambridge, 1999. MR1665576
  • Barthe, Franck; Milman, Emanuel. Transference Principles for Log-Sobolev and Spectral-Gap with Applications to Conservative Spin Systems. Comm. Math. Phys. 323 (2013), no. 2, 575--625. MR3096532 arXiv:1202.5318
  • de la Peña, Víctor H.; Giné, Evarist. Decoupling. From dependence to independence. Randomly stopped processes. $U$-statistics and processes. Martingales and beyond. Probability and its Applications (New York). Springer-Verlag, New York, 1999. xvi+392 pp. ISBN: 0-387-98616-2 MR1666908
  • de la Peña, Victor H.; Montgomery-Smith, S. J. Decoupling inequalities for the tail probabilities of multivariate $U$-statistics. Ann. Probab. 23 (1995), no. 2, 806--816. MR1334173
  • Diakonikolas, Ilias; Kane, Daniel M.; Nelson, Jelani. Bounded independence fools degree-2 threshold functions. 2010 IEEE 51st Annual Symposium on Foundations of Computer Science FOCS 2010, 11--20, IEEE Computer Soc., Los Alamitos, CA, 2010. MR3024771
  • Erdős, László; Yau, Horng-Tzer; Yin, Jun. Bulk universality for generalized Wigner matrices. Probab. Theory Related Fields 154 (2012), no. 1-2, 341--407. MR2981427
  • A. Foucart, H. Rauhut, A Mathematical Introduction to Compressive Sensing. Applied and Numerical Harmonic Analysis. Birkhäuser, 2013.
  • Hanson, D. L.; Wright, F. T. A bound on tail probabilities for quadratic forms in independent random variables. Ann. Math. Statist. 42 1971 1079--1083. MR0279864
  • Hsu, Daniel; Kakade, Sham M.; Zhang, Tong. A tail inequality for quadratic forms of subgaussian random vectors. Electron. Commun. Probab. 17 (2012), no. 52, 6 pp. MR2994877
  • Latała, Rafał. Estimates of moments and tails of Gaussian chaoses. Ann. Probab. 34 (2006), no. 6, 2315--2331. MR2294983
  • Latala, Rafal; Mankiewicz, Piotr; Oleszkiewicz, Krzysztof; Tomczak-Jaegermann, Nicole. Banach-Mazur distances and projections on random subgaussian polytopes. Discrete Comput. Geom. 38 (2007), no. 1, 29--50. MR2322114
  • Ledoux, Michel. The concentration of measure phenomenon. Mathematical Surveys and Monographs, 89. American Mathematical Society, Providence, RI, 2001. x+181 pp. ISBN: 0-8218-2864-9 MR1849347
  • J. Nelson, Johnson--Lindenstrauss notes, http://web.mit.edu/minilek/www/jl_notes.pdf.
  • Talagrand, Michel. Concentration of measure and isoperimetric inequalities in product spaces. Inst. Hautes Études Sci. Publ. Math. No. 81 (1995), 73--205. MR1361756
  • Tao, Terence. Topics in random matrix theory. Graduate Studies in Mathematics, 132. American Mathematical Society, Providence, RI, 2012. x+282 pp. ISBN: 978-0-8218-7430-1 MR2906465
  • Vershynin, Roman. Spectral norm of products of random and deterministic matrices. Probab. Theory Related Fields 150 (2011), no. 3-4, 471--509. MR2824864
  • Vershynin, Roman. Introduction to the non-asymptotic analysis of random matrices. Compressed sensing, 210--268, Cambridge Univ. Press, Cambridge, 2012. MR2963170
  • Wright, F. T. A bound on tail probabilities for quadratic forms in independent random variables whose distributions are not necessarily symmetric. Ann. Probability 1 (1973), no. 6, 1068--1070. MR0353419
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.