# Strategies for bounding the spectral norm of a tensor?

Let $$A$$ be a symmetric $$k$$-tensor over a real or complex vector field $$W$$. We may define its spectral norm $$|A|$$ by $$|A| = \sup_{v\in W} \frac{|\langle A,x^{\otimes k}\rangle|}{|x|_2^k}.$$ (Alternatively, we may define it in a different, standard way and then show that the above inequality holds - that is a theorem of Banach's (see, e.g., https://www.stat.uchicago.edu/~lekheng/work/nuclear.pdf , beginning of section 5).)

What would be some strategies -- combinatorial of preference -- to bound the norm of $$|A|$$? By "combinatorial" I mean something analogous to "counting paths".

Let me give an example of a common strategy for $$k=2$$. The trace of any power $$A^m$$ of a real symmetric matrix can be expressed in two ways: combinatorially, that is, as a sum over closed paths (interpreting $$A$$ as the adjacency matrix of a graph with weights) and spectrally, as a sum $$\sum_i \lambda_i^m$$ over all eigenvalues $$\lambda_i$$. In fact, we do not need the full spectral decomposition - it is enough to note that $$\langle v,A^2 v\rangle = \langle A v,A v\rangle \geq 0$$ for any $$v$$. Then it follows that, for $$m$$ even, $$|A|^m\leq \textrm{Tr}\,A^m = (\text{sum over closed paths}).$$ There are various ways to amplify this bound (e.g., high multiplicity).

Is an inequality even vaguely resembling this one possible for higher $$k$$?

• It depends on what quality of bound you want. You can take the sum $\langle A, x^{\otimes k} \rangle$ and apply Cauchy-Schwarz a bunch to bound it in terms of the $2$-norm of $x$ and some kind of sum-of-product invariants of $A$. The simplest case of this is, for a three-tensor, to observe $|A_{ijk} x_i x_j x_k|^2\leq |x|_2^2 | \sum_{ijlm} x_i x_j x_l x_m \sum_{k} A_{ijk} A_{lmk}|$ and then estimate the spectral norm of $\sum_{k} A_{ijk} A_{lmk}$ as an $n^2\times n^2$ matrix with coordinates $(i,l)$ and $(j,m)$. Mar 30 at 16:59
• However, doing so will not get you bounds for $\langle A, x^{\otimes k} \rangle$ that are as strong as those known for a random tensor (which you can do for matrices, of course). But this may be a reflection of the strength of bounds provable for random tensors more than the weakness of these methods (which I learned about from Tao's paper "Expanding polynomials over finite fields of large characteristic, and a regularity lemma for definable sets " arxiv.org/abs/1211.2894 building on Bukh and Tsimerman's "Sum-product estimates for rational functions") Mar 30 at 17:03
• The only result I know for an explicit tensor sparser than the square-root barrier is "On the polynomial Szemeredi theorem over finite fields" by Peluse (arxiv.org/pdf/1802.02200.pdf), which is about an $n\times n \times \dots n$ $k$-tensor supported on a set of size $n^2$. This is sub-sqrt for $k>4$ but still probably larger than what you want, and the argument very much takes advantage of the additive structure and low-degree polynomial structure. I am no expert but I think this is the level of techniques that would be needed for similar problems... Mar 30 at 19:31
• In a vector space with a basis $e_{a}$ corresponding to the elements $x\in \mathbb F_q$, we have an $m+1$-tensor $B= \sum_{x,y\in \mathbb F_q} e_{x} \otimes e_{ x+P_1(y)} \otimes \dots \otimes e_{ x+ P_m(y)}$, and once we subtract off the "trivial eigenvalue" by taking $A = B - p^{1-m} \sum_{x_0,\dots, x_m \in \mathbb F_q} e_{x_0} \otimes e_{x_1} \otimes \dots \otimes e_{a_m}$, her result is equivalent to a bound for $\langle A, v^{\otimes k} \rangle/ |v|_{\infty}^k$, which is what you wrote down except for the $\ell^\infty$ norm instead of the $\ell^2$. Mar 30 at 20:36
• If you replace $|x|_{2}^{k}$ in the denominator by $|x|^{k}_{\infty}$ then there are lower bounds of this "spectral norm" in terms of $\ell^{\frac{2k}{k+1}}$ norm of $\{A_{i_{1}, .., i_{k}}\}$ and a constant $C=C(k)$. Bohnenblust--Hille, and Littlewood's 4/3 inequality are good keywords. I have not seen "counting paths" in the proofs of lower bounds. The proofs use hypercontractivity, and certain Blei's type inequalities, and perhaps Blei's inequality is the one which should count as "combinatorial part". See around page 8, analytic.wmi.amu.edu.pl/static/slides/Defant.pdf Mar 31 at 22:21

I will show, with some non-rigorous steps, that a bound of this form that is valid for arbitrary tensors and useful for sparse tensors (fewer than $$n^{k/2}$$ nonvanishing entries) does not exist.

First note that there is a problem with using the $$\ell^2$$ norm to define the spectral norm for very sparse tensors $$A$$, regardless of how you try to bound it. The reason is that, assuming the nonzero entries of $$A$$ are normalized to have size $$\approx 1$$, the minimum value you could possibly hope to bound the spectral norm to is $$\approx 1$$, by choosing some nonzero entry $$A_{n_1n_2 \dots n_k}$$ of $$A$$ and choosing $$x$$ a sparse vector supported on $$n_1,\dots, n_k$$.

This means if $$x$$ is a vector of support of size $$m$$ and average size $$1$$, then the $$\ell^2$$ norm of $$x$$ is $$m^{1/2}$$, so the best bound you could hope for on $$\langle A, x^{\otimes k} \rangle$$ from the spectral norm is $$m^{k/2}$$. But the trivial bound for $$\langle A, x^{\otimes k} \rangle$$ is $$md$$ where $$d$$ is the maximum degree of $$A$$ (the maximum number of nonzero entries in a hyperplane slice of $$A$$). So to get a nontrivial bound you want $$m < d^{ \frac{2}{k-2}}$$, which is pretty small if $$d$$ is large!

So I'll use the $$\ell^p$$ norm instead for the remainder, for some $$p\geq k$$.

Let $$W = \mathbb R^n$$ be a real vector space of dimension $$n$$. Suppose that $$f$$ is a homogeneous polynomial in the entries of a tensor $$A$$ in $$W^{ \otimes k}$$ where we have an inequality of the form $$\left(\sup \frac{ \langle A, x^{\otimes k} \rangle}{ |x|_p^k} \right)^{d} \leq f(A)$$

(One could think we should allow absolute values on the right side but we can just square both sides to remove them.)

I will argue rigorously that the coefficient of some monomial in $$f$$ has size at least $$n^{ dk (1/2-1/p)}/ O_{d,k}(1)$$ and heuristically that no $$f$$ with such a large coefficient gives a good bound for highly sparse tensors.

Translating $$f$$ by any matrix $$g$$ in the group $$(\mathbb Z/2) \rtimes S_n$$ produces a tensor with the same spectral norm. So the minimum of $$f( g\cdot A)$$ for $$g \in (\mathbb Z/2) \rtimes S_n$$ for also bounds the spectral norm. It follows that the average of $$f(g\cdot A)$$ over $$g \in (\mathbb Z/2) \rtimes S_n$$ also bounds the spectral norm. This average cannot increase the largest coefficient of a monomial in $$f$$, so we may as well assume $$f$$ is $$(\mathbb Z/2) \rtimes S_n$$-invariant.

By scaling, certainly $$f$$ must be homogeneous of degree $$d$$.

We can write $$f$$ as a sum over monomials of the form $$\prod_{i=1}^d A_{a_{i,1} \dots a_{i,k}}$$ for some tuple $$a_{i,j}$$ of numbers from $$1$$ to $$n$$ indexed by $$i$$ from $$1$$ to $$d$$ and $$j$$ from $$1$$ to $$k$$.

The $$(\mathbb Z/2)^n$$-invariance implies the coefficient of a monomial vanishes if any number appears an odd number of times among the $$a_{i,j}$$. The $$S_n$$-invariance says the coefficients of a monomial depend only on the choice of $$a_{i,j}$$ up to permutation. We can express this as the claim that $$f$$ is a linear combination of the polynomials of the form

$$\sum_{ a \colon [m] \to [n] \textrm{ injective}} \prod_{i=1}^d A_{ a (l_{i,1}) a(l_{i,2}) \dots a(l_{i,j})}$$ for some fixed tuple $$l_{i,j}$$ of integers from $$1$$ to $$m$$ indexed by $$i$$ from $$1$$ to $$d$$ and $$j$$ from $$1$$ to $$k$$, where each number appears an even number of times among the $$l_{i,j}$$ (which we may assume is at least twice). The sum is over injective maps from the numbers $$1$$ to $$m$$ to the numbers $$1$$ to $$n$$. We could, if we chose, drop the "injective" condition.

Now let's consider what happens when we apply this inequality to the all-$$1$$s tensor. This tensor has spectral norm $$\frac{n^k}{ n^{ k/p}}$$, so the left side is $$n^{d k (1-1/p)}$$.

The value of the invariant polynomial $$\sum_{ a \colon [m] \to [n] \textrm{ injective}} \prod_{i=1}^d A_{ a (l_{i,1}) a(l_{i,2}) \dots a(l_{i,j})}$$ is just the number of injective maps from $$[m]$$ to $$n$$, which is at most $$n^m$$.

Because each $$\ell$$ occurs at least twice among the $$\ell_{i,j}$$, we have $$m \leq d k / 2$$.

Thus the sum of the coefficients of these various polynomials in the linear expression for $$f$$ must be at least $$n^{ d k (1/2-1/p)}$$. Since the number of different polynomials that can appear depends only on $$d$$ and $$k$$, the coefficient of one of the monomials must be at least $$n^{ d k (1/2-1/p)}/ (dk)^{dk}$$.

Now consider a sparse tensor $$A$$, say with $$N$$ nonvanishing entries, each of size $$1$$. Assuming $$A$$ comes from some tricky mathematical construction, we are unlikely to get an estimate for $$f(A)$$ with error term smaller than the largest coefficient of a monomial in $$f$$ as that would require getting an estimate for a difficult sum with error term less than a single term of the sum.

Thus, we won't expect to get a bound for the spectral norm of $$A$$ better than $$n^{ k (1/2-1/p)}/ (dk)^k \approx n^{ k(1/2-1/p)}$$ (assuming $$d,k$$ grow slowly, which is reasonable).

If we plug a "typical" vector $$x$$ into $$A$$, whose entries have size around $$1$$, we will therefore not get a bound for $$\langle A, x^{\otimes k} \rangle$$ better than $$n^{ k /2}$$. But if $$N < n^{k/2}$$, this is worse than the trivial bound for the sum, so our spectral norm estimate will be useless for such vectors.

One can actually construct an explicit polynomial bound for the spectral norm where the coefficients of the monomials have size $$\approx n^{1/2 - 1/p}$$ by proving a bound for the $$\ell^2$$-spectral norm using Cauchy-Schwarz a bunch and then bounding the $$\ell^2$$ norm trivially via the $$\ell^p$$ norm.

For $$p<1/2$$, the lower bound is instead $$1$$, which I think you can also achieve by using Holder's inequality repeatedly.

An example of the Cauchy-Schwarz argument, for an $$n \times n \times n$$ tensor:

We have

$$\left(\sum_{i_1,i_2,i_3 \in [n]} A_{i_1i_2i_3} x_{i_1} x_{i_2} x_{i_3}\right)^8 \leq |x|_2^8 \left( \sum_{i_1 \in [n]} \left( \sum_{i_2, i_3 \in [n]} A_{i_1 i_2 i_3} x_{i_2} x_{i_3} \right)^2 \right)^4 = |x|_2^8 \left( \sum_{i_1 ,i_2 ,i_3,i_4,i_5\in [n]} A_{i_1 i_2 i_3} A_{i_1 i_4 i_5} x_{i_2} x_{i_3} x_{i_4} x_{i_5} \right)^4 \leq |x|_2^{16} \left( \sum_{i_2, i_4\in [n]} \left( \sum_{i_1,i_3,i_5\in [n]} A_{i_1 i_2 i_3} A_{i_1 i_4 i_5} x_{i_3} x_{i_5} \right)^2 \right)^2 =|x|_2^{16} \left(\sum_{ i_1, i_2, i_3,i_4, i_5, i_6, i_7, i_8 \in [n]} A_{i_1 i_2 i_3} A_{i_1 i_4 i_5} A_{i_6 i_2 i_7} A_{i_6 i_4 i_8} x_{i_3} x_{i_5} x_{i_7} x_{i_8} \right)^2 \leq |x|_2^{24} \sum_{i_3, i_5 ,i_7, i_8 \in [n ] } \left( \sum_{i_1, i_2, i_4, i_6 \in [n]} A_{i_1 i_2 i_3} A_{i_1 i_4 i_5} A_{i_6 i_2 i_7} A_{i_6 i_4 i_8} \right)^2$$

which, when you expand it out, should have an elegant symmetric structure where the eight copies of $$A$$ correspond to the vertices of the cube and the various $$i$$ indices to edges.

• To whom is this remarkable classification of the O(W)-invariant functions due? I'd never seen this before.
– JSE
Mar 31 at 3:24
• @JSE From a paper of Deligne, it looks like the original reference may be H. Weyl, Classical Groups, their Invariants and Representations. It is (not always) called "the first fundamental theorem of invariant theory for the orthogonal group". Mar 31 at 3:53
• @WillSawin I agree that using the $\ell^k$ norm would make more sense than using the $\ell^2$ norm. But do we have an analogue of the inequality of Banach's alluded to above in that case? Mar 31 at 11:09
• @HAHelfgott I don't dispute this (except the k! on the left helps so maybe it's only exponential in $k$). Mar 31 at 13:39
• Incidentally, the final expression in this new example is (the eighth power of what is known as) the Gowers box norm of the tensor $A$, which is indeed a good tool for understanding the spectral norm of $A$ (and more) when $A$ is dense, but not when $A$ is sparse. Apr 1 at 20:00