Why do Laplacian Eigenmaps ignore the second KKT condition in the solution calculation?

Question

From the original Laplacian Eigenmaps paper, we find the new manifold embedding $Y$ as follows, given the Laplacian and degree matrices $L$ and $D$:

$\arg\min_Ytr(Y^TLY)$ subject to ${Y^TDY=I}$.

Regarding the constraint ${Y^TDY=I}$:

For one-dimensional embedding problem, the constraint prevents collapse onto a point. For the $m$-dimensional embedding problem, the constraint presented above prevents collapse onto a subspace of dimension less than $m-1$ ($m$ if, as in the one-dimensional case, we require orthogonality to the constant vector).

Using a Lagrange function the above objective is formulated as:

$\arg\min_YC(Y)=\arg\min_Y{tr(Y^TLY)+\lambda(I-Y^TDY)}$

The main KKT conditions defining the solutions are:

Condition 1: $\frac{\delta C(Y)}{\delta Y}=0:\quad LY=\lambda DY$

Condition 2: $\frac{\delta C(Y)}{\delta\lambda}=0:\quad Y^TDY=I$

Standard methods show that the solution is provided by the matrix of eigenvectors corresponding to the lowest eigenvalues of the generalized eigenvalue problem $Ly=\lambda Dy$.

However, the imposed constraint ${Y^TDY=I}$ will not necessarily be met by the eigenvectors corresponding to the smallest positive non-zero eigenvalues of $Ly=\lambda Dy$, especially since condition 2 ($Y^TDY=I$) is ignored according to the text.

Why is the second KKT condition ignored in the calculation of the solution?

Answer 1

The second KKT condition is simply omitted, since standard implementations like Matlabs eigs() already divide eigenvectors by their lengths $y^TDy$ (or $y^Ty$) to produce a unit length vector, which would also give the corresponding eigenvalues a more direct interpretation.

So in a typical implementation one does not have to concern oneself with meeting the second condition, which is really only imposed to prevent the trivial zero-vector solution and also arbitrary eigenvector lengths.