Finite ISOMAP with deterministic neighborhoods and connected-graph shortest paths

Input: a finite data matrix $X\in {\mathbb{R}}^{n\times p}$ with $n\ge 2$, an embedding dimension $q\ge 1$, and either a $k$-nearest-neighbor parameter $1\le k<n$ with an explicit union or mutual symmetrization choice, or a radius $r>0$. Use $\mathrm{\parallel }v{\mathrm{\parallel }}_2=({\sum }_{a=1}^p{v}_a^2{)}^{1\mathrm{/}2}$; for the $k$-nearest-neighbor option, each neighbor list orders candidates by increasing $(\mathrm{\parallel }{x}_i-x_j{\mathrm{\parallel }}_2,j)$, so equal distances are broken by sample index. Construct the selected undirected graph and give each edge $\{i,j\}$ weight $\mathrm{\parallel }{x}_i-x_j{\mathrm{\parallel }}_2$. If the graph is disconnected, return the status “disconnected” and do not claim finite all-pairs graph distances. If it is connected, define $d_G(i,j)$ as the minimum total edge weight over all paths from $i$ to $j$; because the graph is finite with nonnegative edge weights, a minimum occurs among its finitely many simple paths. Form the symmetric dissimilarity matrix $D_G=(d_G(i,j))$ and apply classical multidimensional scaling to $D_G$ with requested dimension $q$. This finite procedure makes no guarantee that graph distances accurately approximate manifold geodesics or that the output recovers a manifold.

Deterministic neighbor lists, radius graphs, and symmetrizations

Classical multidimensional scaling

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

Cameron, Linear and Nonlinear Dimensionality Reduction, §6, PDF pp. 9–13