  It has long been a recognized problem that many datasets contain significant
levels of missing numerical data. A potentially critical predicate for
application of machine learning methods to datasets involves addressing this
problem. However, this is a challenging task. In this paper, we apply a
recently developed multi-level stochastic optimization approach to the problem
of imputation in massive medical records. The approach is based on
computational applied mathematics techniques and is highly accurate. In
particular, for the Best Linear Unbiased Predictor (BLUP) this multi-level
formulation is exact, and is significantly faster and more numerically stable.
This permits practical application of Kriging methods to data imputation
problems for massive datasets. We test this approach on data from the National
Inpatient Sample (NIS) data records, Healthcare Cost and Utilization Project
(HCUP), Agency for Healthcare Research and Quality. Numerical results show that
the multi-level method significantly outperforms current approaches and is
numerically robust. It has superior accuracy as compared with methods
recommended in the recent report from HCUP. Benchmark tests show up to 75%
reductions in error. Furthermore, the results are also superior to recent state
of the art methods such as discriminative deep learning.
