Tucker Decomposition and Multilinear Rank

Why Tucker Structure Uses Three Ranks

A matrix has one row space and one column space, and its rank describes both dimensions of its essential structure. A three-way tensor has three modes, each with its own unfolding and associated column space. Tucker decomposition represents these three mode-wise subspaces separately, while a smaller tensor, the core, records how their coordinates interact.

This separation is useful because the tensor’s structure is not summarized by one number. Its three multilinear-rank components say how many directions are needed in each mode. The core dimensions record those counts when the representation is minimal; the factor matrices map those coordinates into the original spaces.

Definition: Let \(X\) be a real three-way tensor of dimensions \(I_1\times I_2\times I_3\). A Tucker representation of \(X\) consists of a core tensor \(G\) of dimensions \(R_1\times R_2\times R_3\) and factor matrices \(U^{(n)}\) of dimensions \(I_n\times R_n\), for \(n=1,2,3\), such that

X=G\times_1 U^{(1)}\times_2 U^{(2)}\times_3 U^{(3)}.

Here \(\times_n\) denotes the mode-\(n\) product. In entries, this means

x_{i_1i_2i_3} =\sum_{r_1=1}^{R_1}\sum_{r_2=1}^{R_2}\sum_{r_3=1}^{R_3} g_{r_1r_2r_3}\,u^{(1)}_{i_1r_1}u^{(2)}_{i_2r_2}u^{(3)}_{i_3r_3}.

The columns of \(U^{(n)}\) describe directions in mode \(n\). The core entries specify how combinations of those directions across the three modes contribute to \(X\). The factors need not be orthonormal, although orthonormal factors are often convenient.

Multilinear Rank and the Mode-Wise Subspaces

For \(n=1,2,3\), the mode-\(n\) unfolding \(X_{(n)}\) is the matrix formed by arranging the mode-\(n\) index along its rows and putting the other two indices along its columns. The order used to combine those other indices does not affect the matrix rank. Define the multilinear rank by the ranks of these three matrices.

Definition: The multilinear rank of \(X\) is the tuple

\operatorname{rank}_{\mathrm{ml}}(X) =\bigl(r_1,r_2,r_3\bigr), \qquad r_n=\operatorname{rank}(X_{(n)}).

The mode-\(n\) subspace of \(X\) is the column space \(\operatorname{col}(X_{(n)})\), a subspace of \(\mathbb{R}^{I_n}\) with dimension \(r_n\).

A Tucker representation with core dimensions \(R_1\times R_2\times R_3\) implies \(r_n\leq R_n\) for each mode: the mode-\(n\) unfolding factors through the \(R_n\)-column matrix \(U^{(n)}\). If the dimensions are exactly the multilinear rank, the factor columns can be chosen as bases for the three mode-wise subspaces. The core then describes \(X\) using coordinates in those bases.

Worked Example: Finding the Three Ranks from Slices

Let \(X\) be a \(3\times2\times2\) tensor whose two frontal slices are identical:

X(:,:,1)=X(:,:,2)= \begin{pmatrix} 1&0\\ 0&2\\ 0&0 \end{pmatrix} =A.

For mode 1, each row of \(X_{(1)}\) collects the entries with a fixed first index. The first two rows are nonzero and independent: one contains the entries equal to \(1\), and the other contains the entries equal to \(2\). The third row is zero. Thus \(r_1=2\).

For mode 2, the rows associated with the two values of the second index are also nonzero and independent: the first has nonzero entries in the first row of each slice, and the second has nonzero entries in the second row of each slice. Hence \(r_2=2\). For mode 3, the two rows of \(X_{(3)}\) are the flattened slices. They are identical and nonzero, so \(r_3=1\). Therefore the multilinear rank is \((2,2,1)\).

A corresponding Tucker representation uses \(U^{(1)}\) with columns \(e_1,e_2\) in \(\mathbb{R}^3\), \(U^{(2)}=I_2\), and \(U^{(3)}=(1,1)^\mathsf{T}/\sqrt{2}\). Take a \(2\times2\times1\) core with its only frontal slice equal to \(\sqrt{2}A_{1:2,:}\):

G(:,:,1)= \begin{pmatrix} \sqrt{2}&0\\ 0&2\sqrt{2} \end{pmatrix}.

For either third-mode index, the mode-3 factor contributes \(1/\sqrt{2}\). Multiplying the core slice by that value gives \(\operatorname{diag}(1,2)\), which \(U^{(1)}\) embeds into the first two rows of the original \(3\times2\) slice. The third row is zero, and both slices are \(A\), as required. The core dimensions match the multilinear rank.

Why the Unfolding Ranks Give the Minimal Core

The relationship between the ranks and core dimensions is exact: no Tucker representation can use fewer than \(r_n\) coordinates in mode \(n\), and a representation with dimensions \((r_1,r_2,r_3)\) always exists. This result makes multilinear rank intrinsic to the tensor, rather than a choice of a particular decomposition.

Theorem: For a real three-way tensor \(X\), the smallest possible Tucker core dimensions, mode by mode, are \((r_1,r_2,r_3)\), where \(r_n=\operatorname{rank}(X_{(n)})\). If \(U^{(n)}\) has orthonormal columns spanning \(\operatorname{col}(X_{(n)})\), then there is a core of dimensions \(r_1\times r_2\times r_3\) giving an exact Tucker representation of \(X\).

Proof. First consider any Tucker representation with dimensions \(R_1\times R_2\times R_3\). Its mode-\(n\) unfolding has \(U^{(n)}\) as a left factor; the remaining factor collects the core and the other two factor matrices. Therefore the column space of \(X_{(n)}\) is contained in the column space of \(U^{(n)}\), and

r_n=\operatorname{rank}(X_{(n)}) \leq \operatorname{rank}(U^{(n)}) \leq R_n.

This proves the lower bound on every core dimension. For existence, choose an orthonormal basis matrix \(U^{(n)}\) for \(\operatorname{col}(X_{(n)})\), and let \(P_n=U^{(n)}(U^{(n)})^\mathsf{T}\) be the orthogonal projection onto that subspace. Because every column of \(X_{(n)}\) lies in this space, \(P_nX_{(n)}=X_{(n)}\), equivalently \(X\times_nP_n=X\).

Mode products on different modes commute. Applying the three projections in sequence therefore still gives \(X\). Define

G=X\times_1(U^{(1)})^\mathsf{T} \times_2(U^{(2)})^\mathsf{T} \times_3(U^{(3)})^\mathsf{T}.

This core has dimensions \(r_1\times r_2\times r_3\). Multiplying it back by the three factor matrices gives

G\times_1U^{(1)}\times_2U^{(2)}\times_3U^{(3)} =X\times_1P_1\times_2P_2\times_3P_3 =X.

So a representation with dimensions \((r_1,r_2,r_3)\) exists, and the lower bound shows those dimensions are minimal. \(\square\)

Reading Exact Ranks from a Tucker Core

A core’s displayed dimensions alone do not guarantee that the representation is minimal. Some core directions may be redundant. There is a useful exact criterion when the factor matrices have full column rank: the rank of each core unfolding then equals the corresponding rank of the represented tensor.

Result: Suppose \(X=G\times_1U^{(1)}\times_2U^{(2)}\times_3U^{(3)}\), and each \(U^{(n)}\) has full column rank. Then

\operatorname{rank}(X_{(n)})=\operatorname{rank}(G_{(n)}), \qquad n=1,2,3.

Thus the Tucker dimensions are minimal exactly when \(\operatorname{rank}(G_{(n)})=R_n\) for all three modes.

Proof. The unfolding identity for a mode product gives

X_{(n)}=U^{(n)}G_{(n)}B^\mathsf{T},

where \(B\) is the Kronecker product, in the order specified by the unfolding convention, of the other two factor matrices. Since both of those matrices have full column rank, their Kronecker product \(B\) has full column rank as well. Consequently \(U^{(n)}\) has a left inverse \(L\), and \(B^\mathsf{T}\) has a right inverse \(C\). Multiplying the displayed identity by these inverses gives \(G_{(n)}=LX_{(n)}C\), so \(\operatorname{rank}(G_{(n)})\leq\operatorname{rank}(X_{(n)})\). Conversely, \(X_{(n)}=U^{(n)}G_{(n)}B^\mathsf{T}\) implies \(\operatorname{rank}(X_{(n)})\leq\operatorname{rank}(G_{(n)})\). The ranks are equal. \(\square\)

Worked Example: A Core with a Redundant Dimension

Let \(X\) have dimensions \(3\times2\times1\), with its only frontal slice

X(:,:,1)= \begin{pmatrix} 1&0\\ 0&1\\ 0&0 \end{pmatrix}.

The mode-1 unfolding is this \(3\times2\) matrix, which has rank 2. The mode-2 unfolding has two nonzero independent rows, so its rank is also 2. The mode-3 unfolding has one nonzero row, so its rank is 1. The multilinear rank is \((2,2,1)\).

The tensor itself can be used as a Tucker core with factor matrices equal to identity matrices of sizes \(3\times3\), \(2\times2\), and \(1\times1\). This representation has core dimensions \(3\times2\times1\), which are larger than necessary in mode 1. The third row of its only core slice is zero, so that core unfolding has rank 2 rather than 3. Removing that zero direction gives a \(2\times2\times1\) core and the minimal dimensions \((2,2,1)\).

Subspaces Are Intrinsic; Core Coordinates Are Not

The mode-wise subspaces are determined by \(X\), but bases for those subspaces are not unique. A change of basis in a factor matrix can be compensated by the inverse change in the corresponding core mode. Thus different factor matrices and different core entries can encode the same tensor. The core is a coordinate description, not an invariant table of values.

Worked Example: Changing a Factor Basis

Consider a \(2\times2\times1\) tensor with the single slice

X(:,:,1)= \begin{pmatrix} 1&0\\ 0&2 \end{pmatrix}.

One representation takes \(U^{(1)}=I_2\), \(U^{(2)}=I_2\), \(U^{(3)}=(1)\), and \(G(:,:,1)=\operatorname{diag}(1,2)\). Now let

Q=\frac{1}{\sqrt{2}} \begin{pmatrix} 1&-1\\ 1&1 \end{pmatrix}.

Replace \(U^{(1)}\) by \(U^{(1)}Q=Q\), and replace the core slice by \(Q^\mathsf{T}G(:,:,1)\):

Q^\mathsf{T} \begin{pmatrix} 1&0\\ 0&2 \end{pmatrix} = \frac{1}{\sqrt{2}} \begin{pmatrix} 1&2\\ -1&2 \end{pmatrix}.

Reconstruction multiplies the new factor by the new core, giving \(Q(Q^\mathsf{T}G(:,:,1))=G(:,:,1)\), since \(QQ^\mathsf{T}=I_2\). The tensor is unchanged, while both the factor coordinates and core entries differ. The represented mode-1 subspace is still all of \(\mathbb{R}^2\).

Common Pitfall: Treating Core Shape as Tensor Rank

A common mistake is to report the tuple of core dimensions as the tensor’s multilinear rank without checking whether the representation is minimal. The redundant-core example shows why this fails: a \(3\times2\times1\) core can represent a tensor with multilinear rank \((2,2,1)\). The correction is to compute the ranks of the three unfoldings, or, when the factors are full column rank, the ranks of the three core unfoldings.

Another distinction is that multilinear rank is a tuple of matrix ranks, not the CP rank. The tuple reports the dimension of each mode-wise subspace separately. It does not, by itself, describe a unique core, a unique set of factors, or a unique decomposition.

Key takeaway: For a three-way tensor, the ranks of its three unfoldings determine its minimal Tucker core dimensions. The factor matrices span the corresponding mode-wise subspaces, while the core records the tensor in coordinates within those subspaces.

Check Your Understanding

Use the definitions and results above to answer these questions.

What are the three components of the multilinear rank, and which matrix rank defines each component?
Why must the mode-\(n\) dimension of any Tucker core be at least \(\operatorname{rank}(X_{(n)})\)?
If all three factor matrices have full column rank, how can the ranks of the core unfoldings be used to check whether the Tucker dimensions are minimal?
A Tucker representation has core dimensions \(4\times3\times2\), but its mode-1 core unfolding has rank 3. What does this tell you about its mode-1 dimension?
Why can two different sets of factor matrices and core entries represent the same tensor?