by exploiting the null space of the Laplacian (L1 = 0) as we saw in Section 2.1.

Let's consider the properties of this objective. Since the error function is in terms of interpoint distances, it is insensitive to translations of the embeddings. The mean of the latent projections is therefore undefined. Further, there is a trivial solution for this objective. If the latent points are all placed on top of one another the interpoint distance matrix will be all zeros. To prevent this collapse Belkin and Niyogi suggest that each dimension of the latent representation is constrained, x
>
:,iVx:,i = 1.

Here the degree matrix, V, acts to scale each data point so that points associated with a larger neighborhood are pulled towards the origin.

Given this constraint the objective function is minimized for a q dimensional space by the generalized eigenvalue problem, Lui = λiVui, where λ is an eigenvalue and u is its associated eigenvector. The smallest eigenvalue is zero and is associated with the constant eigenvector. This eigenvector is discarded, whereas the eigenvectors associated with the next q smallest eigenvalues are retained for the embedding. So we have,

$$\mathbf{x}_{:,i}=\mathbf{u}_{i+1}\quad{\mathrm{for}}\quad i=1..q$$
$\left(4\right)$. 
if we assume that eigenvalues are ordered according to magnitude with the smallest first.

Note that the generalized eigenvalue problem underlying Laplacian eigenmaps can be readily converted to the related, symmetric, eigenvalue problem.

Lvˆi = λivi (4)
where Lˆ is the *normalized Laplacian matrix*,

$${\hat{\mathbf{L}}}\mathbf{v}_{i}=\lambda_{i}\mathbf{v}_{i}$$
$$\operatorname{i}r i x,$$
$${\hat{\mathbf{L}}}=\mathbf{V}^{-{\frac{1}{2}}}\mathbf{L}\mathbf{V}^{-{\frac{1}{2}}}=\mathbf{I}-\mathbf{V}^{-{\frac{1}{2}}}\mathbf{A}\mathbf{V}^{-{\frac{1}{2}}}$$

and the relationship between the eigenvectors is through scaling by the degree matrix, vi = V
1 2 ui (implying v
>
i vi = 1). The eigenvalues remain unchanged in each case.

## 2.6.1 Parameterization In Laplacian Eigenmaps

In Laplacian eigenmaps the adjacency matrix can either be unweighted (Belkin and Niyogi refer to this as the simple-minded approach) or weighted according to the distance between two data points,

$$a_{i,j}=\exp\left(-\frac{\|\mathbf{y}_{i,:}-\mathbf{y}_{j,:}\|_{2}^{2}}{2\sigma^{2}}\right),$$
$$\left(5\right)$$
, (5)
which is justified by analogy between the discrete graph Laplacian and its continuous equivalent, the Laplace Beltrami operator [Belkin and Niyogi, 2003].

## 2.6.2 Relating Laplacian Eigenmaps To Meu

The relationship of MEU to Laplacian eigenmaps is starting to become clear. In Laplacian eigenmaps a graph Laplacian is specified across the data points just as in maximum entropy unfolding. In classical multidimensional scaling, as applied in MEU and MVU, the eigenvectors associated with the largest eigenvalues of the centred covariance matrix, B = H (L + γI)
−1 H (6)
are used for visualization. In Laplacian eigenmaps the smallest eigenvectors of L are used, disregarding the eigenvector associated with the null space.

Note that if we define the eigendecomposition of the covariance in the GRF as K = UΛU>
it is easy to show that the eigendecomposition of the associated Laplacian matrix is L = UΛ
−1 − γIU>.