# Computing dual of the spectral norm of tensor of order 3

It is shown in http://www.stat.uchicago.edu/~lekheng/work/jacm.pdf that computing the spectral norm (see Definition 6.6) of a $3^{rd}$ order tensor $T \in \mathbb{R}^{d_1 \times d_2 \times d_3}$ is NP-hard (Theorem 1.1 in fact shows it is np-hard to approximate it to with a certain factor). Does this statement imply (trivially ?) any hardness result about computing the dual of the spectral norm ? The dual in this case is defined as:

$$\max_{ Y \in\mathbb{R}^{d_1 \times d_2 \times d_3}, \|Y\| \leq 1 } \langle T,Y \rangle,$$ where $\langle \cdot, \cdot \rangle$ is the (tensor) inner product and $\| \cdot \|$ is the spectral norm.

(Note that in the matrix case, dual of the spectral norm is just the sum of singular values of the matrix; also called nuclear norm of the matrix)

• If the dual norm is $\|\cdot \|_*$, then $\|X\| = \max_{Y: \|Y\|_* \leq 1} \langle X, Y\rangle$. If $\|\cdot\|_*$ could be computed efficiently (or in fact if there was a FPTAS for it), then couldn't we use the shallow cut ellipsoid method with the algorithm for $\|\cdot \|_*$ as a membership oracle to approximate $\|\cdot\|$ arbitrarily well? Commented May 9, 2014 at 3:54
• Interesting point Sasho- let me think more about it. Commented May 9, 2014 at 15:56