Multilinear operators for higher-order decompositions.

Tamara G. Kolda2006 · DOI

Abstract: We propose two new multilinear operators for expressing the matrix compositions that are needed in the Tucker and PARAFAC (CANDECOMP) decompositions. The first operator, which we call the Tucker operator, is shorthand for performing an n-mode matrix multiplication for every mode of a given tensor and can be employed to concisely express the Tucker decomposition. The second operator, which we call the Kruskal operator, is shorthand for the sum of the outer-products of the columns of N matrices and allows a divorce from a matricized representation and a very concise expression of the PARAFAC decomposition. We explore the properties of the Tucker and Kruskal operators independently of the related decompositions. Additionally, we provide a review of the matrix and tensor operations that are frequently used in the context of tensor decompositions.

Introduction: The Notation Problem

In fields ranging from chemometrics to signal processing, researchers use tensors (multi-way arrays) to represent multidimensional data. To analyze this data, they rely on decompositions like Tucker and PARAFAC—the higher-order extensions of the Singular Value Decomposition (SVD).

Historically, the notation for these decompositions has been cumbersome. Most authors either rely on massive element-wise summations or "matricize" the tensor—flattening it into a giant matrix to apply standard linear algebra. This matricization approach is often non-intuitive and obscures the multilinear properties that make tensors unique. This paper introduces two new mathematical shorthands—the Tucker operator and the Kruskal operator—to simplify this notation. By treating tensors as first-class mathematical citizens, these operators allow for a cleaner expression of complex operations without the need for messy unfoldings.

Defining Multilinear Operators

The paper defines two primary multilinear operators to standardize tensor algebra:

  1. The Tucker Operator: Denoted as $\llbracket \boldsymbol{\mathcal{Y}} ; \mathbf{A}^{(1)}, \mathbf{A}^{(2)}, \dots, \mathbf{A}^{(N)} \rrbracket$, this represents a core tensor $\boldsymbol{\mathcal{Y}}$ multiplied by a different matrix along every one of its "modes" (dimensions). It provides a compact way to express the Tucker decomposition.
  2. The Kruskal Operator: Denoted as $\llbracket \mathbf{A}^{(1)}, \mathbf{A}^{(2)}, \dots, \mathbf{A}^{(N)} \rrbracket$, this is a special case of the Tucker operator where the core tensor is restricted to be an identity tensor. This elegantly expresses the PARAFAC decomposition as a sum of outer products.

Visualizing Tensor Structure

To understand these operators, one must first understand the internal structure of a tensor. A tensor can be viewed as a collection of "fibers," which are the higher-order analogues of matrix rows and columns. For a 3rd-order tensor, these are referred to as columns, rows, and tubes.

Figure 5: Visualization of tensor fibers (columns, rows, and tubes) which define the different modes of a multi-way array.

By defining operators that act on these modes directly, we can derive properties, calculate norms, and perform optimization without ever having to "unfold" the tensor into a matrix. This keeps the multilinear structure front and center throughout the mathematical derivation.

The Identity Connection

One of the most elegant insights provided by this new notation is the explicit relationship between the two major decomposition types. The PARAFAC decomposition is revealed to be a specific instance of the Tucker decomposition where the "core" is an identity tensor—a tensor with ones on the superdiagonal and zeros elsewhere.

Figure 6: An identity tensor J, which serves as the core for the Kruskal operator representation of PARAFAC decompositions.

The Kruskal operator makes this relationship visually obvious, simplifying the conceptual leap between the two models. Furthermore, by defining these operators formally, the author provides a roadmap for calculating gradients. This is essential for fitting these models using gradient descent or other modern optimization techniques, as it allows researchers to obtain "derivatives for free" through standardized algebraic rules.

Key Results and Impact

While "just notation" might sound trivial, this standardized language allows for a better conceptual understanding and easier implementation of complex algorithms. Key contributions include:

  • Formal Definitions: The paper provides the first formal definitions for these specific bracketed notations, which have since become widely adopted in the tensor community.
  • Property "Cheat Sheet": It compiles a comprehensive list of propositions relating these new operators to standard operations like the Kronecker, Khatri-Rao, and Hadamard products.
  • Algorithm Refinement: The paper presents cleaned-up versions of the Higher-Order Orthogonal Iteration (HOOI) and Alternating Least Squares (ALS) algorithms, making them significantly easier to read and implement in software.

Although the paper focuses on notation and basic properties rather than new decomposition types or rank-selection heuristics, it establishes the foundational language necessary for developing more complex models involving constraints like non-negativity or sparsity.

Summary updated

Abstract

We propose two new multilinear operators for expressing the matrix compositions that are needed in the Tucker and PARAFAC (CANDECOMP) decompositions. The first operator, which we call the Tucker operator, is shorthand for performing an n-mode matrix multiplication for every mode of a given tensor and can be employed to concisely express the Tucker decomposition. The second operator, which we call the Kruskal operator, is shorthand for the sum of the outer-products of the columns of N matrices and allows a divorce from a matricized representation and a very concise expression of the PARAFAC decomposition. We explore the properties of the Tucker and Kruskal operators independently of the related decompositions. Additionally, we provide a review of the matrix and tensor operations that are frequently used in the context of tensor decompositions.
BibTeX
@misc{kolda2006multilinear,
  author = {Tamara G. Kolda},
  title = {{Multilinear operators for higher-order decompositions.}},
  year = {2006},
  doi = {10.2172/923081},
}
Figure