ExampleConstruction: AI-generatedVerification: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Classical MDS, ISOMAP, and LLE give different embeddings of a four-point square

Example

Take four points $x_{1} = (0, 0)$ , $x_{2} = (1, 0)$ , $x_{3} = (1, 1)$ , $x_{4} = (0, 1)$ around a unit square, use $k = 1$ with ties broken by sample index and union symmetrization, and request dimension $q = 1$ . The neighbor graph has edges ${1, 2}$ , ${2, 3}$ , and ${1, 4}$ , so it unrolls to the path $4 - 1 - 2 - 3$ . One valid top-eigenvector choice for classical MDS of the original Euclidean distances gives coordinates $Y_{M} = (- 1 / 2, 1 / 2, 1 / 2, - 1 / 2)^{T}$ . ISOMAP gives coordinates congruent to $Y_{I} = (- 1 / 2, 1 / 2, 3 / 2, - 3 / 2)^{T}$ . LLE gives coordinates proportional to $(a, - a, - 1, 1)^{T}$ , where $a = \sqrt{5} - 2$ . These three one-dimensional configurations are pairwise noncongruent under translations and reflections.

The diagram labels the square’s sample indices. Blue edges are the union 1-nearest-neighbor graph; the dashed side ${3, 4}$ belongs to the square geometry but is not retained by the tie rule.

diagram failed to render:
\begin{tikzpicture}[vertex/.style={draw,circle,minimum size=7mm}]
  \node[vertex] (x1) at (0,0) {$1$};
  \node[vertex] (x2) at (2,0) {$2$};
  \node[vertex] (x3) at (2,2) {$3$};
  \node[vertex] (x4) at (0,2) {$4$};
  \draw[blue,thick] (x1)--(x2)--(x3);
  \draw[blue,thick] (x1)--(x4);
  \draw[gray,dashed] (x3)--(x4);
\end{tikzpicture}

Example references

Hastie, Tibshirani, and Friedman, ESL II, §14.9, printed pp. 572–575

Cameron, Linear and Nonlinear Dimensionality Reduction, §§3, 6, and 7, PDF pp. 4–16

Facts & Assumptions

Given: The four stated square points, $k = 1$ , deterministic index tie-breaking, union symmetrization, and requested dimension $q = 1$ .

[F1]

Classical MDS forms $B = - \frac{1}{2} H_{n} D^{\circ 2} H_{n}$ and returns positive-eigenvalue coordinates (Classical multidimensional scaling from a finite dissimilarity matrix).

[F2]

For Euclidean distances, $B$ is the centered Gram matrix and all positive-eigenvalue coordinates reproduce the distances (Double-centering Euclidean squared distances recovers their centered Gram matrix).

[F3]

The nearest-neighbor order is by distance then sample index, and union edges are selected by either endpoint (Deterministic finite nearest-neighbor lists and graph symmetrizations).

[F4]

ISOMAP uses the connected graph’s all-pairs shortest-path distances and then applies classical MDS (Finite ISOMAP with deterministic neighborhoods and connected-graph shortest paths).

[F5]

LLE uses affine local weights, forms $M = (I - W)^{T} (I - W)$ , and under the simple constant-kernel condition returns the lowest positive eigenvectors (Finite locally linear embedding with minimum-norm weights and a simple constant kernel).

[F6]

The LLE trace minimizers are exactly the q-dimensional eigenspaces for the q smallest positive eigenvalues (Under the simple constant-kernel condition, LLE trace minimizers are bottom positive eigenvectors).

Verification

1.1givenF1F2algebra

After centering the four points, their Gram matrix is $B = (\begin{array}{cccc} 1 / 2 & 0 & - 1 / 2 & 0 \\ 0 & 1 / 2 & 0 & - 1 / 2 \\ - 1 / 2 & 0 & 1 / 2 & 0 \\ 0 & - 1 / 2 & 0 & 1 / 2 \end{array})$ . The unit vector $u_{x} = (- 1, 1, 1, - 1)^{T} / 2$ is an eigenvector with eigenvalue $1$ , as is $u_{y} = (- 1, - 1, 1, 1)^{T} / 2$ ; the other two eigenvalues are zero. Thus the x-coordinate choice $Y_{M} = u_{x}$ is a valid q=1 classical-MDS output, and it has repeated pairs $y_{1} = y_{4}$ and $y_{2} = y_{3}$ .

1.2givenF5F6algebra

With one neighbor per row, each LLE weight is $1$ . Thus $W_{12} = W_{21} = W_{32} = W_{41} = 1$ and other entries are zero; the equations $W y = y$ force $y_{1} = y_{2} = y_{3} = y_{4}$ , so the kernel is exactly the constant vectors. The matrix is $M = (I - W)^{T} (I - W) = (\begin{array}{cccc} 3 & - 2 & 0 & - 1 \\ - 2 & 3 & - 1 & 0 \\ 0 & - 1 & 1 & 0 \\ - 1 & 0 & 0 & 1 \end{array})$ . Its symmetric subspace vectors $(c, c, d, d)$ have eigenvalues $0, 2$ . On antisymmetric vectors $(c, - c, - d, d)$ it acts by $(c, d) \mapsto (5 c - d, d - c)$ , whose characteristic equation is $λ^{2} - 6 λ + 4 = 0$ , giving eigenvalues $3 - \sqrt{5}$ and $3 + \sqrt{5}$ . Hence the lowest positive eigenvalue is $3 - \sqrt{5}$ with eigenvector $(a, - a, - 1, 1)^{T}$ , where $a = \sqrt{5} - 2 \in (0, 1)$ .

2.1givenF2F3F4step 1.1

The distances from each square vertex to its two side-neighbors tie at $1$ . By [F3], the neighbor lists are $N_{1} = (2)$ , $N_{2} = (1)$ , $N_{3} = (2)$ , and $N_{4} = (1)$ ; the union graph has the stated edges and is the path $4 - 1 - 2 - 3$ . Its graph distances are exactly the line distances of the centered vector $Y_{I} = (- 1 / 2, 1 / 2, 3 / 2, - 3 / 2)^{T}$ . Since this graph-distance matrix is Euclidean in one dimension, [F2] shows that ISOMAP’s q=1 classical-MDS output is congruent to $Y_{I}$ . In particular its distance between vertices 1 and 4 is $1$ , unlike the zero MDS distance in step 1.1.

3.1step 1.1step 2.1step 1.2algebra∎

The LLE coordinate has four distinct values, unlike $Y_{M}$ , so it is not congruent to the classical-MDS output. Its sorted consecutive gaps are proportional to $1 - a, 2 a, 1 - a$ , and these are not all equal: $2 a = 1 - a$ would imply $3 \sqrt{5} = 7$ , contradicting $45 \neq 49$ after squaring. The ISOMAP line has equal consecutive gaps, so LLE is not congruent to ISOMAP either. The distinct distance $d_{14} = 1$ in ISOMAP and $d_{14} = 0$ in classical MDS already separates those two outputs.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

18 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

The Elements of Statistical Learning, second edition, corrected 12th printing (standard reference, not scraped)
Maria Cameron, Linear and Nonlinear Dimensionality Reduction, lecture notes (standard reference, not scraped)