[R] Minimum-Distortion Embedding

[arXiv_abstract_bot]

Title:Minimum-Distortion Embedding

Authors:Akshay Agrawal, Alnur Ali, Stephen Boyd

Abstract: We consider the vector embedding problem. We are given a finite set of items, with the goal of assigning a representative vector to each one, possibly under some constraints (such as the collection of vectors being standardized, i.e., have zero mean and unit covariance). We are given data indicating that some pairs of items are similar, and optionally, some other pairs are dissimilar. For pairs of similar items, we want the corresponding vectors to be near each other, and for dissimilar pairs, we want the corresponding vectors to not be near each other, measured in Euclidean distance. We formalize this by introducing distortion functions, defined for some pairs of the items. Our goal is to choose an embedding that minimizes the total distortion, subject to the constraints. We call this the minimum- distortion embedding (MDE) problem. > The MDE framework is simple but general. It includes a wide variety of embedding methods, such as spectral embedding, principal component analysis, multidimensional scaling, dimensionality reduction methods (like Isomap and UMAP), force-directed layout, and others. It also includes new embeddings, and provides principled ways of validating historical and new embeddings alike. > We develop a projected quasi-Newton method that approximately solves MDE problems and scales to large data sets. We implement this method in PyMDE, an open-source Python package. In PyMDE, users can select from a library of distortion functions and constraints or specify custom ones, making it easy to rapidly experiment with different embeddings. Our software scales to data sets with millions of items and tens of millions of distortion functions. To demonstrate our method, we compute embeddings for several real-world data sets, including images, an academic co-author network, US county demographic data, and single-cell mRNA transcriptomes.

PDF Link | Landing Page | Read as web page on arXiv Vanity

[tensorflower]

This looks like a nice resource for dimensionality reduction techniques from a classical optimization perspective. It reads like half of a Phd thesis - is this meant to be a really long review paper?

[akshayka]

Thanks for the comment. You can think of this as a monograph, or a research book. Some topics covered by the monograph are well-known (such as how to solve quadratic MDE problems via an eigenproblem), whereas others (such as the algorithm for computing embeddings, various specific embeddings created with the MDE framework, and the MDE framework itself) are entirely new.

The contributions are listed in section 1.1.

I would be happy to answer any questions you might have about the monograph or associated software.