Tensors with low spectral norm - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T06:06:15Z http://mathoverflow.net/feeds/question/97155 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/97155/tensors-with-low-spectral-norm Tensors with low spectral norm Michal Kotowski 2012-05-16T20:03:03Z 2012-05-16T20:03:03Z <p>Consider a tensor $T$ with six indices, $T_{(ii')(jj')(kk')}$, where each index goes from $1$ to $n$. We can think of $T$ as a linear map from $\mathbb{R}^n \otimes \mathbb{R}^n \otimes \mathbb{R}^n$ to itself and consider its spectral norm:</p> <p>$\Vert T \Vert_{\infty} = \sup \vert \sum T_{(ii')(jj')(kk')} x_{ijk}y_{i'j'k'}\vert$ </p> <p>where the supremum is taken over all unit vectors $x,y \in \mathbb{R}^n \otimes \mathbb{R}^n \otimes \mathbb{R}^n$.</p> <p>On the other hand $T$ can also be viewed as trilinear form on $n$-dimensional matrices, so we can define a norm:</p> <p>$\Vert T \Vert_{2,2,2} = \sup \vert \sum T_{(ii')(jj')(kk')} X_{ii'} Y_{jj'}Z_{kk'}\vert$</p> <p>where the supremum is over all matrices $X,Y,Z$ of Frobenius norm $1$.</p> <p>What are the examples of tensors which have high (as $n \to \infty$) spectral norm as linear maps, but low norm as trilinear forms?</p> <p>Since the question is admittedly rather general, let's specialize to tensors of a more special form, namely $T_{(ii')(jj')(kk')} = g_{ijk}h_{i'j'k'}$, where $g,h \in \mathbb{R}^n \otimes \mathbb{R}^n \otimes \mathbb{R}^n$, so that $T = gh^{T}$ as a linear map. Then its spectral norm is simply $\Vert g\Vert \cdot \Vert h\Vert$. Taking $g$ and $h$, say, to be unit vectors, how should we choose them to get a low trilinear norm:</p> <p>$\Vert T \Vert_{2,2,2} = \sup \vert \sum g_{ijk}h_{i'j'k'} X_{ii'} Y_{jj'}Z_{kk'}\vert$ ?</p> <p>It can be shown that randomly chosen $g, h$ will have the desired property, but I'm interested in more explicit examples. Because there is no direct analog of the spectral decomposition for tensors, the intuition that the "mass" of $T$ should be "spread out" roughly in all directions (as in the case of matrices with low spectral norm, but high Frobenius norm) on the $\mathbb{R}^{n^2}$ components of the tensor product is not easy to formalize.</p>