Abstract
For many machine learning tasks, the input data lie on a low-dimensional manifold embedded in a highdimensional space and, because of this high-dimensional structure, most algorithms inefficient. The typical solution is to reduce the dimension of the input data using a standard dimension reduction algorithms such as ISOMAP, LAPLACIAN EIGENMAPS or LLES. This approach, however, does not always work in practice as these algorithms require that we have somewhat ideal data. Unfortunately, most data sets either have missing entries or unacceptably noisy values. That is, real data are far from ideal and we cannot use these algorithms directly.
Abstract
In this paper, we focus on the case when we have missing data. Some techniques, such as matrix completion, can be used to fill in missing data but these methods do not capture the non-linear structure of the manifold. Here, we present a new algorithm MR-MISSING that extends these previous algorithms and can be used to compute low dimensional representation on data sets with missing entries. We demonstrate the effectiveness of our algorithm by running three different experiments. We visually verify the effectiveness of our algorithm on synthetic manifolds, we numerically compare our projections against those computed by first filling in data using nlPCA and mDRUR on the MNIST data set, and we also show that we can do classification on MNIST with missing data. We also provide a theoretical guarantee for MR-MISSING under some simplifying assumptions.
I. INTRODUCTION
Many real world data sets can be reasonably modeled as low dimensional manifolds embedded in much higher dimensional spaces, and for these models, a class of techniques play a crucial role in revealing or learning these intrinsic manifolds. This class includes ISOMAP [1] , Local Linear Embedding (LLE) [2] , HESSIAN-LLE [3] , MAXI-MUM VARIANCE UNFOLDING [4] , KNN-DIFFUSION [5] , and LAPLACIAN EIGENMAP [6] . All of these algorithms have the basic structure shown in Figure 1 . Given data, we compute a distance matrix (alternatively, we are given a distance matrix), from which we determine neighborhoods about each data point. Some of these algorithms find the K closest points to each data point and others determine the data points in an ✏ neighborhood about each data point. Each algorithm then uses this neighborhood information to compute local Euclidean coordinates in some fashion (i.e., to learn the underlying manifold) and, thus, to determine a low-dimensional representation for the data.
I. INTRODUCTION
Each of these algorithms assumes that the given or computed distance matrix adheres to a metric. To see the importance of using a distance matrix that satisfies a metric with these algorithms, we show in Figure 2 the impact upon the manifold returned by ISOMAP when we corrupt or perturb the distance matrix so that it no longer satisfies a metric. Note that these algorithms are robust to (small) perturbations in the data but not in the distances among the data points. In the top left figure (a), we have the original swissroll dataset with 2,000 points. It is a two dimensional manifold embedded in three dimensions. When we run ISOMAP on the true distance matrix, we see in the upper right figure (b), an "unrolled" version of the intrinsic manifold. To corrupt the distance matrix, we add i.i.d. Gaussian noise ⇠ N (0, 0.01) to each non diagonal entry of the distance matrix. We then replace all negative entries with zero and preserve symmetry by averaging the corrupted distance matrix with its transpose. The perturbed distances may not satisfy the triangle inequality and, hence, the corrupted distances may not adhere to a metric.
I. INTRODUCTION
The lower left figure (c) is the embedding from the corrupted distance matrix. It is considerably different from the original embedding, points are missing, and there is no apparent lower dimensional manifold phillipsbrenda@example.com. Because the distances do not satisfy a metric, the points all collapse to one location and cannot be distinguished in the figure. In the lower right figure (d), we first repair the corrupted distance matrix, using a metric repair algorithm from [7] , and then embed the data using ISOMAP. The resulting embedding is much closer to the original embedding, with some minor distortion. Thus, we can see that unless the distance matrix satisfies a metric, dimension reduction or manifold embedding algorithms fail catastrophically. 
A. Problem Set Up
This example illustrates the main problem we address: if we have either missing data or missing or corrupted entries in the distance matrix and we assume that the data come from an intrinsic low dimensional manifold, compute a low dimensional representation of the imputed or corrected data set. One such approach for missing data is to complete the data matrix using a matrix completion algorithm. These algorithms assume that the data matrix is approximately low rank and fills in the missing entries accordingly. These algorithms fit the data to a linear subspace rather than an intrinsically nonlinear embedding and may miss key features of the data. Other methods that learn the intrinsic low dimensional structure in a data set impute missing data values in the original space but one cannot use other, potentially better, algorithms for the embeddings. Our method aims to repair the distance matrix of the data, so as to extend existing embedding algorithms such as ISOMAP and LAPLACIAN EIGENMAPS to handle missing data or corrupted distances.
A. Problem Set Up
To be precise, let X be the high-dimensional data set and D the distance or dissimilarity matrix amongst the data points, and consider the following four problem scenarios:
A. Problem Set Up
1) The data set X has corrupted entries, 2) The data set X has missing entries, 3) The dissimilarity matrix D has corrupted entries, or 4) The dissimilarity matrix D has missing entries.
A. Problem Set Up
In the first model X has added noise and many of the traditional algorithms are robust and produce satisfactory results. Hence, we shall focus on the second scenario where X has missing entries. The second scenario covers the last two (as missing data corrupt the distances between points) and we sketch the applications of our methods to these scenarios and leave a more in depth analysis of those models as future work.
B. Previous work
There are two main approaches to filling in missing manifold data that we summarize below. Both methods strive to learn, in an unsupervised fashion, a representation of the data and then to use that learned representation to fill in the missing values. The first method employs a lowdimensional representation as an intermediary step in the overall data representation while the second method directly learns a low-dimensional representation. We will also discuss how matrix completion algorithms could be used for model 4
B. Previous work
Non-linear Principle Component Analysis (nlPCA) [8] . This method is a non-linear analog to principle component analysis. The idea is to use a five-layer neural network with architectural dimensions n ⇥ m ⇥ d ⇥ m ⇥ n, where n is the input dimension, m is usually bigger than n, and d is the desired dimension of the embedding. We train the neural network to learn the identity map so that the middle layer with d neurons is the low-dimensional representation of the data. To extend to missing data, the network is also trained to reproduce the input data but during the training procedure, any gradients that depend on missing values are disregarded. Then, to fill in the missing data, the data with missing values is input to the network and the output values are used to fill in any missing data.
B. Previous work
Missing Data Recovery through Unsupervised Regression (mDRUR) [9] . The second major method is the missing data recovery through unsupervised learning (mDRUR). Similarly to the nlPCA algorithm, this algorithm is an extension of a dimensionality reduction algorithm known as dimensionality reduction through unsupervised learning (DRUR). Using the notation of [9] , let Y be the high dimensional representation of the data and X the low dimensional representation. Then we have two maps f, F such that Y = f (X) and X = F (Y ). To learn the low-dimensional representation, we minimize arg min
B. Previous work
where R(f ) and R(F ) are regularization terms. To fill in missing data, we first use a linear matrix completion method to fill in the missing values, then we use a spectral method to compute X. Finally, we learn the low-dimensional representation as above and optimize over the missing values of Y to fill in the missing data. Both algorithms are primarily dimensionality reduction algorithms and, as such, we must first fix the lower dimension and then solve an optimization problem. In most real world applications we do not know the optimal low dimension and, hence, in order to fill in the missing data, we must first find this dimension and then fill in the data, rather than separating these two tasks. Furthermore, the imputed values depend on the computed, specific reduced representation; we cannot avail ourselves of a variety of dimension reduction algorithms and obtain what we hope to be a consistent or robust approximation of the missing values.
B. Previous work
Euclidean distance matrix and metric completion. One might be tempted to restrict our distances to Euclidean distances as it is well known [10] that Euclidean distance matrices (with squared Euclidean distance entries) are low rank matrices with rank at most r + 2 if r is the dimension of the space in which the points lie. Hence, the problem of Euclidean matrix completion can be solved using standard low rank matrix completion algorithms. Additionally, this specific problem has been further studied with many successful algorithms in [11] , [12] , [13] .
B. Previous work
In some cases we want our original data to follow a non-Euclidean metric. For example, it is has been shown that for the MNIST dataset if we use the tangent distance metric instead of Euclidean, then k nearest neighbor classifiers have better performance. In this case, if we have the local neighborhood information for the data we can still run ISOMAP and other various algorithms to get lower dimensional representations. Gower [10] showed that these matrices are either low rank (with the same low rank condition as before) or have full rank. In the case that they have full rank, we can no longer use matrix completion algorithms.
B. Previous work
Even when we have a low rank matrix, we only know we can complete these matrices with high probability if the entries present are sampled according to a certain distribution. Finally, even if we can successfully apply these matrix completion algorithms, there are no guarantees that the resulting distance matrices satisfy a metric.
C. Our approach and contributions
We focus on the second scenario. We separate the problem into three steps. First we estimate distances between the data points, we then correct these distances so that they adhere to a metric, finally we run a suitable dimension reduction algorithm. We use the Increase Only Metric Repair (IOMR) algorithm in Gilbert and Jain [7] to repair the inaccurate distance matrices. As we can see in Figure 1 , all of the dimension reduction algorithms depend on the local distances and not on the actual data points themselves. Hence, filling in the missing data is both costly and unnecessary. Instead, we first estimate the distance matrix from the incomplete data, then we correct it. This approach has two advantages over the previous methods • No parameters: Our algorithm has no parameters that need tuning. Hence making it faster and easier to train compared to nlPCA and mDRUR. Additionally, our algorithm is quadratic is the number of dimensions. Hence, its performance scales well with number of dimensions. • Accuracy: The manner in which we estimate the distances and then correct them is geared to exactly preserve the local structure.
C. Our approach and contributions
Remark 1: For the most general version of scenario three, fast approximation algorithms for the general metric repair problem do not currently exists. A class of approximation algorithms can be found in Gilbert and Sonthalia [14] .
C. Our approach and contributions
The rest of the paper is organized as follows, Section 2 presents background knowledge, Section 3 presents our algorithms for correcting a corrupted distance matrix so as to produce an accurate low dimensional embedding of a data set. We focus specifically on missing data. Section 4 provides our experimental results.
II. BACKGROUND

A. Manifolds and Geodesic distances
Definition 1: M ⇢ R n is called a d dimensional manifold is for all x 2 M there exists an ✏ > 0 such that there if a continuous bijective function f from N = {y 2 M : kx yk < ✏} to R d such that the inverse is continuous as well.
A. Manifolds and Geodesic distances
Intuitively the above definition says that if we look at a d-dimensional manifold M and if we zoom in close enough to any point then it looks like we are in R d . For example the swiss roll (from the introduction) is a two-dimensional manifold because near any point it looks like a plane. As we can see from the definition itself the local structure of a manifold is important. Hence, all dimensionality reduction algorithms start by computing the local neighborhood of each point. This is done in one of two ways:
A. Manifolds and Geodesic distances
• determine the k nearest neighbors, or • compute the neighbors within some distance ✏ These local neighborhoods then overlap to describe the general manifold structure. Hence, having this correct local structure is crucial for the success of any of the dimensionality reduction algorithms.
A. Manifolds and Geodesic distances
In this paper we will we focus on using ISOMAP (though we could have picked any of the other algorithms). For ISOMAP once we have the graph (i.e., two data points are adjacent if one is in the local neighborhood of the other) we then compute the shortest distance (along this graph) between all the points. This usually done using the Floyd Warshall algorithm. We store these distances in a matrixD. These distances are known as geodesic distances. They are the distances we want between our data points in the low dimensional representation.
B. Multidimensional Scaling
The technique used to go from the inferred distance matrixD to an actual embedding is called multidimensional scaling (MDS) and we include this discussion to complete Section IV. An important point to note is that the points we recover are not unique, since rotating and translating the embedding will not change the pairwise distances between the points.
B. Multidimensional Scaling
Suppose we have n by n distance matrixD. We want to find points x 1 , . . . , x n in some d dimensional Euclidean
B. Multidimensional Scaling
where 1 n is the n dimensional vector of all 1s and is the Hadamard product, which we multiply the two matrices coordinate wise.. Then using the fact that the points are translation invariant (we can assume the centroid of x 1 , . . . , x n is the origin) using which it can be shown that S ij would then be x i · x j . This matrix is now positive semi-definite, hence has an eigenvalue decomposition
B. Multidimensional Scaling
Where ⇤ is a diagonal matrix of the eigenvalues. If we then define X = U ⇤ 0.5 . Then this is our embedding. We get a d dimensional embedding by using only the biggest d eigenvalues.
C. Metric Repair
Gilbert and Jain in [7] defined the sparse metric repair problem. They define Sym n (R 0 ) to be the set of positive real symmetric matrices. More generally, let us define Sym n (S) to be the set of symmetric matrices with entries drawn from S. Then, for any matrix D 2 Sym n (R 0 ) we say it satisfies a metric if the diagonal of D is all 0s and for all i, j, k we have that
C. Metric Repair
The sparse metric repair problem seeks a solution to the following optimization problem: Given D 2 Sym n (R 0 ) and
C. Metric Repair
(1) where k·k p is the vector`0 is the pseudonorm that counts the number of non-zero entries. In [7] , they define three variants of the corresponding to three different: S = R 0 decrease only metric repair (DOMR), S = R 0 increase only metric repair (IOMR), and S = R, which is simply called metric repair or MR. In general, for any given set S we shall refer to problem as MR(S) For the rest of paper we will focus on the increase only case and use the following algorithm from [7] :
C. Metric Repair
for k 1 to n do 4:
C. Metric Repair
returnD D While Gilbert and Jain showed that IOMR-FIXED worked empirically, they could not provide any guarantees on its performance nor did they demonstrate how it could be used for actual applications. Gilbert and Sonthalia [14] provides a more in-depth analysis of a generalized problem. One of their results is to show that the problem of increase only metric repair is NP-Hard for even simple sets S. They also provide several approximation algorithms for this problem and more general variants.
C. Metric Repair
As it was noted in the [7] , one could relax Equation (1) to a convex optimization problem by minimizing kP k 1 instead of kP k 0 . Gilbert and Jain used various different convex optimization methods, and while these methods produce satisfactory results, they were extremely slow. Hence, we stick with IOMR-FIXED. The speed of the optimization algorithms will not scale well with the number of data points as that the output solution D 0 = D + P needs to be a metric. In particular, for any i, j, k we need the entries for D 0 to satisfy the triangle inequality. Thus, if we have n data points, we have O(n 3 ) constraints. Even for simple applications where we have 1000 data points, the optimization problem has O(10 9 ) constraints.
III. METRIC REPAIR ON MANIFOLDS
In our model scenario, we are given an incomplete data set X and a matrix Q that specifies the support of the known entries. We present an algorithm to compute a (potentially corrupted) distance matrix from the incomplete data and then use metric repair to correct the perturbed distances. The idea is to ignore missing entries when calculating the distances between two points as in [15] . Thus, we have the following algorithm.
Algorithm 2 MR-missing
Require: X Input data, Q support of the data (Q ij = 1 if and only if X ij is present. Q ij = 0 otherwise) 1: function MR-MISSING(X,Q) 2: D = zeros(n, n) 3: for i 1 to n do 4:
Algorithm 2 MR-missing
for j 1 to n do 5: ISOMAP(D + P )
Algorithm 2 MR-missing
As we will see in Section IV, this algorithm works well in practice and, in this section, we provide theoretical analysis of its performance in a model setting. Before doing so, let us develop some intuition about the algorithm. To analyze how well the algorithm performs, supposed we had a probabilistic model with the following two assumptions: 1) if two data points are far apart, then our estimated distance is small with low probability; and, 2) if two data points are far and our estimated distance is small, then, with high probability, we increase this distance during metric repair. Assuming the above two assumptions hold, we argue that MR-MISSING maintains the local structure of the data. When we compute the distance between two data points so as to ignore missing entries, the estimated distance is smaller than the true distance. Thus, if two points are initially close, then they remain close together. This is beneficial since the crucial structure for all manifold learning algorithms is the local distances. It could happen, that because data are missing, two points x, y that were not close together initially have small inferred distance. Then, by assumption (1), this would happen with small probability and, by assumption (2), we would fix this distance with high probability. Finally, since the metric has been repaired and we have, with high probability preserved the local structure of the data set, ISOMAP produces an embedding consistent with that of the full data set. That is, with high probability, the algorithm preserves the local structures and guarantees that all the distances adhere to a metric, and we conclude the low dimensional embeddings calculated with this repaired distance matrix to preserve most of the manifold structure of the data.
A. Theory Result
There are two steps to our algorithm. The first step is estimating distances between points with missing coordinates. The second is increasing these distances so that the distances adhere to a metric. In this subsection, we are going to analyze the effectiveness of MR-MISSING by showing that in the following model if two points are well separated then the distance estimated by step 1 is large with high probability.
A. Theory Result
In this model our data consists of two Gaussians clusters in R n with means µ 1 , µ 2 2 R (all coordinates for a data point from one cluster have the same mean) and covariances ⌃ 1 = ⌃ 2 = 0.5I n , where I n is the n dimensional identity matrix.
A. Theory Result
We assume that, for any data point x, each of its n coordinates is present independently with probability p. Under these conditions, we want to show that with high probability our algorithm preserves local neighborhoods.
A. Theory Result
For notational connivence let us define d p (x, y) to be the distance between x, y estimated by step 1 of MR-MISSING when each coordinate is present independently with probability p.
A. Theory Result
Before we can state and prove our result we need a few lemmas first Lemma 1 (Birgé 2001, [16] ): For all D 1, if X =
A. Theory Result
then, all 0 < c < D + , we have that
A. Theory Result
. Lemma 2 (Hoeffding's Inequality): If we have n i.i.d. variables X 1 , . . . , X n such that X i = 1 with probability p and X i = 0 with probability 1 p, then, for all ✏ > 0, we have that
A. Theory Result
Lemma 1 allows us to bound the tail of a non-centralsquared distribution and Lemma 2 allows us to bound the probability that we have too much data missing. Combining these two Lemmas, we have the following theorem. Theorem 1: Suppose X ⇠ N(µ 1 1, 0.5I) and Y ⇠ N (µ 2 1, 0.5I) are two points in R n such that each coordinate of X, Y is present with probability p. If µ = µ 1 µ 2 and q = p 2 , then, for all q(1 + µ 2 ) > ✏ > 0 and q(1+µ 2 ) ✏ (1+µ 2 ) > > 0, we have that
A. Theory Result
Proof: Let Z = X Y . Then Z 1 , . . . , Z n are i.i.d Gaussian random variables with mean µ = µ 1 µ 2 and variance 1. We know from MR-MISSING that we use the entry Z i to calculate the distance between X, Y if and only if both X i and Y i are present. This happens with probability p 2 , which we define as q = p 2 . Thus, we have the entry Z i with probability q.
A. Theory Result
Let q(1 + µ 2 ) > ✏ > 0. We want to show that the probability that the distance calculated by step 1 of MR-MISSING is greater than ✏ is small. To do this, we use Hoeffding's inequality to divide into two cases, one in which we observe a large number of coordinates and one a few coordinates. We shall see that the case when we observe a few coordinates occurs with low probability and we obtain a bound on the distance. We will then see that for the case where we see a large number of coordinates, then the distance is large with high probability.
A. Theory Result
. Then, by definition of ✏, we see that q > > 0. Let K be the number of entries we observe and, by Lemma 2, we have that
A. Theory Result
For notational convenience, let D = (q )n and consider two cases.
A. Theory Result
That is, we observe fewer than D entries. Then, by Hoeffding's Inequality, we know that this happens with probability at most e 2 2 n .
A. Theory Result
Thus we have that
A. Theory Result
That is, we observe a large number of entries. Let us condition on the actual value of K. Suppose that K = k and we have observed entries Z i1 , . . . , Z i k . We know these entries are i.i.d. with mean µ and we want to bound
A. Theory Result
.
A. Theory Result
In this case we see that the overall probability that we have a small distance, given that K D, is
A. Theory Result
The next thing to observe is that p k is monotone decreasing in k because each Z i is non-negative with non-zero mean. Thus, we have the following upper bound
A. Theory Result
Now, we can use our tail bound for the -squared distribution with c = ✏n, D = (q )n, and = Dµ 2 . Thus, we have
A. Theory Result
Combining both cases, we see that the probability that the distance calculated is less than ✏n is at most
A. Theory Result
Let us take a closer look at the effect of the various parameters on the above probability:
A. Theory Result
• The dimension n of the data: As n increases, we have an exponential decrease in the probability that two points from the two Gaussian clouds have distance smaller than ✏n. Thus, we expect our algorithm to work better for high dimensional data. • The mean squared distance between the clusters µ 2 n: As µ 2 increases (i.e., as the data are better separated), the probability that they have small distance in the presence of missing data gets smaller. This also allows for a wider range of ✏ and . • The probability of a coordinate being present p: First, we note that as p increases, q increases. Then, as q increases (i.e., we have more data present), the probability that two points from the two Gaussian clouds have distance smaller than ✏n decreases. Additionally, for all q > 0, we have a feasible range for ✏. Thus, for any percentage of missing data, if we have enough data points, we can use MR-MISSING for dimensionality reduction.
A. Theory Result
The final parameter has a range of values it can take on and we could optimize over it to get the smallest possible bound.
A. Theory Result
Finally, as noted before, our method of estimating distances only decreases distances. Thus, points that were close together stay close together. Now by the above the theorem we see that if points were initially far apart, then our method of estimating distances keeps them far apart with high probability.
A. Theory Result
Then, since our method of repairing the metric only increases the distance, we see that we maintain the local neighborhood structure with high probability, in this data model.
IV. EXPERIMENTS
Let us now verify that our algorithm does will in practice through a variety of experiments. Dimensionality reduction and clustering algorithms are normally used when we have unlabeled date (i.e., in the regime of unsupervised learning). In this case figuring out the ground truth can be difficult. Hence, there are no natural numerical metrics on unlabeled data that we can readily use to evaluate our algorithm. Hence, decided to test the effectiveness of our algorithm on both unlabeled and labeled data in a variety of different experiments.
A. Unlabeled Data
For unlabeled data, we tested the performance of MR-MISSING on synthetic manifolds visually as well as compared our algorithms against nlPCA and mDRUR numerically.
A. Unlabeled Data
1) Synthetic Manifolds: Let us first define the six manifolds we tested our algorithm on. For notational convenience, let U (n, m) be an n⇥m matrix with entries drawn uniformly at random from [0, 1] and let N (n, m) be an n ⇥ m matrix with entries are drawn from a standard Gaussian distribution. Finally, we shall write f.(X) to represent applying f coordinate wise to all elements of X. We generated the six synthetic manifolds as follows: In each case we start with 2000 data points on the high dimensional representations of the six manifolds M 1 , . . . , M 6 . We then compute low dimensional representations using the full data set and using data set with missing entries as follows. We ran ISOMAP with the true distance matrices to get the low dimensional projections, as depicted on the left hand side of Figures 3 and 4 . We then picked 40% on the entries uniformly at random, declared these entries to be missing, and used MR-MISSING to get the projections depicted on right of Figures 3 and 4 . We used the same ISOMAP parameters across both algorithms. We then compared how there projections looked visually. In most cases our algorithm did well in preserving the general structure of the low dimensional projection as can be seen in Figures 3  and 4 .
A. Unlabeled Data
In each case, we can see that MR-MISSING does well at preserving not only the general shape of the low dimensional, but also in maintaining the relative ordering of the data points with some minor distortion. Therefore, it is also useful for applications that use these projections for clustering and classification. We test this in the next.
A. Unlabeled Data
2) MR-missing vs nlPCA vs mDRUR: We compare MR-MISSING against Non Linear PCA (nlPCA) and Missing Data Recovery Through Unsupervised Regression (mDRUR) on the MNIST data set. nlPCA and mDRUR are both methods to complete missing data on a manifold, whereas our algorithm is a method to estimate and correct distances so that we can use dimensionality reduction algorithms on data sets with missing entries. So, we must compare all of these algorithms on low dimensional representations. To that end, for the nlPCA and mDRUR algorithm, we first filled in missing data in the MNIST data set and then used ISOMAP to determine the low dimensional projection. To quantify how well these representations do we compared these representations to the low dimensional representation computed by using ISOMAP with the complete data set. We kept the parameters for ISOMAP fixed across all four projections. We compared these projections in the following manner. Let P be the ground truth projection andP the projection computed by any algorithm on the data set with missing entries. We first aligned the two projections, using the Procrustes method because the representation returned by Multidimensional Scaling is unique only up to rotation and translation. Additionally, since we care only about the relative positions of the points and not the magnitude of the distances between them, we also allowed for scaling. That is, to ascertain the quality of the projectionP , we want to find
A. Unlabeled Data
where X is the data matrix that we are trying to align Y with.
A. Unlabeled Data
Here, each row is a data point, ↵ is the scaling constant, Q is our orthogonal rotation matrix and µ is our translational vector and 1 m is the vector of all ones in m dimensions. This problem has a closed form solution in terms of the SVD decomposition of X. Finally, if we letP be our new scaled, rotated, and translated projection that best aligns with the ground truth projection P , then we calculate the relative error between the projections as
A. Unlabeled Data
The data set we used is the first 1000 images of the digit 0,1,2,3,4 from MNIST. For nlPCA we used a 784 ⇥ 800 ⇥ 12⇥800⇥784 structure. For mDRUR we initially filled in the matrix using the singular value projection method. We then calculated an initial 12 dimensional low representation using LAPLACIAN EIGENMAPS. We can see the relative errors in Table 1 .
A. Unlabeled Data
We can see that in all cases mDRUR does the worst so we will focus on comparing MR-MISSING versus nlPCA. When we have 40% missing data MR-MISSING does better than the nlPCA version in all cases. For 50% missing we see that nlPCA does better or as well in some cases with MR-MISSING still doing better in a majority of the cases. For 60% missing the algorithms have similar results and nlPCA does better in the case of 70% missing data. Thus, Additionally we can see that as the dimension increases both methods have worse errors. We posit that this occurs because to compute a rank k projection P (P ,P ) we are using the first k singular values of the distance matrix computed by ISOMAP (see section 1B). Hence our estimation the distance matrix does better at preserving the larger singular values as compared to the smaller values. Let us also take a closer look at what our algorithm does in the case of 70% missing data. See the two dimensional representations shown in Figure 5 .
A. Unlabeled Data
(a) ISOMAP with actual distances (b) ISOMAP with repaired distances Fig. 5 : Two-dimensional projections of the first 1000 images of the digits 0,1,2,3,4 from MNIST using ISOMAP with true distance and ISOMAP with distance obtained from MR-MISSING when 70% of the data is missing.
A. Unlabeled Data
We see that we have a different looking projection, but the projection still does well in maintaining the clustering of the data, as we predicted theoretically in Section 3. In the next subsection, we test the effectiveness of these computed low dimensional representations for classification.
B. Labeled Data
One of the main reasons to find a lower dimensional data representation is to efficiently carry out standard machine learning tasks, such as classification. In this subsection, we test the usefulness of the low dimensional representations produced by MR-MISSING for classification. We calculate a 100-dimensional representation of 500 images of each digit from MNIST. This is our training set. We then used the equation from [17] to calculate the projections for an additional 100 images of each digit. This is our test set. Then, for classification we trained an SVM (Kernel: RBF, C = 200, = 0.0000002) for classification. We then obtained the following classification accuracy for various amounts of missing data shown in Table 2 . We also ran this classifier with no missing data as a benchmark. As we expect, with missing data, we do not have as high accuracy as we do with complete data, but from our experiments we see that even in the presence of missing data, ISOMAP with MR-MISSING produces embeddings on which we still have reasonably high accuracy. Particularly in the cases of 40% and 50% missing data, we have accuracy of over 90% and the accuracy does not drop off drastically until we get to 80% missing data. It is important to note that both the test and the training set had data points missing. We see that MR-MISSING does a good job of maintaining the original clusters of the data.
V. CONCLUSION AND FUTURE WORK
As we can see MR-MISSING has excellent experimental results. That is, MR-MISSING is a method by which we can use traditional dimensionality reduction algorithms in the presence of missing data. While we have some theoretical justification for this observed performance, more work needs to be done in exploring the effectiveness of our method of estimating distances in more general scenarios.
V. CONCLUSION AND FUTURE WORK
Additionally, we did not consider in a detailed fashion other corrupted data or distance models. One approach to metric completion (model scenario 4) is to take the given distances, treat these as edges on a graph, and run APSP on this graph to fill in the missing distances. It is possible that APSP modifies some of the given distance information while also filling in the missing values. Thus, a natural question is are there conditions on the given data that guarantee that an APSP algorithm will not change the given data while simultaneously repairing those that are missing? Gilbert and Sonthalia [14] provide some analysis which suggests a more general version of metric repair may be applied to the metric problem.
V. CONCLUSION AND FUTURE WORK
Theorem 2: (Gilbert and Sonthalia [14] ) Suppose G is a weighted chordal graph such that no three cycle is broken. Then if we run APSP on this graph, the shortest path between any two adjacent vertices, is the edge connecting them.
V. CONCLUSION AND FUTURE WORK
Corollary 1: (Gilbert and Sonthalia [14] ) If the given distances form a graph G, where G is a weighted chordal graph such that no 3 cycle is broken, then this partial distance information can be completed into a metric.
V. CONCLUSION AND FUTURE WORK
The condition that the given data satisfy a chordal graph appears in Positive Semi-Definite matrix completion and Euclidean distance matrix completion as well. While the first theorem tells us when we can use APSP to complete a metric, it doesn't tell us what properties this new metric satisfies. Hence, the problem of completing a distance matrix for a general metric warrants further investigation.
V. CONCLUSION AND FUTURE WORK
In the model scenario 3, when we have a corrupted distance matrix, we may not always want to increase distances. In some cases we might want to decrease distances. Hence, we would need a general metric repair algorithm. Fan, et al. [18] present an algorithm that runs in ✓(n 6 ) and Gilbert and Sonthalia [14] present an alternative algorithm that runs in O(n 5 ). Both of these algorithms are impractical and cannot be used on large data sets. Developing faster algorithms for general metric repair and ascertaining the usefulness of such methods for corrupted distance matrices are two avenues for future work.

{'paper_id': '59618938', 'title': 'Unsupervised Metric Learning in Presence of Missing Data', 's2_url': 'https://api.semanticscholar.org/CorpusID:59618938', 'source': 'S2ORC'}