{"id":"d8449fc9-06f5-4f8b-88f4-bd2e5e83edaf","arxiv_id":"2505.06756","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Known out-of-sample embedding formulas reduce to two principles, projection or restricted reconstruction, and the second is solvable by a one-dimensional search.","lead":"This paper sorts the many formulas for adding a new point to a multidimensional scaling or kernel embedding into two strategies: projecting the new point onto the old picture, or re-embedding the data while keeping the original points fixed. It shows the two can give very different answers and gives a practical one-dimensional search for the second strategy.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 5's trust-region/ridge equivalence is false in the hard case: in Example 2, every regularized solution has ŷ(λ)=0 while the true minimizer is y*=(0,±√368), so the claimed one-dimensional search over λ cannot be justified as stated.","rationale":"The reader's weakest assumption identified Section 5's trust-region/ridge equivalence in the singular case, and my reading confirms that this is the most load-bearing weakness. The paper's central conceptual claim, the projection-versus-restricted-reconstruction dichotomy, is well supported by the derivations in Sections 3 and 4: the projection formulas are consistently unified, and the restricted-reconstruction objective (10) follows from fixing X and optimizing y. The concrete failure in Example 2 does not overturn the dichotomy, but it invalidates the stated computational simplification in Section 5, which is part of the abstract's promise that restricted reconstruction 'can be simplified to a unidimensional search.' The issue is not merely an omitted proof: the proposed φ(λ) procedure demonstrably cannot recover y* in the paper's own example, because the ridge path is constant and the singular value of λ does not uniquely select the correct norm. This strengthens the reader's conditional concern, but the appropriate verdict remains conditional: the conceptual contribution survives, while the computational claim needs repair or a substantially more careful statement involving the trust-region radius r rather than λ alone.","tokens_in":11841,"tokens_out":8002,"duration_ms":85774,"concrete_test":"Re-run Section 5's proposed search on Example 2: enumerate λ over (−∞,0] avoiding the eigenvalues {−50,−32}, compute ŷ(λ) and φ(λ). If, as predicted, φ is constant at 160000 and no ŷ(λ) equals (0,±√368), the claimed reduction is falsified. As a complementary check, independently minimize (10) over y and verify that the global minimizers are (0,±√368), establishing the discrepancy.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing computational claim is the assertion in Section 5 that the global minimizer y* of (10) can be obtained as ŷ(λ*) for λ* minimizing φ(λ)=2||b−Xŷ(λ)||²+(β−ŷ(λ)ᵀŷ(λ))². This equivalence is asserted from the trust-region/ridge correspondence, but it is not true in the 'hard case' where XᵀX+λI is singular. Example 2 is exactly such a case and makes the failure concrete. With XᵀX=diag(50,32), b=0, β=400, every invertible regularized system has unique solution ŷ(λ)=0 and φ(λ)=160000, so φ has no global minimizer that identifies y*=(0,±√368). At λ=−64, XᵀX+λI has a one-dimensional null space and the regularized objective f+λ||y||²=36y₁² is minimized by the entire line y₁=0, not uniquely by y*; the 'arc of possible embeddings' parameterized by λ therefore never reaches y*. Thus the reduction from (10) to a one-dimensional search over λ is not merely missing a proof: it fails on the paper's own example. A correct repair would minimize over the sphere radius r directly, solving a trust-region subproblem for each r, or use the Lagrange multiplier with an additional norm-selection step; neither is the φ(λ) procedure described.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":12174,"tokens_out":14860,"duration_ms":137709,"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":[{"comment":"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.","section":"Section 5, Eq. (15), Example 2"}],"minor_comments":[{"comment":"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":"Section 3, text near Eq. (8)"},{"comment":"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":"Section 5, Eq. (13)"},{"comment":"The phrase 'finding the finding the d-dimensional hyperplane' contains a duplicated word.","section":"Section 4, first paragraph"},{"comment":"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.","section":"Section 5, paragraph after Eq. (14)"}],"recommendation":"major_revision","confidential_remarks":"The Section 5 flaw is the main obstacle; the manuscript's own Example 2 is a concrete counterexample to the claimed one-dimensional search. The conceptual contribution is sound and the paper is in scope. I would ask the authors to either prove a correct hard-case statement or weaken the computational claim, and to fix the pseudoinverse and scaling issues. With those changes I would support publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read on Trosset et al. The projection vs. restricted reconstruction taxonomy is the real contribution. It organizes a surprisingly scattered literature—Gower, Bengio et al., Anderson-Robinson, Landmark MDS—into two clearly defined strategies, and the derivations in Sections 2–4 check out. The point that Bengio et al. is exactly the restricted-reconstruction objective with the quartic term dropped is well made and worth stating.\n\nThe problem is Section 5. The paper claims the global minimizer of the quartic (10) can be found by minimizing φ(λ) over the regularized solutions ŷ(λ), citing the trust-region/ridge equivalence. That equivalence has a known hard case when XᵀX + λI is singular, and the paper does not handle it. Worse, Example 2 is a counterexample to the claim as stated. There XᵀX = diag(50, 32), b = 0, β = 400. For every invertible λ, the regularized solution is ŷ(λ) = 0, so φ(λ) = 160000, while the actual global minimizer is y* = (0, ±√368) with objective 24576. No λ picks out y*; at the singular λ = −64 the regularized objective becomes 36y₁², minimized on the entire line y₁ = 0, not at y*. So the reduction to a one-dimensional search is not missing a proof—it is false on the paper's own example. The abstract's phrase \"simplified to a unidimensional search\" overstates what is justified. A correct approach would parameterize by the norm r² and solve the trust-region subproblem for each r, or minimize the Lagrangian and then select the norm; either repair keeps the rest of the paper intact.\n\nThe pseudoinverse gloss near (8) is also imprecise: L# is the pseudoinverse of X, not of Xᵀ. Minor but worth fixing.\n\nThe taxonomy and the reconciliation are still valuable, and the flaw is localized to the computational section. This deserves serious peer review: a referee who knows trust-region theory will catch the issue, but the paper should not be desk-rejected. I'd probably cite the taxonomy in my own work, and I'd bring it to a reading group as a good example of a paper with a clean conceptual core and a fixable technical bug.","headline":"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.","tokens_in":12705,"tokens_out":6174,"would_cite":true,"duration_ms":55688,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62H25"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every surveyed kernel method for out-of-sample embedding is one of two strategies: projection or restricted reconstruction.","keywords":["out-of-sample embedding","kernel methods","classical multidimensional scaling","proximity data","projection","restricted reconstruction","vector diagrams","trust-region reduction"],"falsifier":"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.","tokens_in":11648,"feed_emoji":"📐","tokens_out":12145,"duration_ms":111828,"temperature":0.7,"pith_summary":"This paper is about adding one new object to an existing geometric map built from pairwise similarities or dissimilarities. It claims that every kernel-based method—one that works from pairwise similarities—for this out-of-sample embedding task is an instance of one of two competing strategies: projection, which fixes the map and drops the new point into it, or restricted reconstruction, which redoes the map with the new point included while forcing the original points to keep their relative positions. The mathematical result is that restricted reconstruction reduces to minimizing $2\\|Xy-b\\|^2+(y^{\\top}y-\\beta)^2$, a quartic whose global minimum can be located by a one-dimensional search over a penalty parameter. If the claim is right, the apparent clash between published embedding formulas is not a technical error but a genuine methodological fork: the two formulas answer different questions about whether the new point's self-similarity should be honored.","feed_headline":"Two strategies explain every kernel out-of-sample embedding","feed_subtitle":"Fixing the map and projecting differs from redrawing it with old distances held fixed—and the difference can be large.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the original problem of adding a point to a vector diagram and gives the distance-based projection formula used in Section 3.","marker":"[7]"},{"why":"Presents the widely used kernel out-of-sample formula whose rejection of the diagonal term is the foil for restricted reconstruction.","marker":"[2, 3]"},{"why":"Introduces the quadratic-plus-quartic objective that restricted reconstruction minimizes, which the paper reconciles with projection.","marker":"[16]"},{"why":"Supplies the kernel-PCA projection formula that anchors the projection derivation for proximity data.","marker":"[18]"},{"why":"States the least-squares rewording of the projection formula that becomes Equation (7).","marker":"[1]"},{"why":"Gives the landmark-MDS triangulation formula that the paper shows is algebraically the same projection formula.","marker":"[5]"},{"why":"Defines the weighted centering operator used to turn squared dissimilarities into the augmented centered-similarity matrix.","marker":"[8, 9]"},{"why":"Establishes the trust-region/ridge-analysis equivalence used to reduce the quartic minimization to a unidimensional search.","marker":"[15]"}],"fun_headline_variants":["Projection vs restricted reconstruction: two embedding strategies","Kernel out-of-sample embedding: two roads diverge","For distant new points, embedding strategies diverge","Every kernel embedding is either projection or reconstruction","Unified kernel embedding: projection or reconstruction"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Projection vs restricted reconstruction: two embedding strategies","Kernel out-of-sample embedding: two roads diverge","For distant new points, embedding strategies diverge","Every kernel embedding is either projection or reconstruction","Unified kernel embedding: projection or reconstruction"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00147,"raw_usage":{"total_tokens":5890,"prompt_tokens":906,"completion_tokens":4984,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":522,"completion_tokens_details":{"reasoning_tokens":4913}},"tokens_in":522,"tokens_out":4984,"duration_ms":33676,"temperature":1.0,"reasoning_tokens":4913,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T22:34:15.226961+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the original problem of adding a point to a vector diagram and gives the distance-based projection formula used in Section 3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces the quadratic-plus-quartic objective that restricted reconstruction minimizes, which the paper reconciles with projection."},{"cited_title":"Williams and M","cited_arxiv_id":null,"evidence_quote":"Supplies the kernel-PCA projection formula that anchors the projection derivation for proximity data."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"States the least-squares rewording of the projection formula that becomes Equation (7)."},{"cited_title":"de Silva and J","cited_arxiv_id":null,"evidence_quote":"Gives the landmark-MDS triangulation formula that the paper shows is algebraically the same projection formula."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the trust-region/ridge-analysis equivalence used to reduce the quartic minimization to a unidimensional search."}],"review_version":1}