CP Decomposition and Tensor Rank

From Matrix Rank to Tensor Rank

For a matrix, rank measures how many rank-one matrices are needed to build it by addition. A tensor admits the same kind of description, but each rank-one term is an outer product of vectors, one from each mode. The smallest number of such terms is the CP rank. It is a basic measure of the complexity of a tensor representation, but it does not by itself guarantee that the representation is unique.

We work over the real numbers and focus on a third-order tensor \(\mathcal{T}\in\mathbb{R}^{I\times J\times K}\). Its entries are \(\mathcal{T}_{ijk}\), where \(1\leq i\leq I\), \(1\leq j\leq J\), and \(1\leq k\leq K\). The same definitions extend to tensors with more modes.

Definition: For nonzero vectors \(a\in\mathbb{R}^I\), \(b\in\mathbb{R}^J\), and \(c\in\mathbb{R}^K\), their outer product \(a\otimes b\otimes c\) is the tensor with entries \((a\otimes b\otimes c)_{ijk}=a_i b_j c_k\). A rank-one tensor is a tensor expressible as one such outer product. A CP decomposition of \(\mathcal{T}\) is a representation \(\mathcal{T}=\sum_{r=1}^{R}\lambda_r a_r\otimes b_r\otimes c_r\), where the vectors are nonzero and the coefficients \(\lambda_r\) are nonzero. The CP rank, denoted \(\operatorname{rank}_{CP}(\mathcal{T})\), is the smallest such \(R\). The zero tensor has CP rank zero.

The name CANDECOMP/PARAFAC (CP) refers to this sum-of-outer-products representation. Each summand is a component whose variation across the three modes factors into one vector per mode. In entries, the decomposition asserts

\mathcal{T}_{ijk}=\sum_{r=1}^{R}\lambda_r (a_r)_i(b_r)_j(c_r)_k.

The coefficient \(\lambda_r\) may instead be absorbed into any one of the three vectors. Keeping it explicit is convenient, but it does not change which tensors can be represented or the minimum number of terms. A component is rank one because its entries factor into a product of three mode-specific values; the whole sum need not be rank one.

Rank Bounds from Unfoldings

A useful way to bound CP rank is to arrange a tensor's entries as a matrix. For example, the mode-1 unfolding \(\mathcal{T}_{(1)}\) is the \(I\times (JK)\) matrix whose row index is \(i\) and whose column index represents the pair \((j,k)\), in a fixed order. The particular ordering of the columns does not affect matrix rank.

For a rank-one tensor \(a\otimes b\otimes c\), the corresponding unfolding has entries \(a_i b_j c_k\). Its \(i\)th row is \(a_i\) times the vector of all products \(b_jc_k\). Thus the unfolding is a rank-one matrix. This gives a lower bound on tensor rank.

Theorem: For every third-order tensor \(\mathcal{T}\), the rank of any mode unfolding is at most \(\operatorname{rank}_{CP}(\mathcal{T})\). Also, \(\operatorname{rank}_{CP}(\mathcal{T})\leq IJK\).

Proof. Let \(\mathcal{T}\) have a CP decomposition with \(R\) terms. Each term unfolds to a rank-one matrix, so \(\mathcal{T}_{(1)}\) is a sum of \(R\) rank-one matrices. The column space of a sum of matrices is contained in the sum of their column spaces, and therefore its dimension is at most the sum of their ranks. Hence \(\operatorname{rank}(\mathcal{T}_{(1)})\leq R\). Since this holds for every decomposition, it holds with \(R=\operatorname{rank}_{CP}(\mathcal{T})\). The same argument applies to the other unfoldings.

For the upper bound, let \(e_i\), \(f_j\), and \(g_k\) be the standard coordinate vectors in the three modes. Then \(\mathcal{T}=\sum_{i=1}^{I}\sum_{j=1}^{J}\sum_{k=1}^{K}\mathcal{T}_{ijk}e_i\otimes f_j\otimes g_k\). Every nonzero summand is rank one, and there are at most \(IJK\) summands. Therefore \(\operatorname{rank}_{CP}(\mathcal{T})\leq IJK\). \(\square\)

In applications, the unfolding bound is especially useful when combined with an explicit decomposition. A decomposition with \(R\) terms proves that the CP rank is no greater than \(R\); an unfolding with matrix rank \(R\) proves that it is no less than \(R\). When these bounds meet, the exact CP rank is established.

Worked Example: A Rank-One Tensor by Direct Calculation

Let \(a=(1,2)^\mathsf{T}\), \(b=(1,-1)^\mathsf{T}\), and \(c=(2,1)^\mathsf{T}\), and set \(\mathcal{T}=a\otimes b\otimes c\). Its two frontal slices, obtained by fixing \(k\), are

\mathcal{T}_{::1}=2ab^\mathsf{T} =\begin{pmatrix}2&-2\\4&-4\end{pmatrix}, \qquad \mathcal{T}_{::2}=ab^\mathsf{T} =\begin{pmatrix}1&-1\\2&-2\end{pmatrix}.

For instance, the entry with indices \((2,1,1)\) is \(a_2b_1c_1=2\cdot1\cdot2=4\), as shown in the first slice. The displayed outer product is a one-term decomposition, so the rank is at most one. The tensor is nonzero, so it cannot have rank zero. Thus \(\operatorname{rank}_{CP}(\mathcal{T})=1\).

Worked Example: Certifying Rank Two with an Unfolding

Consider the \(2\times2\times2\) tensor whose slices are

\mathcal{T}_{::1}=\begin{pmatrix}1&0\\0&0\end{pmatrix}, \qquad \mathcal{T}_{::2}=\begin{pmatrix}0&0\\0&1\end{pmatrix}.

Writing \(e_1=(1,0)^\mathsf{T}\) and \(e_2=(0,1)^\mathsf{T}\) in each mode gives

\mathcal{T}=e_1\otimes e_1\otimes e_1 +e_2\otimes e_2\otimes e_2.

This proves \(\operatorname{rank}_{CP}(\mathcal{T})\leq2\). To obtain the matching lower bound, order the columns of the mode-1 unfolding by \((j,k)=(1,1),(2,1),(1,2),(2,2)\). Then

\mathcal{T}_{(1)} =\begin{pmatrix} 1&0&0&0\\ 0&0&0&1 \end{pmatrix}.

The two rows are linearly independent, so this matrix has rank two. The unfolding bound gives \(\operatorname{rank}_{CP}(\mathcal{T})\geq2\). Together the bounds show that the CP rank is exactly two.

Nonuniqueness: More Than Rescaling

Even when the minimum number of terms is known, a CP decomposition need not be unique. Some changes in a decomposition are unavoidable conventions: terms can be reordered, and a component can be rescaled across its factors. For example, replacing \(a_r,b_r,c_r\) with \(\alpha a_r,\beta b_r,\gamma c_r\) preserves the component if \(\alpha\beta\gamma=1\). These changes do not alter the underlying rank-one tensor.

But different decompositions can also use genuinely different rank-one tensors. The following calculation shows this for a tensor of rank two. Its two slices are both the identity matrix:

\mathcal{S}_{::1}=\mathcal{S}_{::2} =\begin{pmatrix}1&0\\0&1\end{pmatrix}.

Worked Example: Two Distinct Rank-Two Decompositions

Let \(e_1=(1,0)^\mathsf{T}\), \(e_2=(0,1)^\mathsf{T}\), and \(h=(1,1)^\mathsf{T}\). One decomposition is

\mathcal{S}=e_1\otimes e_1\otimes h +e_2\otimes e_2\otimes h.

For each of the two values of \(k\), the slice is \(e_1e_1^\mathsf{T}+e_2e_2^\mathsf{T}=I_2\), as required.

A second decomposition uses \(u_1=(1,0)^\mathsf{T}\), \(u_2=(1,1)^\mathsf{T}\), \(v_1=(1,-1)^\mathsf{T}\), and \(v_2=(0,1)^\mathsf{T}\):

\mathcal{S}=u_1\otimes v_1\otimes h +u_2\otimes v_2\otimes h.

Check each slice by adding the two outer products:

u_1v_1^\mathsf{T}+u_2v_2^\mathsf{T} =\begin{pmatrix}1&-1\\0&0\end{pmatrix} +\begin{pmatrix}0&1\\0&1\end{pmatrix} =\begin{pmatrix}1&0\\0&1\end{pmatrix}.

Since the third factor is \(h\), both slices equal this sum, so the second expression also represents \(\mathcal{S}\). The terms in the two decompositions are not merely reordered or rescaled versions of one another: for example, the first-mode vectors in the second decomposition include \((1,1)^\mathsf{T}\), which is not proportional to either first-mode vector in the first decomposition.

Each expression has two terms, giving an upper bound of two. The mode-1 unfolding, with columns ordered as \((1,1),(2,1),(1,2),(2,2)\), is \(\begin{pmatrix}1&0&1&0\\0&1&0&1\end{pmatrix}\), which has rank two. The lower bound therefore proves \(\operatorname{rank}_{CP}(\mathcal{S})=2\). Both displayed decompositions are thus minimum-term decompositions, not just alternative expressions with extra terms.

This example also explains why a decomposition should not be treated as uniquely determined just because it uses the minimum possible number of components. Establishing uniqueness requires additional conditions; the rank value alone does not provide them. For a particular calculation, the reliable checks are to verify the entries and to establish matching upper and lower bounds on the number of terms.

Common Pitfall and Practical Checks

A common mistake is to equate CP rank with the rank of one unfolding. The unfolding argument proves only that matrix rank is a lower bound on CP rank: each CP term contributes a rank-one matrix to that unfolding, but a matrix decomposition after unfolding need not correspond to rank-one factors that separate across all three tensor modes. Therefore, an unfolding rank of two alone does not prove that the CP rank is two. To certify exact rank, pair the lower bound with a valid two-term CP decomposition, as in the examples.

When checking a proposed decomposition, calculate its entries using the product \((a_r)_i(b_r)_j(c_r)_k\), or calculate its slices as sums of matrix outer products. This catches a frequent indexing error: a factor in one mode must be used consistently across all entries and slices. Keep in mind, too, that exact CP rank concerns exact equality. An approximate representation with a small residual is a separate approximation question.

Key takeaway: CP rank is the minimum number of rank-one outer products needed to represent a tensor. A CP decomposition supplies an upper bound, unfolding matrix ranks supply lower bounds, and multiple distinct decompositions can attain the same minimum.

Check Your Understanding

Use the definitions and calculations above to answer the following questions.

What does it mean for a third-order tensor to be rank one, stated in terms of its entries?
A tensor has a three-term CP decomposition and a mode-2 unfolding of matrix rank two. What lower and upper bounds on its CP rank follow immediately?
Why does a nonzero tensor with a one-term CP decomposition have CP rank exactly one?
In the two decompositions of \(\mathcal{S}\), what calculation verifies that the second expression gives the stated slices?
Why is the rank of an unfolding not, by itself, generally a proof of the tensor's CP rank?

CP Decomposition and Tensor Rank

What You'll Learn