Optimal Recovery of Missing Values for Non-Negative Matrix Factorization

Missing values imputation is often evaluated on some similarity measure between actual and imputed data. However, it may be more meaningful to evaluate downstream algorithm performance after imputation than the imputation itself. We describe a straightforward unsupervised imputation algorithm, a minimax approach based on optimal recovery, and derive probabilistic error bounds on downstream non-negative matrix factorization (NMF). Under certain geometric conditions, we prove upper bounds on NMF relative error, which is the first bound of this type for missing values. We also give probabilistic bounds for the same geometric assumptions. Experiments on image data and biological data show that this theoretically-grounded technique performs as well as or better than other imputation techniques that account for local structure. We also comment on imputation fairness.