On the Nuclear Norm and the Singular Value Decomposition of Tensors

Introduction

Suppose that $V=V^{(1)}\otimes\cdots\otimes V^{(d)}$ is the tensor product of finite dimensional Hilbert spaces. For some applications, we would like to find a decomposition of a given tensor $T$ as a sum of pure tensors:

is small. As pointed out in , there may not always be an optimal solution for which this norm is minimal. The problem of finding a low-rank approximation is known as the PARAFAC () or CANDECOMP () model. There are many applications of this model, for example fluorescence spectroscopy, statistics, psychometrics, geophysics and magnetic resonance imaging.

2. The nuclear and spectral norms

yields the sparsest solution. A sparse relaxation of the rank of a matrix $A$ is the nuclear norm $\|A\|_{\star}=\operatorname{trace}(\sqrt{AA^{\star}})$, which is also the sum of the singular values of $A$. In this context, this relaxation technique has been successfully applied to matrix completion problems in .

The nuclear norm can be generalized to higher order tensors (see [23, Definition 3.2]). The nuclear norm $\|T\|_{\star}$ of a tensor $T$ is the smallest possible value of $\sum_{i=1}^{r}\|v_{i}\|$ over all possible decompositions (1). The nuclear norm for tensors has been used for tensor completion problems in .

The spectral norm $[T]$ of $T$ is defined as the maximum value of $|\langle T,u\rangle|$ where $u$ ranges over all pure tensors of unit length. For a matrix, the spectral norm is just the largest singular value. More generally, if ${\bf T}=(T_{1},\dots,T_{r})$ is an $r$-tuple of tensors, then we define $[{\bf T}]_{\alpha}$ as the maximum of

over all pure tensors $u$ of unit length. The following theorem is useful for obtaining lower bounds for the spectral norm:

If $T$ is a tensor, ${\bf S}=(S_{1},\dots,S_{r})$ is an $r$-tuple of tensors and $\alpha\geq 1$ then we have

The proof of Theorem 1.1 is in Section 5. If ${\bf S}=(S)$ just consists of a single tensor, then $[{\bf S}]_{\alpha}=[S]$ and we have:

Corollary 1.2 can also easily be proven directly without using Theorem 1.1. If we set $S=T$ then we obtain

3. Singular Value Decomposition

The Singular Value Decomposition (SVD) can be generalized to higher-dimensional arrays. One such generalization was given in . Given a tensor $T$, one can choose an orthonormal bases $f_{1}^{(i)},\dots,f^{(i)}_{n_{i}}$ for $V_{i}$ for all $i$ and express $T$ in these bases:

where the sum runs over all $d$-tuples $(i_{1},\dots,i_{d})$ with $i_{j}=k$. For a proper choice of the bases, the tensors $T_{1}^{(j)},\dots,T_{n_{j}}^{(j)}$ are orthogonal for all $j$ and

These numbers are called the singular values in mode $j$. The decomposition (2) is called the higher order single value decomposition (HOSVD).

In this paper, we will give a different generalization of the SVD, which we call the diagonal singular value decomposition (DSVD). A given tensor may not have a diagonal singular value decomposition (see Section 7), but if it does, then the decomposition has many nice properties.

Suppose that $t\geq 1$ is a real number. An $r$-tuple ${\bf S}=(S_{1},\dots,S_{r})$ of tensors of unit length is called $t$-orthogonal if $[{\bf S}]_{2/t}=1$.

If ${\bf v}=(v_{1},\dots,v_{r})$ is an $r$-tuple of pure tensors of unit length, then $t$-orthogonality implies orthogonality in the usual sense. Also, ${\bf v}$ is orthogonal if and only if it is $1$-orthogonal.

If $\sigma_{1}\geq\sigma_{2}\geq\cdots\geq\sigma_{r}>0$ are real, and $(v_{1},\dots,v_{r})$ is a $2$-orthogonal $r$-tuple of pure tensors of unit length, then a decomposition

is called a diagonal singular value decomposition (DSVD) of $T$, and $\sigma_{1},\dots,\sigma_{r}$ are called the singular values of $T$.

For a tensor $T$ that has a diagonal singular value decomposition, we have the following results:

The singular values of $T$ are uniquely determined by $T$ (and do not depend on the choice of the diagonal singular value decomposition).

Suppose that $T$ has a singular value decomposition with singular values $\sigma_{1}\geq\sigma_{2}\geq\cdots\geq\sigma_{r}>0$. Then we have

If the singular values of $T$ are distinct, then the diagonal singular value decomposition is unique.

If $T=\sum_{i=1}^{r}\sigma_{i}v_{i}$ is a diagonal singular value decomposition and $(v_{1},\dots,v_{r})$ is $t$-orthogonal for some $t>2$, then the diagonal singular value decomposition of $T$ is unique.

The proofs of Theorems 1.5–1.8 are in Section 6.

4. Tensors and multi-linear maps

We will apply this correspondence to matrix multiplication.

5. Matrix multiplication

From this formula it is clear that $\operatorname{rank}(M_{p,q,r})\leq pqr$. Strassen proved that $\operatorname{rank}(M_{2,2,2})\leq 7$ (see ) by giving a decomposition

and used this to show that two $n\times n$ matrices can be multiplied by using only $O(n^{\log_{2}(7)})$ arithmetic where $\log_{2}(7)\approx 2.81<3$. The usual way of multiplying two matrices takes $O(n^{3})$ arithmetic operations. More generally, define

If $\varepsilon>0$, then two $n\times n$ matrices can be multiplied using only $o(n^{\omega+\varepsilon})$ arithmetic operations (see and ). Coppersmith and Winograd proved that $\omega<2.376$ in . Only recently, this bound was improved by Stothers () to $\omega<2.3737$ and the current record is $\omega<2.3727$ by Williams ().

For most values of $p,q,r$ the rank of $M_{p,q,r}$ is unknown. It is easy to see that $\operatorname{rank}(M_{n,n,n})\geq n^{2}$. Bläser gave a better, nontrivial lower bound in . A sharper lower bound was given by Landsberg in , and using the same techniques, Massarenti and Raviolo (see ) improved this lower bound to

The decomposition (4) is a diagonal singular value decomposition. In particular, the singular values of $M_{p,q,r}$ are

The proof of the theorem is in Section 4. The following corollary follows from Theorem 1.9 and Theorem 1.6.

We have $\|M_{p,q,r}\|_{\star}=pqr$ and $[M_{p,q,r}]=1$.

Note that the sum of the lengths of the pure tensors in the decomposition (5) is $2\sqrt{2}+12>8$. This shows that minimization of the rank, and minimization of the nuclear norm do not always coincide.

6. The discrete Fourier transform and group algebras

If $G$ is a group of order $n$, $d_{1},\dots,d_{s}$ are the dimensions of the irreducible representations of $G$, then the tensor $T_{G}$ has a diagonal singular value decomposition and its singular values are

The proof of Theorem 1.11 can be found in Section 4. From Theorem 1.11 and Theorem 1.6 we get the following result.

We have $\|T_{G}\|_{\star}=\sqrt{n}\sum_{i=1}^{s}d_{i}^{5/2}$ and $[T_{G}]=\sqrt{n}$.

The following Theorem follows from Theorems 1.11 and 1.8.

The decomposition (7) is the unique diagonal singular value decomposition. In particular, the singular values of $T_{C_{n}}$ are

7. The determinant and the permanent

The determinant and permanent are multilinear functions

From these formulas it is clear that $\operatorname{rank}(\det_{n})\leq n!$ and $\operatorname{rank}(\operatorname{per}_{n})\leq n!$. The upper bound for the rank of the determinant is not sharp for $n\geq 3$ (see Section 8). The bound for the permanent is far from optimal. Another formula for the permanent was given by Glynn :

where $\delta$ runs over all $2^{n-1}$ vectors $\delta=(\delta_{1},\dots,\delta_{n})\in\{1,-1\}^{n}$ with $\delta_{1}=1$. From this formula follows that $\operatorname{rank}(\operatorname{per}_{n})\leq 2^{n-1}$ and $\|\operatorname{per}_{n}\|_{\star}\leq n^{n/2}$. Some easy lower bounds for the rank of the the permanent and determinant are given in Section 8.

We have $\|\operatorname{per}_{n}\|_{\star}=n^{n/2}$.

The formula (8) minimizes the sum of the lengths of the pure tensors, but these pure tensors are not $2$-orthogonal (or even orthogonal) for $n\geq 3$. In fact, for $d\geq 3$ the tensor $\operatorname{per}_{n}$ does not have a diagonal singular value decomposition (see Section 7).

The proofs of Theorems 1.15 and 1.14 are in Section 5.

Orthogonality of vectors

In this section we will study various measures of orthogonality of vectors in a Hilbert space $V$. It is convenient to deal with unit vectors. Suppose that ${\bf v}=(v_{1},\dots,v_{r})$ is an $r$-tuple of unit vectors.

Notice that $\lim_{\alpha\to\infty}\mu_{\alpha}({\bf v})=\mu({\bf v})$. So we may think of $\mu({\bf v})$ as $\mu_{\infty}({\bf v})$.

Suppose that ${\bf v}=(v_{1},\dots,v_{r})$ and ${\bf w}=(w_{1},\dots,w_{r})$ are $r$-tuples of unit vectors. We define the horizontal tensor product of ${\bf v}$ and ${\bf w}$ by

If ${\bf v}=(v_{1},\dots,v_{r})\in V^{r}$ and ${\bf w}=(w_{1},\dots,w_{s})\in W^{s}$ then we define

If ${\bf v}=(v_{1},\dots,v_{r})\in V^{r}$ and ${\bf w}=(w_{1},\dots,w_{s})\in W^{s}$ are tuples of unit vectors, then we have

We will need a slightly more general version of the Hölder inequality.

If $a_{1},\dots,a_{r},b_{1},\dots,b_{r}$ are nonnegative real numbers, and $\alpha,\beta,\gamma$ are positive real numbers with $1/\alpha+1/\beta=1/\gamma$, then we have

The usual Hölder inequality states that, if $1/p+1/q=1$, then we have

with equality if and only if the vectors $(a_{1}^{p},\dots,a_{r}^{p})$ and $(b_{1}^{q},\dots,b_{r}^{q})$ are dependent. Now take $p=\alpha/\gamma$ and $q=\beta/\gamma$, and replace $a_{i}$ and $b_{i}$ by $a_{i}^{\gamma}$ and $b_{i}^{\gamma}$ respectively:

Taking the $\gamma$-th root gives the desired inequality. ∎

For horizontal tensor products we have a Hölder inequality:

If $1/\alpha+1/\beta=1/\gamma$, then we have

for all $i$. Taking the maximum over all $i$ on both sides gives the desired inequality. ∎

If we take $\beta\to\infty$ we get the inequalities

If $\gamma>\alpha>0$ then and ${\bf v}=(v_{1},\dots,v_{r})$ is an $r$-tuple of unit vectors, then we have

If we take the limit $\gamma\to\infty$ we get

For an $r$-tuple ${\bf v}=(v_{1},\dots,v_{r})$ of vectors we define

For an $r$-tuple of unit vectors ${\bf v}$ we have $\mu_{\alpha}({\bf v}^{\otimes d})=\mu_{d\alpha}({\bf v})^{d}$.

Taking the maximum over all $i$ on both sides gives the desired result. ∎

Orthogonality of tensors

In this section, we study another measure for the orthogonality of pure tensors, which takes into account the tensor product structure of the vector space. It is important, when discussing pure tensors, to be clear which tensor product structure we are talking about. To be unambiguous, we make the following definition. An $d$-th order tensor space is a pair ${\bf V}=(V,(V^{(1)},\dots,V^{(d)}))$ where $V^{(1)},\dots,V^{(d)}$ are finite dimensional Hilbert spaces and

A pure tensor (with respect to this tensor space) is an element in $V$ of the form

with $v^{(i)}\in V^{(i)}$ for $i=1,2,\dots,d$. Suppose that ${\bf V}=(V,(V^{(1)},\dots,V^{(d)}))$ and ${\bf W}=(W,(W^{(1)}\dots,W^{(e)}))$ are tensor product spaces. Then their horizontal tensor product is the tensor space

If ${\bf S}=(S_{1},\dots,S_{r})\in{\bf V}^{r}$ and ${\bf T}=(T_{1},\dots,T_{r})\in{\bf W}^{r}$ then we define

For the horizontal tensor product we have a Hölder inequality.

If $1/\alpha+1/\beta=1/\gamma$, then we have

Taking the supremum over all unit pure tensors $x$ and $y$ yields the desired inequality. ∎

The inequality in the other direction follows from Lemma 3.1. ∎

If ${\bf V}=(V,(V^{(1)},\dots,V^{(d)})$ and ${\bf W}=(W,(W^{(1)},\dots,W^{(d)}))$ are tensor product spaces, then their vertical tensor product is

If $S\in{\bf V}$ and $T\in{\bf W}$ we define $S\boxtimes T$ as $S\otimes T$, viewed inside the tensor product space ${\bf V}\boxtimes{\bf W}$. If ${\bf S}\in{\bf V}^{r}$ and ${\bf T}\in{\bf W}^{s}$, then we define

The measure $_{\alpha}$ also behaves multiplicatively with respect to the vertical tensor product.

Suppose that ${\bf V}=(V,(V^{(1)},\dots,V^{(d)}))$ and ${\bf W}=(W,(W^{(1)},\dots,W^{(d)}))$ are tensor product spaces, and $S\in{\bf V}^{r}$ and $T\in{\bf W}^{s}$. Then we have

First, we will assume that $\alpha\leq 1$. For a complex vector $b=(b_{1},\dots,b_{l})$ we have

Suppose that $u$ is a pure tensor in ${\bf V}\boxtimes{\bf W}$. We can write

with $u^{(e)}\in Z^{(e)}=V^{(e)}\otimes W^{(e)}$ and $\|u^{(e)}\|=1$ for all $e$. Using the singular value decomposition, we can write

where $x_{1}^{(e)},x_{2}^{(e)},\dots$ and $y_{1}^{(e)},y_{2}^{(e)},\dots$ are (finite) sequences of orthonormal vectors for all $e$, and $\lambda_{k}^{(e)}>0$ for all $k,e$. Since $u^{(e)}$ is a unit vector, we have $\sum_{k}(\lambda_{k}^{(e)})^{2}=1$. We define $x^{(e)}=\sum_{k}\lambda_{k}^{(e)}$, $y^{(e)}=\sum_{k}\lambda_{k}^{(e)}$ for all $e$, and

Note that $x^{(e)}$ and $y^{(e)}$ are unit vectors, and $x$ and $y$ are pure tensors of unit length. For a $d$-tuple $\underline{k}=(k_{1},\dots,k_{d})$ we define

This is a singular value decomposition of $u$, if $u$ is viewed as a tensor in

Using the inequality (9) and the Cauchy-Schwarz inequality, we get

Since the pure tensor $u$ was arbitrary, we have $[{\bf S}\boxtimes{\bf T}]_{\alpha}^{\alpha}\leq[{\bf S}]_{\alpha}^{\alpha}[{\bf T}]_{\alpha}^{\alpha}$ and $[{\bf S}\boxtimes{\bf T}]_{\alpha}\leq[{\bf S}]_{\alpha}[{\bf T}]_{\alpha}$.

If $\alpha\geq 1$, choose $m$ such that $\alpha/m\leq 1$. By Corollary 3.2 we have

so we get $[{\bf S}\otimes{\bf T}]_{\alpha}\leq[{\bf S}]_{\alpha}[{\bf T}]_{\alpha}$.

Suppose that $\alpha>0$. There exists unit pure tensors $a\in{\bf V}$ and $b\in{\bf W}$ such that

So it follows that $[{\bf S}\boxtimes{\bf T}]_{\alpha}^{\alpha}\geq[{\bf S}]_{\alpha}^{\alpha}[{\bf T}]_{\alpha}^{\alpha}$. We conclude that $[{\bf S}\boxtimes{\bf T}]_{\alpha}=[{\bf S}]_{\alpha}[{\bf T}]_{\alpha}$.

The norm $_{\alpha}$ is hard to compute in practice because we have to solve a optimization problem. But $\mu_{\alpha}(-)$ is easier to compute. Fortunately, $_{\alpha}$ can be estimated in terms of $\mu$:

For an $r$-tuple ${\bf v}=(v_{1},\dots,v_{r})$ of pure tensors of unit length and $\alpha>0$ we have

Suppose that $\alpha>0$. For every $i$ we have

Taking the maximum over all $i$ gives the desired inequality. ∎

For an $r$-tuple ${\bf v}=(v_{1},\dots,v_{r})$ of pure tensors of unit length and $\alpha\geq 1$ we have

Suppose that $\alpha\geq 2$. Choose a unit pure tensor $w$ such that

Let $D$ be the $r\times r$ diagonal matrix with $D_{i,i}=|\langle v_{i},w\rangle|^{2\alpha-2}$ and define

where $v_{1},\dots,v_{r}$ are viewed as column vectors with respect to some orthonormal basis. Consider the Hermitian matrix

be an eigenvector of $B$ with eigenvalue $\lambda$. We have

for $i=1,2,\dots,r$. Choose $i$ such that $|x_{i}|$ is maximal. Then we have

If we set $\beta=\alpha/(\alpha-1)$ and $\gamma=\alpha$, then $1/\beta+1/\alpha=1$ and by Hölder’s inequality we get

So we conclude that $[{\bf v}]^{2\alpha}_{2\alpha}\leq\mu_{\alpha}({\bf v})^{\alpha}+1$.

is attained for $u=(e_{1}+e_{2})/\sqrt{2}$. So we have

t𝑡t-orthogonality

In this section we will discuss a notion of orthogonality for pure tensors that is stronger than the usual notion of orthogonality. Recall that an $r$-tuple ${\bf S}=(S_{1},\dots,S_{r})$ of unit tensors is $t$-orthogonal if $[{\bf S}]_{2/t}=1$.

Suppose that ${\bf S}=(S_{1},\dots,S_{r})$ is $t$-orthogonal $r$-tuple of unit tensors, and ${\bf T}=(T_{1},\dots,T_{r})$ is an $u$-orthogonal $r$-tuple of unit tensors. Then ${\bf S}\otimes{\bf T}$ is $(t+u)$-orthogonal.

From $[{\bf S}]_{2/t}=1$ and $[{\bf T}]_{2/e}=1$ follows that

by Hölder’s inequality. So $[{\bf S}\otimes{\bf T}]_{2/(t+u)}=1$ and ${\bf S}\otimes{\bf T}$ is $(t+u)$-orthogonal. ∎

Orthogonality is also stable under taking vertical tensor products.

If ${\bf S}=(S_{1},\dots,S_{r})$ is an $r$-tuple of unit tensors, ${\bf T}=(T_{1},\dots,T_{s})$ is an $S$-tuple of unit tensors, and ${\bf S}$ and ${\bf T}$ are both $t$-orthogonal, then ${\bf S}\boxtimes{\bf T}$ is also $t$-orthogonal.

Using horizontal and vertical tensor product, we can easily see that the tensor $M_{p,q,r}$ has a Diagonal Singular Value Decomposition.

are $2$-orthogonal. We will write $e_{i,j}$ instead of $e_{i}\boxtimes e_{j}$. Now the tuple

This follows immediately from the definition of the diagonal singular value decomposition and Proposition 4.4. ∎

Let $Z_{1},\dots,Z_{s}$ be the irreducible representations of $G$. We have an isomorphism

where $\pi_{i}$ is the projection onto $Z_{i}$. The decomposition (10) is orthogonal. The multiplication tensor

is the tensor for multiplication in $\operatorname{Hom}(Z_{i},Z_{i})$. We have

Note that ${\bf T}=(T_{1},T_{2},\dots,T_{s})$ is $3$-orthogonal. The tensor $T_{i}$ corresponds to matrix multiplication in $\operatorname{Hom}(Z_{i},Z_{i})$. We can write

Suppose that ${\bf V}=(V,(V^{(1)},\dots,V^{(d)}))$ is a tensor product space, $t\geq 1$ and ${\bf v}=(v_{1},\dots,v_{r})\in V^{r}$ is a $t$-orthogonal $r$-tuple of pure tensors of unit length. Then we have $n\leq\dim(V)^{1/t}$.

Let $x=1/\sqrt{2m}$, and let $D$ be the body defined by

Then $D\subseteq E$ and $E$ is a product of an $(2m-2)$-dimensional ball with radius $1$ and a disk of radius $x$. We have

where we use the formula $\operatorname{vol}(B_{2m})=\pi^{m}/m!$. It follows that

Suppose that $u=u^{(1)}\otimes\cdots\otimes u^{(d)}$ is a fixed unit pure tensor in $V$ and $z=z^{(1)}\otimes\cdots\otimes z^{(d)}$ is a random unit pure tensor. Let $n=\dim(V)$ and $n_{i}=\dim(V_{i})$ for all $i$. Then we have

is also $t$-orthogonal, and it has $r^{q}$ vectors in an $n^{q}$-dimensional vector space. So we have

The following lemma justifies the term $t$-orthogonality.

If $(v,w)$ is $t$-orthogonal, where $v=v^{(1)}\otimes\cdots\otimes v^{(d)}$ and $w=w^{(1)}\otimes\cdots\otimes w^{(d)}$, then we have $\langle v^{(i)},w^{(i)}\rangle=0$ for at least $t$ values of $i$.

Suppose that $u=u^{(1)}\otimes\cdots\otimes u^{(d)}$ is a unit pure tensor. Then we have

Choose $\varepsilon$ with $0<\varepsilon<\sqrt{2}$ and $u^{(i)}$ such that $|\langle v^{(i)},u^{(i)}\rangle|=1-\frac{1}{2}\varepsilon^{2}$ and $u^{(i)},v^{(i)},w^{(i)}$ are dependent. If $w^{(i)}$ and $v^{(i)}$ are orthogonal, then $|\langle w^{(i)},u^{(i)}\rangle|=\varepsilon+o(\varepsilon)$, because $|\langle v^{(i)},u^{(i)}\rangle|^{2}+|\langle w^{(i)},u^{(i)}\rangle|^{2}=1$. If $w^{(i)}$ and $v^{(i)}$ are not orthogonal, then $|\langle w^{(i)},u^{(i)}\rangle|=|\langle w^{(i)},v^{(i)}\rangle|+o(\varepsilon)$. If $s$ is the number of $i$ for which $v^{(i)}$ and $w^{(i)}$ are orthogonal, then we have

for some constant $C$. We must have $s/t\geq 1$, otherwise the inequality is not satisfied for small $\varepsilon$. ∎

Consider the following triple of pure tensors

Then every pair of vectors of ${\bf e}$ is $2$-orthogonal. However, ${\bf e}$ itself is not $2$-orthogonal, because it violates Proposition 4.5:

be a list of $n^{2}$ vectors. We claim that ${\bf v}$ is $\frac{3}{2}$-orthogonal. Suppose that

is a pure tensor with $\sum_{g\in G}|a_{g}|^{2}=\sum_{g\in G}|b_{g}|^{2}=\sum_{g\in G}|c_{g}|^{2}=1$. Using the inequality $pqr\leq\frac{1}{3}(p^{3}+q^{3}+r^{3})$ we get

This proves that ${\bf v}$ is $\frac{3}{2}$-orthogonal. For $t>\frac{3}{2}$, ${\bf v}$ cannot be $t$-orthogonal because otherwise this would violate Proposition 4.5.

Lower bounds for the nuclear norm

Suppose that $\alpha\geq 1$, $T$ is a tensor, and ${\bf S}=(S_{1},\dots,S_{r})$ is an $r$-tuple of tensors. We can write

where $\mu_{1},\dots,\mu_{s}$ are positive real numbers such that $\sum_{j=1}^{s}\mu_{j}=\|T\|_{\star}$ and $w_{1},\dots,w_{s}$ are pure unit tensors. Define

We now study the determinant tensor $\sum_{\sigma}\operatorname{sgn}(\sigma)e_{\sigma}$ and the permanent tensor $\sum_{\sigma}e_{\sigma}$.

If $a^{(1)},\cdots,a^{(n)}$ are vectors of unit length, then Hadamard’s inequality yields

Therefore, we have $[{\textstyle\det_{n}}]\leq 1$. It follows from Corollary 1.2 that

The following theorem proven in is the permanent analog of Hadamard’s inequality.

For vectors $a^{(1)},\cdots,a^{(n)}$ of unit length,we get

So we have $[{\textstyle\operatorname{per}_{n}}]\leq\frac{n!}{n^{n/2}}.$ From Corollary 1.2 follows that

We conclude that $\|\operatorname{per}_{n}\|_{\star}\geq n^{n/2}$. ∎

The Diagonal Singular Value Decomposition

For an $r$-tuple ${\bf v}=(v_{1},\dots,v_{r})$ and $k<r$ we write ${\bf v}^{[k]}$ for $(v_{1},\dots,v_{k})$. We start with the most general, main theorem.

Suppose that $V$ is a tensor product space, ${\bf v}=(v_{1},\dots,v_{r})$ and ${\bf w}=(w_{1},\dots,w_{s})$ consists of pure tensors in $V$ of unit length, $\lambda_{1}\geq\lambda_{2}\geq\cdots\geq\lambda_{s}>0$, $\sigma_{1}\geq\sigma_{2}\geq\cdots\geq\sigma_{r}>0$ and

Also, suppose that $k\leq s$, $l\leq r$ such that $0\leq\delta\leq[{\bf w}^{[k]}]_{1}$ where $\delta:=k[{\bf v}]_{1}-l[{\bf w}^{[k]}]_{1}$. Then we have

Here we use the conventions that $0=\lambda_{s+1}=\lambda_{s+2}=\cdots$ and $0=\sigma_{r+1}=\sigma_{r+2}=\cdots$.

because $\lambda_{i}\geq\lambda_{j}$ whenever $i\geq j$. Using this, we get

Let $y_{i,j}=|\langle w_{i},v_{j}\rangle|$ if $1\leq i\leq s$ and $1\leq j\leq r$. We have

where $x_{j}=\sum_{i=1}^{k}y_{i,j}\leq[{\bf w}^{[k]}]_{1}$. We also have

If we maximalize the functional $\sum_{j=1}^{r}\sigma_{j}x_{j}$ under the constraints $0\leq x_{i}\leq[{\bf w}^{[k]}]_{1}$ for $i=1,2,\dots,l$ and $x_{1}+\cdots+x_{r}\leq k[{\bf v}]_{1}$, then an optimal solution is $x_{1}=x_{2}=\cdots=x_{l}=[{\bf w}^{[k]}]_{1}$, $x_{l+1}=k[{\bf v}]_{1}-l[{\bf w}^{[k]}]_{1}=\delta$ and $x_{l+2}=\cdots=x_{r}=0$, and the optimal value is

The following result gives a lower bound for the nuclear norm:

If ${\bf w}=(w_{1},\dots,w_{s})$ is an orthogonal $r$-tuple of pure tensors of unit length, $\lambda_{1}\geq\cdots\geq\lambda_{s}>0$ and $T=\sum_{i=1}^{s}\lambda_{i}w_{i}$, then we have

We can write $T=\sum_{i=1}^{r}\sigma_{i}v_{i}$ where $v_{i}$ is a pure tensor of unit length for all $i$, $\sigma_{1}\geq\sigma_{2}\geq\cdots\geq\sigma_{r}>0$ and $\|T\|_{\star}=\sum_{i=1}^{r}\sigma_{i}$. We have

and $\mu_{1}({\bf w})=0$ because ${\bf w}$ is orthogonal. From Theorem 6.1 follows that

Suppose that ${\bf v}=(v_{1},\dots,v_{r})$ and ${\bf w}=(w_{1},\dots,w_{s})$ are $2$-orthogonal tuples of pure tensors of unit length, and

such that $\lambda_{1}\geq\cdots\geq\lambda_{s}>0$ and $\sigma_{1}\geq\cdots\geq\sigma_{r}>0$. We apply Theorem 6.1 with $[{\bf v}]_{1}=[{\bf w}^{[k]}]_{1}=1$, $l=k$ and get

for all $k$. If we switch the roles of the $v$’s and $w$’s we also get inequalities in the other directions as well. We conclude that $r=s$ and $\lambda_{i}=\mu_{i}$ for all $i$. ∎

Suppose that the diagonal singular value decomposition of $T$ is

Then we have $\|T\|_{\star}\leq\sum_{i=1}^{r}\sigma_{i}$. If we take $k=r$, and $\lambda_{i}=\sigma_{i}$ in Theorem 6.2 then we get

so we conclude that $\|T\|_{\star}=\sum_{i=1}^{r}\sigma_{i}$.

Since ${\bf v}=(v_{1},\dots,v_{r})$ is 2-orthogonal, we have

If $u$ is a pure tensor of unit length, then

Clearly $\langle T,v_{1}\rangle=\sigma_{1}$. So we conclude that $[T]=\sigma_{1}$. ∎

Suppose that $T$ has a diagonal singular value decomposition with singular values $\sigma_{1}>\dots>\sigma_{r}>0$. We can write $T=\sum_{j=1}^{r}\sigma_{j}v_{j}$. Suppose that we have another singular value decomposition $T=\sum_{i=1}^{r}\sigma_{i}w_{i}$. (Note that the singular values are determined by $T$ because of Theorem 1.5).

Let $y_{i,j}=|\langle w_{i},v_{i}\rangle|$. Then $\sum_{j=1}^{r}y_{i,j}\leq[{\bf v}]_{1}=1$ and $\sum_{i=1}^{r}y_{i,j}leq[{\bf w}]_{1}=1$. Fix $k\leq r$ and let $x_{j}=\sum_{i=1}^{k}y_{i,j}\leq 1$. From the proof of Theorem 6.1 follows that

Since $\sigma_{1},\dots,\sigma_{r}$ are distinct, we must have $x_{1}=x_{2}=\cdots=x_{k}=1$ and $x_{k+1}=\cdots=x_{r}=0$. This implies that $y_{i,j}=0$ if $i\leq k$ and $j\geq k+1$. So $y_{i,j}=0$ for $i<j$ and by symmetry, $y_{i,j}=0$ for $i>j$. This proves that $|\langle v_{i},w_{i}\rangle|=y_{i,i}=1$ for all $i$. So $w_{i}$ is equal to $v_{i}$ up to a unit scalar, say $w_{i}=\gamma_{i}v_{i}$. It follows that

and because $v_{1},\dots,v_{r}$ are linearly independent, it follows that $\gamma_{i}=1$ and $w_{i}=v_{i}$ for all $i$.

Suppose that $T$ is a tensor with 2 diagonal singular value decompositions

with $\sigma_{1}\geq\cdots\geq\sigma_{r}>0$, and that ${\bf w}=(w_{1},\dots,w_{r})$ is $t$-orthogonal with $t>2$. Let $y_{i,j}=|\langle w_{i},v_{j}\rangle|$.

From the proof of Theorem 6.1 follows that

where $\alpha=2/t<1$, because ${\bf w}$ is $t$-orthogonal. Subtracting gives

It follows that $y_{i,j}\in\{0,1\}$ for all $i,j$. The column sums of $Y=(y_{i,j})$ are $1$. So every column has exactly one $1$. So the matrix has exactly $r$ $1$’s. Since the row sums are also $1$, it follows that every row has exactly one 1 as well. So $Y$ is a permutation matrix. There exists a permutation $\phi$ of $\{1,2,\dots,r\}$ such that

where $\gamma_{i}$ is a unit for all $i$. We have

Since ${\bf w}$ is linearly independent, it follows that $\gamma_{i}\sigma_{i}=\sigma_{\phi(i)}$ for all $i$. So $\gamma_{i}=1$ and $\sigma_{i}=\sigma_{\phi(i)}$ for all $i$. This shows that

So the diagonal singular value decomposition is unique. ∎

Tensors without a diagonal singular value decomposition

Consider the permanent $\operatorname{per}_{n}$. Suppose that it has a DSVD and that its singular values are $\sigma_{1},\dots,\sigma_{r}$. Then we have

so it follows that $\sigma_{1}=\sigma_{2}=\cdots=\sigma_{r}$. So

For $n\geq 3$, $n^{n}/n!$ is not an integer (the denominator is divisible by $n-1$), so $\operatorname{per}_{n}$ cannot have a diagonal singular value decomposition.

Consider the determinant $\textstyle\det_{n}$. Suppose that $\det_{n}$ has a DSVD. A similar argument as in the previous example shows that $\det_{n}$ has a singular value $\sigma$ with multiplicity $r$, where

So there exists a $2$-orthogonal $r$-tuple of pure tensors of unit length. This implies that $r\leq n^{n/2}$ by Proposition 4.5. For $n\geq 3$ we have $n!>n^{n/2}$, so $\det_{n}$ cannot have a diagonal singular value decomposition.

Appendix: The tensor rank of the determinant and the permanent

For a subset $I=\{i_{1},i_{2},\dots,i_{r}\}\subseteq\{1,2,\dots,n\}$ with $i_{1}<\cdots<i_{r}$ define

We have the following generalized Laplace expansion

where $I$ runs over all ${n\choose r}$ subsets of $\{1,2,\dots,n\}$ with cardinality $r$.

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

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

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 $\operatorname{rank}(\det_{n})\leq n!$ is not sharp for $n\geq 3$.

So $\operatorname{rank}(\det_{3})\leq 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 $\operatorname{rank}(\det_{3})\geq 4$. If $n>3$, then we can again use the generalized Laplace expansion

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

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 and .

The author thanks Zach Teitler for useful comments and a correction.

References