# Diffusion Maps (DM)

## Introduction

在高維度的空間中，數據往往容易變得稀疏，也不容易觀察出其性質，因此我們想要利用 Diffusion Maps 的方法讓高維度數據 maps 到低維度的空間中觀察，並同時保持數據間的關聯性(affinity).

## Algorithm

### Affinity

首先，我們先給定一個關係矩陣 (Affinity Matrix)，這邊使用Gaussian Kernal

$$K_{ij} := \exp(\frac {-\||X_{i} - X_{j}||^{2}} {\sigma^2})$$

公式中的 $\sigma$ 是一個常數。而這個 $K$ 矩陣滿足下性質

* $K$ 是對稱矩陣 (Symmetric Matrix)
* $K$ 的每一個元素都 $\geq 0$
* $K$ 是一個半正定矩陣 (Non-negative definite)

接著我們對$K$矩陣normalize.

$$P := D^{-1}K$$

$D$ 是一個 rowsum 矩陣，$D_{ii} := \sum^{n}_{j=1}K_{ij}$

$P$ 矩陣滿足一下性質

* P 是馬可夫矩陣 (Markov matrix)
* P 是機率密度函數矩陣 (Probability Density Function)

接著我們可以就可以定義新的空間下的距離。

$$d(X_{i}, X_{j})^{2} := \|p_i-p_j\|^{2}_{R^n}$$

$p_{i}$ 表示 $P$ 的第 i 個 row。

如果兩個點**很近**的話，那麼他們兩個到其他所有點的 Random walk 機率應該會很相似，所以我們將 Diffusion Distance 定義為兩個p.d.f.的距離(Euclidean distance)

### Mapping

我們想要對 $P$ 做 eigen-decomposition，但是 $P$ 沒有很好的性質，會花恨多時間計算。
所以我們定義一個新的 $P'$ 矩陣：

$$P' := D^{-\frac{1}{2}}KD^{-\frac{1}{2}}$$

可以很輕易地判斷 $P'$ 是一個對稱矩陣，而對稱矩陣滿足兩個性質

* Eigenvalues are all real
* Eigenvectors are orthogonal

Apply eigen-decomposion

$$P' = Q\Lambda Q^{T}$$

而我們可以利用 $P'$ 的 eigenvalues, eigenvectors 找出 $P$ 矩陣的 eigen-decomposion.

$P = S\Lambda S^{-1} = \sum^n_{i=1}\lambda_iv_ie_i^T$

其中

* $P$ 和 $P'$ 有相同的 eigenvalues
* $S = D^{-\frac{1}{2}}Q$

$S^{-1}$ is orthogonal. In the other word, it's a orthonormal basis in $R^{n}$ (Diffusion Space). And $S\Lambda$ is the coordinates.

所以現在我們知道何謂 Diffusion Maps 了，就是將 d-dimension 的數據先送到 n-dimension 的 Diffusion Space，而 Diffusion Distance 就是 Diffusion Space 的距離(Euclidean Distance).

### Dimensional Reduction

$\Lambda$ is a diagonal matrix and $\lambda_1\geq
\lambda_2\geq...\geq \lambda_n\geq 0$.

Since $P$ is markov matrix, 最大的 eigenvalue $\lambda_1$ 都會是 $1$

運用類似PCA的想法，我們的想要將資料降到 $\mathbb{R}^q$ ，那麼取 $\lambda_2v_2\sim\lambda_{q+1}v_{q+1}$ 當作 Diffusion Space 的座標就行了。

為什麼是從第二個開始取呢，因為 Markov matrix 的性質，$v_1$ 通常是定值
所以可以想像如果投影到 $[\lambda_1v_1, \lambda_2v_2, \lambda_3v_3]$ 的話，第一個component都是定值的話，等同於三維空間中，其中一個軸的值是固定的，那麼它就會在一個面上。這個結果和投影到 $[\lambda_2v_2, \lambda_3v_3]$ 是一樣的，因此在投影的時候我們可以忽略掉第一個 vector 。

## Extension

在選擇 Kernal Function 的常數 $\sigma$ 時，可以參考Local Scaling 的 Idea 選擇 每個點到第 s 個點的距離，而因為是Global，所以選擇這些距離的中位數。

### Proof of non-negative definite

We shall prove that

$$x^TKx\geq0$$
$K_{ij}=exp(\frac{-\|x_i-x_j\|}{\sigma})\ ,\ x=[a_1\ a_2\cdots a_n]$

我們先討論 1-norm 的情況( $\sigma$是常數，視為 1 )
$x^TKx=\sum_{i,j=1}a_i\ e^{-|x_i-x_j|}\ a_j$

$=\sum_{i,j=1}a_i\ a_j\ e^{-(x_i+x_j)+2\min\{x_i,x_j\}}$

$=\sum_{i,j=1}\frac{a_ia_j}{e^{x_i}e^{x_j}} e^{2\min\{x_i,x_j\}}$

Define a function $\mathbb I_S: \mathbb{R} \to \mathbb{R}$ s.t.

$\mathbb I_S^{(t)} = \left\{ \begin{array}{} 1& \mbox{for}& t\in S \\ 0 & \mbox{for} & t\notin S\end{array}\right.$

Then, $\min\{x, y\}=\int_0^\infty \mathbb{I}_{[0,x]}^{(t)}\ \mathbb{I}_{[0,y]}^{(t)}dt$

$\Rightarrow\sum_{i,j=1}\frac{a_ia_j}{e^{x_i}e^{x_j}} e^{2min\{x_i,x_j\}}$

$=\sum_{i,j=1}\frac{a_ia_j}{e^{x_i}e^{x_j}}\min\{e^{2x_i}, e^{2x_j}\}$

$=\sum_{i,j=1}\frac{a_ia_j}{e^{x_i}e^{x_j}}\int_0^\infty \mathbb{I}_{[0,e^{x_i}]}^{(t)}\ \mathbb{I}_{[0,e^{x_j}]}^{(t)}dt$

$=\int_0^\infty\sum_{i,j=1}\frac{a_ia_j}{e^{x_i}e^{x_j}}\mathbb{I}_{[0,e^{x_i}]}^{(t)}\ \mathbb{I}_{[0,e^{x_j}]}^{(t)}dt$

$=\int_0^\infty[\sum_{i=1}\frac{a_i}{e^{x_i}}\mathbb{I}_{[0,e^{x_i}]}^{(t)}]^2dt\geq0$

$\Rightarrow x^TKx \geq 0$

所以，在1-norm的情況下，Affinity Matrix 是半正定矩陣。

在其他p-norm的情況下
By the $\href{https://proofwiki.org/wiki/Norms_on_Finite-Dimensional_Real_Vector_Space_are_EquivalentThm}
{Equivalent\ Norm},\ \exists\ n,\ m\gt 0$ s.t.

$$n\, \|x\|_{p}\leq |x|\leq m\, \|x\|_p$$

$\Rightarrow n\, \|x\|_p \leq |x|$

$\Rightarrow -|x|\leq -n\, \|x\|_p$

$\Rightarrow e^{-|x|} \leq e^{-n\, \|x\|_p}$

$\Rightarrow$ For all $i,\ j\ ,\ e^{-|x_i-x_j|} \leq e^{-n_{ij}\|x_i-x_j\|_p}$

$\Rightarrow$ Choose $n=\min\{n_{ij}\}$, then $e^{-|x_i-x_j|} \leq e^{-n\|x_i-x_j\|_p} \leq ne^{-\|x_i-x_j\|_p}$

$\Rightarrow K \leq \, ?K_p$, where n is scalar

$\Rightarrow 0 \leq x^TKx \leq n\, x^TK_px$

$\Rightarrow x^TK_px \geq 0$

因此，對於所有 p-norm 而言，這邊所定義的 Affinity Matrix 一定是半正定的。