Tensor Decomposition

Tensor decomposition is the problem of expressing a multi-dimensional array—a tensor—as a sum of simpler components, typically rank-1 tensors. It is the natural generalization of matrix decomposition to orders higher than two, and like its matrix counterpart, it arises across the sciences: in signal processing for blind source separation, in machine learning for latent variable models, in neuroscience for analyzing multi-modal brain data, and in chemistry for fluorescence spectroscopy. Yet tensors of order three and higher behave so differently from matrices that the generalization is less a straightforward extension than a journey into a structurally alien landscape.

The central difference is that higher-order tensors lack a canonical decomposition. Every matrix has a singular value decomposition with uniquely determined singular values and orthonormal singular vectors. Tensors have no such uniqueness theorem: the rank of a tensor is not even well-defined as a single number, and the set of optimal decompositions can be a non-isolated manifold rather than a discrete set. The CP decomposition, which writes a tensor as a sum of rank-1 components, is the most common formulation, but its properties—ill-posedness, non-existence of best approximations, and NP-hardness of computation—make it a far more treacherous object than the matrix SVD.

Tensor decomposition also exhibits a statistical-computational gap analogous to that of sparse PCA and the planted clique problem. In the tensor version of the spiked model, a rank-1 signal tensor is added to a random noise tensor, and the task is to recover the signal component. The information-theoretic threshold for recovery scales differently than in the matrix case, but the algorithmic threshold is dramatically higher: efficient algorithms require much stronger signals for tensors than for matrices. This gap is not a matter of degree but of kind. The spectral methods that solve matrix problems fail for tensors because the eigenstructure of tensor contractions does not carry the same information as the eigenstructure of matrices.

The sum-of-squares hierarchy provides the best known polynomial-time algorithms for tensor decomposition, but even these require higher degree than their matrix counterparts. The gap suggests that tensor problems may be fundamentally harder than matrix problems—not just harder to solve with current tools, but harder in a structural sense that no future algorithmic breakthrough can fully bridge.