Diffusion Maps implementation

Question

Suppose I have n data points lying in $\mathbf{R}^3$. Then, after defining my Gaussian diffusion kernel $k(x,y)$ and computing matrix $K$, I obtain $P$, whose entries $P_{ij}=p(x_i,y_i)$ is the transition probability of jumping from point i to point j in a random walk process. Now, $P\in \mathbf{R}^{n\times n}$, thus its ith eigenvector $\Phi_i$ with eigenvalue $\lambda_i$ lives in $\mathbf{R}^{n\times 1}$. The papers treating diffusion maps now say that the t-th diffusion map of data point $x$ is defined to be

$\Psi_t(x)=(\lambda_1^t\Phi_1(x),\lambda_2^t\Phi_2(x),...,\lambda_d^t\Phi_d(x))^T$, where $d$ is no. of dimensions I chose to retain.

Now I am at a loss here: If $\Phi_1$ in the discrete case is a vector, what is $\Phi_1(x)$? Normally, I would do $\Phi_1^T\cdot x$, however, this is clearly not possible here, as the dimensions don't check out. So, what can possibly be meant by $\Phi_1(x)$?

Answer 1

Let $x_i$ be your $i$-th data point. Here you should interpret $\Phi_k(x_i)$ as the $i$-th element of the $k$-th eigenvector.

---

Here's a bit more detail: Let $D=\{x_i\}_{i=1}^n\subseteq\mathbb{R}^N$ be your data set and $\lambda_k$ and $v_k=(v_{1k},\ldots,v_{nk})^T$ be the $k$-th eigenvalue and eigenvector of $P\in\mathbb{R}^{n\times n}$ (the transition matrix as defined above). The $t$-th diffusion map is given by

$$\psi_t(x_i) = (\lambda_1^t v_{i1}, \lambda_2^t v_{i2},\ldots,\lambda_d^t v_{id})$$

where $d$ is the number of dimensions on wishes to retain. In general, the diffusion map is only defined for points in your data set $D$ and undefined for $x\notin D$. An extension of the diffusion map to $D\subseteq\Omega\subseteq\mathbb{R}^N$ is a map $\Psi_t:\Omega\to \mathbb{R}^d$ such that $\Psi_t(x_i)=\psi_t(x_i)=(\lambda_i^t v_{ik})_{i=1}^d$. Or in other words $\Phi_k(x_i)=v_{ik}$.