🔢 mathematics

Matrices over a Hilbert space and their low-rank cross approximation

Motivated by reduced-order modeling for parametric PDEs, this paper extends low-rank cross approximation to Bochner matrices (matrices with Hilbert space entries), deriving new approximation guarantees and proposing an adaptive, non-intrusive method validated on parametric nonlinear Stokes equations.

Original authors: Stanislav Budzinskiy

Published 2026-06-26

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Stanislav Budzinskiy

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive library of books. In a normal library, each book is a single object you can hold, read, and compare to others. But in this paper's world, imagine that instead of holding a single book, every "book" on your shelf is actually a whole library inside it.

This is the core idea of the paper: dealing with matrices where every single entry isn't just a number (like 5 or 3.14), but an entire complex object (like a whole 3D simulation of fluid flow or a complex sound wave). The author calls these "Bochner matrices."

Here is a breakdown of the paper's journey, using simple analogies:

1. The Problem: The "Too Big to Read" Library

In engineering and physics, we often try to solve equations that change based on different settings (parameters). For example, how does water flow around a wing if we change the wing's shape or the water's speed?

The Old Way: Usually, scientists pick one specific setting, solve the math, get a single number (like "the drag is 50 Newtons"), and repeat this for every setting. This is slow.
The New Way: The author suggests treating the entire solution (the whole flow pattern) as a single "entry" in a giant grid. So, instead of a grid of numbers, you have a grid of entire flow simulations.

2. The Challenge: The "Two-Sided" Puzzle

When you have a normal grid of numbers, you can often simplify it by picking a few key rows and columns. If you know the corners and the middle, you can guess the rest. This is called Cross Approximation.

However, the author discovered a weird quirk with these "library-inside-a-book" matrices:

The Mismatch: In a normal grid, the number of unique rows usually matches the number of unique columns. In this new world, they don't! You might have 100 unique "flow patterns" across the rows, but only 50 unique ones across the columns.
The Analogy: Imagine a spreadsheet where the rows are "different weather patterns" and the columns are "different cities." In a normal spreadsheet, if you know the weather in 5 cities, you might guess the rest. But here, the "weather" is so complex that knowing the weather in 5 cities doesn't tell you everything about the other 95, even if you know the weather in 5 other cities. The "rows" and "columns" behave differently.

3. The Solution: A New Way to Pick Samples

The paper proposes a new method to approximate these giant, complex grids without having to calculate every single entry (which would take forever).

The "Rook" Strategy: Think of a chess rook. It moves in straight lines. The author's algorithm picks a "row" (a specific parameter setting), finds the most interesting "column" (another setting) based on that row, then finds a new "row" based on that column, and so on.
The Twist: Because the rows and columns behave differently (as mentioned above), the author had to invent a new rulebook. You can't just pick a few spots and assume the rest fits perfectly like a puzzle. You have to be careful about how you pick them.

4. The Surprise: "Better" than Normal Numbers

One of the most exciting findings is counter-intuitive.

The Finding: When you pick the "best" spots to sample in these complex matrices, the math actually works out better (more stable) than it does for normal numbers.
The Analogy: Imagine trying to guess the shape of a cloud by looking at a few drops of water. Usually, it's hard. But the author found that because these "drops" (the entries) are so rich and structured (they live in a "Hilbert space," which is a fancy math way of saying they have a lot of internal structure), picking just a few of them gives you a surprisingly clear picture of the whole cloud. The "noise" that usually messes up these calculations is actually smaller here than in the normal world.

5. The Test: The "Non-Linear" Fluid

To prove this works, the author tested it on a real-world problem: Non-linear Stokes equations.

The Scenario: Imagine fluid flowing where the thickness of the fluid changes depending on how fast it's moving (like ketchup or blood). This is very hard to calculate.
The Result: The author's new method (called Adaptive Bochner Cross Approximation) successfully built a "surrogate model." This is a cheap, fast version of the complex math that can predict the fluid flow for any setting without running the heavy simulation every time.
The Catch: It wasn't perfect (it had about twice the error of the "gold standard" method), but it achieved this by looking at only a tiny fraction of the data. It's like guessing the plot of a 10-hour movie by watching only 10 minutes of it, and getting the ending mostly right.

Summary

The paper says: "We have a new type of math object where every entry is a complex simulation. We found that the old rules for simplifying these don't work because the rows and columns act differently. However, we created a new 'sampling' strategy that works surprisingly well, allowing us to predict complex physical behaviors (like fluid flow) much faster than before, with the added bonus that the math is actually more stable than we expected."

It is a toolkit for engineers to stop solving the same hard problem over and over again, allowing them to build a "map" of all possible solutions at once.

Technical Summary: Matrices Over a Hilbert Space and Their Low-Rank Cross Approximation

1. Problem Statement

The paper addresses the challenge of approximating matrices whose entries reside not in a field (like $\mathbb{R}$ or $\mathbb{C}$ ) or a ring, but in an abstract Hilbert space $\mathcal{H}$ . This specific structure arises naturally in Reduced-Order Modeling (ROM) of parametric Partial Differential Equations (PDEs).

In parametric PDEs, one seeks a solution map $(\alpha, \beta) \mapsto u_{\alpha, \beta}$ where parameters vary over a domain. Discretizing these parameters yields a matrix where each entry is a function (specifically, an element of a Sobolev space like $H^1_0(\Omega)$ ). Standard low-rank approximation techniques, such as Cross Approximation (CA) and Adaptive Cross Approximation (ACA), are designed for scalar matrices. The paper investigates whether these techniques can be rigorously extended to "Bochner matrices" (matrices with entries in $\mathcal{H}$ ) to approximate the solution map itself, rather than just scalar quantities of interest derived from the solution.

2. Methodology and Theoretical Framework

2.1. Definition of Bochner Matrices

The authors define a Bochner matrix as an $m \times n$ array with entries in a Hilbert space $\mathcal{H}$ . They establish the algebraic properties of these objects through four distinct perspectives:

As Linear Operators: A Bochner matrix induces a bounded linear operator between finite-dimensional spaces and $\mathcal{H}^m$ . The authors prove that Bochner matrices admit a Singular Value Decomposition (SVD) and that the Eckart–Young–Mirsky theorem holds for them regarding unitarily invariant norms.
As Quasimatrices: Viewing columns as elements of $\mathcal{H}$ , the authors establish the existence of interpolative decompositions ( $A = A(:, J)B$ ) and thin QR decompositions.
As Matrices: The paper distinguishes between column rank ( $rank_c$ ) and row rank ( $rank_r$ ). Unlike classical matrices, $rank_c(A)$ and $rank_r(A)$ can differ significantly. Crucially, the paper demonstrates that standard CUR decompositions (where $A \approx CUR$ ) are structurally impossible for Bochner matrices because the middle factor would require multiplying two Bochner matrices, which is undefined in this framework.
As Third-Order Tensors: Bochner matrices are identified with tensors in the product space $\mathcal{H} \otimes \mathbb{F}^m \otimes \mathbb{F}^n$ . This allows the definition of a Tucker rank tuple $(rank_r, rank_c)$ and the application of Higher-Order SVD (HOSVD).

2.2. Cross Approximation Extension

The core methodology involves extending Cross Approximation to Bochner matrices. The approximation is defined as:
$\text{cross}(A, I, J) = ((G^\top)^\dagger C^\top)^\top G (G^\dagger R)$
where $C, R, G$ are submatrices of selected rows and columns. The authors derive necessary and sufficient conditions for this decomposition to be exact (Theorem 6.2) and analyze the error when it is approximate.

2.3. Error Analysis and Conditioning

A significant portion of the methodology focuses on deriving error bounds:

One-sided Interpolation: Bounds are derived for approximations using only selected rows or columns, relying on the operator norms of the pseudoinverses of submatrices of singular factors.
Maximum-Volume Bounds: The paper generalizes the concept of "maximum-volume" submatrices to Bochner matrices. A key theoretical finding is that the conditioning of maximum-volume submatrices in the Bochner setting is better than in the classical scalar setting. This is attributed to the "inter-row rank excess" ( $\Delta$ ), a quantity that is zero for classical matrices but positive for Bochner matrices with orthonormal entries, leading to tighter bounds on the pseudoinverse norm.
Entrywise Error: The authors derive entrywise error bounds for the cross approximation, showing how the error depends on the singular values of the matrix and the volume properties of the selected submatrix.

2.4. Algorithm: Adaptive Bochner Cross (ABC)

The paper proposes Algorithm 2 (ABC), an extension of Adaptive Cross Approximation.

Unlike classical ACA, where rank-one updates are additive, Bochner cross approximation is not additive due to the mismatch between row and column ranks.
The ABC algorithm employs a "rook pivoting" strategy to select indices but includes an inner loop to perform approximate rank-one corrections on the residual before recomputing the full cross approximation. This handles the non-additivity of the decomposition.

3. Key Contributions

Formal Algebraic Foundation: The paper formally defines Bochner matrices and establishes their properties as linear operators, quasimatrices, and tensors, proving the existence of SVDs and interpolative decompositions.
Theoretical Extension of Cross Approximation: It extends cross approximation theory to Hilbert-space-valued matrices, deriving approximation guarantees based on pseudoinverse norms and maximum-volume properties.
Superior Conditioning Bounds: The authors prove that maximum-volume submatrices of Bochner matrices with orthonormal entries are better conditioned than their classical counterparts. Specifically, the error bounds for the pseudoinverse are smaller, allowing for undersampling (selecting fewer rows than columns) while maintaining stability.
Non-Intrusive ROM Method: The paper introduces the ABC algorithm as a non-intrusive method for ROM. It validates that one can approximate the full solution map of a parametric PDE by querying the PDE solver only a small number of times (evaluating specific rows and columns).

4. Numerical Results

The methodology is validated using parametric nonlinear Stokes equations in a 2D domain.

Setup: The viscosity is modeled as a function of parameters $\alpha$ and $\beta$ . The solution map is discretized into a $100 \times 100$ Bochner matrix with entries in a 6495-dimensional finite element space.
Performance:
- The ABC algorithm with adaptive pivoting ( $n_{rook}=1$ ) successfully reduces approximation error as the number of iterations increases, whereas random selection ( $n_{rook}=0$ ) fails to capture the solution structure.
- The algorithm selects fewer rows than columns, reflecting the stronger dependence of the solution on the parameter $\beta$ (which controls nonlinearity).
- Accuracy: Compared to the quasi-optimal HOSVD (which requires full knowledge of the matrix), the ABC method achieves errors approximately twice as large but does so by querying the PDE solver only a fraction of the times required for full sampling.
- Table 2 shows that for a Tucker rank of roughly $(9, 15)$ , the relative $L^2(H^1)$ error is $2.6 \times 10^{-6}$ for ABC, compared to $1.3 \times 10^{-6}$ for HOSVD.

5. Significance and Claims

The paper claims to provide the theoretical foundation for cross approximation in the context of Hilbert-space-valued data. Its significance lies in:

Non-Intrusive ROM: It offers a rigorous way to construct surrogate models for parametric PDEs without modifying the underlying solver, relying solely on the evaluation of the solution map at specific parameter points.
Algebraic Insight: It clarifies the structural differences between classical matrices and Bochner matrices, specifically regarding rank asymmetry and the impossibility of standard CUR decompositions.
Improved Stability: The discovery that Bochner matrices allow for better-conditioned submatrices (via the inter-row rank excess) suggests that cross approximation may be more robust in high-dimensional functional settings than in classical scalar settings.

The authors conclude that while the current work focuses on matrices, the framework is extendable to Bochner tensors, which is the subject of a follow-up paper. The work is presented as a foundational step toward efficient, data-driven modeling of complex parametric systems.