REVIEW 1 major objections 4 minor 18 references
Out-of-Sample Embedding with Proximity Data: Projection versus Restricted Reconstruction
T0 review · 1 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash
Pith's one-line read Every surveyed kernel method for out-of-sample embedding is one of two strategies: projection or restricted reconstruction.
desk verdict The projection-versus-restricted-reconstruction taxonomy is a genuinely useful way to organize this literature, but the claimed one-dimensional search in Section 5 is wrong in the singular case—including the paper's own Example 2. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the augmented centered similarity matrix $\bar{B}_+=\begin{bmatrix} \bar{B} & b \\ b^{\top} & \beta \end{bmatrix}$, where $\bar{B}$ is the rank-$d$ approximation of the original centered kernel, $b$ holds the centered similarities between the new object and the original $n$, and $\beta$ is the centered self-similarity of the new object. Projection approximates $b$ only; restricted reconstruction approximates both $b$ and $\beta$. The carrying device is the equivalence between the constrained problem $\min\{2\|Xy-b\|^2:y^{\top}y=r^2\}$ and the regularized least-squares problem with penalty $\lambda$, so that the quartic objective can be minimized by sweeping $\lambda$ and, when $\beta>\hat{r}^2$, by searching over negative penalties in intervals cut at eigenvalues of $-X^{\top}X$.
What would settle it
Run Example 2 with a small nonzero perturbation to $b=0$ and compare the true global minimizer of $2\|Xy-b\|^2+(y^{\top}y-400)^2$ with the value $\hat{y}(\lambda^*)$ produced by the one-dimensional search; if the search's minimizer does not match the quartic's global minimizer as the perturbation tends to zero, the reduction fails in the singular case.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is a unification: the out-of-sample embedding formulas scattered through the kernel-methods literature are all derivations of either projection or restricted reconstruction. Projection treats the previous embedding as fixed in its ambient space; the new point is represented by the coordinates of its projection onto that space, which for centered kernels is $y=(X^{\top}X)^{-1}X^{\top}b$ with $b$ the vector of centered similarities to the original points. Restricted reconstruction instead keeps only the pairwise distances among the original points and solves for the new point by minimizing the full rank-$d$ inner-product approximation error, giving the objective $2\|Xy-b\|^2+(y^{\top}y-\beta)^2$. The quartic term is exactly the diagonal entry $\beta=\tilde\gamma(\eta,\eta)$, which projection ignores. In Example 2 the two strategies disagree: a new object far from all original objects is placed at the centroid by projection but far away by restricted reconstruction.
Load-bearing premise
The paper assumes that the global minimizer of the quartic objective can always be obtained as the solution of a penalized least-squares problem at some optimally chosen penalty strength, even when the penalized system becomes singular; its Example 2 reaches the reported minimizer through a singular limit that is not formalized.
Editorial extensions
If this is right
- The widely used kernel out-of-sample formula is projection; rejecting the diagonal term is not an approximation inside a common objective, it is a different principle.
- Restricted reconstruction's global optimum can be found by one-dimensional search, so the more demanding strategy is computationally tractable even though the objective is quartic.
- When the new object's self-similarity $\beta$ is smaller than the squared norm of the projection $\hat{r}^2$, the penalty is positive and computation is stable; when $\beta>\hat{r}^2$, one searches negative penalties and must handle singular $X^{\top}X+\lambda I$.
- For several new objects, projection discards all pairwise proximities among the new objects, while restricted reconstruction approximates them, so multi-point extensions favor restricted reconstruction.
- Choosing between strategies is a modeling choice about whether differences orthogonal to the original representation space matter; neither strategy is universally superior.
Reading between the lines
- The same two-strategy contrast should apply to out-of-sample extensions of non-kernel embeddings, because any embedding defined by optimizing pairwise distances can be re-optimized with the original configuration fixed; the paper sketches this for raw-stress MDS but does not claim a general theorem.
- A practical test of the distinction is anomaly preservation: for a new object far from all original objects, projection places it where the original map can see it, while restricted reconstruction keeps it far away; outlier-detection tasks could choose between the two accordingly.
- The negative-penalty branch can be read as a self-consistency constraint for extending a kernel to a new point, and formalizing the singular-limit argument would let general-purpose trust-region solvers handle the global minimization directly.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper proposes a unifying taxonomy for out-of-sample embedding methods from proximity data. The authors distinguish projection, which fixes the representation space and projects the new object into it, from restricted reconstruction, which keeps the original configuration fixed while re-embedding all n+1 objects. They show that several published formulas (Bengio et al., Anderson-Robinson, Landmark MDS) are projection methods, whereas the Trosset-Priebe method follows from restricted reconstruction and reduces to minimizing 2||Xy-b||^2 + (y^T y - beta)^2 (Eq. 10). Section 5 claims this quartic can be minimized by a one-dimensional search over a ridge parameter lambda. Two examples demonstrate that projection and restricted reconstruction can produce very different embeddings.
Significance. The conceptual dichotomy is valuable and gives a clean way to understand the relationship between the Bengio et al. formula and the Trosset-Priebe formula. The derivation of Eq. (10) from the Eckart-Young theorem is self-contained, and the equivalence of the projection formulas is carefully demonstrated. There are no fitted parameters, and the two examples are simple enough to check by hand. The main weakness is the computational reduction in Section 5, which fails on the paper's own Example 2; this does not undermine the taxonomy but requires correction before the paper can be accepted.
major comments (1)
- [Section 5, Eq. (15), Example 2] The step 'Let lambda* denote the global minimizer of phi, so that y_hat(lambda*) = y*' is not justified and is contradicted by Example 2. In that example b = 0 and X^T X = diag(50, 32), so for every lambda for which the regularized linear system is invertible, y_hat(lambda) = 0 and phi(lambda) = 160000; no value of lambda yields the reported global minimizer y* = (0, +/- sqrt(368)). The only lambda at which a regularized minimizer can have nonzero norm is a singular value of the coefficient matrix, where y_hat(lambda) is not unique; selecting the element of that minimizer set equal to y* requires already knowing y*. The standard trust-region/ridge equivalence therefore does not apply in this hard case, and the abstract's claim that restricted reconstruction 'can be simplified to a unidimensional search' is unsupported for a case the paper itself presents. A correct repair would minimize over the radius r explicitly, solving min_{||y||=r} 2||b - Xy||^2 + (beta - r^2)^2 for each r, or handle the singular lambda values rigorously.
minor comments (4)
- [Section 3, text near Eq. (8)] The matrix L# = Sigma_d^{-1} U_d^T is described as the pseudoinverse of X^T = Sigma_d U_d^T. This is incorrect: it is the pseudoinverse of X. The pseudoinverse of X^T is U_d Sigma_d^{-1}. The subsequent manipulation is correct with L# = X^+, but the terminology should be corrected.
- [Section 5, Eq. (13)] For the objective f(y) + lambda ||y||^2 with f(y) = 2||b - Xy||^2, the stationary equation is (2 X^T X + lambda I)y = 2 X^T b, not (X^T X + lambda I)y = X^T b. The discrepancy is only a rescaling of lambda, but as written the equation does not follow from the stated objective.
- [Section 4, first paragraph] The phrase 'finding the finding the d-dimensional hyperplane' contains a duplicated word.
- [Section 5, paragraph after Eq. (14)] The statement 'It will typically be the case that the d columns of X are linearly independent' should include the standing assumption n >= d; otherwise full column rank is impossible.
Circularity Check
No circularity: the two-strategy taxonomy is derived from independently stated optimality principles; self-citations are provenance only.
full rationale
The paper's central claim is taxonomic: kernel out-of-sample methods either fix the representation space (projection) or re-optimize subject to a fixed original configuration (restricted reconstruction). The projection formulas are re-derived from PCA geometry in Section 3, and the equivalences among (4), (7), and (8) are shown algebraically, not imported as black boxes. Restricted reconstruction is derived in Section 4 from Theorem 1, an Eckart-Young optimality property of PCA, yielding objective (10); no parameter is fitted and no prediction is made from fitted values. The author-self citations [12] and [16] are used as provenance: [12] is cited as previous exposition of Section 3, but Section 3's derivation is self-contained, and [16] is cited as the origin of the restricted-reconstruction objective, which is re-derived here from Theorem 1. Neither citation is load-bearing for the derivation chain. The Section 5 assertion 'Let λ* denote the global minimizer of φ, so that ŷ(λ*) = y*' is not justified for singular X^T X+λI; Example 2 has ŷ(λ)=0 for invertible λ while y*=(0,±√368), so the reduction to a one-dimensional ridge search is a technical completeness concern, not a circularity. No step exhibits an input defined in terms of an output, a fitted parameter renamed as a prediction, or a result forced by self-citation. The appropriate score is 0.
Assumptions & free parameters
assumptions (3)
- standard math Eckart-Young: for a symmetric matrix B, U_d Sigma_d^2 U_d^T is the best rank-d Frobenius-norm approximation.
- standard math Trust-region/ridge equivalence: for any global solution of min f(y) subject to y^T y = r^2, there exists lambda such that y minimizes f(y) + lambda y^T y.
- domain assumption The d columns of X are linearly independent (full rank).
Cite this review
Pith. "Pith review of Out-of-Sample Embedding with Proximity Data: Projection versus Restricted Reconstruction." pith.science (2026). https://pith.science/paper/ARCHJKR6
@misc{pith2026250506756,
author = {Pith},
title = {Pith review of: Out-of-Sample Embedding with Proximity Data: Projection versus Restricted Reconstruction},
year = {2026},
howpublished = {\url{https://pith.science/paper/ARCHJKR6}},
note = {Machine review of arXiv:2505.06756}
}
read the original 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.
Figures
Reference graph
Works this paper leans on
-
[1]
M. J. Anderson and J. Robinson. Generalized discriminant analysis based on distances. Australian & New Zealand Journal of Statistics , 45:301–318, 2003. 17
work page 2003
-
[2]
Y. Bengio, J.-F. Paiement, and P. Vincent. Out-of-sample extensions for LLE, Isomap, MDS, eigenmaps, and spectral clustering. Technical Report 1238, D´ epartement d’Informatique et Recherche Op´ erationelle, Universit´ e de Montr´ eal, Montr´ eal, Qu´ ebec, Canada, July 2003
work page 2003
-
[3]
Y. Bengio, J.-F. Paiement, P. Vincent, O. Delalleau, N. Le Roux, and M. Ouimet. Out-of-sample extensions for LLE, Isomap, MDS, eigenmaps, and spectral clus- tering. In S. T. S. Becker and K. Obermayer, editors, Advances in Neural In- formation Processing Systems 15 , pages 177–184. MIT Press, Cambridge, MA, 2003
work page 2003
-
[4]
V. de Silva and J. B. Tenenbaum. Global versus local methods in nonlinear dimensionality reduction. In S. T. S. Becker and K. Obermayer, editors, Ad- vances in Neural Information Processing Systems 15, pages 705–712. MIT Press, Cambridge, MA, 2003
work page 2003
-
[5]
V. de Silva and J. B. Tenenbaum. Sparse multidi- mensional scaling using landmark points. Available at http://mypage.iu.edu/~mtrosset/Courses/675/LMDS2004.pdf, June 2004
work page 2004
-
[6]
J. C. Gower. Some distance properties of latent root and vector methods in multivariate analysis. Biometrika, 53:325–338, 1966
work page 1966
-
[7]
J. C. Gower. Adding a point to vector diagrams in multivariate analysis. Biometrika, 55(3):582–585, 1968
work page 1968
-
[8]
J. C. Gower. Euclidean distance geometry. Mathematical Scientist, 7:1–14, 1982
work page 1982
Show all 18 references
-
[9]
J. C. Gower. Properties of Euclidean and non-Euclidean distance matrices. Lin- ear Algebra and Its Applications , 67:81–97, 1985
1985
-
[10]
J. B. Kruskal. Multidimensional scaling by optimizing goodness of fit to a non- metric hypothesis. Psychometrika, 29:1–27, 1964
1964
-
[11]
J. B. Kruskal and R. E. Hart. A geometric interpretation of diagnostic data from a digital machine: Based on a study of the Morris, Illinois electronic central office. Bell System Technical Journal , 45:1299–1338, 1966
1966
-
[12]
Tang and M
M. Tang and M. W. Trosset. The out-of-sample problem for classical mul- tidimensional scaling: Addendum. Technical Report 10-03, Department of Statistics, Indiana University, Bloomington, November 2010. Available at https://mtrosset.pages.iu.edu/Research/out2.pdf
2010
-
[13]
J. B. Tenenbaum, V. de Silva, and J. C. Langford. A global geometric framework for nonlinear dimensionality reduction. Science, 290:2319–2323, 2000. 18
2000
-
[14]
W. S. Torgerson. Multidimensional scaling: I. Theory and method. Psychome- trika, 17:401–419, 1952
1952
-
[15]
M. W. Trosset. Trust regions and ridge analysis. In Proceedings of the Statistical Computing Section, pages 4287–4291. American Statistical Association, 2003
2003
-
[16]
M. W. Trosset and C. E. Priebe. The out-of-sample problem for classical multidi- mensional scaling. Computational Statistics & Data Analysis , 52(10):4635–4642, 2008
2008
-
[17]
M. W. Trosset, C. E. Priebe, Y. Park, and M. I. Miller. Semisupervised learning from dissimilarity data. Computational Statistics & Data Analysis , 52(10):4643– 4657, 2008
2008
-
[18]
Williams and M
C. Williams and M. Seeger. Using the Nystr¨ om method to speed up kernel machines. In Advances in Neural Information Processing Systems 13 , pages 682–688. MIT Press, 2001. 19
2001
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.