Year: 2019

Abstract:
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.

heading: 1 Introduction
text: In many machine learning applications sometimes the measurements are noisy or affected by artifacts, resulting in incomplete data samples. Examples of this situation include: self-driving vehicle or robot where objects in the view field can be partially occluded; recommendation systems built from the information gathered by different users where not all the users have fully completed their forms; or medical datasets where typically not all tests can be performed on all patients. A classical approach of supervised learning with missing entries is to apply entry imputation as a preprocessing step, followed by standard training based on these reconstructions (Little & Rubin, 2014). For example, some techniques compute missing entries using statistical methods, such as the “mean”, “regression” and “multiple” imputation methods (Little & Rubin, 2014). Other completion methods are based on machine learning ideas by estimating missing entries through K-nearest neighbor (Batista & Monard, 2002), Self Organization Maps (SOM) (Fessant & Midenet, 2002), multilayer or recurrent neural networks (Yoon & Lee, 1999; Bengio & Gingras, 1995), tensor completion algorithms (Solé-Casals et al., 2018) and others (García-Laencina et al., 2009). In (Huang et al., 2018), a technique for completing the matrix of features was proposed by imposing low-rankness and incorporating the label information into the completion process. A different
approach is to avoid direct imputation of lost inputs and rely on a probabilistic model of input data, learning model parameters through the Expectation Maximization (EM) algorithm and building a Bayesian classification (Ghahramani & Jordan, 1993; Little & Rubin, 2014). However, the latter “model-based” approach has the disadvantage that it requires a good probabilistic data model, which is usually not available, especially for real-world applications such as those involving natural images. On the other hand, during the last few years in the signal processing community, there has been a rapid development of the Compressed Sensing (CS) theory and sparse coding algorithms that exploit the redundancy of natural signals (Candes et al., 2006; Donoho, 2006; Eldar & Kutyniok, 2012; Gregor & LeCun, 2010). A particular case of CS is the signal completion problem, i.e. the reconstruction of signals from incomplete measurements. Several algorithms for matrix and tensor (multidimensional signals) completion have been recently proposed relying on different low-dimensional manifold models that are fit to the available entries, allowing for an extrapolation of the unobserved entries. This category of models ranges from sparse representation of vectors (Aharon et al., 2006; Fadili et al., 2008) and tensors (Caiafa & Cichocki, 2012) to low-rank matrix (Candes & Tao, 2010) and tensor decompositions (Liu et al., 2012; Yuan et al., 2018). The success of sparse representations in many signal processing applications motivated researchers to use dictionary learning techniques for data classification (Mairal et al., 2008), either using class-specific dictionaries (Ramirez et al., 2010; Sprechmann & Sapiro, 2010), or using a single one for all classes (Tosic & Frossard, 2011). In this paper, the goal is to develop a method for training a classifier using incomplete data samples with their labels and to identify the conditions under which such a classifier performs as good as the ideal classifier, i.e. the one that could be obtained from complete observations. We propose to use the sparse representation model for data vectors, and analyze the limitations of the sequential approach, i.e. imputation followed by training (section 2). In section 3 we introduce the simultaneous classification and coding approach, which consists of incorporating a sparse data representation model into a cost function optimized for training the classifier and, at the same time, finding the best sparse representation of the observed data. We provide theoretical conditions under which we can guarantee that the obtained classifier is as good as the ideal classifier. In section 4, a computational method is presented to train a classifier on incomplete data; in section 5, extensive experimental results are presented using synthetic and well known benchmark datasets illustrating the effectiveness of our proposed algorithms; and finally, in section 6, the main conclusions are outlined.

heading: 1.1 Preliminary definitions and problem formulation
text: We assume a supervised learning scenario with vector samples and their labels {xi, yi}, i = 1, 2, . . . I, xi ∈ RN and yi ∈ {0, 1, . . . , C − 1} (C classes), so that we only have access to subsets of entries in each data vector along with their labels, which is denoted by {x̃i, yi}, x̃i ∈ RM with M < N . The success of CS theory is based on the fact that sparse coding of natural signals is nearly ubiquitous. It is found, for example, in the way that neurons encode sensory information (Olshausen & Field, 1996; 1997; Lee et al., 2007). We define the set of all K-sparse vectors ΣLK = {s ∈ RL such that ‖s‖0 ≤ K} (containing at most K non-zero entries) and assume that data vectors xi admit K-sparse representations over an unknown dictionary D ∈ RN×L (L ≥ N), i.e. xi = Dsi, with si ∈ ΣLK . The columns di ∈ RN of a dictionary are called “atoms” because we can express any data vector as a combination of at most K atoms. Without losing generality, to simplify the mathematical treatment, we shuffle the entries of the full vector xi to have the observed values placed in the upper M positions, so that we can write:
xi = [ x̃i zi ] , with zi ∈ R(N−M). (1)
However, our results are valid for any pattern of missing entries for each data vector. Accordingly, we define Di ∈ RN×L as the shuffled version of D, such that it stacks in the top M rows those corresponding to the observed entries:
Di = [ D̃i Ei ] , with D̃i ∈ RM×L and Ei ∈ R(N−M)×L. (2)
Some important uniqueness properties of sparse vector reconstructions are characterized by the Restricted Isometry Property (RIP) of a matrix, which is defined as follows: a matrix A ∈ RN×L satisfies the RIP of order K if there exists δK ∈ [0, 1) such that (1−δK)‖s‖22 ≤ ‖As‖22 ≤ (1+δK)‖s‖22, holds for all s ∈ ΣLK . RIP was introduced in the context of CS by Candes and Tao (Candès & Tao, 2005) and characterizes matrices which are nearly orthonormal when operating on sparse vectors. Let us assume that a perfect classifier pΘ(y | x) in a two classes scenario (yi ∈ {0, 1}), e.g. a logistic regression or deep neural network, can be trained on the complete dataset {xi, yi}, such that 0.5 < pΘ(yi = 1 | xi) ≤ 1.0 and 0 ≤ pΘ(yi = 0 | xi) ≤ 0.5, ∀i = 1, 2, . . . , I, where Θ is the set of trained parameters. We want to develop a method to estimate the classifier parameters Θ̂ using only the incomplete data {x̃i, yi} and to identify the conditions under which such classifier is compatible with the ideal classifier. In the following section we will show that, when data imputation based on sparsity followed by training is used, some limitations are clearly identified.

heading: 2 The problem of training after data imputation
text: First, we will provide some intuition about the limitation of the sparsity-based imputation or “sequential” approach through a toy example. We consider the classification of hand-written digit images belonging to two classes: the numbers “3” and “8”. We will assume that they admit 2-sparse representations over a dictionary and only the right halves of these digits are observed. Let us consider two example vectors xi and xj belonging to classes “3” and “8”, respectively, as shown in Figure 1 (a-d). Here, we are clearly faced with the indiscernible observations problem because our observations of two vectors from different classes are identical (x̃i = x̃j). It is obvious that at least two possible 2-sparse representations for the observed data exist, let’s say x̃i = D̃isi = D̃is′i, with si 6= s′i. Since the solution is not unique, we are not able to correctly reconstruct the original data vectors based only on the observations and the sparsity assumption. If the K-sparse representation of the observations x̃i are unique, then xi can be perfectly reconstructed from the incomplete observations and the classifier can be successfully trained using these reconstructions, but unfortunately this is not the case most of the times. In the particular case where the dictionary D is known in advance, there are some conditions on the sampling patterns based on properties of matrices such as coherence, spark or RIP that can guarantee a correct reconstruction (Eldar & Kutyniok, 2012). However, these conditions are difficult to meet in practice. Moreover, in the more general case where the dictionary D is unknown and needs to be learned from data, it is even more difficult to obtain reconstructions of partially observed data vectors that are well separated. For example, even in the case where complete data vectors are well separated, it could happen that their reconstructions become difficult to separate, leading to suboptimal classifiers. In this paper, motivated by the limitation of the sequential approach, we propose to incorporate the class information of incomplete samples in order to learn simultaneously their sparsest representations and the classifier, such that the classification error of the reconstructions is minimized.

heading: 3 The simultaneous classification and coding approach
text: In the previous section, we showed that sparsity-based imputation methods using only the information on available entries are prone to fail because the non-uniqueness of solutions can make the training of a good classifier an impossible task. It is interesting to note that we could solve this problem by incorporating from the beginning the information of the class to which the incomplete data vectors belong to. Let us consider the toy example of previous section, for which we assumed the classes are linearly separable and each data vector admits a K-sparse representation over a dictionary D ∈ RN×L. A two-dimensional simplified visualization for this example is provided in Figure 1(e). When we apply a sparsity-based reconstruction algorithm on observations x̃i, and x̃j such that x̃i = x̃j and, assuming for now that dictionary D is known, we search for the K-sparse representation that is compatible with the measurements, i.e. we find s ∈ ΣLK such that x̃i = Dis. In this case, there are at least two equally acceptable solutions si and sj corresponding to vectors xi and xj , respectively. If we were to make the wrong decision of assigning sj to xi and si to xj , then the resulting set of reconstructed vectors would not be linearly separable, which is illustrated in Figure 1(f), therefore it would be impossible to find a linear classifier. The key observation here is that, in order to assign the proper sparse representation we could also look at the label information yi and yj , and make the solution unique by discarding any K-sparse representation resulting in not separable vector reconstructions. This suggests that we would need to train the classifier and find the proper representation not only as sparse as possible but also providing the best separation of classes. In other words, we should simultaneously learn the optimal classifier and find sparse representation of observations. Next, we theoretically analyze the case of using a logistic regression classifier and demonstrate that, if we are able to train a classifier on incomplete observations such that their sparse representations are well separated by a hyperplane, then the same classifier correctly separates the original (unobserved) data vectors.

heading: 3.1 Theoretical guarantees in the logistic regression case
text: Let us consider the case of a logistic regression classifier (Hastie et al., 2009) where the set of parameters Θ = {w, b} are a vector w ∈ RN and a scalar (bias) b ∈ R, and a perfect classifier exists if there is a hyperplane that separates both classes, i.e., for each data vector xi: f(xi) = wTxi+b > 0 when yi = 1 and f(xi) ≤ 0 if yi = 0. We investigate the conditions under which a perfect classifier can be trained using incomplete data samples and their labels. By using the same shuffling as in equation (1), we can write the partition of the shuffled coefficients wi ∈ RN as follows:
wi = [ w̃i ui ] , where ui ∈ R(N−M). (3)
Since the classifier is based on the feature f(xi) = wTi xi + b = w̃Ti x̃i + uTi zi + b, the vector ui ∈ R(N−M) contains the weights associated with unobserved entries zi. The following definition introduces a way to measure the amount of discriminative information associated with missing entries. Definition 3.1. Discriminative Missing Information (DMI) µi: Given a classifier {w, b} and a partition of observed/missing entries in sample vector xi such that the shuffled vector of coefficients wi can be partitioned as in eq. (3), we define the DMI for sample xi as: µi = ‖ui‖1 = ∑N−M m=1 |ui(m)|.
Intuitively, if the DMI is small enough, the classification will not strongly depend on the unobserved entries zi and then a classifier could be trained from incomplete data samples. The following theorem establishes precise conditions under which the existence of a classifier obtained from incomplete
data can be guaranteed and thus, a perfect classifier can be successfully trained. The proof can be found in Appendix A Theorem 3.2. Given a dataset {xi, yi}, i = 1, 2, . . . , I with normalized data vectors (‖xi‖ ≤ 1) admitting a K-sparse representation over a dictionary D ∈ RN×L with unit-norm columns and satisfying the RIP of order K with constant δK , and suppose that, we have obtained an alternative dictionary D′ ∈ RN×L also satisfying the RIP of order K with constant δK such that, for the incomplete observation x̃i ∈ RM , the K-sparse representation solution is non-unique, i.e. ∃si, s′i ∈ ΣLK such that x̃i = D̃isi = D̃′is′i, where D̃i, D̃′i ∈ RM×L are the matrices containing the observed rows of D and D′, respectively; si ∈ RL is the vector of coefficients of the true data, i.e. xi = Disi and s′i provides a plausible reconstruction through x̂i = D′is′i with ‖x̂i‖ ≤ 1. If a perfect classifier {wi, b} of the reconstruction x̂i exists such that
> 2Kµi/(1− δK), (4)
with > 0 being the minimum distance of reconstructed data sample to the separating hyperplane, then the full data vector xi is also perfectly separated with this classifier, in other words: f(xi) = wTi xi + b > 0 (≤ 0) if yi = 1 (yi = 0).
It is interesting to note that, supposing that we have obtained a classifier from incomplete data, if we are able to evaluate condition (4) then we can figure out whether such a classifier is optimal by testing the condition of the theorem. However, It is well known that, in general, the RIP constant is difficult to compute in practice. When the dictionary is highly uncorrelated1, i.e. if ρK < 1, then the RIP constant can be written in terms of the correlation coefficients ρ as follows: δK = (K − 1)ρ (Eldar & Kutyniok, 2012), and ρ is easy to compute. Our theorem provides useful insights of the problem. For example, we it suggests the following conditions are desirable: (a) very well separated reconstructed vectors (large ); (b) very sparse model (small K); (c) small norm variability of transformed K-sparse vectors through D (small δK), which can be interpreted as a
1Correlation coefficient is the maximum absolute correlation between any two columns in a normalized dictionary.
quasi-orthonormal basis behaviour (low correlation, for example); and (d), small weights assigned to unobserved entries of xi (small DMI µi).

heading: 4 The proposed method
text: Here, we propose to combine the training of the classifier together with the learning of a dictionary and optimal sparse representations such that reconstructed data vectors are compatible with the observed entries and, at the same time, well separated. To do that we propose to minimize the following global cost function, where we consider that x, x̂ and m are now the original unruffled vectors and the pattern of missing features is not the same for each data sample i :
J(Θ,D, si) = 1 I I∑ i=1 { J0(Θ, x̂i, yi) + λ1J1(D, si) + λ2J2(si) } , (5)
where Θ contains the classifier parameters, i.e. the vector of coefficients and bias for a logistic regression model, or the vector of weights in a deep neural network classifier architecture; D ∈ RN×L (L ≥ N) is a dictionary and si ∈ RL are the representation coefficients such that the reconstructed data vectors are x̂i = Dsi. J0(Θ, x̂i, yi) is a measure of the classification error for sample i. Typically, we use the crossentropy measure, i.e. J0(Θ,x, yi) = − log(pyiΘ (x)), where p yi Θ (xi) is the probability assigned by the classifier to sample xi as belonging to class yi. J1(D, si) is a measure of the error associated with the sparse representation when it is restricted to the observed entries, and is defined as follows: J1(D, si) = MN ‖mi ∗ (xi−Dsi)‖
2, where ∗ stands for the entry-wise product, mi ∈ RN is the observation mask for sample i, with mi(n) ∈ {0, 1} such that mi(n) = 1 or 0 if data entry xi(n) is available or missing, respectively. J2(si) = 1N ‖si‖1 is the `1-norm whose minimization promotes the sparsity of the representation (Candès & Tao, 2005). Finally, the hyper-parameters λ1 and λ2 allow to give more or less importance to the representation accuracy and its sparsity, with respect to the classification error. Intuitively, minimizing equation (5) favors solutions that not only have sparse representations compatible with observed entries, but also provides reconstructions that are best separated in the given classes. To minimize the cost function in equation (5) we propose to alternate between the optimization over {Θ,D} and si (i = 1, 2, . . . , I). As usual, we adopt a first order (gradient based) search of minima, where gradients of functions J0(·), J1(·) and J2(·) are easily derived. Note that in the case of feedforward architectures, the back-propagation technique can be used for the first term J0(·). It is also noted that function J2(·) is not differentiable at zero, so we need to avoid zero crossing in every update. In the case where the given test dataset is also incomplete we can use the dictionary learned during the training phase to find the sparsest representation for the given observations, compute the corresponding full vector reconstructions and apply the classifier to them. The algorithms are presented in Appendix B.

heading: 5 Experimental results
text: We synthetically generated I = 11, 000 (10, 000 training +1, 000 test)K-sparse data vectors xi ∈ R100 using a dictionary D ∈ R100×200 obtained from a Gaussian distribution with normalized atoms, i.e. ‖D(:, l)‖ = 1,∀l. A random hyperplane {w, b} with w ∈ RN , b ∈ R was randomly chosen dividing data vectors into two classes according to the sign of the expression wTxi + b, which defines the value of label yi. We also controlled the degree of separation between the two classes by regenerating all data vectors with distances to the hyperplane lower than a pre-specified threshold d. For each case we generated 10 realizations using different masks and input data. We applied our simultaneous method, with hyperparameters λ1 and λ2 tuned via cross-validation, to train a
logistic regression classifier on the training dataset with randomly distributed missing entries, and compared the obtained Test Accuracy against the following standard sequential methods: Seq. Sparse: reconstructions are obtained by finding the sparsest representation compatible with the observations solving a LASSO problem; Zero Fill (ZF): missing entries are filled with zeros, which is equivalent to ignore unknown values; Mean Unsupervised (MU): missing entries are filled with the mean computed on the available values in the same position in the rest of data samples; Mean Supervised (MS): as in the previous case but the mean is computed on the samples of the same class vectors only; K-Nearest Neighbor (KNN): as in the previous case but the mean is computed on the K-Nearest Neighbors of the same class only. Since the objective here is to compare the performance of obtained classifiers, we computed the accuracy (mean ± standard error of the mean - s.e.m.) on the test dataset using all the methods for two cases of degree of separation between classes (d = 0.0, 0.2), two levels of sparsity (K = 4, 32) and missing values in the training dataset ranging from 25% to 95% as shown in Fig. 2. Our results show that the simultaneous algorithm clearly outperforms all the sequential methods. A t-test was performed to evaluate the statistical significance of the difference between our algorithm (Simul) and MS. It is interesting to note that, when classes has some degree of separation (d = 0.2), using simple methods as computing the mean or filling with zeros, can give acceptable results but not better than our simultaneous algorithm.
We also applied our algorithm to three popular computer vision datasets: MNIST (LeCun et al., 1989) and Fashion (Xiao et al., 2017) consisting of 70,000 images (60,000 train + 10,000 test) each; and CIFAR10 (Krizhevsky & Hinton, 2009) having 60,000 images (50,000 train + 10,000 test). MNIST/Fashion datasets contains 28× 28 gray scale images while CIFAR10 dataset is built upon 32×32×3 color images of different objects. The corresponding data sample size is N = 28×28 = 784 for MNIST/Fashion and N = 32× 32× 3 = 3, 072 for CIFAR10. We considered a dictionary of size 784× 784 (MNIST/Fashion) and 1, 024× 1, 024 (CIFAR10) and applied our simultaneous algorithm to learn the classifier on incomplete data for these datasets using uniform random missing masks at several levels of missing entries (25%, 50% and 75%) and for 50% random partial occlusions for MNIST/Fashion. We used a logistic regression classifier (single layer neural network) and a 4-layer convolutional neural network (CNN4) for the MNIST/Fashion dataset using batch normalization (BN) in the Fashion dataset, while for CIFAR10 dataset, a residual neural network (Resnet-18, (He et al., 2016)) was implemented. Table 1, columns 3rd through 10th, show the accuracy obtained in the test step, when the model was trained on incomplete data and applied to incomplete as well as
to complete test data. The right-most column shows the baseline results obtained by training the model on complete training dataset using the implementations found in 2 and 3. We implemented our algorithm in Pytorch 1.0.0 and ran the experiments on a single GPU. Note that for the logistic regression classifier, we obtained better results when training with incomplete data rather than using complete data. Also, it is highlighted that training on incomplete data, with 50% or less random missing entries, provides the same test accuracy as training on complete data for MNIST dataset. The hyper-parameters λ1 and λ2 were adjusted by cross-validation through a grid-search, as shown in Appendix C. In Fig. 3 we present some selected examples comparing the original images in the MNIST/Fashion test dataset, their observations using random masks and partial occlusions, and reconstructions computed using their sparse representation over a dictionary learned from the incomplete training data. Additional visual examples are provided in Appendix C.

heading: 6 Conclusions
text: We demonstrated that assuming a sparse representation model for input data vectors allows the successful learning of a general classifier on incomplete data. We analyzed the limitations of the classical imputation approach and demonstrated through experiments that our simultaneous algorithm always outperforms sequential methods for various cases such as LASSO, zero-filling, supervised/unsupervised mean and KNN based methods. Our approach is conceptually similar to the work in Ghahramani & Jordan (1993) but, instead of using a probabilistic model, we use sparse coding, which is known to fit very well for natural signals. It is also noted that in Huang & Aviyente (2006), sparse representations of data vectors were incorporated in the optimization process for maximizing the Fisher discriminant in a context of classification. However, no theoretical guarantee was presented in that paper and our approach can be applied to any deep learning classifier architecture by simply incorporating a sparse data model, and adding two regularization terms to the objective function: one to measure the accuracy of the sparse model to explain the observations, and another to favor sparsity of the data representation, which is based on the `1 norm.
2https://github.com/pytorch/examples/tree/master/mnist 3https://github.com/kuangliu/pytorch-cifar

heading: A Proof of Theorem 3.2
text: Proof. Let us first consider the case with yi = 1. We assume that we are able to find a perfect classifier on the reconstructed full data vector such that
f(x̂i) = wTi x̂i + b > > 0, (6)
where x̂i = D′is′i. Now, we note that the K-sparse representation solution given the observation is non-unique, i.e. ∃si, s′i ∈ ΣLK , such that x̃i = D̃isi = D̃′is′i. We assume that si is the true K-sparse vector such that the unobserved full vector is xi = Disi and s′i provides an alternative reconstruction through D′i which explains the observations but x̂i 6= xi. Analogously to equation (1), we can find a partition of the reconstructed vector x̂i as follows:
x̂i = [ x̃i z′i ] = [ D̃′i E′i ] s′i, (7)
where z′i ∈ R(N−M), and we want to prove that f(x̂i) > implies f(xi) > 0, i.e. the original data vector xi (unobserved) is also correctly classified by the logistic regression with parameters {wi, b}. To that end we need to evaluate the following expression:
f(xi) = wTi xi + b = w̃Ti x̃i + uTi zi + b, (8)
where equation (3) was used. If we add and substract uTi z′i and arrange the terms in the previous equation, we get:
f(xi) = w̃Ti x̃i + uTi z′i + b+ uTi (zi − z′i), (9) = f(x̂i) + uTi Eisi − uTi E′is′i. (10)
The first term in the right-hand side of last equation is f(x̂i) > > 0 so if we show that |uTi Eisi − uTi E′is′i| < , then the proof will be complete. To do so, we can write:
|uTi Eisi − uTi E′is′i| ≤ |uTi Eisi|+ |uTi E′is′i|, (11)
and
|uTi Eisi| = ∣∣∣N−M∑ m=1 ui(m) N∑ n=1 Ei(m,n)si(n) ∣∣∣ ≤ N−M∑ m=1 |ui(m)| N∑ n=1 |Ei(m,n)||si(n)|. (12)
Since we assumed normalized vectors ‖xi‖ ≤ 1, by applying the left-hand side of the RIP we obtain: ‖si‖ ≤ 1/(1 − δK), which implies that |si(n)| ≤ 1/(1 − δK). Now, taking into account that |Ei(m,n)| ≤ 1 (columns of D are unit-norm) and using the fact that si ∈ ΣLK we obtain: |uTi Eisi| ≤ K(1−δK) ∑N−M m=1 |ui(m)|; and, similarly, we can obtain that |uTi Eis′i| ≤
K (1−δK) ∑N−M m=1 |ui(m)|. Putting everything together into equation (11) we get:
|uTi Eisi − uTi E′is′i| ≤ 2K
(1− δK) N−M∑ m=1 |ui(m)| < , (13)
where we used that ∑N−M m=1 |ui(m)| < (1−δK) 2K , which completes the proof for the case yi = 1. Similarly, it is strait-forward to prove that, if yi = 0, having f(x̂i) < − < 0 implies that f(xi) < 0.

heading: B Algorithms
text: Here, the pseudocode of the algorithms discussed in the paper are presented. In Algorithm 1, the simultaneous classification and coding method is described. It consists in the iterative alternation between the update of the classifier’s parameters together with the dictionary, and the update of the sparse coefficients for the representation of data observations. Once the classifier is trained, we are able to apply it to incomplete test data by using Algorithm 2, where for fixed Θ and D, we need to find the corresponding sparse coefficients si, compute the full data vector estimations and, finally, apply the classifier. The standard sparsity-based imputation method is presented in Algorithm 3 (sequential approach), which consists of learning first the optimal D and sparse coefficients si compatible with the incomplete observations (dictionary learning and coding phase), followed by the training phase, where the classifier is tuned in order to minimize the classification error of the reconstructed input data vectors x̂i = Dsi.
Algorithm 1 : Simultaneous classification and coding (training on incomplete data) Require: Incomplete data vectors and their labels {x̃i, yi}, i = 1, 2, . . . , I, hyper-parameters α, λ1 and λ2,
number of iterations Niter and update rate σ Ensure: Classifier parameters Θ and sparse representation of full data vectors x̂i = Dsi, ∀i 1: Initialize Θ,D, si,∀i randomly 2: for n ≤ N do 3: Fix si, update Θ and D: 4: Θ = Θ− σ ∂J
∂Θ , D = D− σ ∂J ∂D
5: Normalize columns of matrix D 6: Fix Θ and D, update si, ∀i: 7: ∆i = −σ ∂J∂si , ∀i 8: if si(j)[si(j) + ∆i(j)] < 0 then 9: ∆i(j) = −si(j); avoid zero crossing 10: end if 11: si = si + ∆i, ∀i 12: end for 13: return Θ,D, si, x̂i = Dsi, ∀i
Algorithm 2 : Testing on incomplete data Require: Incomplete data vectors {x̃i}, i = 1, 2, . . . , I, classifier parameters Θ, dictionary D, hyper-
parameters λ1 and λ2, number of iterations Niter and update rate σ Ensure: Class assigned to each vector yi and sparse representation of full data vectors x̂i = Dsi, ∀i 1: Sparse coding stage: for fixed dictionary D find sparse representations of observations x̃i 2: Initialize si,∀i randomly 3: for n ≤ Niter do 4: ∆i = −σ [ λ1
∂J1 ∂si + λ2 ∂J2∂si ] , ∀i
5: if si(j)[si(j) + ∆i(j)] < 0 then 6: ∆i(j) = −si(j); avoid zero crossing 7: end if 8: si = si − σ∆i, ∀i 9: end for 10: x̂i = Dsi,∀i; Compute reconstructions of unobserved vector data xi 11: Classification stage: apply classifier to reconstructions xi 12: yi = arg maxy(p y Θ(x̂)) 13: return Θ, yi, si, x̂i, ∀i
Algorithm 3 : Sequential approach (imputation method) Require: Incomplete data vectors and their labels {x̃i, yi}, i = 1, 2, . . . , I, hyper-parameters α, λ1 and λ2,
number of iterations Niter and update rate σ Ensure: Classifier parameters Θ and sparse representation of full data vectors x̂i = Dsi, ∀i 1: Initialize D, si, ∀i randomly 2: Dictionary learning and coding stage: update D and si 3: for n ≤ N do 4: D = D− σ ∂J1
∂D 5: Normalize columns of matrix D 6: ∆i = −σ [ λ1
∂J1 ∂si + λ2 ∂J2∂si ] , ∀i
7: if si(j)[si(j) + ∆i(j)] < 0 then 8: ∆i(j) = −si(j); avoid zero crossing 9: end if 10: si = si + ∆i, ∀i 11: end for 12: x̂i = Dsi,∀i; Compute reconstructions of unobserved vector data xi 13: Training stage: update Θ 14: for n ≤ N do 15: Θ = Θ− σ ∂J0
∂Θ ; Update Θ: 16: end for 17: return Θ,D, si, x̂i = Dsi, ∀i

heading: C Additional experimental results
text: C.1 Comparison to sequential methods on benchmark datasets
In Table 2, we compare our simultaneous algorithm (Simul) with the following standard sequential methods: Zero Fill - ZF, Mean Supervised - MS, KNN-10, KNN-20, KNN-50 and KNN-100. We computed the Test Accuracy on incomplete data using random masks for MNIST and CIFAR10 datasets. It is noted that the bests result using standard sequential method were obtained with KNN-10 or KNN-20. However, the simultaneous algorithm outperforms KNN in all the cases increasing the performance by approximately 10.% for MNIST and CIFAR10, when the percentage of random missing features is 75%.
C.2 Hyperparameter tunning
In Table 3 and Figure 4 we present the results of the grid search for hyper-parameter tuning on MNIST and CIFAR10 datasets. We fit our model to the training dataset for a range of values of parameters λ1 and λ2 and apply it to the test data set. Figure 4 shows the accuracy obtained for the test dataset with different classifiers and levels of missing entries. We chose the hyper-parameters values such that the test accuracy is maximum, as shown in Table 3.
C.3 Additional visual results
To visually evaluate our results, additional selected examples of original (complete) images of the test dataset in MNIST and Fashion, together with their given incomplete observations and obtained reconstructions, are shown in Figure 5 and Figure 6

Review summaries:
This manuscript studies supervised learning with incomplete observation of the features, assuming a low-rank structure in the full set of features. The work tackles the problem with a global cost function that optimizes the classifier on observations reconstructed with a dictionary penalized jointly for sparse coding. Importantly, the dictionary is optimized both for the supervised-learning task (the classifier) and the sparse coding. The manuscript contributes a theoretical argument showing with sparse-recovery arguments that if the data can be decomposed sparsely, the incomplete feature prediction problem can perform as well as the complete one. Finally, it performs a empirical study on simulated data as well as computer-vision problems with random missing pixels as well as occlusions, and using for the classifier logistic regression as well as classic neural network architectures.

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.