The singular value decomposition does more than give a convenient coordinate system for a matrix. Truncating it gives a best low-rank approximation: a minimizer really exists. It is tempting to expect a tensor version of this story, perhaps with a more complicated algorithm.
But for tensors there is an obstruction before algorithms even enter the picture. The best approximation may not exist. Already for a \(2\times2\times2\) array, a sequence of tensors with two rank-one terms can approach a tensor that needs three. The approximation error tends to zero while the individual components blow up.
This beautiful example is part of the systematic analysis of de Silva and Lim [1]. We will prove it using only two matrix slices and a determinant.
What is the rank of a tensor?
An order-\(d\) tensor is an array \(T\in\mathbb R^{n_1\times\cdots\times n_d}\). The outer product of \(d\) vectors is the array
\[ (u^{(1)}\otimes\cdots\otimes u^{(d)})_{i_1,\ldots,i_d} =u^{(1)}_{i_1}\cdots u^{(d)}_{i_d}. \]When nonzero, such a tensor has rank one. For \(d=2\), this is just the matrix \(uv^\top\). The CP rank, for canonical polyadic rank, counts the smallest number of such terms:
\[ \operatorname{rank}_{\rm CP}(T) =\min\left\{r:T=\sum_{\ell=1}^r u_\ell^{(1)}\otimes\cdots\otimes u_\ell^{(d)}\right\}. \]Set the rank of zero to zero. This agrees with matrix rank at order two. CP decompositions are also called CANDECOMP or PARAFAC; see Kolda and Bader [2].
The set relevant for best approximation is the set of rank at most \(r\),
\[ \mathcal R_r=\{T:\operatorname{rank}_{\rm CP}(T)\le r\},\qquad \inf_{S\in\mathcal R_r}\lVert T-S\rVert_F, \]where \(\lVert T\rVert_F^2=\sum_{i_1,\ldots,i_d}|T_{i_1,\ldots,i_d}|^2\). In a finite-dimensional space, a nearest point exists in every nonempty closed set: restrict a minimizing sequence to a bounded ball and extract a convergent subsequence. Thus closedness is the first question to ask.
A derivative of rank-one tensors
Let \(e_1,e_2\) be the standard basis of \(\mathbb R^2\), and define
\[ W=e_2\otimes e_1\otimes e_1 +e_1\otimes e_2\otimes e_1 +e_1\otimes e_1\otimes e_2. \]Its displayed expression has three terms. A two-term approximation is easy: for \(\varepsilon\ne0\), take
\[ T_\varepsilon= \frac{(e_1+\varepsilon e_2)^{\otimes3}-e_1^{\otimes3}}{\varepsilon}. \]Each numerator term is decomposable, so \(\operatorname{rank}_{\rm CP}(T_\varepsilon)\le2\). Expanding the product gives
\[ \begin{aligned} T_\varepsilon-W &=\varepsilon(e_2\otimes e_2\otimes e_1 +e_2\otimes e_1\otimes e_2+e_1\otimes e_2\otimes e_2)\\ &\quad+\varepsilon^2e_2^{\otimes3}, \end{aligned} \] \[ \lVert T_\varepsilon-W\rVert_F =\sqrt{3\varepsilon^2+\varepsilon^4}\longrightarrow0. \]It remains to prove that the limit cannot itself have two terms.
Theorem 1 (rank three, border rank two). The tensor \(W\) has CP rank three, but lies in the closure of \(\mathcal R_2\). Consequently,
\[ \inf_{S\in\mathcal R_2}\lVert W-S\rVert_F=0, \qquad\text{and the infimum is not attained.} \]Proof: a two-dimensional slice space with only one rank-one direction
Fixing the third index of \(W\) gives the matrix slices
\[ A=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad B=\begin{pmatrix}1&0\\0&0\end{pmatrix}. \]They are linearly independent. If \(W=u_1\otimes v_1\otimes w_1+u_2\otimes v_2\otimes w_2\), both slices would lie in the span of the rank-one matrices \(u_1v_1^\top,u_2v_2^\top\). Independence of the slices forces these two matrices to be independent as well, and hence their span must be exactly \(\operatorname{span}\{A,B\}\).
Yet every matrix in this slice space has the form
\[ aA+bB=\begin{pmatrix}b&a\\a&0\end{pmatrix}, \qquad \det(aA+bB)=-a^2. \]A nonzero \(2\times2\) matrix has rank one precisely when its determinant vanishes. Here this requires \(a=0\): the only rank-one direction is the line through \(B\). The space cannot contain two independent rank-one matrices. This contradiction rules out a two-term decomposition. The three-term expression proves rank exactly three. The sequence above proves the approximation claim. \(\square\)
The border rank of a tensor is the smallest \(r\) such that it belongs to the closure of \(\mathcal R_r\). Thus border rank counts how many terms are sufficient with arbitrarily small error, whereas CP rank counts how many are needed exactly. For \(W\), these answers differ.
The cancellation is not a numerical accident
Consider the rank-one curve \(\gamma(t)=(e_1+te_2)^{\otimes3}\). Our tensor is \(W=\gamma'(0)\), and \(T_\varepsilon\) is its secant slope. A tangent direction to the rank-one cone can require three terms even though every secant slope uses two [3].
The norms of the two components in \(T_\varepsilon\) are
\[ \frac{(1+\varepsilon^2)^{3/2}}{|\varepsilon|} \quad\text{and}\quad\frac1{|\varepsilon|}. \]They diverge, but their difference stays bounded. More generally, any sequence of two-term decompositions converging to \(W\) must have unbounded component norms along a subsequence. Otherwise normalize each component’s factors, absorb their norms into bounded scalar coefficients, and extract convergent subsequences. The limit would be a two-term decomposition of \(W\), which is impossible. This is a representational degeneracy, not a failure of a particular optimizer.
What remains closed?
Proposition 1. The set \(\mathcal R_1\) is closed for tensors of any order. For matrices, every set \(\mathcal R_r\) is closed.
Proof: compact unit factors, or vanishing minors
Write a convergent rank-at-most-one sequence as \(S_k=\lambda_k u_{1,k}\otimes\cdots\otimes u_{d,k}\), with unit factors. Zero terms cause no difficulty. Because \(\lVert S_k\rVert_F=|\lambda_k|\), the coefficients are bounded. Compactness of the unit spheres gives a subsequence on which all factors and the coefficient converge; its limit is again rank at most one.
For a matrix, rank at most \(r\) is equivalent to all \((r+1)\times(r+1)\) minors vanishing. These polynomial equalities define a closed set. This is the existence property behind the best-approximation theorem of Eckart and Young [4]. \(\square\)
Do not confuse rank at most one with rank exactly one: the latter is not closed even for matrices, since a nonzero rank-one matrix can tend to zero. Our example is more striking: the limit’s rank jumps up.
The counterexample extends to larger dimensions by padding with zeros, and to higher orders by tensoring with fixed nonzero vectors. Both preserve its rank: coordinate projection or contraction back to the original tensor gives the reverse inequality. More generally, de Silva and Lim prove that, for real order-\(d\ge3\) tensors with all \(n_i\ge2\), \(\mathcal R_r\) is nonclosed whenever \(2\le r\le\min_i n_i\) [1, Theorem 4.10]. No claim is made for every larger rank; eventually the rank bound includes the whole space.
Finally, this obstruction is specific to CP rank. A Tucker or multilinear rank bound restricts the matrix rank of each unfolding and hence defines a closed set [2]. Before designing a tensor analogue of the SVD, it matters which notion of rank we want to preserve.
Bibliography
- Vin de Silva and Lek-Heng Lim. Tensor rank and the ill-posedness of the best low-rank approximation problem. SIAM Journal on Matrix Analysis and Applications 30(3), 1084–1127, 2008. Paper.
- Tamara G. Kolda and Brett W. Bader. Tensor Decompositions and Applications. SIAM Review 51(3), 455–500, 2009. Paper · Author page.
- Lek-Heng Lim. Tensors in computations. Acta Numerica 30, 555–764, 2021. Author PDF.
- Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psychometrika 1, 211–218, 1936. Paper.