Locally linear embedding

Reconstruct each point from its neighbours, then find a low-dimensional layout that keeps the same weights

Locally linear embedding (LLE) assumes each point lies close to a linear patch of a smooth manifold. Each point is reconstructed from its k nearest neighbours with weights that sum to 1. A low-dimensional embedding is then found that keeps those same weights.

Implement two functions.

• lle_weights(X, k, reg=1e-3): X is n by d. For each point i, take its k nearest neighbours (excluding itself, ties to the lower index). Let Z be the neighbours minus x_i, and G = Z Z^T. Solve (G + eps I) w = 1, where eps = reg * trace(G), or eps = reg when the trace is zero. Normalise w to sum to 1 and store it in row i at the neighbour columns. Return the n by n weight matrix W.
• lle_embedding(W, dim): let M = (I - W)^T (I - W). Return the eigenvectors of M for the second through (dim + 1)-th smallest eigenvalues, as an n by dim array. Skip the first eigenvector, which is constant.

Constraints

• X must be 2-D, and 1 <= k < n. Otherwise raise ValueError.
• W must be square, and 1 <= dim < n. Otherwise raise ValueError.
• Do not modify the inputs.

Hints