  In this paper, the problem of training a classifier on a dataset with
incomplete features is addressed. We assume that different subsets of features
(random or structured) are available at each data instance. This situation
typically occurs in the applications when not all the features are collected
for every data sample. A new supervised learning method is developed to train a
general classifier, such as a logistic regression or a deep neural network,
using only a subset of features per sample, while assuming sparse
representations of data vectors on an unknown dictionary. Sufficient conditions
are identified, such that, if it is possible to train a classifier on
incomplete observations so that their reconstructions are well separated by a
hyperplane, then the same classifier also correctly separates the original
(unobserved) data samples. Extensive simulation results on synthetic and
well-known datasets are presented that validate our theoretical findings and
demonstrate the effectiveness of the proposed method compared to traditional
data imputation approaches and one state-of-the-art algorithm.
