Tensors allow us to capture multi-way interactions that matrices simply cannot. However, optimizing parameters directly within a high-order tensor is notoriously difficult. A full tensor optimization problem is inherently non-linear and non-convex, meaning that standard simultaneous optimization techniques often stall in poor local minima or suffer from extreme computational overhead.
The core insight that makes tensor decomposition tractable is conditional linearity. While a tensor product is globally non-linear, it is multilinear. If you freeze all dimensions or core components except for one, the objective function collapses into a simple, well-understood linear least squares problem or a standard convex sub-problem. By cycling through each component and updating them one at a time, we can break an intractable global problem into a sequence of easily solvable steps.
The Core Intuition: Conditional Linearity
To understand why alternating optimization works, consider a simple three-way tensor decomposition where we want to approximate a tensor $\mathcal{X}$ using three factor matrices: $A$, $B$, and $C$. Optimizing all three matrices simultaneously is a highly non-convex problem.
However, if we hold $B$ and $C$ constant, the relationship between the remaining matrix $A$ and the target tensor $\mathcal{X}$ becomes strictly linear. As noted by Tamara G. Kolda in Tensor Decompositions and Data Mining, this property allows us to simplify a complex non-linear objective into a sequence of linear least squares problems.
Simultaneous Optimization (Non-Convex):
[Update A, B, C together] ---> High computational complexity, unstable
Alternating Optimization (Conditionally Convex):
Step 1: Fix B, C ---> [Optimize A via Linear Least Squares]
Step 2: Fix A, C ---> [Optimize B via Linear Least Squares]
Step 3: Fix A, B ---> [Optimize C via Linear Least Squares]
(Repeat until convergence)
By cycling through the modes of the tensor, we can iteratively refine each factor matrix. Brett W. Bader et al. demonstrate in Tensor Decompositions and Applications that this alternating factor optimization guarantees a monotonic decrease in the global reconstruction error, providing a highly stable approach for non-convex tensor problems.
Mode-Wise and Block Coordinate Descent
This strategy of isolating a single dimension is widely referred to as mode-wise optimization or block coordinate descent. In Tensor Decomposition for Signal Processing and Machine Learning, Xiao Fu explains that fixing all but one mode allows practitioners to solve for the remaining factor matrix using standard matrix operations.
This mode-by-mode isolation is powerful across diverse applications:
- Dimension Reduction: In gait recognition, Rudolf Fleischer (Multilinear Tensor-Based Non-parametric Dimension Reduction for Gait Recognition) shows that fixing all but one tensor dimension allows the active projection matrix to be optimized sequentially, converging to a stable local optimum in very few iterations.
- Constrained Spaces: When dealing with complex constraints like $\ell_1$ penalties, Yang Liu et al. (Multilinear Maximum Distance Embedding Via L1-Norm Optimization) utilize an iterative greedy algorithm to update the projection for each tensor dimension sequentially, ensuring convergence in high-dimensional settings.
Tensor Networks and Sweeping Algorithms
For high-dimensional systems—such as quantum states or multi-variable partial differential equations—traditional tensor decompositions suffer from storage explosions. Instead, researchers use Tensor Networks, such as Tensor Trains (TT) or Tensor Rings (TR), which break a high-order tensor into a chain of low-order core tensors.
Alternating optimization adapts to tensor networks through a "sweeping" mechanism. Instead of updating a whole mode matrix, the algorithm freezes all cores in the network except for one or two adjacent cores, updates them, and then moves down the chain.
Tensor Train Chain: [Core 1] <---> [Core 2] <---> [Core 3] <---> [Core 4]
| | | |
Sweep Forward: [UPDATE] [FIXED] [FIXED] [FIXED]
[FIXED] [UPDATE] [FIXED] [FIXED]
[FIXED] [FIXED] [UPDATE] [FIXED]
This sweeping strategy provides unique computational advantages:
- Reduced-Order Subproblems: Sergey Dolgov et al. (Computation of extreme eigenvalues in higher dimensions using block tensor train format) demonstrate that freezing most parameters allows them to solve a reduced-order local eigenvalue problem, bypassing the curse of dimensionality when finding extreme eigenvalues.
- Training Stability: In linked chains like Matrix Product States, simultaneous gradient updates can cause severe numerical instabilities. As shown by Cong Chen et al. in Matrix Product Operator Restricted Boltzmann Machines, updating tensor cores individually provides significantly greater training stability and accuracy compared to simultaneous updates.
- Linear Subproblems: Kim Batselier et al. (Tensor Network alternating linear scheme for MIMO Volterra system identification) leverage this core-by-core update to transform massive system identification tasks into a sequence of smaller, numerically stable linear systems.
- Probabilistic Learning: The authors of Learning Generative Models for Active Inference Using Tensor Networks use an alternating sweep algorithm to maximize the likelihood of observed data sequentially, allowing autonomous agents to learn environment dynamics without relying on backpropagation.
Mathematical Convergence and Efficiency
Why are alternating schemes preferred over standard gradient descent for structured tensors? The answer lies in mathematical guarantees and the avoidance of hyperparameter tuning. Because each sub-problem is convex, block coordinate descent inherently ensures that the objective function cannot worsen.
To formalize these convergence properties, Huan Wang et al. (A Convengent Solution to Tensor Subspace Learning) proved that reformulating tensor optimization from a ratio trace approximation into a trace difference problem allows for a mathematically rigorous iterative procedure that guarantees monotonic convergence to a stable set of projection matrices.
Furthermore, practitioners can accelerate these updates by avoiding nested optimization loops. Athanasios A. Rontogiannis et al. (Block-Term Tensor Decomposition: Model Selection and Computation) show that applying majorization-minimization techniques transforms complex non-smooth tensor objectives into a sequence of reweighted least squares problems. This yields closed-form updates that drastically reduce computational latency. Similarly, in image processing, Xiao Bai et al. (Nonlocal Similarity Based Nonnegative Tucker Decomposition for Hyperspectral Image Denoising) utilize a Hierarchical Alternating Least Squares (HALS) strategy to update individual components sequentially, avoiding computationally expensive matrix inversions entirely.
Scaling Machine Learning Without Gradients
By turning non-linear problems into linear ones, alternating tensor optimization provides an efficient alternative to deep learning models that rely on stochastic gradient descent (SGD).
For instance, when solving high-dimensional partial differential equations, Lorenz Richter et al. (Solving high-dimensional parabolic PDEs using the tensor train format) demonstrate that alternating least squares for structured tensors offers superior convergence speeds compared to neural networks, achieving high precision without extensive hyperparameter tuning.
This scalability also extends to kernel machines. Frederiek Wesel et al. (Quantized Fourier and Polynomial Features for more Expressive Tensor Network Models) show that optimizing tensor-structured kernel machines via Alternating Least Squares keeps the computational complexity strictly linear relative to the number of parameters. This allows large-scale models to be trained efficiently on modest hardware while maintaining strong generalization capabilities.
Key Foundational Work
Multilinear algebra for analyzing data with multiple linkages. (2006) — contributed 1 concept elements to this direction.