skip to main content


The NSF Public Access Repository (NSF-PAR) system and access will be unavailable from 5:00 PM ET until 11:00 PM ET on Friday, June 21 due to maintenance. We apologize for the inconvenience.

Title: The Hanson–Wright inequality for random tensors

We provide moment bounds for expressions of the type$$(X^{(1)} \otimes \cdots \otimes X^{(d)})^T A (X^{(1)} \otimes \cdots \otimes X^{(d)})$$(X(1)X(d))TA(X(1)X(d))where$$\otimes $$denotes the Kronecker product and$$X^{(1)}, \ldots , X^{(d)}$$X(1),,X(d)are random vectors with independent, mean 0, variance 1, subgaussian entries. The bounds are tight up to constants depending ondfor 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$$\Vert B (X^{(1)} \otimes \cdots \otimes X^{(d)})\Vert _2$$B(X(1)X(d))2.

more » « less
Author(s) / Creator(s):
; ;
Publisher / Repository:
Springer Science + Business Media
Date Published:
Journal Name:
Sampling Theory, Signal Processing, and Data Analysis
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Abstract

    Let$$(h_I)$$(hI)denote the standard Haar system on [0, 1], indexed by$$I\in \mathcal {D}$$ID, the set of dyadic intervals and$$h_I\otimes h_J$$hIhJdenote the tensor product$$(s,t)\mapsto h_I(s) h_J(t)$$(s,t)hI(s)hJ(t),$$I,J\in \mathcal {D}$$I,JD. We consider a class of two-parameter function spaces which are completions of the linear span$$\mathcal {V}(\delta ^2)$$V(δ2)of$$h_I\otimes h_J$$hIhJ,$$I,J\in \mathcal {D}$$I,JD. This class contains all the spaces of the formX(Y), whereXandYare either the Lebesgue spaces$$L^p[0,1]$$Lp[0,1]or the Hardy spaces$$H^p[0,1]$$Hp[0,1],$$1\le p < \infty $$1p<. We say that$$D:X(Y)\rightarrow X(Y)$$D:X(Y)X(Y)is a Haar multiplier if$$D(h_I\otimes h_J) = d_{I,J} h_I\otimes h_J$$D(hIhJ)=dI,JhIhJ, where$$d_{I,J}\in \mathbb {R}$$dI,JR, and ask which more elementary operators factor throughD. A decisive role is played by theCapon projection$$\mathcal {C}:\mathcal {V}(\delta ^2)\rightarrow \mathcal {V}(\delta ^2)$$C:V(δ2)V(δ2)given by$$\mathcal {C} h_I\otimes h_J = h_I\otimes h_J$$ChIhJ=hIhJif$$|I|\le |J|$$|I||J|, and$$\mathcal {C} h_I\otimes h_J = 0$$ChIhJ=0if$$|I| > |J|$$|I|>|J|, as our main result highlights: Given any bounded Haar multiplier$$D:X(Y)\rightarrow X(Y)$$D:X(Y)X(Y), there exist$$\lambda ,\mu \in \mathbb {R}$$λ,μRsuch that$$\begin{aligned} \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C})\text { approximately 1-projectionally factors through }D, \end{aligned}$$λC+μ(Id-C)approximately 1-projectionally factors throughD,i.e., for all$$\eta > 0$$η>0, there exist bounded operatorsABso thatABis the identity operator$${{\,\textrm{Id}\,}}$$Id,$$\Vert A\Vert \cdot \Vert B\Vert = 1$$A·B=1and$$\Vert \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C}) - ADB\Vert < \eta $$λC+μ(Id-C)-ADB<η. Additionally, if$$\mathcal {C}$$Cis unbounded onX(Y), then$$\lambda = \mu $$λ=μand then$${{\,\textrm{Id}\,}}$$Ideither factors throughDor$${{\,\textrm{Id}\,}}-D$$Id-D.

    more » « less
  2. Abstract

    For a smooth projective varietyXover an algebraic number fieldka conjecture of Bloch and Beilinson predicts that the kernel of the Albanese map ofXis a torsion group. In this article we consider a product$$X=C_1\times \cdots \times C_d$$X=C1××Cdof smooth projective curves and show that if the conjecture is true for any subproduct of two curves, then it is true forX. For a product$$X=C_1\times C_2$$X=C1×C2of two curves over$$\mathbb {Q} $$Qwith positive genus we construct many nontrivial examples that satisfy the weaker property that the image of the natural map$$J_1(\mathbb {Q})\otimes J_2(\mathbb {Q})\xrightarrow {\varepsilon }{{\,\textrm{CH}\,}}_0(C_1\times C_2)$$J1(Q)J2(Q)εCH0(C1×C2)is finite, where$$J_i$$Jiis the Jacobian variety of$$C_i$$Ci. Our constructions include many new examples of non-isogenous pairs of elliptic curves$$E_1, E_2$$E1,E2with positive rank, including the first known examples of rank greater than 1. Combining these constructions with our previous result, we obtain infinitely many nontrivial products$$X=C_1\times \cdots \times C_d$$X=C1××Cdfor which the analogous map$$\varepsilon $$εhas finite image.

    more » « less
  3. Abstract

    We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in$\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$Quasi-NP=NTIME[n(logn)O(1)]and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes$\mathcal { C}$C, by showing that$\mathcal { C}$Cadmits non-trivial satisfiability and/or#SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial#SAT algorithm for a circuit class${\mathcal C}$C. Say that a symmetric Boolean functionf(x1,…,xn) issparseif it outputs 1 onO(1) values of${\sum }_{i} x_{i}$ixi. We show that for every sparsef, and for all “typical”$\mathcal { C}$C, faster#SAT algorithms for$\mathcal { C}$Ccircuits imply lower bounds against the circuit class$f \circ \mathcal { C}$fC, which may bestrongerthan$\mathcal { C}$Citself. In particular:

    #SAT algorithms fornk-size$\mathcal { C}$C-circuits running in 2n/nktime (for allk) implyNEXPdoes not have$(f \circ \mathcal { C})$(fC)-circuits of polynomial size.

    #SAT algorithms for$2^{n^{{\varepsilon }}}$2nε-size$\mathcal { C}$C-circuits running in$2^{n-n^{{\varepsilon }}}$2nnεtime (for someε> 0) implyQuasi-NPdoes not have$(f \circ \mathcal { C})$(fC)-circuits of polynomial size.

    Applying#SAT algorithms from the literature, one immediate corollary of our results is thatQuasi-NPdoes not haveEMAJACC0THRcircuits of polynomial size, whereEMAJis the “exact majority” function, improving previous lower bounds againstACC0[Williams JACM’14] andACC0THR[Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class.

    more » « less
  4. Abstract

    A classical parking function of lengthnis a list of positive integers$$(a_1, a_2, \ldots , a_n)$$(a1,a2,,an)whose nondecreasing rearrangement$$b_1 \le b_2 \le \cdots \le b_n$$b1b2bnsatisfies$$b_i \le i$$bii. The convex hull of all parking functions of lengthnis ann-dimensional polytope in$${\mathbb {R}}^n$$Rn, which we refer to as the classical parking function polytope. Its geometric properties have been explored in Amanbayeva and Wang (Enumer Combin Appl 2(2):Paper No. S2R10, 10, 2022) in response to a question posed by Stanley (Amer Math Mon 127(6):563–571, 2020). We generalize this family of polytopes by studying the geometric properties of the convex hull of$${\textbf{x}}$$x-parking functions for$${\textbf{x}}=(a,b,\dots ,b)$$x=(a,b,,b), which we refer to as$${\textbf{x}}$$x-parking function polytopes. We explore connections between these$${\textbf{x}}$$x-parking function polytopes, the Pitman–Stanley polytope, and the partial permutahedra of Heuer and Striker (SIAM J Discrete Math 36(4):2863–2888, 2022). In particular, we establish a closed-form expression for the volume of$${\textbf{x}}$$x-parking function polytopes. This allows us to answer a conjecture of Behrend et al. (2022) and also obtain a new closed-form expression for the volume of the convex hull of classical parking functions as a corollary.

    more » « less
  5. Abstract

    The Eden cell growth model is a simple discrete stochastic process which produces a “blob” (aggregation of cells) in $$\mathbb {R}^d$$Rd: start with one cube in the regular grid, and at each time step add a neighboring cube uniformly at random. This process has been used as a model for the growth of aggregations, tumors, and bacterial colonies and the healing of wounds, among other natural processes. Here, we study the topology and local geometry of the resulting structure, establishing asymptotic bounds for Betti numbers. Our main result is that the Betti numbers at timetgrow at a rate between$$t^{(d-1)/d}$$t(d-1)/dand$$P_d(t)$$Pd(t), where$$P_d(t)$$Pd(t)is the size of the site perimeter. Assuming a widely believed conjecture, this establishes the rate of growth of the Betti numbers in every dimension. We also present the results of computational experiments on finer aspects of the geometry and topology, such as persistent homology and the distribution of shapes of holes.

    more » « less