PaperlayerView exact revision on arXiv

Source-linked AI summary

Hybrid Methods for Robust Tabular Data Imputation

Jinwei Li, Michelle Bruch, Daniel Tenbrinck

arXiv:2609.39613v1cs.LG

TL;DR

Missing-data imputation matters because downstream analyses depend on imputation quality, while iterative random-forest methods can be computationally costly. The paper combines low-rank initialization with one random-forest refinement, and reports competitive quality with substantial speedups over MissForest.

  • Problem

    Imputation quality affects downstream analyses, while iterative random-forest methods such as MissForest require repeated model fitting and can be computationally costly.

    Source: §1 · pp. 1–2

  • Method

    NuclearForest uses adaptive SVT and SoftForest uses SoftImpute for low-rank initialization, followed by one random-forest refinement step.

    Source: §1 · p. 3

  • Results

    Across real-data settings, the hybrids offer competitive imputation quality versus iterative random-forest baselines; NuclearForest and SoftForest achieve 5.81× and 9.52× speedups over MissForest in one representative experiment.

    Source: §1 · p. 3, §4 · p. 9

  • Takeaways & Limitations

    The results support low-rank warm starts followed by a single random-forest pass as a practical, computationally efficient approach for preserving structural information during tabular imputation.

    Source: §4 · p. 10

    Matrix completion is ill-posed without assumptions about the complete matrix; the approach uses the standard assumption that it has low-rank structure.

    Source: §2 · p. 3

Abstract

from arXiv · show

Missing data are a fundamental challenge in statistical analysis and machine learning, as the choice of imputation method substantially impacts downstream inference. In this work, we propose two hybrid imputation methods called NuclearForest and SoftForest, which combine nuclear-norm-based low-rank initialization using Singular Value Thresholding (SVT) and SoftImpute, respectively, with a non-iterative Random Forest refinement. For the SVT-based component, we further introduce an adaptive step-size rule, prove adaptive step-size bounds, and establish convergence for the corresponding zero-initialized iteration. The low-rank initialization provides a structured warm start that captures the global covariance patterns in the data, while the subsequent Random Forest step recovers residual nonlinear signals encoding local dependencies. We conduct an extensive benchmark on diverse datasets from different application domains, comparing the proposed methods with seven established imputation methods under the Missing Completely at Random (MCAR), Missing at Random (MAR), and Missing Not at Random (MNAR) mechanisms across varying missingness rates. Our results demonstrate that NuclearForest and SoftForest match or exceed the imputation fidelity of state-of-the-art iterative methods such as MissForest, while significantly reducing computational cost. In particular, they achieve speedups of approximately 5.81 times and 9.52 times over MissForest by replacing iterative cycles with a single refinement step. Our approach effectively exploits the low-rank structure of real-world tabular data and accommodates mixed-type variables, providing an efficient and robust solution for data imputation in bioinformatics, economics, and beyond.

1 INTRODUCTION

The introduction motivates faster, reliable imputation for real-world tabular data and presents hybrids that use low-rank starts before random-forest refinement.

1 INTRODUCTION

  • Imputation quality directly affects downstream analyses, while MissForest repeatedly fits forests until convergence, making repeated use across experimental conditions computationally costly.Its simple univariate initialization also lacks explicit global structural assumptions.Source: §1 · pp. 1–2
  • Low-rank completion exploits latent structure in real-world and omics data, but may miss nonlinear dependencies.The introduction links omics feature correlations to biological pathways and shared regulatory mechanisms.Source: §1 · p. 2
  • The benchmark tests metabolomics and housing data under MCAR, MAR, and MNAR settings, including left-censored MNAR in metabolomics and separate MCAR/MAR conditions in housing.MCAR and MAR are combined for the metabolomics benchmark because they are often difficult to distinguish in MS-based data.Source: §1 · pp. 2–3
  • Evaluation spans masked-entry reconstruction, structural preservation, group-level signals, distributional similarity, and downstream predictive utility across nine imputation methods.Measures include NRMSE and sum of ranks, Procrustes analysis, group-difference correlations, Gower’s distance, and predictive R2 degradation.Source: §1 · p. 3
  • Adaptive SVT combines column-mean warm starting with error-responsive step sizes; bounds and convergence for the corresponding zero-initialized iteration are proved, and ablations indicate both changes improve quality.The step-size adjustment responds to relative observed-entry reconstruction error.Source: §1 · p. 3
  • NuclearForest and SoftForest deliver competitive imputation quality against iterative random-forest baselines, with 5.81× and 9.52× speedups over MissForest in one representative experiment.Both methods use a single random-forest refinement step after low-rank initialization.Source: §1 · p. 3

2 METHODOLOGY

The methods combine low-rank matrix completion with random-forest regression: NuclearForest uses SVT and SoftForest uses SoftImpute, each followed by one refinement pass. The section describes the matrix-completion formulations and an adaptive step-size variant of SVT.

2 METHODOLOGY

  • Matrix completion seeks a complete matrix that matches observed entries; assuming low rank makes recovery tractable through nuclear-norm minimization.The rank-minimization problem is nonconvex and NP-hard, motivating its replacement with a convex relaxation.Source: §2 · pp. 3–4
  • SVT alternates singular-value thresholding of the primal estimate with a dual update driven by the observed-entry residual.The iteration applies X^k = S_τ(Y^{k−1}) and updates Y using the step size and observed-entry residual.Source: §2 · p. 4
  • The improved SVT variant starts from column means and adapts its step size to observed-entry reconstruction error, while keeping the threshold fixed.It contracts δ_k by 0.9 when error rises and expands it by 1.05 when error falls, up to 2; under a finite-contraction condition, step sizes stay bounded away from zero.Source: §2 · p. 4
  • SoftImpute minimizes observed-entry reconstruction error plus a nuclear-norm penalty, alternating imputation from the current iterate with singular-value thresholding.The penalty promotes low-rank structure, and the objective values decrease monotonically toward the optimal value at rate O(1/k).Source: §2 · pp. 4–5
  • In the MissForest-style baseline, each incomplete column is predicted from observed rows using the other columns, and round-robin updates continue until a stopping condition.The procedure stops at a maximum iteration count or when consecutive completed matrices differ by less than a predefined tolerance.Source: §2 · p. 5
  • NuclearForest uses SVT and SoftForest uses SoftImpute for low-rank initialization, followed by one random-forest refinement pass that models nonlinear dependencies in missing entries.The low-rank stage captures global correlation structure; the forest acts as a nonlinear residual corrector, while observed entries remain fixed.Source: §2 · p. 5

3 EXPERIMENTS AND RESULTS

The benchmark evaluates nine imputation methods on metabolomics and housing data under MCAR, MAR, and MNAR settings. The hybrids are competitive across settings, with large runtime advantages over MissForest in the metabolomics MCAR/MAR experiment.

Experimental design

  • The benchmark uses ten repeated runs with independently regenerated missing masks and evaluates metabolomics and housing under distinct MCAR/MAR and MNAR designs.Metabolomics uses uniform random masking for MCAR/MAR and left-censored missingness for MNAR; housing MAR uses conditional logistic masking.Source: §3 · pp. 5–6

Ablations and SVD implementation in the SVT

  • Both zero initialization and adaptive step size improve imputation quality, and the full SVT method performs best overall under MCAR/MAR.On the dense 198 × 131 metabolomics matrix, full SVD is 2.89× faster than partial SVD with indistinguishable imputation error.Source: §3 · p. 6, Figure 1 · p. 6

Metabolomics dataset under MCAR/MAR missingness

  • ~9.52× and ~5.81× speedups over MissForest were achieved by SoftForest and NuclearForest, respectively, on metabolomics under MCAR/MAR.The benchmark reports runtime in seconds as mean ± standard deviation.Source: §3 · p. 6, Table 1 · p. 7
  • On metabolomics under MCAR/MAR, MissForest is slightly better on NRMSE at 20%–60% missingness, while NuclearForest leads selected PCA, log-p, and PLS comparisons.NuclearForest has the lowest PCA Procrustes distance at 10%, 20%, and 40%, highest Pearson log-p correlation at 20% and 90%, and lowest PLS Procrustes distance at 10%–30%.Source: §3 · p. 6, Figure 2 · p. 7

Metabolomics dataset under MNAR missingness

  • Under metabolomics MNAR, SoftImpute has the lowest SOR except at 20% missingness, while Half-min leads the other three reported metrics.The authors relate Half-min’s performance to the left-censored design, where missing values are low-abundance entries below feature-specific thresholds.Source: Figure 3 · p. 7, §3 · p. 8

Housing dataset under MCAR and MAR missingness

  • NuclearForest and SoftForest perform strongly across housing metrics at low-to-moderate missingness, while MissForest and SoftImpute become more favorable at higher missingness.The results vary by metric and missingness mechanism; under MAR, SoftForest leads most PCA/PLS structure-preservation settings.Source: Figure 4 · p. 8, §3 · p. 9

4 CONCLUSION

NuclearForest and SoftForest pair low-rank initialization with one random-forest refinement pass, offering a favorable accuracy–efficiency trade-off across the metabolomics and housing benchmarks. Their gains do not fully extend to left-censored MNAR, where Half-min is aligned with the missingness mechanism.

Conclusion

  • Across metabolomics and housing benchmarks, the hybrid methods offer a favorable accuracy–efficiency trade-off, with substantial speedups over MissForest in metabolomics MCAR/MAR.SoftForest and NuclearForest achieve approximately 9.52× and 5.81× speedups, respectively.Source: §4 · pp. 9–10
  • The hybrids are most effective when the missingness pattern preserves enough global correlation structure for informative low-rank initialization.Their gains do not fully extend to left-censored MNAR, where Half-min is well aligned with the mechanism.Source: §4 · p. 9
  • The authors identify fuller theoretical characterization and low-rank warm starts for other nonlinear refiners, including neural-network imputers, as future work.Source: §4 · p. 10

A ADAPTIVE SVT VARIANT AND STEP-SIZE ANALYSIS

The section presents an SVT variant that adapts its step size to observed-entry reconstruction error and analyzes conditions for boundedness and convergence. It also provides the algorithms for SVT, adaptive SVT, and SoftImpute.

A ADAPTIVE SVT VARIANT AND STEP-SIZE ANALYSIS

  • The adaptive SVT step size shrinks by 0.9 when reconstruction error increases and grows by 1.05 when error decreases, subject to an upper bound.The original SVT uses a fixed step size, whereas this variant adapts it based on relative observed-entry reconstruction error.Source: A ADAPTIVE SVT VARIANT AND STEP-SIZE… · p. 11, B ALGORITHMS · p. 15
  • With finitely many contraction steps, the adaptive step sizes remain bounded away from zero and their sum diverges.These bounds provide the step-size conditions used in the convergence analysis.Source: A ADAPTIVE SVT VARIANT AND STEP-SIZE… · pp. 11, 13
  • Under the same finite-contraction condition, the corresponding zero-initialized adaptive SVT iteration converges to a unique solution.The section also states a convergence-rate bound for that iteration.Source: A ADAPTIVE SVT VARIANT AND STEP-SIZE… · p. 14

B ALGORITHMS

  • The algorithm listings provide standard SVT, warm-start adaptive SVT, and SoftImpute procedures for partially observed matrices.The adaptive listing updates its step size according to whether observed-entry reconstruction error rises or falls.Source: B ALGORITHMS · p. 15

C EXPERIMENTAL DETAILS

The section summarizes experimental implementation details, with tables for additional-experiment hyperparameters, global settings, and total runtime.

  • The experimental-details section summarizes the hyperparameters and implementation details used in the experiments.Source: C EXPERIMENTAL DETAILS · p. 16
  • Additional-experiment settings include the fixed-step configuration for SVT_OGpaper and the soft-thresholded SVD formulation for SoftImpute.Source: Table 3 · p. 16
  • The section provides tables of global experimental settings and total wall-clock runtime.Source: Table 4 · p. 16, Table 5 · p. 16

D.1 RESULTS INCLUDING THE ORIGINAL SVT METHOD

The appendix compares original and adapted SVT-based methods across specified datasets and missingness settings, and includes a separate comparison of SVD implementations.

D.1 RESULTS INCLUDING THE ORIGINAL SVT METHOD

  • Figures compare SVT_OGpaper and NF_OGpaper with adapted SVT and NuclearForest on metabolomics and housing data under the listed missingness settings.The metabolomics figure covers joint MCAR/MAR and MNAR; the housing figure covers MCAR and MAR.Source: Figure 5 · p. 17, Figure 6 · p. 18
  • A housing-dataset figure compares imputation methods under MCAR and MAR.Source: Figure 7 · p. 18

D.2 PARTIAL SVD VERSUS FULL SVD IN SVT

  • The SVD comparison assesses partial versus full SVD in SVT and tabulates runtime and four imputation metrics.The metric tables cover NRMSE, PCA Procrustes distance, Pearson correlation of −log10 p, and PLS Procrustes distance.Source: §D.2 · pp. 18–19, Table 6 · p. 19, Table 7 · p. 19

D.3 ABLATION STUDY

The ablation section compares SVT design variants across missingness levels and lists quality metrics and runtime for the variants.

  • The ablation isolates column-mean warm starting and adaptive versus fixed step size, comparing variants across missingness levels.Source: §D.3 · p. 20, Figure 8 · p. 20
  • The ablation tables report NRMSE, PCA Procrustes distance, PLS Procrustes distance, and Pearson log-p correlation across missing rates.Source: Table 11 · p. 21, Table 12 · p. 21, Table 13 · p. 21
  • A separate table reports runtime for the SVT ablation variants in seconds as mean ± standard deviation.Source: Table 15 · p. 22

D.4 RUNTIME DECOMPOSITION AND SCALING

The section reports runtime scaling on rank-10 Gaussian matrices and decomposes runtime by stage for a metabolomics dataset. It excludes mask generation from imputation runtime.

D.4 RUNTIME DECOMPOSITION AND SCALING

  • Table 16 decomposes runtime stages on the 198 × 130 metabolomics dataset under MCAR, with times averaged over three runs.Its labels define Pre as Preprocess, SVD as one SVD, NF as NuclearForest, MF as MissForest, and SI as SoftImpute.Source: Table 16 · p. 22
  • Mask generation is part of the evaluation protocol, not the imputation procedure, and is excluded from reported imputation runtime.Source: §D.4 · p. 22
  • At 2000 rows and 1000 columns, runtime reached 6885.7 s, with RF refinement accounting for 87.0% of total runtime.With 130 columns, doubling rows from 1000 to 2000 approximately doubled runtime from 66.0 s to 130.0 s.Source: §D.4 · p. 22

E.1 MCAR/MAR RESULTS ON THE METABOLOMICS DATASET

The appendix presents metric-specific results tables for metabolomics and housing datasets across missingness settings. It also provides runtime comparison tables for the two datasets and their evaluated settings.

E.1 MCAR/MAR RESULTS ON THE METABOLOMICS DATASET

E.2 MNAR RESULTS ON THE METABOLOMICS DATASET

E.3 MCAR RESULTS ON THE HOUSING DATASET

E.4 MAR RESULTS ON THE HOUSING DATASET

E.5 RUNTIME COMPARISON

Loading 2609.39613v1…