Finite locally linear embedding with minimum-norm weights and a simple constant kernel

Input: a data matrix $X\in {\mathbb{R}}^{n\times p}$ with $n\ge 2$, a neighbor count $1\le k<n$, and an output dimension $1\le q<n$, using $\mathrm{\parallel }v{\mathrm{\parallel }}_2=({\sum }_{a=1}^p{v}_a^2{)}^{1\mathrm{/}2}$. For every row point $x_i$, select the first $k$ other sample indices ordered by $(\mathrm{\parallel }{x}_i-x_j{\mathrm{\parallel }}_2,j)$ and use the minimum-Euclidean-norm affine least-squares weights on that neighborhood, with weights summing to $1$. Form $W\in {\mathbb{R}}^{n\times n}$ by placing those weights in the selected columns of row $i$ and zeros elsewhere; every row of $W$ then sums to $1$. If $\ker (I_n-W)\mathrm{\ne }\mathrm{span}\{{\mathbf{1}}_n\}$, return the status “constant kernel not isolated” and do not specify an embedding. Otherwise put $M=(I_n-W{)}^T(I_n-W)$ and return any $Y\in {\mathbb{R}}^{n\times q}$ minimizing

$\mathrm{tr}(Y^{T}MY)\text{subject to}{Y}^T{\mathbf{1}}_n=0,Y^{T}Y=I_q,$

where $\mathrm{tr}$ is the sum of diagonal entries. Equivalently, take orthonormal eigenvectors for the $q$ smallest positive eigenvalues of $M$. Ties allow multiple outputs. This finite-matrix procedure makes no guarantee of manifold recovery or consistency.

Deterministic finite neighbor selection

Minimum-norm affine reconstruction weights

Existence and uniqueness of the minimum-norm weights

Trace minimizers are the bottom positive eigenvectors under the kernel condition ↗

Trace as the sum of diagonal entries

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

Cameron, Linear and Nonlinear Dimensionality Reduction, §7, PDF pp. 13–16