Codes and Expansions (CodEx) Seminar

Abiy Tasissa (Tufts University):
A dual basis approach to classical multidimensional scaling

Given similarity information of a set of objects, a problem in various domains is to find embeddings that best preserve their underlying similarities. A common technique to derive embeddings from similarity information is classical multidimensional scaling (CMDS). CMDS embeds a set of objects in a Euclidean space using their pairwise Euclidean distance matrix as input. The crux of CMDS involves double centering a squared distance matrix and using a truncated eigendecomposition to find the point coordinates. A key aspect of CMDS is the connection of the squared Euclidean matrix to a Gram matrix derived from the points. We explore a dual basis approach to CMDS. We provide an explicit formula for the dual basis and characterize the spectrum of an essential matrix in the dual basis framework. We also establish connections to a related problem in metric nearness.