Certified Robust Multiple Imputation via Geodesic Convexity

Multiple imputation fills each missing entry several times with random draws, so that later analyses can report honest error bars. Doing this well for heavy-tailed data, such as sensor recordings, financial returns or clinical labs with outliers, depends on estimating a covariance-like "scatter" matrix from incomplete rows. Two things go wrong in practice. The standard estimator, the Expectation-Maximization (EM) algorithm, can stall or land in poor local optima when much data is missing. And modern imputers mostly return a single best guess rather than draws whose spread reflects the uncertainty.

This note proposes a different way to solve the estimation step. The negative log-likelihood of incomplete rows splits into a Euclidean convex part minus a Euclidean convex part, called a difference-of-convex or DC structure. That split lets a simple closed-form algorithm, the convex-concave procedure (CCCP), handle it. Recent theory shows that CCCP reaches the global optimum at a rate of $O(1/k)$ whenever the objective is also geodesically convex, meaning convex along the curved shortest paths of the space of positive definite matrices. We propose to map out which missingness patterns keep the objective geodesically convex. Inside that region we would build a proper multiple-imputation procedure whose estimation step carries a certificate of global optimality. Outside it, we would measure how often local optima actually hurt the imputations.

Core Claim

Take $n$ rows $x_i$, each with an observed sub-vector $x_{o,i}$ selected by a 0/1 mask $M_i$, and a scatter matrix $\Sigma$. The Gaussian (inner) objective for incomplete data is

$$F(\Sigma)=\sum_{i=1}^n \log\det(M_i\Sigma M_i^\top) + x_{o,i}^\top (M_i\Sigma M_i^\top)^{-1}x_{o,i}.$$

Its first term is concave in Euclidean space and its second term is convex in Euclidean space (it is a matrix-fractional function), so $F$ is DC. CCCP replaces the concave term by its tangent plane and solves a convex surrogate at each step.

Geometrically the picture is mixed. The log-determinant of a masked matrix is geodesically convex, as shown in Conic Geometric Optimization on the Manifold of Positive Definite Matrices. The inverse-of-masked quadratic term is the one that can break geodesic convexity. This is the same obstruction that leaves the masked covariance-averaging result of Geodesically-convex optimization for averaging partially observed covariance matrices proven only for restricted matrix classes.

Our claim has three parts:

  1. There are identifiable families of masks under which $F$ is geodesically convex. Candidates include monotone patterns, where columns drop out in a nested order, and patterns that share a common observed block.
  2. On those families, CCCP inherits the global $O(1/k)$ guarantee of Global optimality for Euclidean CCCP under Riemannian convexity without requiring any Riemannian machinery.
  3. Wrapping this solver in bootstrap-then-draw multiple imputation, with heavy tails handled by multivariate-t or Tyler-type reweighting, gives confidence intervals with better coverage than flexible point imputers at high missingness.

Relation to Prior Work

The closest work is Yger et al.'s masked Riemannian mean (paper). It estimates a single global covariance from partially observed EEG covariances under geodesic convexity, but it explicitly refuses to impute and produces no posterior draws. We use the same mask geometry for a different object, a likelihood over incomplete rows, and for a different goal, proper multiple imputation with Rubin pooling (the standard rule for combining estimates across imputed datasets).

The method comes from two sources:

Neither handles missing coordinates; extending them to missing coordinates is our contribution.

Matrix Manifold Optimization for Gaussian Mixtures motivates the work, because it shows EM slowing badly where manifold methods do not (about 2159 s versus 658 s on image patches). Its latent variables are cluster labels, not missing entries.

On the imputation side, HyperImpute, DiffPuter, RefiDiff and Sinkhorn imputation push accuracy. They are evaluated mainly on RMSE, MAE and Wasserstein distance rather than on interval coverage, which is the gap we target.

Research Program

The work has four parts.

Theory. We will look for sufficient conditions on the mask family $\{M_i\}$ under which $F$, and its t/Tyler reweighted versions, is geodesically convex. We will also construct explicit counterexamples with multiple local optima for patterns that fall outside these conditions. Gap 2 of the literature suggests this is genuinely hard in general, so we commit only to characterizing tractable families. Where the conditions hold, CCCP's global rate depends on the Euclidean Lipschitz constant of the concave term. We will bound that constant in terms of the eigenvalue range of the iterates.

Algorithm. Each CCCP step linearizes $\sum_i \log\det(M_i\Sigma M_i^\top)$ and solves the resulting convex matrix-fractional surrogate. For heavy tails, the outer loop updates per-row weights in the usual elliptical fixed-point way.

Imputation. We draw $m$ bootstrap resamples and estimate $\hat\Sigma^{(b)}$ (and a location parameter) for each, warm-starting from the previous resample. Missing entries are then sampled from the conditional elliptical distribution given the observed entries. Analyses on the $m$ completed datasets are pooled with Rubin's rules.

Diagnostic. For patterns outside the certified family, we run many random starts. We report how often CCCP and EM reach a worse optimum, and by how much that changes the imputations.

Baselines

Naive references. These are complete-case analysis and mean imputation. The file reports that mean imputation stays competitive for linear downstream models in Does imputation matter?, so it is not a straw man. It sets the floor on downstream AUC and on coverage.

Same model, different solver. EM for the identical Gaussian and multivariate-t models is the most direct competitor and is our key ablation. It uses the same model, the same bootstrap and the same draws; only the optimizer changes. It runs under an equal wall-clock budget and an equal number of random restarts. We will count CCCP as beating EM if it reaches a lower objective, or the same objective faster, in high-missingness cells, with a resulting difference in interval coverage. A second ablation, Cholesky-parameterized L-BFGS, tests whether any positive-definite solver suffices. The Gaussian-mixture paper above reports that parameterization to be often more than ten times slower and prone to spurious minima.

Strongest flexible imputers. These are HyperImpute, which reports an 18% RMSE improvement over chained equations across 12 UCI datasets, and DiffPuter, which reports an average 8.10% MAE and 5.64% RMSE improvement over 17 baselines. Neither paper reports absolute values in the file. We will rerun both with their published defaults and equal tuning budgets. For DiffPuter we draw multiple samples so that pooling is possible. We expect to lose to them on point RMSE for non-elliptical data.

What would count as winning. "Beating" these imputers means nominal 95% coverage holding where they undercover. There is no reported result found on Lacuna for coverage of these methods. Chained equations with predictive mean matching (MICE-PMM), MissForest and Sinkhorn imputation complete the comparison.

EEG application. On the EEG data, the masked Riemannian mean is the reference. Our imputed channels must match its classification accuracy, which the authors report as "nearly identical" to the no-missing gold standard without giving a number, while also supplying uncertainty.

Why not just…?

Why not just run EM for a multivariate-t model? This is the real threat. EM is also a monotone majorization method and may find the same optimum almost always. The solver-swap ablation and the multi-start diagnostic settle this directly. If EM rarely stalls, the contribution shrinks to the certificate and the DC view. If EM's known slowdown when much information is missing appears, as it did with overlapping clusters in the Gaussian-mixture paper, the solver matters. We will report either outcome.

Why not just use MICE with predictive mean matching? PMM imputes by borrowing observed values from similar rows, so it tolerates heavy tails and is proper by construction. It is therefore a serious coverage competitor. However, Sinkhorn imputation shows chained regressions collapsing toward conditional means. Under heavy-tailed contamination, its per-column regressions are also not robust. The contaminated-Kotz experiments test whether this costs coverage.

Why not just Gaussianize the columns first and use Gaussian multiple imputation? Marginal transforms fix marginal tails but not joint tail dependence, which is exactly what elliptical scatter captures. We include a rank-transform Gaussian baseline. If it matches us on coverage, the heavy-tail component is unnecessary and we would narrow the claim to the solver.

Proposed Experiments

Synthetic data. Kotz-type and multivariate-t data at $d\in\{4,16,32,64\}$, following Geometric optimisation on positive definite matrices for elliptically contoured distributions, with monotone and arbitrary masks at 10–70% missingness under MCAR, MAR and MNAR. Here the true scatter is known, so we measure:

  • objective gap to the best multi-start optimum;
  • rate of reaching the global optimum;
  • coverage and width of intervals for correlations and regression slopes.

Tabular data. California Housing, Letter, Gesture, Magic and Dry Bean, using the DiffPuter/RefiDiff protocol, both as given and with injected heavy-tailed outliers. Reported metrics are RMSE, MAE, Wasserstein distance and Rubin-pooled interval coverage for a fixed linear model fit on a held-out complete copy.

EEG data. The BCI motor-imagery data with 40–60% channel loss, comparing classifiers on channels imputed by our method against the masked Riemannian mean.

Decisive checks. Two results decide the claim. First, on certified mask families, CCCP should always reach the multi-start best optimum while EM sometimes does not. Second, on contaminated data at 50% or more missingness, our intervals should stay near 95% coverage while HyperImpute and DiffPuter fall below it. If neither holds, the geometric machinery is not earning its keep.