1
$\begingroup$

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.

$\endgroup$

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.