# nonlinear Dimensionality Reduction by Semidefinite Programming and Kernel Matrix Factorization

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## Introduction

In recent work, Semidefinite programming (SDE) that learns a kernel matrix by maximizing variance while preserving the distance and angles between nearest neigbors has been introduced. Although it has many advantages such as optimization convexity, it sufferes from computational cost for large problems. In this paper <ref>K. Q. Weinberger et al. Graph Laplacian Regularization for Larg-Scale Semidefinite Programming, Proceedings of the the Tenth international workshop on Artificial Intelligence and Statistics (AISTATS-05), pages 381-388, Barbados, West Indies, 2005.</ref> , a new framework based on factorization of the entire kernel matrix in terms of a much smaller submatrix of inner products between randomly chosen landmarks has been proposed.

## Semidefinite Embedding

Given high dimensional vectors $\,\{x_1, x_2, ..., x_n\} \in R^D$ lying on or near a manifold that can be embeded in $\,d\ll D$ dimensions to produce low dimensional vectors $\,\{y_1, y_2, ..., y_n\} \in R^d$, the goal is to find d and produce an appropriate embedding. The algorithm starts with computing k-nearest neighbors of each input and adding a constraint to preserve distances and angles between k-nearest neighbors:
$\,\|y_i-y_j\|^2 = \|x_i-x_j\|^2$ for all (i,j) in k-nearest neighbors (2)
and also a constraint on outputs to be centerd on the origin:
$\,\sum_i{y_i} = 0$ (3)
And maximizining the variance of outputs will be the final step: $\,var(y)=\sum_i{\|y_i\|^2}$ (4)
(since (3), it is cleat that $\sum_{i,j}{\|y_i - y_j\|^2} = 2\sum_i{\|y_i\|^2}$, therefore maximizing the variance of Y will stretch the distances and force the data to lie on a lower dimensional subspace)

Assuming $\,K_{ij}=y_i^T . y_j$, the above optimzation problem can be reformulated as an SDE:
Maximize trace(K) subject to :
1) $\,K\succeq 0$
2)$\,\sum_{ij}K_{ij}=0$
3) For all (i,j) such that $\,\eta_{ij}=1$,

  $\,K_{ii}-2K_{ij}+K_{jj}=\|x_i-x_j\|^2$


the top d eigenvalues and eigenvectors of the kernel matrix will be used to derive the embedding. Here, learning the kernel matrix dominates the total computation time.

## Kernel Matrix Factorization

As we saw in the last section, learning the kernel matrix takes a lot of computational time. Therefore, if we can approximate it by a much smaller matrix , the computation time will be drastically improved. This can be done through the following steps:
First, reconstructing high dimensional datasate $\,\{x_i\}_{i=1}^n$ from m randomly chosen landmarks $\,\{\mu_{\alpha}\}_{\alpha=1}^m$ :
$\,\hat{x_i} = \sum_{\alpha}{Q_{i\alpha}\mu_{\alpha}}$
Based on the similar intuition from locally linear embedding (LLE), the same linear transformation (Q) can be used to reconstruct the output:
$\,\hat{y_i} = \sum_{\alpha}{Q_{i\alpha}l_{\alpha}}$ (6)
Now, if we make the approximation:
$\,K_{ij}=y_i.y_j \approx \hat{y_i}.\hat{y_j}$ (7)
substituting (6) into (7) gives $\,K\approx QLQ^T$ where $\,L_{\alpha\beta} = l_{\alpha}.l_{\beta}$

## Reconstructing from landmarks

To derive Q, we assume that the manifold can be locally approximated by a linear subspace. Therefore, each input in the high dimensional space can be reconstructed by a weighted sum of its r-nearest neighbors. These weights are found by :
Minimize  :$\,\varepsilon(W)=\sum_i{\|x_i-\Sigma_j{W_{ij}x_j}\|^2}$
subject to:$\,\Sigma_j{W_{ij}}=1$ for all j
and $\,W_{ij}=0$ if $\,x_i$ are not r-nearest neighbor of $\,x_j$
Rewriting the reconstruction error as function of inputs will give us: $\,\varepsilon(X)=\sum_{ij}{\phi_{ij}x_i.x_j}$
where $\,\phi = (I_n-W)^T(I_n-W)$ or
$\,\phi=\begin{bmatrix} \overbrace{\phi^{ll}}^{m} & \overbrace{\phi^{lu}}^{n-m} \\ \phi^{ul} & \phi^{uu}\end{bmatrix}$

and the solution will be:
$\,Q=\begin{bmatrix} I_m \\ -(\phi^{uu})^{-1}\phi^{ul}\end{bmatrix}$
As $\,W_{ij}$ are invariant to translations and rotations of each input and its r-nearsest neighbors, the same weights can be used to reconstruct $\,y_i$

## Embedding the landmarks

Considering the factorization $\,K\approx QLQ^T$, we will get the following SDP:
Maximize trace($\,QLQ^T$) subject to :

1) $\,L\succeq 0$
2)$\,\sum_{ij}(QLQ^T)_{ij}=0$
3) For all (i,j) such that $\,\eta_{ij}=1$,

  $\,(QLQ^T)_{ii}-2(QLQ^T)_{ij}+(QLQ^T)_{jj}\leq\|x_i-x_j\|^2$


Because the matrix factorization is an approximate, the distance constraint has changed from equality to inequality.

The computation time in semidefinite programming depends on the matrix size and the number of constraints. Here, the matrix size in lSDE is much smaller than SDE. The number of constraints are the same. However, the constraints in lSDE are not sparse and this may lead to an lSDE even slower than SDE. To overcome this problem, one can feed an initial subset of constraints like just centering and semidifiniteness instead of the whole constraints. In the case that the solution violates the unused constraints, these will be added to the problem and the SDP solver will be run again.

## Experimental Results

In the first experiment, Figure 1<ref> The same paper. Figure 1 </ref>, only 1205 out of 43182 constraints had to be enforced based on Table 2.

In the second experiment, Table 1<ref> The same paper. Table 1 </ref>, despite the huge dimensionality reduction from D=60000 to d=5, many expected neighbors were preserved.

In the third experiment, Figure 2<ref> The same paper. Figure 2 </ref>, the results from $lSDE$ are differnet from the results from SDE, but they get close to each other with increasing number of landmarks. Here, as shown in Figure 4<ref> The same paper. Figure 4 </ref>, $lSDE$ is slower than SDE. Because the ddataset is too small and has a particular cyclic structure so that incremental scheme for adding constraints doesn't work well.