<p>It is shown in <a href="http://www.stat.uchicago.edu/~lekheng/work/jacm.pdf" rel="nofollow">http://www.stat.uchicago.edu/~lekheng/work/jacm.pdf</a> 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:</p>

<p>\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.</p>

<p>(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)</p>

CC BY-SA 3.0
2014-05-09T03:54:48.023Z
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?
Sasho Nikolov
CC BY-SA 3.0
2014-05-09T15:56:02.140Z
Interesting point Sasho- let me think more about it.
Kcafe
<computability><matrices><tensor-rank>
Computing dual of the spectral norm of tensor of order 3
Kcafe
# Computing dual of the spectral norm of tensor of order 3

(Asked by: username_0 on 2014-05-09)

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)

**Tags:** computability, matrices, tensor-rank
> **Comments:**
> **username_1**: 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?  
> **username_0**: Interesting point Sasho- let me think more about it.  

---

## 0 answers

