Positive Definite Constraints The maximum variance unfolding (MVU) algorithm maximizes the trace of the covariance matrix

$$\operatorname{tr}\left(\mathbf{K}\right)=\sum_{i=1}^{n}\lambda_{i},$$

subject to constraints on the elements of K arising from the squared distances. These constraints are linear in the elements of K. There is a further constraint on K, that it should be positive semi-definite. This means MVU can be optimized through a a semi-definite program. In contrast MEU cannot be optimized through a semidefinite program because the objective linear in K. This implies we need to find other approaches to maintaining the positive-definite constraint on K. Possibilities include exploiting the fact that if the Lagrange multipliers are constrained to be positive the system is "attractive" and this guarantees a valid covariance [see e.g. Koller and Friedman, 2009, pg 255]. Although now (as in a suggested variant of the MVU) the distance constraints would be inequalities. Another alternative would be to constrain L to be diagonally dominant through adjusting γ. We will also consider two further approaches in Section 2.7 and Section 3. Non-linear Generalizations of PCA Kernel PCA provides a non-linear generalization of PCA. This is achieved by 'kernelizing' the principal coordinate analysis algorithm: replacing data point inner products with a kernel function. Maximum variance unfolding and maximum entropy unfolding also provide non linear generalizations of PCA. For these algorithms, if we increase the neighborhood size to K = n − 1, then all squared distances implied by the GRF model are constrained to match the observed inter data point squared distances and L becomes nonsparse. Classical multidimensional scaling on the resulting squared distance matrix is known as principal coordinate analysis and is equivalent to principal component analysis [see Mardia et al., 1979]4.

## 2.6 Relation To Laplacian Eigenmaps

Laplacian eigenmaps is a spectral algorithm introduced by Belkin and Niyogi [2003]. In the Laplacian eigenmap procedure a neighborhood is first defined in the data space. Typically this is done through nearest neighbor algorithms or defining all points within distance  of each point to be neighbors. In Laplacian eigenmaps a symmetric sparse (possibly weighted) adjacency matrix, A ∈ <n×n, is defined whose *i, j*th element, ai,j is non-zero if the ith and jth data points are neighbors. Belkin and Niyogi argue that a good *one dimensional embedding* is one where the latent points, X minimize

$$E(\mathbf{X})={\frac{1}{4}}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}{\big(}x_{i}-x_{j}{\big)}^{2},$$

For a multidimensional embedding we can rewrite this objective in terms of the squared distance between two latent points, δi,j = kxi,: − xj,:k 2 2
, as

$$E(\mathbf{X})={\frac{1}{4}}\sum_{i=1}^{n}\sum_{j=1}^{n}a_{i,j}\delta_{i,j}.$$

The motivation behind this objective function is that neighboring points have non-zero entries in the adjacency matrix, therefore their inter point squared distances in latent space need to be minimized. In other words points which are neighbors in data space will be kept close together in the latent space. The objective function can be rewritten in matrix form as

$$E(\mathbf{X})={\frac{1}{4}}\mathrm{tr}\left(\mathbf{A}\mathbf{\Delta}\right).$$

Squared Euclidean distance matrices of this type can be rewritten in terms of the original vector space by introducing the Laplacian matrix. Introducing the degree matrix, V, which is diagonal with entries, vi,i =Pj Ai,j the Laplacian associated with the neighborhood graph can be written

$$\mathbf{L}=\mathbf{V}-\mathbf{A}$$

and the error function can now be written directly in terms of the latent coordinates,

$$E(\mathbf{X})={\frac{1}{2}}\mathrm{tr}\left(\mathbf{L}\mathbf{X}\mathbf{X}^{\top}\right)$$
