Out-of-Sample Embedding with Proximity Data: Projection versus Restricted Reconstruction

Michael W. Trosset, Kaiyi Tan, Minh Tang, Carey E. Priebe · 2025

Read Out-of-Sample Embedding with Proximity Data: Projection versus Restricted Reconstruction by Michael W. Trosset, Kaiyi Tan, Minh Tang, Carey E. Priebe (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-06756.txt.

Introduction

Michael Trosset, Kaiyi Tan, Minh Tang, and Carey Priebe survey methods for placing a new point into an existing map of data in a 2025 statistics study. Maps built from similarity data help analysts see structure, but new items arrive after the map is drawn. Adding a point without redoing everything is the out-of-sample embedding problem, first studied in the nineteen sixties.

The authors show that known kernel methods each follow one of two strategies. Projection extends a familiar formula from principal component analysis. Restricted reconstruction imitates a full reanalysis while holding the old points fixed. Organizing the field this way clarifies which method suits which job.

Catalog record

CREATORMichael W. Trosset, Kaiyi Tan, Minh Tang, Carey E. Priebe
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-06756

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Out-of-Sample Embedding with Proximity Data: Projection versus Restricted Reconstruction Michael W. Trosset, Kaiyi Tan, Minh Tang, Carey E. Priebe Abstract The problem of using proximity (similarity or dissimilarity) data for the purpose of “adding a point to a vector diagram” was first studied by J. C. Gower in 1968. Since then, a number of methods—mostly kernel methods—have been proposed for solving what has come to be called the problem of out-of-sample embedding . We survey the various kernel methods that we have encountered and show that each can be derived from one or the other of two competing strategies: projection or restricted reconstruction . Projection can be analogized to a well-known formula for adding a point to a principal component analysis. Restricted reconstruction poses a different challenge: how to best approximate redoing the entire multivariate analysis while holding fixed the vector diagram that was previously obtained. This strategy results in a nonlinear optimization problem that can be simplified to a unidimensional search. Various circumstances may warrant either projection or restricted reconstruction. Key words: vector diagrams, kernel methods, classical multidimensional scaling. 1 Introduction The embedding method that is now called classical multidimensional scaling (CMDS) was proposed by Torgerson [ 14 ] . A seminal paper by Gower [ 6 ] characterized CMDS as a Q technique, i.e., a technique that depends on a set of points through their pairwise interpoint distances. As such distances can be computed from pairwise inner products, CMDS is, in the parlance of our times, a kernel method . Subsequently, in a pioneering example of what is now termed out-of-sample embedding , Gower [ 7 ] considered the problem of “adding a point to vector diagrams in multivariate analysis” using information about pairwise interpoint distances. Since Gower’s contributions in the 1960s, various researchers have considered out-of-sample embedding problems with both similarity and dissimilarity data. The present investigation was motivated by our efforts to understand and reconcile the differences between the methods proposed in [ 2 , 3 ] and in [ 16 ] . Briefly, the method in [ 16 ] is derived by approximating entries in a certain matrix, resulting in a polynomial objective function that contains a quadratic and a quartic term. The quadratic term results from certain off-diagonal entries, whereas the quartic term results from a diagonal entry. Discarding the quartic term results in a linear least squares problem, the solution of which is the embedding formula proposed by Bengio et al. [ 2 , 3 ] , who explicitly rejected consideration of the diagonal entry and (therefore) the possibility of minimizing the entire quartic polynomial. In contrast, the authors of [ 16 ] long believed the quartic polynomial to be the appropriate objective function and viewed its quadratic term as a simplifying approximation of it. Only recently have we come to understand that each solution can be derived from (different) first principles. By a vector diagram , Gower [ 7 ] meant a Cartesian representation of n points in d -dimensional Euclidean space. Key to our development is the distinction between the representation space and the configuration of n points within it. Out-of-sample embedding fixes a configuration of points in the sense that it fixes the corresponding set of pairwise interpoint distances. It may or may not fix the space in which this configuration is represented. As it turns out, both [ 7 ] and [ 2 , 3 ] fix the representation space, whereas [ 16 ] does not. We elaborate on the distinction between representation space and configuration of points in Section 2 . We identify two fundamental embedding strategies and illustrate their consequences in the familiar case of classical principal component analysis (PCA). Following previous exposition in an unpublished technical report [ 12 ] , we demonstrate in Section 3 that most well-known methods for out-of-sample embedding, including [ 7 ] and [ 3 ] , follow from the first strategy. In Section 4 we implement the second strategy, culminating in the method proposed in [ 16 ] . The second set of methods present computational challenges, which we discuss in Section 5 . Section 6 discusses how a user might choose a suitable strategy. 2 Two Fundamental Strategies 1. Projection. Construct an ambient space that contains the original representation space. Position the new point in the ambient space, then project it into the representation space. 2. Restricted Reconstruction. Suppose that the original configuration was obtained by optimizing a function of n points. Minimize the analogous function of n+1 points, subject to an additional constraint that fixes the interpoint distances between the original n points, to obtain a new configuration of n+1 points. Figure 1: Two fundamental strategies for out-of-sample embedding. Both strategies fix the original configuration of points. The projection strategy also fixes the representation space. Unlike the projection strategy, the restricted reconstruction strategy depends on the method used to construct the original configuration. Figure 1 provides brief summaries of two strategies for out-of-sample embedding. To appreciate the nuances of these strategies, suppose that we have used PCA to construct a d -dimensional representation of feature vectors \xi_{1},\ldots,\xi_{n}\in\Re^{q} . We subsequently observe an additional feature vector \eta\in\Re^{q} . How might we construct a d -dimensional representation of \xi_{1},\ldots,\xi_{n},\eta ? Of course, we might simply set \xi_{n+1}=\eta and apply PCA to \xi_{1},\ldots,\xi_{n+1} . We refer to this practice as reconstruction . But perhaps we have already used the original representation for some purpose and wish to preserve some or all of its features. This is the consideration that motivates the problem of out-of-sample embedding . PCA may be characterized as the method of finding the d -dimensional affine linear subspace (hyperplane) {\mathcal{H}}\subset\Re^{q} that minimizes the sum of the squared Euclidean distances of the \xi_{i} from {\mathcal{H}} . (Other characterizations are possible; another turns out to be more useful when embedding proximity data.) PCA adopts a particular coordinate system for {\mathcal{H}} , thereby identifying it with \Re^{d} . This is the representation space constructed by PCA, and the x_{1},\ldots,x_{n}\in\Re^{d} that correspond to \xi_{1},\ldots,\xi_{n}\in\Re^{q} (often called the PC scores) constitute a configuration of points in representation space. Reconstruction, i.e., application of PCA to \xi_{1},\ldots,\xi_{n+1}\in\Re^{q} , results in a new approximating hyperplane, hence a new representation space, and a new configuration of points. Suppose, however, that we wish to add a point y\in\Re^{d} that corresponds to \eta\in\Re^{q} while holding fixed both the representation space and the configuration of points within it. Fixing the representation space means fixing {\mathcal{H}} , so the natural way to represent \eta is to project \eta into {\mathcal{H}} , obtaining \hat{\eta} , then represent \hat{\eta} in PC coordinates, obtaining \hat{y}\in\Re^{d} . This construction illustrates the projection strategy for out-of-sample embedding. Alternatively, suppose that we are prepared to adopt a new representation space but wish to hold fixed the representation of \xi_{1},\ldots,\xi_{n} , e.g., by fixing the pairwise interpoint distances of x_{1},\ldots,x_{n}\in\Re^{d} . This is reconstruction subject to a constraint, hence the phrase restricted reconstruction . The restricted reconstruction strategy for out-of-sample embedding answers the following question: how does PCA perform on \xi_{1},\ldots,\xi_{n+1}\in\Re^{q} if the representation of \xi_{1},\ldots,\xi_{n} is fixed? The answer depends on how one chooses to characterize PCA. A simple example illustrates the distinction between projection and restricted

Read the complete text