We know that the smallest eigenvalue of L is zero with a constant eigenvector. That implies that the largest eigenvalue of K is γ
−1 and is associated with a constant eigenvector. However, we don't use the eigenvectors of K
directly. We first apply the centering operation in (6). This projects out the constant eigenvector, but leaves the remaining eigenvectors and eigenvalues intact.

To make the analogy with Laplacian eigenmaps direct we consider the formulation of its eigenvalue problem with the normalized graph Laplacian as given in (4). Substituting the normalized graph Laplacian into our covariance matrix, K, we see that for Laplacian eigenmaps we are visualizing a Gaussian random field with a covariance as follows, K = (Lˆ + γI)
−1.

Naturally we could also consider a variant of the algorithm which used the unnormalized Laplacian directly, K =
(L + γI)
−1. Under the Laplacian eigenmap formulation that would be equivalent to preventing the collapse of the latent points by constraining x
>
:,ix:,i = 1 instead of x
>
:,iVx:,i = 1.

This shows the relationship between the eigenvalue problems for Laplacian eigenmaps and CMDS. The principal eigenvalues of K will be the smallest eigenvalues of L. The very smallest eigenvalue of L is zero and associated with the constant eigenvector. However, in CMDS this would be removed by the centering operation and in Laplacian eigenmaps it is discarded. Once the parameters of the Laplacian have been set CMDS is being performed to recover the latent variables in Laplacian eigenmaps.

## 2.6.3 Laplacian Eigenmaps Summary

The Laplacian eigenmaps procedure doesn't fit parameters through maximum likelihood. It uses analogies with the continuous Laplace Beltrami operator to set them via the Gaussian-like relationship in (5). This means that the local distance constraints are not a feature of Laplacian eigenmaps. The implied squared distance matrix used for CMDS will not preserve the interneighbor distances as it will for MVU and MEU. In fact since the covariance matrix is never explicitly computed it is not possible to make specific statements about what these distances will be in general. However, Laplacian eigenmaps gains significant computational advantage by not representing the covariance matrix explicitly. No matrix inverses are required in the algorithm and the resulting eigenvalue problem is sparse. This means that Laplacian eigenmaps can be applied to much larger data sets than would be possible for MEU or MVU.

## 2.7 Relation Of Meu To Locally Linear Embedding

The locally linear embedding [LLE Roweis and Saul, 2000] is a dimensionality reduction that was originally motivated by the idea that a non-linear manifold could be approximated by small linear patches. If the distance between data points is small relative to the curvature of the manifold at a particular point, then the manifold encircling a data point and its nearest neighbors may be approximated locally by a linear patch. This idea gave rise to the locally linear embedding algorithm. First define a local neighborhood for each data point and find a set of linear regression weights that allows each data point to be reconstructed by its neighbors. Considering the ith data point, yi,: and a vector of reconstruction weights, w:,i, associated with that data point a standard least squares regression objective takes the form,

$$E(\mathbf{w}_{:,i})=\frac{1}{2}\left\|\mathbf{y}_{i,:}-\sum_{j\in\mathcal{N}(i)}\mathbf{y}_{j,:}w_{j,:}\right\|_{2}^{2},\tag{7}$$  for the reconstruction weights, $\mathbf{w}_{:,i}$ is restricted to data points, $\left\{\mathbf{y}_{j,:}\right\}_{\leq\mathcal{N}(i)\setminus\mathcal{N}}$
for each data point. Here the sum over the reconstruction weights, w:,j is restricted to data points, {yj,:}j∈N(()i)
which are in the neighborhood of the data point of interest, yi,:. Roweis and Saul point out that the objective function in (7) is invariant to rotation and rescaling of the data. If we rotate each data vector in (7) the objective does not change. If data are rescaled, e.g. multiplied by a factor α, then the objective is simply rescaled by a factor α 2. However, the objective is not invariant to translation. For example if we were to translate the data, yˆi,: = yi,: −µ, where µ could be the sample mean of our data set (or any other translation), we obtain the following modified objective,

$$E(\mathbf{w}_{:,i})={\frac{1}{2}}\left\|\hat{\mathbf{y}}_{i,:}+\boldsymbol{\mu}-\sum_{j\in{\mathcal{N}}(i)}\hat{\mathbf{y}}_{j,:}w_{j,i}-\boldsymbol{\mu}\sum_{j\in{\mathcal{N}}(i)}w_{j,i}\right\|_{2}^{2},$$  on $\boldsymbol{\mu}$. Broweis and Saul point out that if we constrain $\sum_{i}$
2
which retains a dependence on µ. Roweis and Saul point out that if we constrain Pj∈N(i) wj,i = 1 the terms involving µ cancel and we recover the original objective. Imposing this constraint on the regression weights (which can also be written w>
:,i1 = 1), ensures the objective is translation invariant.