📊 statistics

Kernel Regression with Tensor Trains and Hadamard Overparameterization

This paper introduces KReTTaH, a training-data-free, interpretable framework for multi-way data imputation that reformulates the problem as kernel regression with tensor-train coefficients and Hadamard overparameterization, jointly optimizing these components on Riemannian manifolds to achieve state-of-the-art accuracy in high-dimensional fMRI and dynamic graph applications without costly cross-validation.

Original authors: Duc Thien Nguyen, Konstantinos Slavakis, Eleftherios Kofidis, Dimitris Pados

Published 2026-07-21

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Duc Thien Nguyen, Konstantinos Slavakis, Eleftherios Kofidis, Dimitris Pados

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 are trying to finish a giant, multi-layered jigsaw puzzle, but someone has ripped out thousands of pieces. You can see the picture on the box, and you have a few scattered pieces left, but huge chunks of the sky, the ocean, and the trees are missing. This is the daily struggle for scientists and engineers working with "multi-way data." Whether it's a 3D movie of a brain lighting up, a map of traffic flowing through a city, or a video of a sports game, this data is often messy. Sensors break, connections drop, or measurements get lost, leaving us with a giant, incomplete puzzle.

To fix this, scientists usually try to guess the missing pieces by looking for patterns. They assume the data has a hidden structure, like a low-resolution sketch that, when filled in, reveals the high-definition picture. However, real-world data is rarely simple; it's full of complex, twisting, non-linear relationships that are hard to predict. Traditional methods often struggle to capture these twists without getting bogged down in massive calculations or requiring huge amounts of extra training data. The big question is: How can we fill in the blanks of a complex, multi-dimensional puzzle accurately, quickly, and without needing a massive library of other puzzles to learn from?

Enter a new method called KReTTaH (Kernel Regression with Tensor Trains and Hadamard Overparameterization), developed by a team of researchers. Think of KReTTaH as a super-smart, pattern-hunting detective that doesn't need to memorize a thousand other puzzles to solve the one in front of it. Instead of just guessing, it uses a clever mathematical trick called "kernel regression" to understand the hidden, non-linear connections between the pieces it does have.

Here is how it works in plain language. Imagine the data is a giant, multi-dimensional block of clay. KReTTaH doesn't try to sculpt the whole block at once. Instead, it breaks the problem down into a chain of smaller, manageable "train cars" (this is the "Tensor Train" part). These cars are linked together, and the way they connect is constrained to a specific, efficient shape, which keeps the math from getting too heavy.

But here is the magic sauce: KReTTaH also uses a technique called "Hadamard overparameterization." Imagine you are trying to find a specific needle in a haystack. Instead of just looking for one needle, you pretend there are many layers of needles, but you add a rule that forces most of them to be invisible (zero) unless they are absolutely necessary. This forces the model to be "sparse," meaning it only keeps the most important, meaningful patterns and throws away the noise. It's like a sculptor who starts with a huge block of stone but only chips away the parts that aren't the statue, leaving a clean, efficient shape.

The researchers tested this new detective on two very different, challenging puzzles. First, they tried to reconstruct 4D functional MRI (fMRI) scans of human brains. These are like 3D movies of brain activity over time, but with many missing frames. KReTTaH successfully filled in the missing brain activity, outperforming other top methods in accuracy while running faster than many of its competitors. Second, they tested it on traffic flow data in real-world networks (like roads in Massachusetts and Berlin). They tried to predict missing traffic speeds on roads that weren't being monitored. Again, KReTTaH did a better job of guessing the missing flows than the other methods, even when the data was very sparse.

What makes KReTTaH special is that it figures out its own settings automatically. Usually, scientists have to spend hours manually tuning knobs and dials (called hyperparameters) to get the best result. KReTTaH, however, uses a special mathematical landscape (a "Riemannian manifold") to roll downhill toward the best solution on its own, finding the perfect settings without human help.

The paper shows that this approach is not just a theoretical idea; it works in practice. In simulations using real brain scan data and real traffic data, KReTTaH consistently produced more accurate reconstructions than existing state-of-the-art methods. It managed to be both highly accurate and computationally efficient, proving that you can fill in the missing pieces of a complex, multi-dimensional puzzle without needing a massive training dataset or spending days tuning your tools. It suggests that by combining smart geometry with a bit of "overthinking" (overparameterization) that is then pruned down to the essentials, we can solve some of the messiest data problems we face today.

Technical Summary: Kernel Regression with Tensor Trains and Hadamard Overparameterization (KReTTaH)

Problem Statement

Multi-way data, naturally represented as tensors, frequently contain missing entries due to acquisition imperfections. Traditional tensor completion (TC) methods often rely on linear tensor decomposition models (e.g., CPD, Tucker, Tensor Train) which, while effective at capturing low-rank structures, fail to explicitly model the strong nonlinear relationships latent in many application domains. Furthermore, existing kernel-based tensor methods often suffer from limitations such as restrictive uniqueness conditions (CPD), rotational ambiguity (Tucker), high computational complexity (Bayesian inference), or the need for costly manual hyperparameter tuning via cross-validation. Additionally, many state-of-the-art approaches rely on "black-box" neural networks requiring external training data, lacking interpretability.

Methodology: The KReTTaH Framework

The paper introduces KReTTaH (Kernel Regression with Tensor Trains and Hadamard Overparameterization), a training-data-free, interpretable, and nonparametric framework for multi-way data imputation. The core methodology reformulates the imputation problem as a regression task within Reproducing Kernel Hilbert Spaces (RKHS).

1. Data Modeling and Regression:
Instead of imposing tensor train (TT) structure directly on the data tensor, KReTTaH constrains the regression coefficient tensors to lie on fixed-rank TT manifolds. The data tensor $Y$ is approximated using a multi-kernel model:
$Y \approx \sum_{\nu=1}^{N_K} \left( \bigodot_{p=1}^P U_{\nu,p} \right) \times_1 K_\nu \times_1 \left( \bigodot_{q=1}^Q V_{\nu,q} \right)$
where:

$K_\nu$ are kernel matrices derived from landmark points.
$U_{\nu,p}$ and $V_{\nu,q}$ are learnable coefficient tensors.
$\bigodot$ denotes the Hadamard (entry-wise) product.

2. Hadamard Overparameterization (HP):
To promote sparsity and enhance representational efficiency without relying on non-smooth $\ell_1$ -norm regularization, the framework employs Hadamard overparameterization. The coefficient tensors are expressed as the Hadamard product of multiple smaller tensors ( $U_\nu = \bigodot U_{\nu,p}$ ). When combined with smooth Frobenius norm regularization on these factors, HP effectively induces a non-convex quasi-norm regularizer that yields sparser solutions and reduces parameter storage.

3. Riemannian Optimization:
The framework jointly optimizes three sets of parameters on a Cartesian-product Riemannian manifold:

Fixed-rank TT Manifolds: The coefficient tensors are constrained to manifolds of fixed TT rank.
Positive-Definite (PD) Matrix Manifolds: The covariance matrices of multiple Gaussian kernels are treated as learnable parameters on the manifold of PD matrices. This eliminates the need for manual kernel hyperparameter tuning (e.g., bandwidth selection) typically performed via cross-validation.
Optimization Algorithm: The inverse problem is solved using a Riemannian Gradient Descent (R-GD) method with line search. This approach updates all factors simultaneously along a smooth trajectory, avoiding the sensitivity to initialization and overfactoring issues common in alternating minimization schemes.

4. Navigator Data and Landmark Points:
To handle sparsely observed data, the method utilizes "navigator data" (groups of observed entries) reduced to lower-dimensional representations via Local Linear Embedding (LLE). These are further compressed into "landmark points" to define the RKHS feature space.

Key Contributions

The paper outlines three primary contributions:

C1: Introduction of KReTTaH, a novel framework that integrates nonlinear/nonparametric modeling (via RKHS), dimensionality reduction (via TT decomposition), and sparse coding (via Hadamard overparameterization) within a unified Riemannian optimization setting.
C2: Generalization of prior two-way data work to multi-way settings by employing an explicit Riemannian manifold construction for regression coefficients, contrasting with implicit manifold-learning approaches where the underlying manifold is unspecified.
C3: Extension to handle multiple Gaussian kernels with learnable covariance matrices constrained to the PD manifold. This integration enables automated hyperparameter selection, circumventing the computationally expensive manual tuning required in previous works.

Experimental Results

The authors evaluated KReTTaH on two challenging applications:

4D Functional MRI (fMRI) Reconstruction:
- Datasets: COBRE (resting-state) and BOLD5000 (event-related).
- Baselines: RTTC (fixed-rank manifold), VKBTR (Bayesian TRD), and NCP (kernel-based CPD).
- Results: KReTTaH consistently achieved the lowest Normalized Root Mean Squared Error (NRMSE) across all sampling ratios (0.1 to 0.5). In terms of runtime, it was second only to NCP, significantly outperforming the memory-intensive VKBTR and the slower RTTC.
Dynamic Graph Flow Imputation:
- Datasets: Traffic flow data from Eastern-Massachusetts (EMA) and Berlin-Friedrichshain (BF) networks.
- Baselines: PS, S-VAR, HodgeNet (NN-based), RTTC, STTC, NCP, and VKBTR.
- Results: KReTTaH achieved the lowest NRMSE in most scenarios, outperforming both tensor-based and neural-network-based methods. Notably, it achieved high sparsity (reducing parameter storage by >40% with specific HP settings) while maintaining superior accuracy. The use of multiple kernels ( $N_K > 1$ ) further improved performance and allowed for smaller rank selections.

Significance and Claims

The paper claims that KReTTaH offers a distinct advantage by operating in a training-data-free manner, providing an interpretable solution through RKHS regression rather than relying on black-box neural networks. By leveraging the rich geometric structure of fixed-rank TT manifolds and PD matrices, the method achieves:

Automated Hyperparameter Selection: The joint learning of kernel covariances removes the burden of cross-validation.
Efficiency and Sparsity: Hadamard overparameterization promotes sparsity and dimensionality reduction without non-smooth optimization.
Robustness: The Riemannian gradient descent approach reduces sensitivity to initialization and overfitting compared to block coordinate descent methods.

The authors conclude that KReTTaH represents a significant step forward in tensor completion, successfully balancing modeling accuracy, computational efficiency, and interpretability for multi-way data imputation. Future directions suggested include automatic rank selection and extensions to online learning from streaming data.