Fast Iterative Methods for Symmetric Tensor Systems

This direction is merged into another direction: tensor decomposition scalability. Its last version stays readable and citable here.

Version 1 of 111 papers18 conceptsfrozen 2026-10-04

In classical linear algebra, we have a robust toolkit for solving systems and finding eigenvalues: the QR algorithm, Newton’s method, and Kaczmarz projections. However, when we move from matrices (2D) to tensors (nD), these tools often break. The traditional "workhorse" for tensors—the power method—is frequently too slow and often fails to find all the relevant "eigenpairs" of a system.

Recent research has focused on adapting high-order iterative solvers to work directly on tensors. By avoiding the common pitfall of "flattening" tensors into matrices, these methods preserve the data's inherent structure while achieving much faster convergence.

The Problem with Flattening and Power Methods

To solve a tensor problem, the simplest approach is to "unfold" or flatten the tensor into a giant matrix. But this destroys the multi-dimensional relationships—like the spatial pixels in a video or the coordinates in a 3D scan. Furthermore, the standard Tensor Power Method is a first-order solver; it converges linearly, meaning it crawls toward a solution one steady step at a time. It also tends to get stuck, finding only the most dominant eigenpairs and missing "unstable" ones that are physically or mathematically significant.

To overcome this, researchers are lifting more sophisticated iterative strategies—Newton steps, QR decompositions, and randomized projections—into the tensor domain.

Achieving Quadratic Convergence with Newton Steps

One of the most powerful leaps in this field is the shift from linear to quadratic convergence. In Newton Correction Methods for Computing Real Eigenpairs of Symmetric Tensors, Ariel Jaffe, Boaz Nadler, and Roi Weiss reformulate the search for tensor eigenvalues as a nonlinear root-finding problem.

The intuition is simple: instead of just moving in the direction of the gradient (like a power method), the Newton Correction Method (NCM) uses a local linearization to calculate a "correction vector." By accounting for the curvature of the tensor's landscape, the precision of the estimate approximately doubles with every iteration. This allows the solver to find nearly all real eigenpairs—even the elusive ones—up to two orders of magnitude faster than global solvers that don't use local curvature.

Shifting Strategies in Tensor QR

The QR algorithm is the gold standard for finding all eigenvalues of a matrix. kim batselier and Ngai Wong successfully extended this to tensors in A QR Algorithm for Symmetric Tensors.

The core innovation here is the use of shifting strategies. In a standard iterative process, the "energy" of the tensor might be spread out, making it hard to isolate individual eigenvalues. By applying a "shift"—essentially subtracting a value from the diagonal elements during the decomposition—the algorithm can "deflate" the tensor, making the underlying eigenstructure stand out more clearly. This acceleration technique allows the QRST algorithm to converge rapidly on multiple eigenpairs that traditional methods would simply overlook.

Preserving Structure through Slice Projections

When solving massive linear systems, we often use the Kaczmarz method, which finds a solution by repeatedly projecting a point onto the rows of the system. In Randomized Kaczmarz for Tensor Linear Systems, Anna Ma introduces Tensor Randomized Kaczmarz (TRK).

The key intuition is the use of the t-product framework. Instead of projecting onto a single flattened row (a vector), TRK projects onto "row slices" of the tensor.

Why does this work better?

  1. Spatial Integrity: By treating slices as the fundamental unit, the algorithm respects the multi-dimensional tubes of data (like a temporal sequence in a video).
  2. Contraction Efficiency: High-dimensional geometry actually helps here. In large-scale systems, the "angle" between these tensor slices allows for a more favorable contraction coefficient, meaning each randomized step gets you significantly closer to the true solution than a matrix-based step would.

Summary

The transition from simple power iterations to structured iterative solvers represents a major shift in tensor computations. By leveraging Newton-based corrections for quadratic speed, shifting strategies for eigenpair isolation, and t-product projections to preserve spatial data, these methods make high-dimensional problems computationally tractable without sacrificing the rich structure of the original data.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_fast_iterative_methods_for_symmetric_ten_b6fc5fee,
  title = {Fast Iterative Methods for Symmetric Tensor Systems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fast-iterative-methods-for-symmetric-tensor-systems/rdr_b6fc5fee000f4ca5add369f0839e4e4f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_fast_iterative_methods_for_symmetric_ten_b6fc5fee_v1,
  title = {Fast Iterative Methods for Symmetric Tensor Systems},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/fast-iterative-methods-for-symmetric-tensor-systems/rdr_b6fc5fee000f4ca5add369f0839e4e4f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}