📊 statistics

Distributionally Faithful Imputation via Positive Semi-Definite Kernel Density Estimation

This paper introduces PSD Impute, a distributionally faithful imputation method that formulates missing value recovery as a convex density estimation problem using positive semi-definite kernels to achieve statistical consistency and competitive accuracy without restrictive parametric assumptions.

Original authors: Andrea Basteri, Carlo Ciliberto, Alessandro Rudi

Published 2026-07-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Andrea Basteri, Carlo Ciliberto, Alessandro Rudi

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 solve a giant jigsaw puzzle, but someone has ripped out huge chunks of the picture. Maybe a few pieces are missing from the sky, others from the ocean, and some from the trees. Your goal is to fill in those gaps so the picture looks real again.

For decades, scientists have tried to fix these missing pieces using various tricks. Some methods just guess the "average" color for the missing spot. If a tree branch is missing, they might paint a generic green blob there. The problem? Real life isn't just about averages. A tree branch has a specific shape, and the wind might have bent it one way. If you only paint the average, you lose the story of the whole picture. You might get the colors right, but the relationships between the pieces—the way the clouds touch the mountains—get all wrong.

This is exactly the problem with missing data in computers. Old methods often focus on getting the single "best guess" for a missing number, ignoring how that number connects to everything else. They treat the data like a list of isolated facts rather than a living, breathing system.

The New Approach: A "Shape-Shifting" Cloud

The authors of this paper, Andrea Basteri, Carlo Ciliberto, and Alessandro Rudi, propose a different way to play the puzzle game. Instead of guessing single numbers, they want to rebuild the entire shape of the missing picture.

They call their method PSD-Impute. Here is how it works, using a simple analogy:

Imagine the data you have (the pieces you do see) as a set of shadows cast by a mysterious 3D object. You can't see the object itself because parts of it are hidden behind a curtain (the missing data). However, you know that the shadows on the wall must match the object exactly.

The authors' method tries to build a "cloud" of possibilities that fits perfectly behind the curtain. This cloud is made of a special kind of mathematical fog called a Positive Semi-Definite (PSD) Kernel Density.

The Magic Fog: Think of this fog as a flexible, stretchy sheet that can mold itself into any shape. Unlike older methods that force the fog to be a perfect sphere (like a ball) or a flat sheet, this fog can twist and turn to match the weird, complex shapes of real-world data.
The Perfect Fit: The method adjusts this fog until the "shadows" it casts (the parts of the data we can see) match the actual shadows in your puzzle exactly. It doesn't just guess a number; it learns the entire distribution of how the data behaves.
The Math Trick: The authors found a clever way to make this fitting process "convex." In plain English, this means the path to the perfect solution is like rolling a ball down a smooth bowl. No matter where you start, the ball will always roll to the very bottom (the best answer) without getting stuck in a fake valley. This is a huge deal because many other methods get stuck in local traps, thinking they found the best answer when they haven't.

What They Don't Do (And Why)

The paper is very clear about what this method is not.

It does not just predict the average value. If you have a dataset of heights and weights, it won't just tell you "the missing person is 5'10"." It will tell you the range of possible heights and weights and how they likely go together.
It does not rely on the assumption that everything follows a perfect bell curve (a "Normal" distribution). Real life is messy, and this method embraces that messiness.
It does not use deep neural networks that are hard to train and sometimes give different answers every time you run them. This method is stable and deterministic.

How Sure Are They?

The authors have done a lot of homework to back up their claims:

The Theory: They have mathematically proved that as they get more data, their "fog" gets closer and closer to the true shape of the missing picture. They showed that the error shrinks at a specific, fast rate, even when the data has many dimensions (many different variables).
The Experiments: They tested this on one synthetic dataset (a made-up puzzle they created) and eleven real-world datasets. In these tests, their method suggested that it could reproduce the "joint structure" (the relationships between variables) better than popular existing tools.
The Caveat: While the math is solid, the real-world results are described as "preliminary experiments." The authors suggest the method has "strong practical promise," but they haven't claimed it solves every problem in the world yet. They are still working on making it faster and handling even more complex missing data patterns.

The Result: One Model, Two Uses

Because this method builds a complete "fog" of the data, it's incredibly versatile.

Single Imputation: If you just need one number to fill a gap, you can take the "center" of the fog.
Multiple Imputation: If you need to understand the uncertainty (how sure you are about the gap), you can sample different points from the fog. This gives you many different, realistic versions of the missing picture, which is crucial for scientists who need to know how much they can trust their results.

In a Nutshell

The paper suggests that by treating missing data as a puzzle of "shadows" and using a flexible, mathematically stable "fog" to fill the gaps, we can recover the true shape of the data much better than before. It's a step toward making computer analysis more honest about the relationships between things, rather than just filling in blanks with averages. The math checks out, the early tests look promising, and the method offers a fresh, reliable way to handle the messy reality of missing information.

Technical Summary: Distributionally Faithful Imputation via Positive Semi–Definite Kernel Density Estimation

1. Problem Formulation

The paper addresses the challenge of missing data in statistical inference and machine learning. While missing values are ubiquitous, existing imputation methods often rely on heuristics or restrictive parametric assumptions (e.g., multivariate Normality) that fail to capture the true joint data distribution. Furthermore, popular metrics like Root-Mean-Square Error (RMSE) reward pointwise predictions (conditional means) but ignore multivariate dependencies and uncertainty.

The authors focus on the Missing Completely At Random (MCAR) mechanism. They recast the imputation problem not as a regression task, but as a density estimation problem from masked observations. The core objective is to estimate a distribution $p$ such that its observed marginals exactly match the empirical marginals of the data. Formally, given a true data-generating density $p^\star$ and a mask distribution $\mu$ , the goal is to find $p$ such that $p_S = p^\star_S$ for $\mu$ -almost every mask $S$ .

The learning objective is defined as minimizing the masked Kullback–Leibler (KL) risk:
$L(p) := \sum_{S \subseteq [d]} \mu(S) \text{KL}(p^\star_S \parallel p_S)$
This formulation ensures that the imputed data reproduces the joint structure of the ground truth, enabling both single and multiple imputations.

2. Methodology: PSD-Impute

The proposed solution, PSD-Impute, leverages Positive Semi-Definite (PSD) Kernel Densities to transform the non-convex density estimation problem into a convex optimization task with closed-form marginals.

2.1 The Model

The method approximates the density $p(x)$ using a feature map $\phi(x)$ derived from a Gaussian kernel $k_\eta(x, x') = \exp(-\eta \|x - x'\|^2)$ and a set of anchor points $W = \{w_1, \dots, w_\ell\}$ . The density is parameterized by a PSD matrix $Q \in \mathbb{S}^d_+$ :
$p_Q(x) = \phi(x)^\top Q \phi(x)$
To ensure $p_Q$ is a valid probability density, it is normalized via the moment matrix $H = \int \phi(x)\phi(x)^\top dx$ , imposing the constraint $\text{Tr}(QH) = 1$ .

2.2 Key Properties

The choice of PSD kernel densities is motivated by four properties:

Universality: The model class can approximate any continuous density as the number of anchors $\ell \to \infty$ .
Closed-Form Marginals: Unlike standard kernel density estimators, marginals of PSD densities can be computed analytically. For a subset $S$ , the marginal is:
$p_{Q,S}(x_S) = c_{2\eta}^{N_S} \text{Tr}(Q (K_S(x_S) \circ H_{N_S}))$
where $K_S$ is a rank-one kernel matrix and $H_{N_S}$ is a pre-computable matrix depending only on the unobserved dimensions.
Convexity: The negative log-likelihood of the masked observations is convex with respect to $Q$ .
Optimal Approximation: The family achieves minimax optimal rates for smooth densities, breaking the curse of dimensionality barriers associated with non-negative kernel histograms.

2.3 Optimization

The empirical risk minimization problem is formulated as:
$\min_{Q \succeq 0, \text{Tr}(QH)=1} \left[ -\frac{1}{N} \sum_{i=1}^N \log \text{Tr}(Q A_i) + \lambda \text{Tr}(Q A_0) \right]$
where $A_i$ is a data-dependent matrix derived from the observed mask $S_i$ and the anchor points. The term $\lambda \text{Tr}(Q A_0)$ acts as a regularizer (controlling the RKHS norm), and a log-det barrier is used to enforce positive semi-definiteness.

The authors solve this using a damped Newton interior-point method. By exploiting the Kronecker structure of the matrices involved, the algorithm scales efficiently, avoiding the need for stochastic tricks or non-convex training.

3. Theoretical Guarantees

The paper establishes statistical consistency and convergence rates for the estimator $\hat{p}$ :

Consistency: The estimator converges to the true density $p^\star$ in terms of the masked KL risk.
Convergence Rate: Under assumptions of Hölder smoothness ( $s$ ) and compact support, the excess risk bound is $O(N^{-s/(6s+2d)})$ .
Dimensionality: The rate adapts to the regularity of the probability distribution, offering a way to beat the curse of dimensionality for very regular probabilities.
Proof Strategy: The analysis decomposes the error into a learning error (estimating $Q$ from finite samples) and an approximation error (how well the PSD class approximates $p^\star$ ), bounding both separately before combining them.

4. Experimental Results

The authors report preliminary experiments on one synthetic dataset and eleven real-world datasets.

Performance: PSD-Impute demonstrates competitive distributional accuracy compared to popular baselines (including MICE, missForest, and deep generative models).
Metrics: Evaluation focuses on distributional metrics (Energy Distance, Optimal Transport) rather than just RMSE, showing that PSD-Impute better preserves the joint structure of the data.
Capabilities: The single fitted density successfully generates both single imputations (via conditional means) and multiple imputations (via sampling), unifying these two approaches.

5. Significance and Contributions

The paper claims to fill a critical gap in the literature by providing a method that is simultaneously:

Flexible: Free from Gaussian or low-rank assumptions.
Distributionally Principled: Optimizes for the joint distribution rather than pointwise errors.
Convex: Anchored in convex optimization, guaranteeing global optima.
Computationally Feasible: Solvable on modest CPUs via structured Newton steps.

The authors position this work as a step toward "principled, distribution-aware treatment of missing data." They note that while the current work focuses on MCAR, the Maximum Likelihood framework naturally extends to Missing At Random (MAR) settings. Future directions mentioned include extending to MAR/MNAR, accelerating anchor selection, and combining PSD models with deep kernels for high-dimensional data like images or text.

The paper concludes that while further engineering is required, the theoretical guarantees and preliminary empirical results suggest strong practical promise for PSD-Impute in scenarios where preserving the statistical properties of the data is paramount.