Memory-Efficient Sampling for Minimax Distance Measures

Learning a proper representation is usually the first step in every machine learning and data analytic tasks. Some recent representation learning methods have been developed in the context of deep learning [1], which are highly parameterized and require a huge amount of labeled data for training. On the other hand, there are methods that learn a proper representation in an unsupervised way and usually do not require learning free parameters. A category of unsupervised representations and distance measures, called link-based distance [2, 3], take into account all the paths between the objects represented in a graph. These distance measures are often obtained by inverting the Laplacian of the base distance matrix in the context of Markov diffusion kernel [2].