I had read a few papers on Laplacian Eigenmaps and have been a bit confused on 1 step in the standard derivation. First I just want to deal with the 1-D case. We are given that we want to find the vector $y\in \mathbb{R}^n$ that minimizes $y^TLy$ where L is an $n$ x $n$ symmetric real matrix (positive semidefinite).

If we know that $y$ is an eigenvector of $L$ then I can see that finding the $\text{argmin } y^TLy$ boils down to finding the eigenvector of $L$ with the least non-zero eigenvalue.

Without assuming that $y$ is an eigenvector of $L$ (I don't think we should make this assumption), I get that $\text{argmin } y^TLy = \text{argmin } y^T(\sum\limits_{i=1}^n\lambda_iu_iu_i^T)y$ where $u_i$ is the eigenvector of $L$ corresponding to the eigenvalue $\lambda_i$. Assuming unit length for $y$ and $u_i$, minimizing $y^TLy$ reduces to finding the smallest $d$ eigenvalues (assuming our embedded space is of dimension $d$). Does this mean our embedded space has the basis given by the corresponding $d$ eigenvectors (or for the 1-D case the eigenvector corresponding to the smallest non-zero eigenvalue)?

Thanks so much.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.