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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.