Spectral norm of random tensors

Notation and main result

if $\boldsymbol{u}_{k}\in S_{n_{k}-1}$ for $k=1,\ldots,K$.

By the assumption $E\left[e^{sX_{i_{1}i_{2}\cdots i_{K}}u_{1i_{1}}u_{2i_{2}}\cdots u_{Ki_{K}}}\right]\leq\exp(u_{1i_{1}}^{2}u_{2i_{2}}^{2}\cdots u_{Ki_{K}}^{2}\sigma^{2}s^{2}/2)$. Then follow the line of the proof of Hoeffding’s inequality to obtain

Minimizing over $s$, the right-hand side becomes $e^{-t^{2}/(2\sigma^{2})}$. Similarly we obtain $P(\mathcal{X}(\boldsymbol{u}_{1},\ldots,\boldsymbol{u}_{K})\leq-t)\leq e^{-t^{2}/(2\sigma^{2})}$, and the statement is obtained by taking the union of the two cases. ∎

Assume that for each fixed $\boldsymbol{u}_{k}\in S_{k}$ ($k=1,\ldots,K$), we have

Then the spectral norm \bigl{|}\!\bigl{|}\!\bigl{|}\mathcal{X}\bigr{|}\!\bigr{|}\!\bigr{|} can be bounded as follows:

with probability at least $1-\delta$ and $K_{0}=\log(3/2)$.

We use a covering number argument. Let $C_{1},\ldots,C_{K}$ be $\epsilon$-covers of $S^{n_{1}-1},\ldots,S^{n_{K}-1}$. Then since $S^{n_{1}-1}\times\cdots\times S^{n_{K}-1}$ is compact, there is a maximizer $(\boldsymbol{u}_{1}^{\ast},\ldots,\boldsymbol{u}_{K}^{\ast})$ of (1) and using the $\epsilon$-covers, we can write

where $\bar{\boldsymbol{u}}_{k}\in C_{k}$ and $\|\boldsymbol{\delta}_{k}\|\leq\epsilon$ for $k=1,\ldots,K$ by the definition. Now

Take $\epsilon=K_{0}/K$ then the sum inside the parenthesis can be bounded as follows:

Since the $\epsilon$-covering number $|C_{k}|$ can be bounded by $\epsilon/2$-packing number, which can be bounded by $(2/\epsilon)^{n_{k}}$, using the union bound we obtain

Finally, we take $t=\sqrt{8\sigma^{2}\left((\sum_{k}n_{k})\log(2K/K_{0})+\log(2/\delta)\right)}$ to obtain our claim. ∎

We note that a similar bound was proved in Nguyen et al. (2010). We believe that our proof is more concise and simple.

Assume that each entry $X_{i_{1}\cdots i_{K}}$ is conditionally independent given $\boldsymbol{\epsilon}=(\epsilon_{i})_{i=1}^{M}$ and distributed as

where we used the fact that $\sum_{i_{1}}\cdots\sum_{i_{K}}u_{1i_{1}}^{2}\cdots u_{Ki_{K}}^{2}=1$. Therefore, we have

2 Implication for sampling without replacement

with probability at least $1-\delta$ and $K_{0}=\log(3/2)$.

This is analogous to the proof of Lemma 4 in Rohde and Tsybakov (2011). Let $\mathcal{W}_{1},\ldots,\mathcal{W}_{M}$ be tensors that each are an indicator of the observed positions. Then $\mathcal{X}=\sum_{j=1}^{M}\epsilon_{j}\mathcal{W}_{j}$. Since each entry is observed maximally once, we have

Taking expectation over the choice of $\mathcal{W}_{j}$ $(j=1,\ldots,M)$, we obtain

References