The Hanson-Wright inequality for random tensors

DOI10.1007/S43670-022-00028-4MaRDI QIDQ2164658zbMATH OpenOpenAlexWikidataFDO

Authors Stefan Bamberger, Felix Krahmer, Rachel Ward

Publication date 15 August 2022

Published in Sampling Theory, Signal Processing, and Data Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2106.13345

zbMATH Keywords

Hanson-Wright inequalityJohnson-Lindenstrauss embeddingsKronecker productrandom tensorssubgaussian random variables

Mathematics Subject Classification ID

Multilinear algebra, tensor calculus (15A69) Random matrices (probabilistic aspects) (60B20) Inequalities; stochastic orderings (60E15)

Abstract: We provide moment bounds for expressions of the type $(X^{(1)}otimesdotsotimes{X}^{(d)}{)}^{T}A(X^{(1)}otimesdotsotimes{X}^{(d)})$ where $otimes$ denotes the Kronecker product and $X^{(1)},dots,X^{(d)}$ are random vectors with independent, mean 0, variance 1, subgaussian entries. The bounds are tight up to constants depending on $d$ for the case of Gaussian random vectors. Our proof also provides a decoupling inequality for expressions of this type. Using these bounds, we obtain new, improved concentration inequalities for expressions of the form $|B(X^{(1)}otimesdotsotimes{X}^{(d)}){|}_2$.

Review text

The Hanson-Wright inequality is an important probabilistic tool and can be found in various textbooks covering the basics of signal processing and probability theory. It has found numerous applications, in particular it has been a key ingredient for the construction of fast Johnson-Lindenstrauss embeddings. The main results of the present paper provide moment estimates for the semi-decoupled chaos process that is the sum of the exspressions of the type \[ (X(1)\otimes\cdots\otimes X(d))^T A(X(1)\otimes\cdots\otimes X(d)), \] where \(\otimes\) denotes the Kronecker product and \(X(1), \dots , X(d)\) are random vectors with independent, zero mean subgaussian entries with unit variance. In other words, the Hanson-Wright inequality for random tensors is obtained. The bounds are tight up to constants depending on \(d\) for the case of Gaussian random vectors. The proof also provides a decoupling inequality for expressions of the mentioned type. Using these bounds, the authors obtain new, improved concentration inequalities. The results also lay the foundations for an order-optimal analysis of fast Kronecker-structured Johnson-Lindenstrauss embeddings.

Recommendations

• Concentration inequalities for random tensors
• Hanson-Wright inequality and sub-Gaussian concentration
• Hanson-Wright inequality in Banach spaces
• A note on the Hanson-Wright inequality for random vectors with dependencies
• Sparse Hanson-Wright inequalities for subgaussian quadratic forms

Cites work

• A Bound on Tail Probabilities for Quadratic Forms in Independent Random Variables
• A mathematical introduction to compressive sensing
• A Practical Randomized CP Tensor Decomposition
• Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order
• Concentration inequalities for polynomials in \(\alpha\)-sub-exponential random variables
• Concentration inequalities for random tensors
• Decoupling and Khintchine's inequalities for \(U\)-statistics
• Decoupling inequalities for multilinear forms in independent symmetric random variables
• Decoupling inequalities for polynomial chaos
• Decoupling inequalities for the tail probabilities of multivariate \(U\)- statistics
• Estimates of moments and tails of Gaussian chaoses
• Faster Johnson-Lindenstrauss transforms via Kronecker products
• Hanson-Wright inequality and sub-Gaussian concentration
• High-dimensional probability. An introduction with applications in data science
• scientific article; zbMATH DE number 53996 (Why is no real title available?)
• Invertibility of ``large submatrices with applications to the geometry of Banach spaces and harmonic analysis
• Moment estimates for chaoses generated by symmetric random variables with logarithmically convex tails
• Moment inequalities for functions of independent random variables
• Moments of Gaussian chaoses in Banach spaces
• New and Improved Johnson–Lindenstrauss Embeddings via the Restricted Isometry Property
• Oblivious Sketching of High-Degree Polynomial Kernels
• On decoupling, series expansions, and tail behavior of chaos processes
• Optimal fast Johnson-Lindenstrauss embeddings for large data sets
• Tail and moment estimates for a class of random chaoses of order two
• Tail and moment estimates for chaoses generated by symmetric random variables with logarithmically concave tails
• Two-sided moment estimates for a class of nonnegative chaoses

Cited in

(14)

• T-product tensors. II: Tail bounds for sums of random T-product tensors
• Convenient tail bounds for sums of random tensors
• Tensor Bernstein concentration inequalities with an application to sample estimators for high-order moments
• Concentration inequalities for random tensors
• Probabilistic estimates for tensor products of random vectors
• scientific article; zbMATH DE number 7523387 (Why is no real title available?)
• Moments tensors, Hilbert's identity, and \(k\)-wise uncorrelated random variables
• Johnson–Lindenstrauss Embeddings with Kronecker Structure
• Some notes on concentration for -subexponential random variables
• Applied harmonic analysis and data science. Abstracts from the workshop held April 21--26, 2024
• Small ball probabilities for simple random tensors
• Sharp concentration of simple random tensors
• Entrywise tensor-train approximation of large tensors via random embeddings
• A note on the Hanson-Wright inequality for random vectors with dependencies

This page was built for publication: The Hanson-Wright inequality for random tensors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2164658)