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:

\begin{equation} \max_{ Y \in\mathbb{R}^{d_1 \times d_2 \times d_3}, \|Y\| \leq 1 } \langle T,Y \rangle, \end{equation} 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)

  • 1
    $\begingroup$ 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? $\endgroup$ Commented May 9, 2014 at 3:54
  • $\begingroup$ Interesting point Sasho- let me think more about it. $\endgroup$
    – Kcafe
    Commented May 9, 2014 at 15:56


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.