et al., 1998]. In kernel PCA the squared distances are computed between points in a Hilbert space and related to the original data through a kernel function, di,j = k(yi,:, yi,:) − 2k(yi,:, yj,:) + k(yj,:, yj,:). (2)
For the linear kernel function, k(yi,:, yj,:) = y
>
i,:yj,: this reduces to the squared Euclidean distance, but for nonlinear kernel functions such as k(yi,:, yj,:) = exp(−γ kyi,: − yj,:k 2 2
) the distances are nonlinearly related to the data space.

They are recognized as squared distances which are computed in a "feature space" [see e.g. Ham et al., 2004, Bengio et al., 2004b,a]. If we equate the kernel matrix, K, to the similarity matrix in CMDS then this equation is also known as the *standard transformation* between a similarity and distance [Mardia et al., 1979].

Kernel PCA (KPCA) recovers an xi,: for each data point and a mapping from the data space to the X space.

Under the CMDS procedure we outlined above the eigenvalue problem is performed on the centered kernel matrix,

## B = Hkh,

where K = [k(yi,:, yj,:)]i,j . This matches the procedure for the KPCA algorithm [Sch¨olkopf et al., 1998]2. However, for the commonly used exponentiated quadratic kernel,

## K(Yi,:, Yj,:) = Exp(−Γ Kyi,: − Yj,:K 2 2 ),

KPCA actually *expands* the feature space rather than reducing the dimension [see Weinberger et al., 2004, for some examples of this]. Unless data points are repeated the exponentiated quadratic kernel always leads to a full rank matrix, K, and correspondingly a rank n−1 centred kernel matrix, B. To exactly reconstruct the squared distances computed in feature space all but one of the eigenvectors of B need to be retained for our latent representation, X. If the dimensionality of the data, p, is smaller than the number of data points, n, then we have a latent representation for our data which has higher dimensionality than the original data.

The observation that KPCA doesn't reduce the data dimensionality motivated the maximum variance unfolding algorithm [MVU, Weinberger et al., 2004]. The idea in MVU is to learn a kernel matrix that will allow for dimensionality reduction. This is achieved by only considering *local relationships* in the data. A set of neighbors is defined (e.g. by k-nearest neighbors) and only distances between neighboring data points are respected. These distances are specified as constraints, and the other elements of the kernel matrix are filled in by maximizing its trace, tr (K), i.e. the *total variance* of the data in feature space, while respecting the distance constraints and keeping the resulting matrix centered. Maximizing tr (K) maximizes the interpoint squared distances for all points that are unconnected in the neighborhood graph, thereby unravelling the manifold.

In this paper we consider an alternative maximum entropy formalism of this problem. Since entropy is related to variance, we might expect a similar result in the quality of the resulting algorithm, but since maximum entropy also provides a probability distribution we should also obtain a probabilistic model with all the associated advantages
(dealing with missing data, extensions to mixture models, fitting parameters by Bayesian methods, combining with other probabilistic models). Importantly, our interpretation will also enable us to relate our algorithm to other well known spectral techniques as they each turn out to approximate maximum entropy unfolding in some way.

## 2.1 Constraints From D Lead To A Density On Y

The maximum entropy formalism [see e.g. Jaynes, 1986] allows us to derive a probability density given only a set of constraints on expectations under that density. These constraints may be derived from observation. In our case the observations will be squared distances between data points, but we will derive a density over Y directly (not over the squared distances). We will do this by looking to constrain the expected squared inter-point distances, di,j , of any two samples, yi,: and yj,:, from the density. This means that while our observations may be only of the squared distances, di,j , the corresponding density will be over the data space that gives rise to those distances, p(Y). Of course, once we have found the form of probability density we are free to directly model in the space Y or make use only of the squared distance constraints. Direct modeling in Y turns out to be equivalent to maximum likelihood.

However, since we do not construct a density over the squared distance matrix, modeling based on that information alone should be thought of as maximum entropy under distance constraints rather than maximum likelihood.

Maximum entropy is a free form optimization over all possible forms for the density given the moment constraints we impose. In the maximum entropy formalism, we specify the density by a free form maximization of the entropy subject to the imposed expectation constraints. The constraints we use will correspond to the constraints applied to maximum variance unfolding: the expectations of the squared distances between two neighboring data points sampled from the model.

2For stationary kernels, kernel PCA also has an interpretation as a particular form of *metric* multidimensional scaling, see Williams
[2001] for details.