Metric and non-metric proximity transformations at linear costs

• We propose a linear time and memory efficient approach for converting low rank dissimilarity matrices to similarity matrices and vice versa.
• Our approach is applicable for proximities obtained from non-metric proximity measures (indefinite kernels, non-standard dissimilarity measures).
• The presented approach also comprises a generalization of Landmark MDS – the presented approach is in general more accurate and flexible than Landmark MDS.
• We provide an alternative derivation of the Nyström approximation together with a convergence proof, also for indefinite kernels not given in the workshop paper as a core element of the approach.

Domain specific (dis-)similarity or proximity measures used e.g. in alignment algorithms of sequence data are popular to analyze complicated data objects and to cover domain specific data properties. Without an underlying vector space these data are given as pairwise (dis-)similarities only. The few available methods for such data focus widely on similarities and do not scale to large datasets. Kernel methods are very effective for metric similarity matrices, also at large scale, but costly transformations are necessary starting with non-metric (dis-) similarities. We propose an integrative combination of Nyström approximation, potential double centering and eigenvalue correction to obtain valid kernel matrices at linear costs in the number of samples. By the proposed approach effective kernel approaches become accessible. Experiments with several larger (dis-)similarity datasets show that the proposed method achieves much better runtime performance than the standard strategy while keeping competitive model accuracy. The main contribution is an efficient and accurate technique, to convert (potentially non-metric) large scale dissimilarity matrices into approximated positive semi-definite kernel matrices at linear costs.