Tunable Hierarchical Low-Rank Matrix Approximations

This direction is merged into another direction: precision-complexity tradeoff. Its last version stays readable and citable here.

Version 1 of 114 papers19 conceptsfrozen 2026-10-04

In large-scale machine learning and scientific computing, we often face a frustrating binary choice. On one hand, we have "first-order" methods like Stochastic Gradient Descent or Temporal Difference learning: they are computationally cheap and scale linearly with data, but they are statistically "blind," requiring many samples to converge. On the other hand, "second-order" or least-squares methods are data-efficient and precise, but they require manipulating massive matrices, leading to quadratic or cubic costs that quickly become impossible as problems grow.

A growing body of research suggests we don't have to choose. By treating large matrices not as dense blocks of numbers, but as hierarchical low-rank structures, we can create a "tunable dial" between speed and precision.

The Rank as a Control Dial

The core intuition behind this direction is that the matrices governing complex systems—whether they are Hessians in optimization, system matrices in Reinforcement Learning (RL), or kernels in physics—often contain redundant information.

In RL, Clement Gehring, Martha White, and Yangchen Pan demonstrate this with t-LSTD (Incremental Truncated LSTD). Standard Least-Squares Temporal Difference (LSTD) learning is highly sample-efficient but requires $O(d^2)$ memory and computation. By using a truncated Singular Value Decomposition (SVD), they maintain a low-rank approximation of the system matrix.

The "rank" here acts as a mathematical lever:

  • Low Rank: The algorithm behaves like a fast, first-order gradient method.
  • High Rank: The algorithm approaches the full, data-efficient least-squares solution.

This allows practitioners to adapt to their hardware. If you have more memory, you increase the rank to get better estimates; if you are on a constrained device, you lower it. Adam White and colleagues extended this to Accelerated Gradient Temporal Difference (ATD) (Accelerated Gradient Temporal Difference Learning), showing that even a low-rank "quasi-second-order" update can significantly outperform standard linear methods without the full quadratic cost.

Hierarchical Compression and Skeletonization

While simple low-rank approximations work for some problems, others have "local" complexity that a single global approximation can't capture. This is where hierarchical ($\mathcal{H}$ or $\mathcal{H}^2$) matrices come in.

Instead of approximating the whole matrix at once, researchers like Hadi Pouransari and Eric Darve break the matrix into a tree-like structure (Fast hierarchical solvers for sparse matrices). They treat the "fill-in" (the new non-zero entries created during matrix factorization) as compressible interactions.

In 3D simulations, Zhenli Xu and Haizhao Yang use a technique called "skeletonization" to identify the most important points on the faces and edges of a grid (Hierarchical Interpolative Factorization for Self Green's Function in 3D Modified Poisson-Boltzmann Equations). By compressing these interactions, they turn an $O(N^3)$ bottleneck into a near-linear $O(N)$ process. This allows for a "coarse-to-fine" strategy: use a very low-rank, fast approximation early in a simulation, and increase the rank for high-fidelity results only when necessary.

Partitioning the Search Space

A similar logic applies to optimization. In Semidefinite Programming (SDP), we often struggle with massive constraints that must be "positive semidefinite." Aivar Sootla, Antonis Papachristodoulou, and Yang Zheng introduced block factor-width-two matrices (Block Factor-Width-Two Matrices in Semidefinite Programming).

Instead of enforcing one giant, expensive constraint, they partition the matrix into smaller, overlapping blocks.

  • Small blocks: The problem becomes as easy to solve as a simple SOCP (Second-Order Cone Program).
  • Large blocks: The problem approaches the accuracy of a full SDP.

By merging or splitting these blocks, they create a tunable hierarchy. This is particularly useful in Bayesian inference, where Brian L. Trippe and Tamara Broderick show that low-rank data approximations can speed up Generalized Linear Models (GLMs) while providing a "conservative" posterior that never underestimates uncertainty (LR-GLM: High-Dimensional Bayesian Inference Using Low-Rank Data Approximations).

Why It Works: The Middle Ground

The unifying insight across these papers is that numerical precision is a resource to be managed, not a fixed requirement.

Whether it is Akihiro Ida reducing QR factorization complexity through Block Low-Rank (BLR) structures (QR Factorization of Block Low-rank Matrices with Weak Admissibility Condition) or Ilona Ambartsumyan approximating Hessians for PDEs (Hierarchical Matrix Approximations of Hessians Arising in Inverse Problems Governed by PDEs), the mechanism is the same:

  1. Identify structure: Recognize that the matrix interactions are not full-rank.
  2. Define a hierarchy: Create a way to partition the matrix (blocks, trees, or SVD components).
  3. Tune the tolerance: Use a rank or truncation parameter to slide between the efficiency of first-order methods and the power of second-order ones.

This "middle ground" enables us to solve problems that were previously too large for exact methods and too complex for simple ones.

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_tunable_hierarchical_low_rank_matrix_app_be49251e,
  title = {Tunable Hierarchical Low-Rank Matrix Approximations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tunable-hierarchical-low-rank-matrix-approximations/rdr_be49251ebd0444ca92df2f0efa28f60a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_tunable_hierarchical_low_rank_matrix_app_be49251e_v1,
  title = {Tunable Hierarchical Low-Rank Matrix Approximations},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tunable-hierarchical-low-rank-matrix-approximations/rdr_be49251ebd0444ca92df2f0efa28f60a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}