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](https://www.stat.uchicago.edu/%7Elekheng/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$?



Strategies for bounding the spectral norm of a tensor?
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.


