5.8.2 Tensor Decomposable Factorization Pattern

Tensor Decomposable Factorization Pattern is a method in algebra that breaks down complex tensors into simpler components through factorization techniques.

Tensor Decomposable Factorization Pattern is the specific entrywise multiplicative structure that a decomposable tensor's coordinate array exhibits — every coordinate equal to a product of one number contributed independently by each factor — and the recurring family of computational and notational patterns (outer products, Kronecker products, rank-one updates) through which this structure is expressed across different areas of linear and multilinear algebra.

The Entrywise Pattern

Let t = v1 ⊗ v2 ⊗ ⋯ ⊗ vn be a decomposable tensor in V1 ⊗ ⋯ ⊗ Vn, with each Vi finite-dimensional and equipped with a basis so that vi has coordinates (vi)1, …, (vi)di. The coordinates of t follow the pattern

t_{k_{1} \dots k_{n}} = {(v_{1})}_{k_{1}} {(v_{2})}_{k_{2}} \dots {(v_{n})}_{k_{n}}

for every choice of indices k1, …, kn. This is the defining factorization pattern: the full n-index array separates completely into a product of n one-index arrays, one per factor, with no coupling between the indices beyond this multiplicative combination.

The Outer Product as the Two-Factor Instance

The most familiar realization of the factorization pattern is the matrix outer product, from which the general pattern takes its name and its intuition.

Outer Product Notation

For vectors a and b, the outer product a bᵀ produces a matrix M with entries

M_{i j} = a_{i} b_{j}

exactly matching the two-factor case of the general factorization pattern. Every row of an outer-product matrix is a scalar multiple of bᵀ, and every column is a scalar multiple of a, a visible symptom of the pattern that generalizes, in a less immediately visible form, to higher-order decomposable tensors.

Kronecker Product Relation

Stacking the coordinates of a decomposable tensor into a single long vector (vectorization) turns the factorization pattern into the Kronecker product of the individual factor vectors, v1 ⊗ v2 ⊗ ⋯ ⊗ vn corresponding under vectorization to the Kronecker product v1 ⊗_K v2 ⊗_K ⋯ ⊗_K vn, a standard computational device in numerical linear algebra for representing decomposable structure using ordinary matrix and vector operations.

Pattern Recognition Through Flattenings

Because the factorization pattern is entrywise multiplicative, it leaves a specific, testable trace in every matrix obtained by flattening (matricizing) the tensor along a subset of its indices.

Rank-One Flattenings

Any flattening of a decomposable tensor — regrouping its indices into two blocks and reading off the result as a matrix — produces a matrix that itself follows the outer-product pattern, hence has rank exactly one (assuming the corresponding factor is nonzero). This is the computational signature used to recognize decomposable tensors and to extract their factors: examine any flattening, confirm rank one, and read the row and column spaces off as candidate factors.

Pattern Breakdown for Non-Decomposable Tensors

A tensor formed as a genuine sum of two or more decomposable terms generally loses the pure entrywise multiplicative pattern in every one of its flattenings simultaneously, which is why checking rank-one status of the flattenings serves as a reliable diagnostic for whether the factorization pattern is present at all.

Pattern in Rank Decomposition Algorithms

Because a general tensor decomposes as a finite sum of terms each following the factorization pattern, algorithms that fit such decompositions structure their internal computations directly around the pattern.

Canonical Polyadic Structure

A rank-r decomposition writes a tensor as a sum of r decomposable terms, each following the entrywise product pattern independently:

t_{k_{1} \dots k_{n}} = \sum_{r = 1}^{R} {(a_{1}^{(r)})}_{k_{1}} \dots {(a_{n}^{(r)})}_{k_{n}}

with each summand contributing its own instance of the pattern. Alternating least squares and related fitting algorithms exploit this by fixing all but one set of factor vectors at a time and solving a linear problem for the remaining factors, relying at every step on the entrywise multiplicative pattern to keep the subproblem linear.

Storage and Computation Savings from the Pattern

The multiplicative pattern is what makes decomposable and low-rank-decomposed tensors cheap to store and manipulate: a decomposable tensor with di-dimensional factors requires only the sum of the di numbers to store, and its entrywise pattern lets many downstream operations (contractions, inner products, norm computation) be carried out using the individual factors rather than the full expanded array.

Illustrative Diagram

Each entry of the resulting grid is the product of one entry from the column factor and one entry from the row factor, illustrating the entrywise multiplicative pattern in its simplest, two-factor form.