On the Nuclear Norm and the Singular Value Decomposition of Tensors

Abstract

Finding the rank of a tensor is a problem that has many applications. Unfortunately, it is often very difficult to determine the rank of a given tensor. Inspired by the heuristics of convex relaxation, we consider the nuclear norm instead of the rank of a tensor. We determine the nuclear norm of various tensors of interest. Along the way, we also do a systematic study various measures of orthogonality in tensor product spaces and we give a new generalization of the singular value decomposition to higher-order tensors.

Appendix: The Tensor Rank of the Determinant and the Permanent

For a subset $I=\{i_1,i_2,\ldots ,i_r\}\subseteq \{1,2,\ldots ,n\}$ with $i_1<\cdots <i_r$, define

$$\begin{aligned} {\textstyle \det _r}(I)= & {} \sum {\text {sgn}}(\sigma ) e_{i_{\sigma (1)}}\otimes \cdots \otimes e_{i_{\sigma (r)}},\\ {\text {sgn}}(I)= & {} (-1)^{\textstyle i_1+\cdots +i_r-{r+1\atopwithdelims ()2}}, \end{aligned}$$

and

$$\begin{aligned} I^c=\{1,2,\ldots ,n\}\setminus I. \end{aligned}$$

We have the following generalized Laplace expansion

$$\begin{aligned} {\textstyle \det _n}=\sum _{I}{\text {sgn}}(I)\textstyle \det _r(I)\otimes \det _{n-r}(I^c), \end{aligned}$$

where $I$ runs over all ${n\atopwithdelims ()r}$ subsets of $\{1,2,\ldots ,n\}$ with cardinality $r$.

By flattening, we may view the tensor $\det _n$ as a tensor in ${\mathbb {C}}^{n^r}\otimes {\mathbb {C}}^{n^{n-r}}$. The tensors $\det _r(I)$ where $I$ is a subset of $\{1,2,\ldots ,n\}$ with $r$ elements are linearly independent. The tensors $\det _r(I^c)$ are linearly independent as well. This shows that the flattened tensor has rank at least ${n\atopwithdelims ()r}$. So, we have

$$\begin{aligned} {\text {rank}}({\textstyle \det _n})\ge {n\atopwithdelims ()r}. \end{aligned}$$

We get the best lower bound if $r=\lfloor n/2\rfloor$:

$$\begin{aligned} {\text {rank}}({\textstyle \det _n})\ge {n\atopwithdelims ()\lfloor n/2\rfloor }. \end{aligned}$$

We have a similar Laplace expansion for the permanent, so we also get

$$\begin{aligned} {\text {rank}}({\textstyle {\text {per}}_n})\ge {n\atopwithdelims ()\lfloor n/2\rfloor }. \end{aligned}$$

So the ranks of the determinant and permanent grow at least exponentially. We also have an exponential lower bound for the permanent. An exponential upper bound for the rank of the determinant seems not to be known. However, the obvious bound ${\text {rank}}(\det _n)\le n!$ is not sharp for $n\ge 3$.

For $n=3$, we have

$$\begin{aligned} {\textstyle \det _3}= & {} {\textstyle \frac{1}{2}}\Big ((e_3+e_2)\otimes (e_1-e_2)\otimes (e_1+e_2)+(e_1+e_2)\otimes (e_2-e_3)\otimes (e_2+e_3)\\&+ 2e_2\otimes (e_3-e_1)\otimes (e_3+e_1)\\&+(e_3-e_2)\otimes (e_2+e_1)\otimes (e_2-e_1)+(e_1-e_2)\otimes (e_3+e_2)\otimes (e_3-e_2)\Big ). \end{aligned}$$

So ${\text {rank}}(\det _3)\le 5$. Zach Teitler pointed out that this implies that the Waring rank of a $3\times 3$ matrix is at most 20. He also pointed out that one can show that ${\text {rank}}(\det _3)\ge 4$. If $n>3$, then we can again use the generalized Laplace expansion

$$\begin{aligned} {\textstyle \det _n}=\sum _{I}{\text {sgn}}(I)\textstyle \det _3(I)\otimes \det _{n-3}(I^c), \end{aligned}$$

where $I$ runs over all subsets of $\{1,2,\ldots ,n\}$ with three elements. This proves that

$$\begin{aligned} {\text {rank}}({\textstyle \det _n})\le {n\atopwithdelims ()3}{\text {rank}}({\textstyle \det _{n-3}}){\text {rank}}({\textstyle \det _3})\le \frac{5\cdot n!}{6\cdot (n-3)!} \end{aligned}$$

We can rewrite this as

$$\begin{aligned} \frac{{\text {rank}}(\det _n)}{n!}\le \frac{5}{6}\cdot \frac{{\text {rank}}(\det _{n-3})}{(n-3)!}. \end{aligned}$$

By induction, we get

$$\begin{aligned} {\text {rank}}({\textstyle \det _n})\le \Big (\frac{5}{6}\Big )^{\textstyle \lfloor \frac{n}{3}\rfloor } \cdot n!. \end{aligned}$$

Remark 8.1

Homogeneous polynomials can be thought of as symmetric tensors. For symmetric tensors, there is also a notion of rank, the so-called symmetric rank. The symmetric rank is different from, but closely related to the tensor rank. The determinant and permanent can be thought of as homogeneous polynomials. Lower bounds for the symmetric tensor rank of the determinant and permanent can be found in [23] and [31].