Is it necessary to constrain the size of the neighborhood in LLE to be less than the space dimensionality? The wikipedia entry on Locally Linear Embedding (LLE) says that LLE can be broken into stages, the first of which is to learn a barycentric linear model of the data with its $k$-nearest neighbors:

$$ E(W) = \sum_i |{\mathbf{X}_i - \sum_j {\mathbf{W}_{ij}\mathbf{X}_j}|}^\mathsf{2}$$

Where $j$ ranges over $x_i$'s $k$-nearest neighbors.  However, if the $x_i$ have $d$ dimensions and $k > d$, then if data are sampled randomly, they will almost surely be linearly independent, and thus the loss function above can always be made zero (since we can write $x_i$ exactly as a linear combination of $d$ other vectors in the space) and the $W_{ij}$ are not uniquely determined.  This seems like a caveat for LLE.  Specifically, if $k>d$, can LLE be expected to fail to give reasonable results?  What if $k>>d$?  If not, then why is this intuition incorrect?
 A: For LLE to work, the number of neighbors $K$ must be greater than the intrinsic dimensionality of the underlying manifold. But, as you pointed out, the reconstruction weights are not uniquely defined if $K$ exceeds the extrinisc dimensionality $D$ (i.e. number of input dimensions). In this case, Saul and Roweis recommend regularization, which ensures a unique solution. The approach they describe amounts to penalizing the $\ell_2$ norm of the weight vector for each point. Using this approach, LLE does indeed work in the $K > D$ regime. For example, fig. 1 in the paper below shows LLE working for several problems where $K=8, D=3$.
But, the solution will eventually break down as $K$ becomes too large, which you can see in fig. 10. This happens because LLE assumes local linearity, which only holds over certain scales if the manifold is nonlinear. The local linear approximation will fail if the neighborhood becomes too large, due to the curvature of the data. Note that this effect has to do with the intrinsic geometry (curvature) of the manifold and how densely it has been sampled, rather than extrinsic dimensionality of the input.
References:
Saul and Roweis (2003). Think globally, fit locally: Unsupervised learning of low dimensional manifolds.
