Strategies for bounding the spectral norm of a tensor?

Question

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$?

Answer 1

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.