This paper addresses the problem of training a classifier on a dataset with missing features and its application to a complete or incomplete test dataset. A supervised learning method is developed to train a general classifier, such as a logistic regression or a deep neural network, using only a limited number of observed entries (features), assuming sparse representations of data vectors on an unknown dictionary. The pattern of missing entries is independent of the sample and can be random or structured. The proposed method simultaneously learns the classifier, the dictionary and the corresponding sparse representations of each input data sample. A theoretical analysis is also provided comparing this method with the standard imputation approach, which consists on performing data completion followed by training the classifier based on their reconstructions. The limitations of this last "sequential" approach are identified, and a description of how the proposed new "simultaneous" method can overcome the problem of indiscernible observations is provided. Additionally, it is shown that, if it is possible to train a classifier on incomplete observations so that its reconstructions are well separated by a hyperplane, then the same classifier also correctly separates the original (unobserved) data samples. Extensive simulation results are presented on synthetic and well-known reference datasets that demonstrate the effectiveness of the proposed method compared to traditional data imputation methods.
1. Summary
The authors propose a scheme for simultaneous dictionary learning and classification based on sparse representation of the data within the learned dictionary. Their goal is achieved via optimization of a three-part training cost function that explicitly models the accuracy and sparsity of the sparse model, simultaneously with usual classification error minimization. An alternating optimization algorithm is used, alternating between sparse representations and other parameters.
The problem they want to address with this scheme is training over incomplete/partial feature vectors. A clean theoretical statement is provided that provides conditions under which a classifier trained via partial feature vectors would do no better in terms of accuracy, had it been trained on complete feature vectors. The authors claim this condition can be checked after training, although this ability is not validated/illustrated numerically.
2. Decision and Arguments
Weak Accept
a) Very nice mathematical result and justification. The proof is clear. However, why wasn’t the result used in the numerical section? You claim that the condition (4) can be evaluated to test optimality: how do your trained dictionaries compare to say another dictionary learning scheme? After all, this doesn’t seem to inform your actual learning scheme and is not used to evaluate your results. It would be nice to see a numerical validation/illustration of this result. Also is \delta_K really that easy to compute?
b) The numerical results are good—but lack error bars and comparators. I don’t understand why you considered so many comparators on synthetic data and none on more ‘realistic’ benchmark data.
c) Also I don't feel very satisfied doing image examples, it would be more interesting to work on difficult (eg medical) classification problems with large feature vectors
4. Additional Feedback
a) Very well and clearly written with intuitive examples and clean math. My only suggestion is to clarify in the abstract that there are missing *features*-- when I first read "incomplete data" I think of entire data samples that are missing from the training set. That makes no sense, but it became clear when I got to section 2.
b) Please use markers and dashes etc. with *every* line in your plots. It is hard (or impossible for many) to compare as is with such tiny thin lines.
5. Questions
a) Could you comment on statistical significance of your results? For synthetic data it should be easy to perform the experiments on a number of mask realizations and include error bars.
b) Why no comparators on benchmark datasets?
c) The proof of Thm 3.2 is nice—but how reasonable is the assumption that you have two dictionaries each with the exact same RIP constant \delta_K? Can that property be enforced (even approximately) during training? Or is it trivial that, given one such dictionary, there exists a second one? 
d) See 2.a