# Multi-View Diffusion Maps

Ofir Lindenbaum1 Arie Yeredor1 Moshe Salhov2 Amir Averbuch2111Corresponding
author<EMAIL_ADDRESS>
1School of Electrical Engineering, Tel Aviv University, Israel
2School of Computer Science, Tel Aviv University, Israel

###### Abstract

In this paper, a reduced dimensionality representation is learned from
multiple views of the processed data. These multiple views can be obtained,
for example, when the same underlying process is observed using several
different modalities, or measured with different instrumentation. The goal is
to effectively utilize the availability of such multiple views for various
purposes such as non-linear embedding, manifold learning, spectral clustering,
anomaly detection and non-linear system identification. The proposed method,
which is called multi-view, exploits the intrinsic relation within each view
as well as the mutual relations between views. This is achieved by defining a
cross-view model in which an implied random walk process is restrained to hop
between objects in the different views. This multi-view method is robust to
scaling and it is insensitive to small structural changes in the data. Within
this framework, new diffusion distances are defined to analyze the spectra of
the implied kernels. The applicability of the multi-view approach is
demonstrated for clustering, classification and manifold learning using both
artificial and real data.

##  I Introduction

High dimension big data exist in various fields and it is difficult to analyze
them as is. Extracted features are useful in analyzing these datasets. Some
prior knowledge or modeling is required in order to identify the essential
features. On the other hand, dimensionality reduction methods are purely
unsupervised aiming to find a low dimensional representation that is based on
the intrinsic geometry of the analyzed dataset that includes the
connectivities among multidimensional data points within the dataset. A “good”
dimensionality reduction methodology reduces the complexity of a data
processing while preserving the coherency of the original data such that
clustering, classification, manifold learning and many other data analysis
tasks can be applied effectively in the reduced space. Many methods such as
Principal Component Analysis (PCA) [1], Multidimensional Scaling (MDS) [2],
Local Linear Embedding [3], Laplacian Eigenmaps [4], Diffusion Maps (DM) [5]
and more have been proposed to achieve dimensionality reduction that preserve
its data coherency. Exploiting the low dimensional representation yields
various applications such as face recognition that is based on Laplacian
Eigenmaps [6], Non-linear independent component analysis with DM [7], Musical
Key extraction using DM [8], and many more. The DM framework extends and
enhances ideas from other methods by utilizing a stochastic Markov matrix that
is based on local affinities between multidimensional data points to identify
a lower dimension representation for the data. All the mentioned methods do
not consider the possibility of having more than one view to represent the
same process. An additional view can provide meaningful insight regarding the
dynamical process that has generated and governed the data.

In this paper, we consider learning from data that is analyzed by multiple
views. The goal is to effectively utilize multiple views such as non-linear
embedding, multi-view manifold learning, spectral clustering, anomaly
detection and non-linear system identification to achieve better analysis of
high dimension big data. Most dimensionality reduction methods suggest to
concatenate the datasets into a single vector space. However, this methodology
is sensitive to scalings of each data component. It does not utilize for
example the fact that noise in both datasets could be uncorrelated. It assumes
that both datasets lie in one high dimensional space which is not always true.

The problem of learning from two views has been studied in the field of
spectral clustering. Most of these studies have been focused on classification
and clustering that are based on spectral characteristics of the data while
using two or more sampled views. Some approaches, which address this problem,
are Bilinear Model [9], Partial Least Squares [10] and Canonical Correlation
Analysis [11]. These methods are powerful for learning the relation between
different views but do not provide separate insights or combined into the low
dimensional geometry or structure of each view. Recently, a few kernel based
methods (e.g [12]) propose a model of co-regularizing kernels in both views in
a way that resembles joint diagonalization. It is done by searching for an
orthogonal transformation that maximizes the diagonal terms of the kernel
matrices obtained from all views. A penalty term, which incorporates the
disagreement between clusters from the views, was added. Their algorithm is
based on alternating maximization procedure. A mixture of Markov chains is
proposed in [13] to model multiple views in order to apply spectral
clustering. It deals with two cases in graph theory: directed and undirected
graph where the second case is related to our work. This approach converges
the undirected graph problem to a Markov chains averaging where each is
constructed separately within the views. A way to incorporate a given multiple
metrics for the same data using a cross diffusion process is described in
[14]. They define a new diffusion distance which is useful for classification,
clustering or retrieval tasks. However, the proposed process is not
symmetrical thus does not allow to compute an embedding. An iterative
algorithm for spectral clustering is proposed in [15]. The idea is to
iteratively modify each view using the representation of the other view. The
problem of two manifolds, which were derived from the same data (i.e two
views), is described in [16]. This approach is similar to Canonical
Correlation Analysis [17] that seeks a linear transformation that maximizes
the correlation among the views. It demonstrates the power of this method in
canceling uncorrelated noise present in both views. Furthermore, [16] applies
its method to a non-linear system identification task. A similar approach is
proposed in [18]. It suggests data modeling that uses a bipartite graph and
then, based on the ‘minimum-disagreement’ algorithm, partitions the dataset.
This approach attempts to minimize the cluster’s disagreement between two
views. The study presented in [19] utilizes the agreement also called
consensus between different views to extract the geometric information from
all views. The framework takes advantage of properties of the Mahalanobis
distance to compute a robust multi-view kernel.

The problem of multi-view dimensionality reduction was also studied using
Gaussian Process Latent Variable Models [20]. The work by [21] uses a Gaussian
process regression to learn common hidden structure. The studies by [22] and
[23] demonstrate the capabilities of such models for extracting meaningful
parameters from images. A related work by [24] attempts to maximize the mutual
information between the sampled views and the latent variables. Studies such
as [25, 26, 27] use a probabilistic CCA to factorize the data to a common and
view specific information.

In this work, we present a framework based on the construction in [18] and
show that this approach is a special case of a more general diffusion based
process. We build and analyze a new framework that generalizes the random walk
model while utilizing multiple views. Our proposed method utilizes the
intrinsic relation within each view as well as the mutual relations between
views. The multi-view is achieved by defining a cross diffusion process in
which a special structured random walk is imposed between the various views.
Within this framework, new diffusion distances are defined to analyze the
spectra of the new kernels and compute the infinitesimal generator to where
the multi-view-based our kernel converges. The constructed multi-view kernel
matrix is similar to a symmetric matrix thus guarantees real eigenvalues and
eigenvectors, this property enables us to define an multi-view embedding. The
advantages of the proposed method for manifold learning and spectral
clustering are explored using vast experiments.

The paper has the following structure: Background is given in section II.
Section III presents and analyzes the multi-view framework. Section IV-F
studies the asymptotic properties of the proposed kernel
$\widehat{{\mbox{\boldmath$K$}}}$ (Eq. (5)). Section VI presents the
experimental results.

##  II Background

###  II-A General dimensionality reduction framework

Consider a high dimensional dataset
${{\mbox{\boldmath$X$}}=\\{{{{\mbox{\boldmath$x$}}_{1},{\mbox{\boldmath$x$}}_{2},{\mbox{\boldmath$x$}}_{3},...,{\mbox{\boldmath$x$}}_{M}}}\\}\in{\mathbb{R}^{M\times
N}}},$
${\mbox{\boldmath$x$}}_{i}\in\mathbb{R}^{N},~{}i=1,\ldots,M$. The goal is to
find a low dimensional representation
${{\mbox{\boldmath$Z$}}=\\{{{{\mbox{\boldmath$z$}}_{1},{\mbox{\boldmath$z$}}_{2},{\mbox{\boldmath$z$}}_{3},...,{\mbox{\boldmath$z$}}_{M}}}\\}\in{\mathbb{R}^{M\times
S}}}$, ${\mbox{\boldmath$z$}}_{i}\in\mathbb{R}^{S},~{}i=1,\ldots,M$, such that
${S\ll N}$ and the local connectivities among the multidimensional data points
are preserved. This problem setup is based on the assumption that the data is
represented (viewed) by a single vector space (single view).

###  II-B Diffusion Maps (DM)

DM [5] is a dimensionality reduction method that finds the intrinsic geometry
in the data. This framework is highly effective when the data is densely
sampled from some low dimensional manifold that is not linear. Given a high
dimensional dataset $X$, the DM framework contains the following steps:

  1. 1.

A kernel function
${{\cal{K}}:{\mbox{\boldmath$X$}}\times{{\mbox{\boldmath$X$}}}\longrightarrow{\mathbb{R}}}$
is chosen. It is represented by a matrix
${\mbox{\boldmath$K$}}\in{\mathbb{R}^{M\times M}}$ which satisfies for all
${({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$x$}}_{j})\in{{\mbox{\boldmath$X$}}}}$
the following properties: Symmetry:
${K_{i,j}={\cal{K}}({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$x$}}_{j})={\cal{K}}({\mbox{\boldmath$x$}}_{j},{\mbox{\boldmath$x$}}_{i})}$,
positive semi-definiteness:
${{\mbox{\boldmath$v$}}_{i}^{T}{\mbox{\boldmath$K$}}{\mbox{\boldmath$v$}}_{i}\geq
0}$ for all ${\mbox{\boldmath$v$}}_{i}\in\mathbb{R}^{M}$ and
${{\cal{K}}({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$x$}}_{j})\geq 0.}$
These properties guarantee that the matrix $K$ has real eignenvectors and non-
negative real eigenvalues. Gaussian kernel is a common example where
$K_{i,j}=exp\\{{-\frac{||{\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$x$}}_{j}||^{2}}{2\sigma_{x}^{2}}\\}}$
with an $L_{2}$ norm as the affinity measure between two data vectors;

  2. 2.

By normalizing the kernel using $D$ where
$D_{i,i}=\underset{j}{\sum}{K_{i,j}}$, we compute the following matrix
elements:

${P_{i,j}^{x}={\cal{P}}({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$x$}}_{j})=[{{{\mbox{\boldmath$D$}}}^{-1}{{\mbox{\boldmath$K$}}}}}]_{i,j}.$
(1)

The resulting matrix ${\mbox{\boldmath$P$}}^{x}\in\mathbb{R}^{M\times M}$ can
be viewed as the transition kernel of a (fictitious) Markov chain on $X$ such
that the expression
${[{({\mbox{\boldmath$P$}}^{x})^{t}}]_{i,j}}=p_{t}({\mbox{\boldmath$x$}}_{i}$,${\mbox{\boldmath$x$}}_{j})$
describes the transition probability from point ${{\mbox{\boldmath$x$}}_{i}}$
to point ${{\mbox{\boldmath$x$}}_{j}}$ in $t$ steps.

  3. 3.

Spectral decomposition is applied to matrix ${\mbox{\boldmath$P$}}^{x}$ or to
one of its powers $({\mbox{\boldmath$P$}}^{x})^{t}$ to obtain a sequence of
eigenvalues ${\\{{\lambda_{m}}\\}}$ and normalized eigenvectors
${\\{{{\mbox{\boldmath${\psi}$}}_{m}}\\}}$ that satisfies
${{{\mbox{\boldmath$P$}}^{x}}{\mbox{\boldmath${\psi}$}_{m}}=\lambda_{m}{\mbox{\boldmath${\psi}$}}_{m},m=0,...,M-1}$;

  4. 4.

Define a new representation for the dataset $X$

${{\mbox{\boldmath$\Psi$}}_{t}{({\mbox{\boldmath$x$}}_{i})}:{\mbox{\boldmath$x$}}_{i}\longmapsto\begin{bmatrix}{\lambda_{1}^{t}\psi_{1}[i]},{\lambda_{2}^{t}\psi_{2}[i]},{\lambda_{3}^{t}\psi_{3}[i]},{.}{.}{.},\par{\lambda_{M-1}^{t}\psi_{M-1}[i]}\\\
\end{bmatrix}^{T}\in{\mathbb{R}^{M-1}}},$ (2)

where $t$ is the selected number of steps and $\psi_{m}[i]$ denotes the
$i^{\rm{th}}$ element of ${\mbox{\boldmath${\psi}$}_{m}}$.

The main idea behind this representation is that the Euclidian distance
between two data points in the new representation is equal to the weighted
$L_{2}$ distance between the conditional probabilities
${{p}_{t}({\mbox{\boldmath$x$}}_{i},:)}$, and
${{p}_{t}({\mbox{\boldmath$x$}}_{j},:)}$, $i,j=1,...,M$ (the $i$-th and $j$-th
rows of ${\mbox{\boldmath$P$}}^{t}$). The following is referred as the
Diffusion Distance

${{{\cal{D}}^{2}_{t}({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$x$}}_{j})=||{{\mbox{\boldmath$\Psi$}}_{t}{({\mbox{\boldmath$x$}}_{i})}}-{{\mbox{\boldmath$\Psi$}}_{t}{({\mbox{\boldmath$x$}}_{j})}}||^{2}={\sum_{m\geq{1}}{\lambda}^{2t}_{m}(\psi_{m}[i]-\psi_{m}[j])^{2}}}=||{p_{t}}({\mbox{\boldmath$x$}}_{i},:)-{p_{t}}({\mbox{\boldmath$x$}}_{j},:)||^{2}_{\tiny{\mbox{\boldmath$W$}}^{-1}}},$
(3)

where $W$ is a diagonal matrix with elements
$W_{i,i}=\frac{D_{i,i}}{\sum_{i=1}^{M}D_{i,i}}$. This equality is proven in
[5].

  5. 5.

The desired accuracy $\delta\geq 0$ is chosen for the diffusion distance
defined by Eq. (3) such that $s(\delta,t)=\text{max}\\{\ell\in\mathbb{N}$ such
that $|\lambda_{\ell}|^{t}>\delta|\lambda_{1}|^{t}\\}$. By using $\delta$, a
new mapping of $s(\delta,t)$ dimensions is defined as
${\Psi^{(\delta)}_{t}:X\rightarrow\begin{bmatrix}{\lambda_{1}^{t}\psi_{1}[i]},{\lambda_{2}^{t}\psi_{2}(i)},{\lambda_{3}^{t}\psi_{3}[i]},{.}{.}{.},\par{\lambda_{s}^{t}\psi_{s}[i]}\\\
\end{bmatrix}^{T}\in\mathbb{R}^{s(\delta,t)}}$ .

This approach has been found useful in various fields. As previously noted, it
is limited to a single view representation. A common extension of this
approach to multiple views is to use a data concatenation from all views and
then apply the diffusion framework. This method assumes orthogonality of the
sampled dimensions which is an unrealistic assumption in many cases.
Furthermore, this approach can create redundancy in some dimensions and
requires scaling of each dimension separately such that none is preferable
over the others. Previous studies such as [28, 29] apply the DM framework to
each view individually and then incorporated the learned mapping from various
views. However, they do not exploit the mutual relations which might exist
between the different views to create and utilize the correct mapping.

##  III Multi-view dimensionality reduction

Problem Formulation: Given multiple sets of observations
${\mbox{\boldmath$X$}}^{l}\text{ },l=1,...,L$. Each view is a high dimensional
dataset
${{\mbox{\boldmath$X$}}^{l}=\\{{{{\mbox{\boldmath$x$}}_{1}^{l},{\mbox{\boldmath$x$}}_{2}^{l},{\mbox{\boldmath$x$}}_{3}^{l},...,{\mbox{\boldmath$x$}}_{M}^{l}}}\\}\in{\mathbb{R}^{M\times
N_{l}}}}$, $N_{l}$ is the dimension of each feature space. Note that a
bijective correspondence between views is assumed. For each view $l=1,...,L$,
we seek for a lower dimensional representation that preserves the interactions
between multidimensional data points within a given view
${\mbox{\boldmath$X$}}^{l}$ and among the views
$\\{{\mbox{\boldmath$X$}}^{1},{\mbox{\boldmath$X$}}^{2},...,{\mbox{\boldmath$X$}}^{L}\\}$.

###  III-A Multi-view Diffusion Maps

We begin by generalizing the DM framework for handling a multi-view scenario.
Our goal is to impose a random walk model using the local connectivities
between data points within all views. Our way to generalize the DM framework
is by restraining the random walker to “hop” between views in each step. The
construction requires to choose symmetrical positive semi-definite kernels for
each view
${{\cal{K}}^{l}:{\mbox{\boldmath$X$}}^{l}\times{{\mbox{\boldmath$X$}}^{l}}\longrightarrow{R}\text{
},l=1,...,L}$, we use the Gaussian function

${K^{l}_{i,j}=exp\\{{-\frac{||{\mbox{\boldmath$x$}}^{l}_{i}-{\mbox{\boldmath$x$}}^{l}_{j}||^{2}}{2\sigma_{l}^{2}}\\}}},$
(4)

then the multi-view kernel is formed by the following matrix

${\mbox{\boldmath$\widehat{K}$}}=\begin{bmatrix}{\mbox{\boldmath$0$}}_{M\times
M}&{{\mbox{\boldmath$K$}}^{1}{\mbox{\boldmath$K$}}^{2}}&{{\mbox{\boldmath$K$}}^{1}{\mbox{\boldmath$K$}}^{3}}&...&{{\mbox{\boldmath$K$}}^{1}{\mbox{\boldmath$K$}}^{L}}\\\
{\mbox{\boldmath$K$}}^{2}{\mbox{\boldmath$K$}}^{1}&{\mbox{\boldmath$0$}}_{M\times
M}&{{\mbox{\boldmath$K$}}^{2}{\mbox{\boldmath$K$}}^{3}}&...&{{\mbox{\boldmath$K$}}^{2}{\mbox{\boldmath$K$}}^{L}}\\\
{\mbox{\boldmath$K$}}^{3}{\mbox{\boldmath$K$}}^{1}&{{\mbox{\boldmath$K$}}^{3}{\mbox{\boldmath$K$}}^{2}}&{\mbox{\boldmath$0$}}_{M\times
M}&...&{{\mbox{\boldmath$K$}}^{3}{\mbox{\boldmath$K$}}^{L}}\\\ :&:&:&...&:\\\
{\mbox{\boldmath$K$}}^{L}{\mbox{\boldmath$K$}}^{1}&{{\mbox{\boldmath$K$}}^{L}{\mbox{\boldmath$K$}}^{2}}&{{\mbox{\boldmath$K$}}^{L}{\mbox{\boldmath$K$}}^{3}}&...&{{\mbox{\boldmath$0$}}_{M\times
M}}.\end{bmatrix}.$ (5)

Finally, by using the diagonal matrix $\widehat{D}$ where
${\widehat{D}}_{i,i}=\underset{j}{\sum}{{\widehat{K}}_{i,j}}$, the normalized
row-stochastic matrix is defined as

${\mbox{\boldmath$\widehat{P}$}}={{\mbox{\boldmath$\widehat{D}$}}}^{-1}{\mbox{\boldmath$\widehat{K}$}},~{}~{}~{}{\widehat{P}}_{i,j}=\frac{{{\widehat{K}}_{i,j}}}{\widehat{D}_{i,i}},$
(6)

where the $m,l$ block is a square $M\times M$ matrix located at
$[1+(m-1)M,1+(l-1)M],l=1,...,L$. This block describes the probability of
transition between view ${\mbox{\boldmath$X$}}^{m}$ and
${\mbox{\boldmath$X$}}^{l}$.

###  III-B Alternative multi-view approaches

In this section, we describe two additional methods for incorporating
different views. We do not analyze these approaches but use them as references
for comparisons in the experimental evaluations.
1\. Kernel Product DM (KP): The kernel matrix elements are multiplied element
wise
${\mbox{\boldmath$K$}}^{{\circ}}\stackrel{{\scriptstyle\triangle}}{{=}}{\mbox{\boldmath$K$}}^{1}\circ{\mbox{\boldmath$K$}}^{2}\circ...\circ{\mbox{\boldmath$K$}}^{L}$,
${K}_{i,j}^{\circ}\stackrel{{\scriptstyle\triangle}}{{=}}{K}_{i,j}^{1}\cdot{K}_{i,j}^{2}\cdot...\cdot{K}_{ij}^{L}$.
Then, they are normalized by the sum of rows. The resulting row stochastic
matrix is

${P_{i,j}^{\circ}=[{{{\mbox{\boldmath$D$}}^{\circ}}^{-1}{{\mbox{\boldmath$K$}}^{\circ}}}}]_{i,j},$
(7)

where $D_{i,i}^{\circ}=\underset{j}{\sum}{K_{i,j}^{\circ}}$.

######  Lema 1.

In the special case of a Gaussian kernel with
$\sigma_{1}=\sigma_{2}=...=\sigma_{L}$ in Eq. (4), the resulting matrix
${\mbox{\boldmath$K$}}^{\circ}$ is equal to the matrix
${\mbox{\boldmath$K$}}^{w}$ constructed using the concatenated vector
${\mbox{\boldmath$w$}}_{i}=[({\mbox{\boldmath$x$}}^{1}_{i})^{T},...,({\mbox{\boldmath$x$}}^{L}_{i})^{T}]^{T}$
such that
$K_{i,j}^{w}=exp\\{{-\frac{||{\mbox{\boldmath$w$}}_{i}-{\mbox{\boldmath$w$}}_{j}||^{2}}{2\sigma_{w}^{2}}\\}}$.
The scale is set to

${\sigma}_{w}=\sqrt{\sum_{{}_{i}=1}^{L}{\sigma}^{2}_{i}}=\sqrt{L\cdot{\sigma}^{2}_{1}},$
(8)

where the last equality holds only for this special case.

This approach, which corresponds to [5], will be referred as the Kernel
Product DM in section VI.
2\. Kernel Sum DM (KS): The sum kernel is defined as
${\mbox{\boldmath$K$}}^{+}\stackrel{{\scriptstyle\triangle}}{{=}}\sum^{L}_{l=1}{\mbox{\boldmath$K$}}^{l}$.
By normalizing the sum kernel by the diagonal matrix
${\mbox{\boldmath$D$}}^{+}=\underset{j}{\sum}{K_{i,j}^{+}}$, we get

${P_{i,j}^{+}=[{{{\mbox{\boldmath$D$}}^{+}}^{-1}{{\mbox{\boldmath$K$}}^{+}}}}]_{i,j}.$
(9)

This random walk sums the step probabilities from each view. This approach is
proposed in [13].

###  III-C Probabilistic interpretation of
$\widehat{{\mbox{\boldmath$P$}}}^{t}$

In our proposed construction (Eqs. (4), (5) and (6)), the entries
$[\widehat{{\mbox{\boldmath$P$}}}^{t}]_{i,j}=\widehat{p}_{t}({\mbox{\boldmath$x$}}^{1}_{i},{\mbox{\boldmath$x$}}^{1}_{j})$
denote for each $i,j=1,\ldots,M$, the transition probability from node
${\mbox{\boldmath$x$}}^{1}_{i}$ to node ${\mbox{\boldmath$x$}}^{1}_{j}$ in $t$
time steps by “hopping” between the views ${\mbox{\boldmath$X$}}^{1}$ and
${\mbox{\boldmath$X$}}^{l},l=2,...,L$ in each time step, where $L$ is the
total number of views. Note that due to the block-anti-diagonal structure of
$\widehat{K}$ (and $\widehat{P}$ (Eq. (6))), this probability is zero for
$t=1$. However, for higher values of $t$, this probability is nonzero
describing a time transition from view ${\mbox{\boldmath$X$}}^{1}$ through any
view ${\mbox{\boldmath$X$}}^{l},l=2,...,L$ and back to
${\mbox{\boldmath$X$}}^{1}$. In the same way,
$[\widehat{{\mbox{\boldmath$P$}}}^{t}]_{i+(l-1)\cdot
M,j+(l-1)M}=\widehat{p}_{t}({\mbox{\boldmath$x$}}^{l}_{i},{\mbox{\boldmath$x$}}^{l}_{j})$
denotes the transition probability from node ${\mbox{\boldmath$x$}}^{l}_{i}$
to node ${\mbox{\boldmath$x$}}^{l}_{j}$, $i,j=1,\ldots,M$, in $t$ time steps.
Likewise, $[\widehat{P}^{t}]_{i+(l-1)\cdot
M,j+(m-1)M}=\widehat{p}_{t}({\mbox{\boldmath$x$}}^{l}_{i},{\mbox{\boldmath$x$}}^{m}_{j})$
denotes the transition probability from node ${\mbox{\boldmath$x$}}^{l}_{i}$
to node ${\mbox{\boldmath$x$}}^{m}_{j}$, $i,j=1,\ldots,M$, $l\neq m$ in $t$
time steps.

####  III-C1 Smoothing effect $t=1$

For simplicity let us examine the term
$\widehat{p}_{t}({\mbox{\boldmath$x$}}^{l}_{i},{\mbox{\boldmath$x$}}^{m}_{j}),l\neq
m$ for $t=1$. The transition probability for $t=1$ is

${{\widehat{p}}}_{1}({\mbox{\boldmath$x$}}^{l}_{i},{\mbox{\boldmath$x$}}^{m}_{j})=\frac{\sum_{s}{K^{l}_{i,s}}K^{m}_{s,j}}{{\widehat{D}_{i,i}}}.$

This probability takes into consideration all the various connectivities of
node ${\mbox{\boldmath$x$}}^{l}_{i}$ to node ${\mbox{\boldmath$x$}}^{l}_{s}$
and the connectivities of the corresponding node
${\mbox{\boldmath$x$}}^{m}_{s}$ to the destination node
${\mbox{\boldmath$x$}}^{m}_{j}$. The proposed multi-view approach has a
smoothing effect in terms of the transition probability. By smoothing effect,
we mean that the probability of transitioning from
${\mbox{\boldmath$x$}}^{l}_{i}$ to ${\mbox{\boldmath$x$}}^{m}_{j}$ could be
larger than zero even if $K^{l}_{i,j}=0$ and $K^{m}_{i,j}=0$. Assume that
there is a subset ${\cal{S}}=\\{s_{1},...,s_{F}\\}$ such that
$K^{l}_{i,s_{f}}>0$ and $K^{m}_{s_{f},j}>0,f=1,..,F$, by definition of the
multi-view probability we get that
${\widehat{p}}_{1}({\mbox{\boldmath$x$}}^{l}_{i},{\mbox{\boldmath$x$}}^{m}_{j})>0$.

Figure 1 illustrates the multi-view transition probabilities compared to a
single view approach using two deformed Swiss-roll manifolds ($L=2$). In each
view, there is no probability of transition from one side of the gap to the
other. The multi-view transition probability is non-zero for points at both
sides of the gap. This smoothing effect occurs because the gap is located near
different points on both views, thus allowing the multi-view kernel to smooth
the nonlinear gap.

Figure 1: Top left: Non-smooth Swiss Roll sampled from View-I ($X$), colored
by the single view probability of transition ($t=1$) from
${\mbox{\boldmath$x$}}_{1}$ to ${\mbox{\boldmath$x$}}_{:}$. Top right: second
Swiss Roll sampled from View-II ($Y$), colored by the single view probability
of transition ($t=1$) from ${\mbox{\boldmath$y$}}_{1}$ to
${\mbox{\boldmath$y$}}_{:}$. Bottom left: the first Swiss Roll colored the
multi-view probabilities of transition ($t=1$) from $x_{i}$ to
${\mbox{\boldmath$y$}}_{:}$. This point ${\mbox{\boldmath$x$}}_{1}$ denoted
with an arrow in the top left figure. Bottom right: a low dimensional
representation extracted based on the multi-view transition matrix
$\widehat{{\mbox{\boldmath$P$}}}$ (Eq. 6).

####  III-C2 Increasing the diffusion step $t$

Under the stochastic Markov model assumption, increasing the power of the
matrix $\widehat{{\mbox{\boldmath$P$}}}$ spreads the probability along the
data points based on the connectivities in all views. This probability spread
as describe in [5] reduces the influence of high eigenvectors on the diffusion
distance (Eq. (10)). This implies that the eigenvectors corresponding to low
eigenvalues have a low-frequency content, whereas the eigenvectors
corresponding to the high eigenvalues describe the oscillatory behavior of the
data [5]. In Fig. 2, we present the eigenvalues of the matrix
$\widehat{{\mbox{\boldmath$P$}}}^{t}$ at different values of $t$. For the
experiment we have generated $L=3$ Swiss rolls with $M=1200$ data points each.
It is evident that the numerical rank of $\widehat{{\mbox{\boldmath$P$}}}^{t}$
decreases for higher values of $t$.

Figure 2: The decay of the eigenvalues for increasing powers of the matrix
$\widehat{{\mbox{\boldmath$P$}}}$.

###  III-D Multi-view diffusion distance

In a variety of real data types, the Euclidean distance does not provide a
sufficient information about the intrinsic relations between data points. The
Euclidean distance is highly sensitive to scaling and rotations of
multidimensional data points. Tasks such as classification, clustering or
system identification require a measure for the intrinsic connectivity between
data points. This type of measure is only satisfied locally by the Euclidean
distance in the high dimensional ambient space. The multi-view diffusion
kernel (defined in section (III-A)) describes all the small local connections
between data points. The row stochastic matrix
${\mbox{\boldmath$\widehat{P}$}}^{t}$ (Eq. (6)) incorporates all the
possibilities for having a transition in $t$ time steps between data points
that are hopping between both views. For a fixed value $t>0$, two data points
are intrinsically similar if the conditional distributions
${\widehat{{\mbox{\boldmath$p$}}}}_{t}({\mbox{\boldmath$x$}}_{i},:)={\mbox{\boldmath${[\widehat{P}]}$}}^{t}_{i,:}$
and
${\widehat{{\mbox{\boldmath$p$}}}}_{t}({\mbox{\boldmath$x$}}_{j},:)={\mbox{\boldmath${[\widehat{P}]}$}}^{t}_{j,:}$
are similar. This type of similarity measure indicates that the points $x_{i}$
and $x_{j}$ are similarly connected to several mutual points. Thus, they are
connected by a geometrical path. In many cases, a small Euclidean distance can
be misleading due to the fact that two data points can be “close” without
having any geodesic path that connects them. Comparing the transition
probabilities is more robust as it takes into consideration all of the local
connectivities between the compared points. Therefor, even if two points do
not have a small Euclidean distance between them, they may have many common
neighbors and thus have a low diffusion distance.

Based on this observation, by expanding the single view construction given in
[5], we define the weighted inner view diffusion distances for the first view
as

${{{{{\cal{D}}_{t}}}^{2}({\mbox{\boldmath${{x}}$}}^{1}_{i},{\mbox{\boldmath$x$}}^{1}_{j})\stackrel{{\scriptstyle\triangle}}{{=}}\sum_{k=1}^{L\cdot
M}\frac{([{{\mbox{\boldmath${\widehat{P}}$}}}^{t}]_{i,k}-[{{\mbox{\boldmath${\widehat{P}}$}}}^{t}]_{j,k})^{2}}{\phi_{o}(k)}}=||({\mbox{\boldmath${e}$}}_{i}-{\mbox{\boldmath${e}$}}_{j})^{T}{\mbox{\boldmath$\widehat{P}$}}^{t}||^{2}_{\tiny{{\mbox{\boldmath$\widehat{D}$}}}^{-1}}},$
(10)

where $1\leq i,j\leq M$, ${\mbox{\boldmath${e}$}}_{i}$ is the $i$-th column of
an $L\cdot M\times L\cdot M$ identity matrix, $\phi_{0}$ is the first left
eigenvector of $\hat{P}$ and its $k$-th element is
$\phi_{0}(k)={\widehat{D}_{k,k}}$. The weighted norm of $x$ is defined by
$||{\mbox{\boldmath$x$}}||_{\tiny{{\mbox{\boldmath$W$}}}}^{2}={\mbox{\boldmath$x$}}^{T}{\mbox{\boldmath$W$}}{\mbox{\boldmath$x$}}$.
Similarly, the weighted norm is defined for the $l$-th view

${{{{{\cal{D}}_{t}}}^{2}({\mbox{\boldmath${{x}}$}}^{l}_{i},{\mbox{\boldmath$x$}}^{l}_{j})\stackrel{{\scriptstyle\triangle}}{{=}}\sum_{k=1}^{L\cdot
M}\frac{([{{\mbox{\boldmath${\widehat{P}}$}}}^{t}]_{\tilde{l}+i,k}-[{{\mbox{\boldmath${\widehat{P}}$}}}^{t}]_{\tilde{l}+j,k})^{2}}{\phi_{o}(k)}}=||({\mbox{\boldmath${e}$}}_{\tilde{l}+i}-{\mbox{\boldmath${e}$}}_{\tilde{l}+j})^{T}{\mbox{\boldmath$\widehat{P}$}}^{t}||^{2}_{\tiny{{\mbox{\boldmath$\widehat{D}$}}}^{-1}}},$
(11)

where $\tilde{l}=(l-1)\cdot M$. The main advantage of these distances (Eqs.
(10) and (11)) is that they can be expressed in terms of the eigenfunctions
and the eigenvectors of the matrix $\widehat{P}$. This insight allows us to
use a representation (defined in section III-E) where the induced Euclidean
distance is proportional to the diffusion distances defined in Eqs. (10) and
(11).

######  Theorem 1.

The inner view diffusion distance defined by Eqs. (10) and (11) is equal to

${{{{{\cal{D}}_{t}}}^{2}({\mbox{\boldmath$x$}}^{l}_{i},{\mbox{\boldmath$x$}}^{l}_{j})=\sum_{{k}=1}^{L\cdot
M-1}\lambda_{k}^{2t}(\psi_{k}[i+\tilde{l}]-\psi_{k}[j+\tilde{l}])^{2}},i,j=1,...,M},$
(12)

where $\tilde{l}=(l-1)\cdot M$.

###### Proof.

We express
${\mbox{\boldmath$\widehat{P}$}}^{t}\widehat{{\mbox{\boldmath$D$}}}^{-1}(\widehat{{\mbox{\boldmath$P$}}}^{t})^{T}$
by
${\mbox{\boldmath$\widehat{P}$}}^{t}\widehat{{\mbox{\boldmath$D$}}}^{-1}(\widehat{{\mbox{\boldmath$P$}}}^{t})^{T}={\mbox{\boldmath$\Psi$}}{\mbox{\boldmath$\Lambda$}}^{t}{\mbox{\boldmath$\Phi$}}^{T}\widehat{{\mbox{\boldmath$D$}}}^{-1}{\mbox{\boldmath$\Phi$}}{\mbox{\boldmath$\Lambda$}}^{t}{\mbox{\boldmath$\Psi$}}^{T}={\mbox{\boldmath$\Psi$}}{\mbox{\boldmath$\Lambda$}}^{2t}{\mbox{\boldmath$\Psi$}}^{t}$
since
${\mbox{\boldmath$\Phi$}}^{T}{\mbox{\boldmath$\widehat{D}$}}^{-1}{\mbox{\boldmath$\Phi$}}={\mbox{\boldmath$\Pi$}}^{T}{\mbox{\boldmath$\Pi$}}={\mbox{\boldmath$\rm{I}$}}$.
Therefore,
${{{\cal{D}}_{t}}}^{2}({\mbox{\boldmath$x$}}^{l}_{i},{\mbox{\boldmath$x$}}^{l}_{j})=\\\
||({\mbox{\boldmath${e}$}}_{\tilde{l}+i}-{\mbox{\boldmath${e}$}}_{\tilde{l}+j})^{T}{\mbox{\boldmath$\widehat{P}$}}^{t}||^{2}_{\tiny{{\mbox{\boldmath$\widehat{D}$}}}^{-1}}=({\mbox{\boldmath${e}$}}_{\tilde{l}+i}-{\mbox{\boldmath${e}$}}_{\tilde{l}+j})^{T}{\mbox{\boldmath$\widehat{P}$}}^{t}\widehat{{\mbox{\boldmath$D$}}}^{-1}(\widehat{{\mbox{\boldmath$P$}}}^{t})^{T}({\mbox{\boldmath${e}$}}_{\tilde{l}+i}-{\mbox{\boldmath${e}$}}_{\tilde{l}+j})=\\\
({\mbox{\boldmath${e}$}}_{\tilde{l}+i}-{\mbox{\boldmath${e}$}}_{\tilde{l}+j})^{T}{\mbox{\boldmath$\Psi$}}{\mbox{\boldmath$\Lambda$}}^{2t}{\mbox{\boldmath$\Psi$}}^{T}({\mbox{\boldmath${e}$}}_{\tilde{l}+i}-{\mbox{\boldmath${e}$}}_{\tilde{l}+j})=\sum_{{k}=0}^{L\cdot
M-1}\lambda_{k}^{2t}(\psi_{k}[{\tilde{l}+i}]-\psi_{k}[{\tilde{l}+j}])^{2}=\\\
\sum_{{k}=1}^{L\cdot
M-1}\lambda_{k}^{2t}(\psi_{k}[{\tilde{l}+i}]-\psi_{k}[{\tilde{l}+j}])^{2}.$
$\ell=0$ is excluded due to $\Psi_{0}={\mbox{\boldmath$1$}}$ (an all-ones
vector) that holds for all stochastic matrices. ∎

###  III-E Multi-view data parametrization

Tasks such as classification, clustering or regression in a high-dimension
feature space are considered to be computationally expensive. In addition, the
performance of these tasks is highly dependent on the distance measure. As
explained in section III-D, distance measures in the original ambient space
are meaningless in many real life situations. Interpreting Theorem 1 in terms
of Euclidean distance enables us to define mappings for every view
${\mbox{\boldmath$X$}}^{l},l=1,...,L$, using the right eigenvectors of
$\widehat{{\mbox{\boldmath$P$}}}$ (Eq. (6)) weighted by $\lambda^{t}_{i}$. The
representation for instances in ${\mbox{\boldmath$X$}}^{l}$ is given by

${{\mbox{\boldmath$\widehat{\Psi}$}}_{t}{({\mbox{\boldmath$x$}}^{l}_{i})}:{\mbox{\boldmath$x$}}^{l}_{i}\longmapsto\begin{bmatrix}{\lambda_{1}^{t}\psi_{1}[i+\bar{l}]},{.}{.}{.},\par{\lambda_{M-1}^{t}\psi_{M-1}[i+\bar{l}]}\par\end{bmatrix}^{T}\in{\mathbb{R}^{M-1}}},$
(13)

where $\bar{l}=(l-1)\cdot M$. These $L$ mappings capture the intrinsic
geometry of the views as well as the mutual relation between them. As shown in
[30], the set of eigenvalues ${\lambda_{m}}$ has a decaying property such that
${1=\lvert{\lambda_{0}}\rvert\geq\lvert{\lambda_{1}}\rvert\geq\text{...}\geq\lvert{\lambda_{M-1}}\rvert}$.
Exploiting the decaying property enables us to represent data up to a
dimension $r$ where $r\ll N_{1},...,N_{L}$. The dimension $r\equiv r(\delta)$
is determined by approximating the diffusion distance (Eq. (12)) up to a
desired accuracy $\delta$. This argument is expanded in section IV-D. The
reduced dimension version of
${{\mbox{\boldmath$\widehat{\Psi}$}}_{t}{({\mbox{\boldmath$X$}})}}$ is denoted
by ${{\mbox{\boldmath$\widehat{\Psi}$}}^{r}_{t}{({\mbox{\boldmath$X$}})}}$.

Using the inner view diffusion distances defined in Eqs. (10) and (11), we
define a multi-view diffusion distance as a linear combination of the inner
views distances such that

${{{{{\cal{D}}_{t}}^{(MV)}}^{2}(i,j)\stackrel{{\scriptstyle\triangle}}{{=}}\sum_{l=1}^{L}||{{\mbox{\boldmath$\widehat{\Psi}$}}^{r}_{t}{({\mbox{\boldmath$x$}}^{l}_{i})}}-{{\mbox{\boldmath$\widehat{\Psi}$}}^{r}_{t}{({\mbox{\boldmath$x$}}^{l}_{j})}}||^{2}}}.$
(14)

This distance is the induced Euclidean distance in a space constructed from
the concatenation of all low dimensional multi-view mappings

$\widehat{{\mbox{\boldmath$\Psi$}}}_{t}({{\mbox{\boldmath$X$}}})={[{\mbox{\boldmath$\widehat{\Psi}$}}^{r}_{t}{({\mbox{\boldmath$X$}}^{1})}},{\mbox{\boldmath$\widehat{\Psi}$}}^{r}_{t}{({\mbox{\boldmath$X$}}^{2})},...,{\mbox{\boldmath$\widehat{\Psi}$}}^{r}_{t}{({\mbox{\boldmath$X$}}^{L})}].$
(15)

This mapping is used in section VI-B for the experimental evaluation of
clustering.

###  III-F Multi-view kernel bandwidth

When constructing the Gaussian kernels ${\mbox{\boldmath$K$}}^{l},l=1,...,L$,
in Eq. (4), the values of the scale (width) parameter $\sigma^{2}_{l}$ have to
be set. Setting these values to be too small may result in very small local
neighborhoods that are unable to capture the local structure around the data
point. On the contrary, setting the values to be too large may result in a
fully connected graph that may generate a coarse description of the data. In
[31], a max-min measure is suggested such that the scale becomes

$\sigma_{{l}}^{2}={{C}}\cdot\underset{j}{\max}[\underset{i,i\neq
j}{\min}(||{\mbox{\boldmath$x$}}^{l}_{i}-{\mbox{\boldmath$x$}}^{l}_{j}||^{2})],$
(16)

where ${{C}}$ is set within the range $[1,1.5]$. This approach attempts to set
a small scale to maintain local connectivities. This single view approach
could be relaxed in the multi-view scenario. The multi-view kernel
$\widehat{K}$ (Eq. 5) contains multiplication of single view kernel matrices
${\mbox{\boldmath$K$}}^{l},l=1,...,L$ (Eq. 4). The diagonal values of each
kernel matrix ${\mbox{\boldmath$K$}}^{l},l=1,...,L$ are all $1$’s, therefore,
a connectivity in only one view is sufficient. This insight suggests that
smaller value for the parameter ${{C}}$ could be used.

Another scheme by [32] aims to find a range of values for $\sigma_{l}$. The
idea is to compute the kernel ${\mbox{\boldmath$K$}}^{l}$ (Eq. (4)) for
various values of $\sigma$ and search for the range of values where the
Gaussian bell shape exists. The range is identified by applying a logarithmic
function to the sum of the kernel. We expand this idea for a multi-view
scenario based on the following algorithm:

Algorithm 1 Multi-view kernel bandwidth selection

Input: Multiple sets of observations (views)
${\mbox{\boldmath$X$}}^{l},l=1,...,L$.
Output: Scale parameters for all views $\\{\sigma_{1},...,\sigma_{L}\\}$.

1: Compute Gaussian kernels
${{\mbox{\boldmath$K$}}^{l}(\sigma_{l})},l=1,...,L$ for several values of
${\sigma}_{l}$.

2: Compute for all pairs $l\neq m$:
${S^{lm}(\sigma_{l},\sigma_{m})=\underset{i}{{\sum}}\underset{j}{{\sum}}K^{lm}_{i,j}(\sigma_{l},\sigma_{m})}$,
where
${\mbox{\boldmath$K$}}^{lm}(\sigma_{l},\sigma_{m})={\mbox{\boldmath$K$}}^{l}(\sigma_{l})\cdot{\mbox{\boldmath$K$}}^{m}(\sigma_{m})$.

3: for $l=1:L$ do

4: Find the minimal value for $\sigma_{l}$ such that
${\mbox{\boldmath$S$}}^{lm}(\sigma_{l},\sigma_{m})$ is linear for all $m\neq
l$.

5: end for

Note that the two dimensional function $S^{lm}(\sigma_{l},\sigma_{m})$
consists of two asymptotes,
$S^{lm}(\sigma_{l},\sigma_{m})\overset{\sigma_{l},\sigma_{m}\rightarrow
0}{\longrightarrow}\text{log}(N)$, and
$S^{lm}(\sigma_{l},\sigma_{m})\overset{\sigma_{l},\sigma_{m}\rightarrow\infty}{\longrightarrow}\text{log}(N^{3})=3\text{log}(N)$,
since for $\sigma_{l},\sigma_{m}\rightarrow 0$, both
${\mbox{\boldmath$K$}}^{l}$ and ${\mbox{\boldmath$K$}}^{m}$ approach the
Identity matrix, and for $\sigma_{l},\sigma_{m}\rightarrow\infty$, both
${\mbox{\boldmath$K$}}^{l}$ and ${\mbox{\boldmath$K$}}^{m}$ approach all-ones
matrices. An example of the plot $S^{lm}(\sigma_{l},\sigma_{m})$ for two views
($L=2$) is presented in Fig. 3.

Figure 3: Left: an example of the two dimensional function
$S(\sigma_{l},\sigma_{m})$. Right: a slice at the first row
($\sigma_{2}=10^{-5}$). The asymptotes are clearly visible in both figures.
Algorithm 1 exploits the multi-view to set a small scale parameter for both
views.

##  IV Coupled views $L=2$

In this section we provide analytical results for the simple case of a coupled
data set (i.e $L=2$). Some of the results could be expanded to a larger number
of views but not in a straight forward manner. To simplify the notation in the
rest of this section we denote
${\mbox{\boldmath$X$}}\stackrel{{\scriptstyle\triangle}}{{=}}{\mbox{\boldmath$X$}}^{1}$
and
${\mbox{\boldmath$Y$}}\stackrel{{\scriptstyle\triangle}}{{=}}{\mbox{\boldmath$X$}}^{2}$.

###  IV-A Coupled mapping

The mappings provided by our approach (Eq. (13)) are justified by the
relations given by Eq. (12). In this section, we provide another analytic
justification for the proposed mapping. We begin with an analysis of a
1-dimensional mapping for each view. Let
${\mbox{\boldmath$\rho(x)$}}=(\rho({\mbox{\boldmath$x$}}_{1}),\rho({\mbox{\boldmath$x$}}_{2}),...,\rho({\mbox{\boldmath$x$}}_{M}))$
and
${\mbox{\boldmath$\rho(y)$}}=(\rho({\mbox{\boldmath$y$}}_{1}),\rho({\mbox{\boldmath$y$}}_{2}),...,\rho({\mbox{\boldmath$y$}}_{M}))$
denote such mappings (one for each view) and let
$\widehat{{\mbox{\boldmath$\rho$}}}\stackrel{{\scriptstyle\triangle}}{{=}}({\mbox{\boldmath$\rho(x)$}},{\mbox{\boldmath$\rho(y)$}})$
and
$\widehat{{\mbox{\boldmath$\rho$}}}_{i}\stackrel{{\scriptstyle\triangle}}{{=}}({\rho({\mbox{\boldmath$x$}}_{i})},{\rho({\mbox{\boldmath$y$}}_{i})})$.
Define
${\mbox{\boldmath$K$}}^{z}={\mbox{\boldmath$K$}}^{x}\cdot{\mbox{\boldmath$K$}}^{y}$,
where ${\mbox{\boldmath$K$}}^{x},{\mbox{\boldmath$K$}}^{y}$ are computed based
on Eq. (4). Our mapping should preserve local connectivities, therefore, we
want to ensure that if the data points $i$ and $j$ are close in both views,
then $\widehat{{\mbox{\boldmath$\rho$}}}_{i}$ and
$\widehat{{\mbox{\boldmath$\rho$}}}_{j}$ will be close. Minimization of the
objective function

$\underset{\widehat{{\mbox{\boldmath$\rho$}}}}{\operatorname{argmin}}{\sum_{i,j}\Big{[}(\rho({\mbox{\boldmath$x$}}_{i})-\rho({\mbox{\boldmath$x$}}_{j}))^{2}{K}_{i,j}^{z}+(\rho({\mbox{\boldmath$y$}}_{i})-\rho({\mbox{\boldmath$y$}}_{j}))^{2}({K}_{i,j}^{z})^{T}\Big{]},}$
(17)

with additional constraints provides such a connectivity preserving mapping.
If ${K}_{i,j}^{z}$ is small indicating a low connectivity between data point
$i$ and $j$, the distance between $\widehat{{\mbox{\boldmath$\rho$}}}_{i}$ and
$\widehat{{\mbox{\boldmath$\rho$}}}_{j}$ can be large. On the other hand, if
${K}_{i,j}^{z}$ is large indicating a high connectivity between point $i$ and
$j$, the distance between $\widehat{{\mbox{\boldmath$\rho$}}}_{i}$ and
$\widehat{{\mbox{\boldmath$\rho$}}}_{j}$ will be small to minimize the
objective function.

######  Theorem 2.

Setting $\widehat{{\mbox{\boldmath$\rho$}}}={\mbox{\boldmath$\psi$}}_{1}$
minimizes the objective function in Eq. (17), where
${\mbox{\boldmath$\psi$}}_{1}$ is the second eigenvector of the eigenvalue
problem
$\lambda_{i}{\mbox{\boldmath$\widehat{P}$}}={\mbox{\boldmath$\psi$}}_{i}{\mbox{\boldmath$\widehat{P}$}}$.

###### Proof.

$\\\
{\underset{i,j}{\sum}\Big{[}(\rho({\mbox{\boldmath$x$}}_{i})-\rho({\mbox{\boldmath$x$}}_{j}))^{2}{K}_{i,j}^{z}+(\rho({\mbox{\boldmath$y$}}_{i})-\rho({\mbox{\boldmath$y$}}_{j}))^{2}{K}_{i,j}^{z}\Big{]}}={\underset{i,j}{\sum}\rho({\mbox{\boldmath$x$}}_{i})^{2}K_{i,j}^{z}+\underset{i,j}{\sum}\rho({\mbox{\boldmath$x$}}_{j})^{2}(K_{i,j}^{z})^{T}}$
${-\underset{i,j}{\sum}2\rho({\mbox{\boldmath$x$}}_{i})\rho({\mbox{\boldmath$x$}}_{j}){K}_{i,j}^{z}+}{\underset{i,j}{\sum}\rho({\mbox{\boldmath$y$}}_{i})^{2}K_{i,j}^{z}+\underset{i,j}{\sum}\rho({\mbox{\boldmath$y$}}_{j})^{2}(K_{i,j}^{z})^{T}-\underset{i,j}{\sum}2\rho({\mbox{\boldmath$y$}}_{i})\rho({\mbox{\boldmath$y$}}_{j}){K}_{i,j}^{z}}=$
${\underset{i}{\sum}\rho({\mbox{\boldmath$x$}}_{i})^{2}D_{i,i}^{rows}+\underset{j}{\sum}\rho({\mbox{\boldmath$x$}}_{j})^{2}D_{j,j}^{cols}-\underset{i,j}{\sum}2\rho({\mbox{\boldmath$y$}}_{i})\rho({\mbox{\boldmath$y$}}_{j}){K}_{i,j}^{z}}+$
${\underset{i}{\sum}\rho({\mbox{\boldmath$y$}}_{i})^{2}D_{i,i}^{cols}+\underset{j}{\sum}\rho({\mbox{\boldmath$y$}}_{j})^{2}D_{j,j}^{rows}-\underset{i,j}{\sum}2\rho({\mbox{\boldmath$y$}}_{i})\rho({\mbox{\boldmath$y$}}_{j}){K}_{i,j}^{z}}=\\\
\begin{bmatrix}{\mbox{\boldmath$\rho$}}(x)&{\mbox{\boldmath$\rho$}}(y)\end{bmatrix}\Bigg{[}\begin{bmatrix}{\mbox{\boldmath$D$}}^{rows}&{\mbox{\boldmath$0$}}_{M\times
M}\\\ {\mbox{\boldmath$0$}}_{M\times
M}&{\mbox{\boldmath$D$}}^{cols}\end{bmatrix}-\begin{bmatrix}{\mbox{\boldmath$0$}}_{M\times
M}&{{\mbox{\boldmath$K$}}^{z}}\\\
({{\mbox{\boldmath$K$}}^{z}})^{T}&{\mbox{\boldmath$0$}}_{M\times
M}\end{bmatrix}\Bigg{]}\begin{bmatrix}{\mbox{\boldmath$\rho$}}(x)^{T}\\\
{\mbox{\boldmath$\rho$}}(y)^{T}\end{bmatrix}$.
By adding a scaling constrain, the minimization problem is rewritten as

$\underset{\widehat{{\mbox{\boldmath$\rho$}}}\widehat{{\mbox{\boldmath$D$}}}\widehat{{\mbox{\boldmath$\rho$}}}^{T}=1}{{arg}\text{min
}}\widehat{{\mbox{\boldmath$\rho$}}}(\widehat{{\mbox{\boldmath$D$}}}-\widehat{{\mbox{\boldmath$K$}}})\widehat{{\mbox{\boldmath$\rho$}}}^{T}.$
(18)

This minimization problem can be solved by finding the minimal eigenvalue of
$(\widehat{{\mbox{\boldmath$D$}}}-\widehat{{\mbox{\boldmath$K$}}})\widehat{{\mbox{\boldmath$\rho$}}}^{T}=\bar{\lambda}\widehat{{\mbox{\boldmath$D$}}}\widehat{{\mbox{\boldmath$\rho$}}}^{T}$
since the minimization term is
${\mbox{\boldmath$\rho$}}\bar{\lambda}\widehat{{\mbox{\boldmath$D$}}}\widehat{{\mbox{\boldmath$\rho$}}}^{T}=\bar{\lambda}$.
This eigenproblem has a trivial solution which is an eigenvector of all ones
(denoted as $1$) with $\bar{\lambda}=0$. The following constraint
$\widehat{{\mbox{\boldmath$\rho$}}}\widehat{{\mbox{\boldmath$D$}}}{\mbox{\boldmath$1$}}=0$
was added to remove the trivial solution. The solution is given by the
smallest non-zero eigenvalue. Multiplying Eq. (18) by
$\widehat{{\mbox{\boldmath$D$}}}^{-1}$ reduces the problem to
$\widehat{{\mbox{\boldmath$\rho$}}}\widehat{{\mbox{\boldmath$P$}}}=\lambda\widehat{{\mbox{\boldmath$P$}}}$.
Thus, we are looking for the eigenvector which corresponds to the second
largest eigenvalue. ∎

Theorem 2 provides yet another justification to use our proposed mapping Eq.
(13).

###  IV-B Spectral decomposition

In this section, we show how to efficiently compute the spectral decomposition
of $\widehat{P}$ (Eq. (6)) when only two view exist ($L=2$). The matrix
$\widehat{P}$ is algebraically similar to the symmetric matrix
${{\mbox{\boldmath$\widehat{P}$}}}_{s}$ where
${{\mbox{\boldmath$\widehat{P}$}}_{s}={{\mbox{\boldmath$\widehat{D}$}}}^{1/2}{\mbox{\boldmath$\widehat{P}$}}{{\mbox{\boldmath$\widehat{D}$}}}^{-1/2}={\mbox{\boldmath$\widehat{D}$}}^{-1/2}{\mbox{\boldmath$\widehat{K}$}}{{\mbox{\boldmath$\widehat{D}$}}}^{-1/2}}$.
Therefore, both $\widehat{P}$ and $\widehat{P}_{s}$ share the same set of
eigenvalues $\\{\lambda_{m}\\}$. Due to symmetry of the matrix
${\mbox{\boldmath$\widehat{P}$}}_{s}$, it has a set of $2M$ real eigenvalues
$\\{\lambda_{i}\\}_{i=0}^{2M-1}\in\mathbb{R}$ and a corresponding real
orthogonal eigenvectors
$\\{{\mbox{\boldmath$\pi$}}_{m}\\}_{m=0}^{2M-1}\in\mathbb{R}^{2M}$, thus,
${\mbox{\boldmath$\widehat{P}_{s}$}}={\mbox{\boldmath$\Pi\Lambda\Pi^{T}$}}$.
By denoting
${\mbox{\boldmath$\Psi$}}={\mbox{\boldmath$\widehat{D}^{-1/2}\Pi$}}$ and
${\mbox{\boldmath$\Phi$}}={\mbox{\boldmath$\widehat{D}^{1/2}\Pi$}}$, we
conclude that the set
$\\{{\mbox{\boldmath$\psi$}}_{m},{\mbox{\boldmath$\phi$}}_{m}\\}_{m=0}^{2M-1}\in\mathbb{R}^{2M}$
denotes the right and the left eigenvectors of
${\mbox{\boldmath$\widehat{P}$}}={\mbox{\boldmath$\Psi\Lambda$}}{\mbox{\boldmath$\Phi$}}^{T}$,
respectively, satisfying
${\mbox{\boldmath$\psi_{i}$}}^{T}{\mbox{\boldmath$\phi_{j}$}}=\delta_{i,j}$.
In the sequel, we use the symmetric matrix
${\mbox{\boldmath$\widehat{P}$}}_{s}$ to simplify the analysis.

To avoid the spectral decomposition of a $2M\times 2M$ matrix
$\widehat{{\mbox{\boldmath$P$}}}_{s}$, the spectral decomposition of
${\mbox{\boldmath$\widehat{P}$}}_{s}$ can be computed using the Singular Value
Decomposition (SVD) of the matrix
$\bar{{\mbox{\boldmath$K$}}}^{z}={{\mbox{\boldmath$D$}}^{rows}}^{-1/2}{\mbox{\boldmath$K$}}^{z}{{\mbox{\boldmath$D$}}^{cols}}^{-1/2}$
of size $M\times M$ where ${D_{i,i}^{rows}}=\sum_{j=1}^{M}{{K^{z}_{i,j}}}$ and
${D_{j,j}^{cols}}=\sum_{i=1}^{M}{{K^{z}_{i,j}}}$ are diagonal matrices.
Theorem 3 enables us to form the eigenvectors of $\widehat{P}$ as a
concatenation of the singular vectors of
${\mbox{\boldmath$K$}}^{z}={\mbox{\boldmath$K$}}^{x}\cdot{\mbox{\boldmath$K$}}^{y}$.

######  Theorem 3.

By using the left and right singular vectors of $K^{z}=V\Sigma U^{T}$, the
eigenvectors and the eigenvalues of $\widehat{{\mbox{\boldmath$K$}}}$ are
computed explicitly by

${{\mbox{\boldmath$\Pi$}}=\frac{1}{\sqrt{2}}\begin{bmatrix}{\mbox{\boldmath$V$}}&{\mbox{\boldmath$V$}}\\\
{\mbox{\boldmath$U$}}&{\mbox{\boldmath$-U$}}\\\
\end{bmatrix},{{\mbox{\boldmath$\Lambda$}}=\begin{bmatrix}{\mbox{\boldmath$\Sigma$}}&{\mbox{\boldmath$0$}}_{M\times
M}\\\ {\mbox{\boldmath$0$}}_{M\times M}&{\mbox{\boldmath$-\Sigma$}}\\\
\end{bmatrix}.}}$ (19)

###### Proof.

Both $V$ and $U$ are orthonormal sets, therefore,
${{\mbox{\boldmath$u$}}_{i}}^{T}{\mbox{\boldmath$u$}}_{j}=\delta_{i,j}$, and
${{\mbox{\boldmath$v$}}_{i}}^{T}{\mbox{\boldmath$v$}}_{j}=\delta_{i,j}$, thus,
the set $\\{{\mbox{\boldmath$\pi$}}_{m}\\}$ is orthonormal. Therefore,
$\Pi\Pi^{T}=I$. By using the construction defined in Eq. (19),
${\mbox{\boldmath$\Pi\Lambda\Pi$}}^{T}$ is computed explicitly by $\\\
{\mbox{\boldmath$\Pi\Lambda\Pi$}}^{T}=\frac{1}{{2}}\begin{bmatrix}{\mbox{\boldmath$V$}}&{\mbox{\boldmath$V$}}\\\
{\mbox{\boldmath$U$}}&{\mbox{\boldmath$-U$}}\\\
\end{bmatrix}\begin{bmatrix}{\mbox{\boldmath$\Sigma$}}&{\mbox{\boldmath$0$}}\\\
{{\mbox{\boldmath$0$}}}&{\mbox{\boldmath$-\Sigma$}}\end{bmatrix}\begin{bmatrix}{\mbox{\boldmath$V^{T}$}}&{\mbox{\boldmath$U^{T}$}}\\\
{\mbox{\boldmath$V^{T}$}}&{\mbox{\boldmath$-U^{T}$}}\\\
\end{bmatrix}=\frac{1}{{2}}\begin{bmatrix}{\mbox{\boldmath$V\Sigma$}}&{\mbox{\boldmath$-V\Sigma$}}\\\
{{\mbox{\boldmath$U\Sigma$}}}&{\mbox{\boldmath$U\Sigma$}}\end{bmatrix}\begin{bmatrix}{\mbox{\boldmath$V^{T}$}}&{\mbox{\boldmath$U^{T}$}}\\\
{\mbox{\boldmath$V^{T}$}}&{\mbox{\boldmath$-U^{T}$}}\\\ \end{bmatrix}=\\\
\frac{1}{{2}}\begin{bmatrix}{\mbox{\boldmath$0$}}&{2{\mbox{\boldmath$K$}}^{z}}\\\
{(2{\mbox{\boldmath$K$}}^{z})^{T}}&{\mbox{\boldmath$0$}}\end{bmatrix}={\centering{{\mbox{\boldmath$\widehat{K}$}}}\<EMAIL_ADDRESS>The $0$ denotes the $M\times M$ matrix of zeros.
∎

Thus the proposed mapping in Eq. (13). could be computed for $L=2$ using the
SVD of ${\mbox{\boldmath$K$}}^{z}$, Eq. (19) and
${\mbox{\boldmath$\Psi$}}={\mbox{\boldmath$\widehat{D}^{-1/2}\Pi$}}$.

###  IV-C Cross view diffusion distance

In some physical systems, the observed dataset denoted by $X$ changes over
some underlying parameter denoted by $\alpha$. Under this model, we can obtain
multiple snapshots for various values of $\alpha$. Each snapshot is denoted by
${\mbox{\boldmath$X$}}^{\alpha}$. If these datasets are high dimensional,
quantifying the amount of change in the datasets is a difficult task. This
scenario was recently studied in [29]. It generalizes the diffusion framework
for cases in which the data changes over the parameter $\alpha$. An example of
such a scenario occurs in hyper-spectral images that change over time. The DM
framework is applied in [29] to a fixed value of $\alpha$. Then, by using the
extracted low dimensional mapping, the Euclidean distance enables to quantify
the amount of changes over $\alpha$. This approach is sensitive since every
small change in the data can result in different mappings and the mappings are
extracted independently. Thus, there is no mutual influence on the extracted
mapping. Our approach incorporates the mutual relations of data within the
view and the relations among views. This observation enables us to measure in
a more robust way the number of variations between two datasets that
correspond to a small variation in $\alpha$. We now define a new diffusion
distance. This distance measures the relation between two views, i.e. between
all the data points at different values of $\alpha$. We measure the distance
between all the coupled data points among the mappings of the snapshots
${\mbox{\boldmath$X$}}^{\alpha_{l}}$ and ${\mbox{\boldmath$X$}}^{\alpha_{m}}$
by using the expression

${{{{{\cal{D}}_{t}}^{(CV)}}^{2}({\mbox{\boldmath$X$}}^{\alpha_{l}},{\mbox{\boldmath$X$}}^{\alpha_{m}})\stackrel{{\scriptstyle\triangle}}{{=}}\sum\limits_{i=1}^{M}||{{\mbox{\boldmath$\widehat{\Psi}$}}_{t}{({\mbox{\boldmath$x$}}^{\alpha_{l}}_{i})}}-{{\mbox{\boldmath$\widehat{\Psi}$}}_{t}{({\mbox{\boldmath$x$}}^{\alpha_{m}}_{i})}}||^{2}}}.$
(20)

Our kernel matrix is a product of the Gaussian kernel matrices in each view.
If these values of the kernel matrices
(${\mbox{\boldmath$K$}}^{x^{\alpha_{l}}},{\mbox{\boldmath$K$}}^{x^{\alpha_{m}}}$)
are similar, this corresponds to similarity between the views inner geometry.
The right and left singular vectors of the matrix
${\mbox{\boldmath$K$}}^{x^{\alpha_{l}}}{\mbox{\boldmath$K$}}^{x^{\alpha_{m}}}$
will be similar, thus, ${{{\cal{D}}_{t}}^{(CV)}}$ will be small.

######  Theorem 4.

The cross manifold distance (defined in Eq. ()20)) is invariant to orthonormal
transformations between the ambient spaces
${\mbox{\boldmath$X$}}^{{\alpha_{l}}}$ and
${\mbox{\boldmath$X$}}^{{\alpha_{m}}}$.

###### Proof.

Denote an orthonormal transformation matrix
${\mbox{\boldmath$R$}}:{\mbox{\boldmath$X$}}^{{\alpha_{l}}}\rightarrow{\mbox{\boldmath$X$}}^{{\alpha_{m}}}$
w.l.o.g. by
${\mbox{\boldmath$x$}}^{{\alpha_{m}}}_{i}={\mbox{\boldmath$R$}}{\mbox{\boldmath$x$}}^{{\alpha_{l}}}_{i}$.
${K^{x^{\alpha_{m}}}_{i,j}}=exp\\{{-\frac{||{\mbox{\boldmath$x$}}^{\alpha_{m}}_{i}-{\mbox{\boldmath$x$}}^{{\alpha_{m}}}_{j}||^{2}}{2\sigma^{2}_{{{m}}}}\\}}=exp\\{{-\frac{||{\mbox{\boldmath$R$}}{\mbox{\boldmath$x$}}^{\alpha_{l}}_{i}-{\mbox{\boldmath$R$}}{\mbox{\boldmath$x$}}^{\alpha_{l}}_{j}||^{2}}{2\sigma^{2}_{l}}\\}=exp\\{{-\frac{||{\mbox{\boldmath$x$}}^{\alpha_{l}}_{i}-{\mbox{\boldmath$x$}}^{\alpha_{l}}_{j}||^{2}}{2\sigma_{l}^{2}}\\}}}={K^{x^{\alpha_{m}}}_{i,j}}$.
The last equality is due to the orthonomality of $R$ and to the choice
$\sigma_{l}=\sigma_{m}$. Therefore, the matrix
${\mbox{\boldmath$K$}}^{z}=({\mbox{\boldmath$K$}}^{x^{\alpha_{m}}})^{2}$ from
Eq. (4) is symmetric and its right and left singular vectors are equal, i.e.
$U=V$, Eq. (19). This induces a repetitive form in
${\mbox{\boldmath$\Psi$}}=\widehat{{\mbox{\boldmath$D$}}}^{{-1}/{2}}{\mbox{\boldmath$\Pi$}}\rightarrow\psi_{l}[i]=\psi_{l}[M+i],\text{
}1\leq i,l\leq
M-1\rightarrow{\Psi_{t}{({\mbox{\boldmath$x$}}^{\alpha_{l}}_{i})}}={\Psi_{t}{({\mbox{\boldmath$x$}}^{\alpha_{m}}_{i})}}$,
thus,
${{{\cal{D}}_{t}}^{(CM)}}^{2}({\mbox{\boldmath$X$}}^{\alpha_{l}},{\mbox{\boldmath$X$}}^{\alpha_{m}})=0$.

∎

###  IV-D Spectral decay of $\widehat{K}$

The power of kernel based methods for dimensionality reduction stems from the
spectral decay of the kernel’s eigenvalues. In this section, we study the
relation between the spectral decay of the Kernel Product (Eq. (7)) and our
multi-view kernel (Eq. (6)). In section VI-A1, we evaluate the spectral decay
empirically using two experiments. The rest of this section is devoted to the
theoretical justification for the spectral decay of our proposed framework. We
start with some background.

######  Theorem 5.

The eigenvalues of $\widehat{P}$ (Eq. (6)) are real and bounded where
$|\lambda_{i}|\leq 1$, $i=1,...,2M$.

A similar proof is given in [33].

###### Proof.

As shown in section IV-B, $\widehat{P}$ is algebraically similar to a
symmetric matrix, thus, its eigenvalues are guaranteed to be real. Denote by
$\lambda$ and $\psi$ the eigenvalue and the eigenvector, respectively, such
that
$\lambda{\mbox{\boldmath$\psi$}}={\mbox{\boldmath$\widehat{P}$}}{\mbox{\boldmath$\psi$}}$.
Define $i_{0}=\underset{1\leq i\leq 2M}{\text{argmax}}|\psi[i]|$ to be the
index of the largest entry in $\psi$. The maximal value $\psi(i_{0})$ can be
computed using ${\widehat{P}}$ from Eq. (6) such that
$\lambda\psi[i_{0}]={\sum\limits_{j=1}^{2M}{{\widehat{P}}_{i_{0}j}\psi[j]}}\longrightarrow|\lambda|=|{\sum\limits_{j=1}^{2M}{{\widehat{P}}_{i_{0}j}\frac{\psi[j]}{\psi[i_{0}]}}}|\leq{\sum\limits_{j=1}^{2M}{{\widehat{P}}_{i_{0}j}\frac{|\psi[j]|}{\psi[i_{0}]}}}\leq{\sum\limits_{j=1}^{2M}{{\widehat{P}}_{i_{0}j}}}=1.$
The first inequality is due to the triangle inequality and the second equality
is due to the kernel normalization by $\widehat{D}^{-1}$.

∎

Theorem 5 shows that the eigenvalues are bounded. However, bounded eigenvalues
are insufficient for dimensionality reduction. Dimensionality reduction is
meaningful when there is a significant spectral decay.

######  Defenition 1.

Let $\cal{M}$ be a manifold. The intrinsic dimension $d$ of the manifold is a
positive integer determined by how many independent “coordinates” are needed
to describe $\cal{M}$. Using a parametrization to describe a manifold, the
dimension of $\cal{M}$ is the smallest integer $d$ such that a smooth map
${\mbox{\boldmath$f$}}({\mbox{\boldmath$\xi$}})=\cal{M}$,
${\mbox{\boldmath$\xi$}}\in{\cal{R}}^{d}$, describes the manifold, where
${\mbox{\boldmath$\xi$}}\in{\cal{R}}^{d}$.

Our framework is based on a Gaussian kernel. The spectral decay of Gaussian
kernels was studied in [5]. We use Lemma 2 to evaluate the spectral decay of
our kernel.

######  Lema 2.

Assume that the data is sampled from a manifold with intrinsic dimension $d\ll
M$. Let $K^{\circ}$ (section III-B) denotes the kernel with an exponential
decay as a function of the Euclidean distance. For $\delta>0$, the number of
eigenvalues of ${\mbox{\boldmath$K$}}^{\circ}$ above $\delta$ is proportional
to $(log(\frac{1}{\delta}))^{d}$.

Lemma 2 is based on Weyl’s asymptotic law [30]. Let
$r_{\delta}=r(\delta)=\text{max}\\{\ell\in N\text{ such that
}|\lambda_{\ell}|\geq\delta\\}$ denotes the number of eigenvalues of
$K^{\circ}$ above $\delta$. $K^{\circ}_{i,j}=K^{x}_{i,j}K^{y}_{i,j}$
corresponds to a single DM view given in [5]. Theorem 6 relates the spectral
decay of the kernel $\widehat{{\mbox{\boldmath$P$}}}$ from (Eq. (6)) to the
decay of the Kernel Product-based DM (${\mbox{\boldmath$P$}}^{\circ}$ Eq. (7)
and in [5]).

######  Lema 3.

Let ${\mbox{\boldmath$A,B$}}\in\mathbb{R}^{M\times M}$ be such that
${\mbox{\boldmath$A,B$}}\geq 0$. Then for any
$1\leq k\leq M-1$

${\prod\limits_{{\ell}=k}^{M-1}{\lambda_{\ell}({\mbox{\boldmath$A\cdot
B$}})}\leq\prod\limits_{{\ell}=k}^{M-1}{{\lambda_{\ell}({\mbox{\boldmath$A\circ
B$}})}}}$ (21)

where $\circ$ is the Kronecker matrix product.

This inequality is proved in [34] and [35].

######  Theorem 6.

Multiplying the last $M-1-r_{\delta}$ eigenvalues of
${\mbox{\boldmath$K$}}^{z}$ is smaller than $\delta^{M-1-r_{\delta}}$.
Formally,
${\prod\limits_{{\ell}=r_{\delta}}^{M-1}{\lambda_{\ell}({\mbox{\boldmath$K$}}^{x}\cdot{\mbox{\boldmath$K$}}^{y})}\leq\delta^{M-1-r_{\delta}}}$.

###### Proof.

Denote by $\\{\lambda_{i}({\mbox{\boldmath$A$}})\\}^{M-1}_{i=0}$ the
eigenvalues of the matrix $A$. They are enumerated in descending order such
that
$\lambda_{0}({\mbox{\boldmath$A$}})\geq\lambda_{2}({\mbox{\boldmath$A$}})\geq...\geq\lambda_{M-1}({\mbox{\boldmath$A$}})$.
We use Lemma 3 to prove Theorem 6 by choosing ${\mbox{\boldmath$A=K$}}^{x}$
and ${\mbox{\boldmath$B=K$}}^{y}$, which are positive semi-definite.
${\mbox{\boldmath$K$}}^{x}\circ{\mbox{\boldmath$K$}}^{y}={\mbox{\boldmath$K$}}^{\circ}$
corresponds to the approach in [5]. By using Lemma 3 and choosing
${\ell}=r_{\delta}$ in Eq. 21, we get
${\prod\limits_{{\ell}=r_{\delta}}^{M-1}{\lambda_{\ell}({\mbox{\boldmath$K$}}^{x}\cdot{\mbox{\boldmath$K$}}^{y})}\leq\prod\limits_{{\ell}=r_{\delta}}^{M-1}{{\lambda_{\ell}({\mbox{\boldmath$K$}}^{\circ})}}\leq\delta^{M-1-r_{\delta}}}.$

∎

Using the kernel matrix spectral decay, we can approximate Eq. (12) by
neglecting all the eigenvalues that are smaller than $\delta$. Thus, we can
compute a low dimensional mapping such that

${\widehat{{\mbox{\boldmath$\Psi$}}}^{r}_{t}{({\mbox{\boldmath$x$}}_{i})}:{\mbox{\boldmath$x$}}_{i}\longmapsto\begin{bmatrix}{\lambda_{1}^{t}\psi_{1}[i]},{\lambda_{2}^{t}\psi_{2}[i]},{\lambda_{3}^{t}\psi_{3}[i]},{.}{.}{.},\par{\lambda_{r-1}^{t}\psi_{r-1}[i]}\\\
\end{bmatrix}^{T}\in{\mathbb{R}^{r-1}}}.$ (22)

This mapping of dimension $r$ provides a low dimensional space which improves
the performance and the efficiency of various machine learning tasks. The
following Lemma introduces an error bound for using low dimension mapping
$\widehat{{\mbox{\boldmath$\Psi$}}}^{r}_{t}{({\mbox{\boldmath$x$}}_{i})}$.

######  Lema 4.

The truncated diffusion distance up to coordinate $r$ defined as

$[{\cal{D}}^{r}_{t}({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$x$}}_{j})]^{2}\stackrel{{\scriptstyle\triangle}}{{=}}||\widehat{{\mbox{\boldmath$\Psi$}}}^{r}_{t}{({\mbox{\boldmath$x$}}_{i})}-\widehat{{\mbox{\boldmath$\Psi$}}}^{r}_{t}{({\mbox{\boldmath$x$}}_{j})}||^{2}=\sum^{r}_{s=1}\lambda_{s}^{2t}({\mbox{\boldmath$\psi$}}_{s}[i]-{\mbox{\boldmath$\psi$}}_{s}[j])^{2},$
(23)

is bounded by the inner view diffusion distance (defined in Eq. (10))

$2\cdot[\sum^{M-1}_{s=1}\lambda_{s}^{2t}({\mbox{\boldmath$\psi$}}_{s}[i]-{\mbox{\boldmath$\psi$}}_{s}[j])^{2}-\delta^{2t}\cdot(\frac{1-\delta_{i,j}}{\tilde{D}})]\leq[{\cal{D}}^{r}_{t}({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$x$}}_{j})]^{2}\leq
2\cdot\sum^{M-1}_{s=1}\lambda_{s}^{2t}({\mbox{\boldmath$\psi$}}_{s}[i]-{\mbox{\boldmath$\psi$}}_{s}[j])^{2},$

where $\delta_{i,j}$ is the Kronecker delta function.

###### Proof.

For the right inequality, clearly

$[{\cal{D}}^{r}_{t}({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$x$}}_{j})]^{2}\leq[{\cal{D}}^{2M}_{t}({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$x$}}_{j})]^{2}=2\cdot\sum^{M-1}_{s=1}\lambda_{s}^{2t}({\mbox{\boldmath$\psi$}}_{s}[i]-{\mbox{\boldmath$\psi$}}_{s}[j])^{2},$

the equality is a result of the repetitive form of $\Psi$ which was defined in
Theorem 3 for $L=2$. Note that $s=0$ was excluded from the sum as
${\mbox{\boldmath$\psi$}}_{0}={\mbox{\boldmath$1$}}$ is constant. For the left
inequality, using that
${\mbox{\boldmath$\Psi$}}=\widehat{{\mbox{\boldmath$D$}}}^{-1/2}{\mbox{\boldmath$\Pi$}}$,
where $\Pi$ is an orthonormal basis defined in Eq. (19) by using the
orthogonality of $\Pi$ we get that

${\mbox{\boldmath$\Psi\Psi$}}^{T}=\widehat{{\mbox{\boldmath$D$}}}^{-1/2}{\mbox{\boldmath$\Pi$}}{\mbox{\boldmath$\Pi$}}^{T}\widehat{{\mbox{\boldmath$D$}}}^{-1/2}=\widehat{{\mbox{\boldmath$D$}}}^{-1},$

which means that

$\sum^{2M-1}_{s=0}({\mbox{\boldmath$\psi$}}_{s}[i]-{\mbox{\boldmath$\psi$}}_{s}[j])^{2}=\frac{1}{\widehat{D}_{i,i}}+\frac{1}{\widehat{D}_{j,j}}-\frac{2\delta_{i,j}}{\widehat{D}_{i,i}}.$
(24)

By the definition of the truncated diffusion distance we have

$[{\cal{D}}^{r}_{t}({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$x$}}_{j})]^{2}=\sum^{2M-1}_{s=0}\lambda_{s}^{2t}({\mbox{\boldmath$\psi$}}_{s}[i]-{\mbox{\boldmath$\psi$}}_{s}[j])^{2}-\sum^{2M-1}_{s=r+1}\lambda_{s}^{2t}({\mbox{\boldmath$\psi$}}_{s}[i]-{\mbox{\boldmath$\psi$}}_{s}[j])^{2}\geq$
$2\cdot\sum^{M-1}_{s=1}\lambda_{s}^{2t}({\mbox{\boldmath$\psi$}}_{s}[i]-{\mbox{\boldmath$\psi$}}_{s}[j])^{2}-\delta^{2t}\sum^{2M-1}_{s=0}({\mbox{\boldmath$\psi$}}_{s}[i]-{\mbox{\boldmath$\psi$}}_{s}[j])^{2}\geq
2\cdot[\sum^{2M-1}_{s=1}\lambda_{s}^{2t}({\mbox{\boldmath$\psi$}}_{s}[i]-{\mbox{\boldmath$\psi$}}_{s}[j])^{2}-\delta^{2t}\cdot(\frac{1-\delta_{i,j}}{\tilde{D}})],$

where $\tilde{D}$ is the minimal value of $\widehat{D}_{i,i}\text{ and
}\widehat{D}_{j,j}$. In the same way, a bound for the truncated diffusion
distance between ${\mbox{\boldmath$y$}}_{i}$ and ${\mbox{\boldmath$y$}}_{j}$
is derived.

∎

###  IV-E Out-of-sample extension

To extend the diffusion coordinates to new data points without re-applying a
large-scale eigendecomposition [31], the Nyström extension is widely used.
Here we formulate the extension method for a multi-view scenario. Given the
data sets $X$ and $Y$ and new points
$\tilde{{\mbox{\boldmath$x$}}}\notin{\mbox{\boldmath$X$}}\text{ and
}\tilde{{\mbox{\boldmath$y$}}}\notin{\mbox{\boldmath$Y$}}$, we want to extend
the multi-view diffusion mapping to $\tilde{{\mbox{\boldmath$x$}}}\text{ and
}\tilde{{\mbox{\boldmath$y$}}}$ without re-applying the proposed framework.
First, we describe the explicit form for the eigenvalue problem for two views
$X$ and $Y$. The eigenvector ${\mbox{\boldmath$\psi$}}_{k}$ with the
corresponding eigenvalue $\lambda_{k}$ satisfies
$\lambda_{k}{\mbox{\boldmath$\psi$}}_{k}=\widehat{{\mbox{\boldmath$P$}}}{\mbox{\boldmath$\psi$}}_{k}$.
By using the definition of $\widehat{{\mbox{\boldmath$P$}}}$ from Eqs. (4) and
(6) we get that

$\lambda_{k}{\mbox{\boldmath$\psi$}}_{k}=\widehat{{\mbox{\boldmath$D$}}}^{-1}\begin{bmatrix}{\mbox{\boldmath$0$}}_{M\times
M}&{{\mbox{\boldmath$K$}}^{x}\cdot{\mbox{\boldmath$K$}}^{y}}\\\
{{\mbox{\boldmath$K$}}^{y}\cdot{\mbox{\boldmath$K$}}^{x}}&{\mbox{\boldmath$0$}}_{M\times
M}\end{bmatrix}\cdot{\mbox{\boldmath$\psi$}}_{k},$

due to the block form of the matrix $\widehat{{\mbox{\boldmath$P$}}}$

$\lambda_{k}{\mbox{\boldmath$\psi$}}^{x}_{k}[i]=\sum_{j}{{\widehat{p}}}({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$y$}}_{j}){\mbox{\boldmath$\psi$}}^{y}_{k}[j],$
$\lambda_{k}{\mbox{\boldmath$\psi$}}^{y}_{k}[i]=\sum_{j}{{\widehat{p}}}({\mbox{\boldmath$y$}}_{i},{\mbox{\boldmath$x$}}_{j}){\mbox{\boldmath$\psi$}}^{x}_{k}[j],$

where
${\mbox{\boldmath$\psi$}}^{x}_{k}[i]\stackrel{{\scriptstyle\triangle}}{{=}}{\mbox{\boldmath$\psi$}}_{k}[i],i=1,...,M$
and
${\mbox{\boldmath$\psi$}}^{y}_{k}[i]\stackrel{{\scriptstyle\triangle}}{{=}}{\mbox{\boldmath$\psi$}}_{k}[i+M],i=1,...,M$.
The transition matrices are

${{\widehat{p}}}({\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$y$}}_{j})=\frac{\sum_{s}{K^{x}_{i,s}}K^{y}_{s,j}}{{\widehat{D}_{i,i}^{rows}}}\text{,
and
}{{\widehat{p}}}({\mbox{\boldmath$y$}}_{i},{\mbox{\boldmath$x$}}_{j})=\frac{\sum_{s}{K^{y}_{i,s}}K^{x}_{s,j}}{{\widehat{D}_{i,i}^{cols}}}.$

The Nyström extension is an approximated weighted sum of the original
eigenvectors. The weights are computed by applying the kernel $\cal{\hat{P}}$
to the extended data points. For the proposed mapping, the extension is
defined by

${\hat{\psi}_{k}({\mbox{\boldmath$\tilde{x}$}})=\frac{1}{\lambda_{k}}\underset{{j}}{\sum}{\widehat{\cal{P}}({{\mbox{\boldmath$\tilde{x}$}}},{\mbox{\boldmath$y$}}_{j})\psi^{y}_{k}[j]}=\frac{1}{\lambda_{k}}{\sum_{j}{\sum_{s}{exp\bigg{\\{}-\frac{||\tilde{{\mbox{\boldmath$x$}}}-{\mbox{\boldmath$x$}}_{s}||^{2}}{2\sigma^{2}_{x}}\bigg{\\}}}exp\bigg{\\{}-\frac{||{\mbox{\boldmath$y$}}_{s}-{\mbox{\boldmath$y$}}_{j}||^{2}}{2\sigma^{2}_{y}}\bigg{\\}}}}\frac{\psi_{k}[j+M]}{\tilde{D}_{j}}}\,$
(25)
${\hat{\psi}_{k}({\mbox{\boldmath$\tilde{y}$}})=\frac{1}{\lambda_{k}}\underset{{j}}{\sum}{\widehat{\cal{P}}({{\mbox{\boldmath$\tilde{y}$}}},{\mbox{\boldmath$x$}}_{j})\psi^{x}_{k}[j]}=\frac{1}{\lambda_{k}}{\sum_{j}{\sum_{s}{exp\bigg{\\{}-\frac{||\tilde{{\mbox{\boldmath$y$}}}-{\mbox{\boldmath$y$}}_{s}||^{2}}{2\sigma^{2}_{y}}\bigg{\\}}}exp\bigg{\\{}-\frac{||{\mbox{\boldmath$x$}}_{s}-{\mbox{\boldmath$x$}}_{j}||^{2}}{2\sigma^{2}_{x}}\bigg{\\}}}}\frac{\psi_{k}[j]}{\tilde{D}_{j}}}\,$
(26)

and the new mapping vector for data point is

${{\hat{{{{\Psi}}}}}({{\mbox{\boldmath$\tilde{x}$}})=\begin{bmatrix}{\lambda_{1}\hat{\psi}_{1}({{\mbox{\boldmath$\tilde{x}$}}})},{\lambda_{2}\hat{\psi}_{2}({{\mbox{\boldmath$\tilde{x}$}}})},{\lambda_{3}\hat{\psi}_{3}({{\mbox{\boldmath$\tilde{x}$}}})},{.}{.}{.},{\lambda_{M-1}\hat{\psi}_{M-1}({{\mbox{\boldmath$\tilde{x}$}}})}\par\end{bmatrix}}\in{\mathbb{R}^{M-1}}}.$
(27)

The new coordinates in the diffusion space are approximated and the new data
points ${\mbox{\boldmath$\tilde{x}$}},{\mbox{\boldmath$\tilde{y}$}}$ have no
effect on the original map’s structure.

###  IV-F Infinitesimal generator

A family of diffusion operators were introduced in [5]. Each operator differs
by the normalization applied to it. If appropriate limits are taken such that
$M\rightarrow\infty$, $\epsilon\rightarrow 0$ and $\epsilon=2\sigma^{2}$, then
from [5] it follows that the DM kernel operator will converge to one of the
following differential operators: 1. Normalized graph Laplacian. 2. Laplace-
Beltrami diffusion. 3. Heat kernel equation. These are proved in [5]. The
operators are all special cases of the diffusion equation. This convergence
provides not only a physical justification for the DM framework, but allows in
some cases to distinguish between the geometry and the density of the data
points. In this section, we study the asymptotic properties of the proposed
kernel $\widehat{{\mbox{\boldmath$K$}}}$ (Eq. (5)) by using only two views,
i.e. $L=2$.

We are interested in understanding the properties of the eigenfunctions of the
proposed multi-view kernel ${\widehat{P}}$ (Eqs. (5), (6)) for two views. We
assume that there is some unknown mapping
${\mbox{\boldmath$\beta$}}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}$ from view
$X$ to view $Y$ that satisfies
${\mbox{\boldmath$y$}}_{i}={\mbox{\boldmath$\beta$}}({\mbox{\boldmath$x$}}_{i}),i=1,...,M$.
Each view-specific kernel function has the same properties
${K}^{x}={K}^{y}={K}$ such that $K\geq 0$,
$K({\mbox{\boldmath$z$}})=K(-{\mbox{\boldmath$z$}})$ and the kernel is
normalized such that
$\int_{\mathbb{R}^{d}}K({\mbox{\boldmath$z$}}){\mbox{\boldmath$dz$}}=1$. Note
that with proper normalizations the Gaussian kernel satisfies these
requirements. The analysis is performed for data points
$\\{{\mbox{\boldmath$x$}}_{1},...,{\mbox{\boldmath$x$}}_{M}\\}\in\mathbb{R}^{D}$
sampled from a uniform distribution over a bounded domain in
${\mathbb{R}^{d}}$. The image of the function $\beta$ is a bounded domain in
$\mathbb{R}^{d}$ with distribution
${\alpha}({\mbox{\boldmath${\mbox{\boldmath$z$}}$}})$.

######  Theorem 7.

The infinitesimal generator induced by the proposed kernel ${\hat{P}}$ (Eq.
(5)) converges when $M\rightarrow\infty,\epsilon\rightarrow 0$,
$\epsilon=2\sigma_{x}^{2}=2\sigma_{y}^{2}$ to a “cross domain Laplacian
operator”. The convergence is to functions $f({\mbox{\boldmath$x$}})$ and
$g({\mbox{\boldmath$y$}})$, which are the eigenfunctions of ${\hat{P}}$. These
functions are the solutions of the following diffusion like equations:

$\displaystyle(\widehat{{\mbox{\boldmath$P$}}}f)({\mbox{\boldmath$x$}}_{i})$
$\displaystyle=g({\mbox{\boldmath$\beta(x_{i})$}})+{{\epsilon}}\triangle\gamma({\mbox{\boldmath$\beta({\mbox{\boldmath$x$}}_{i})$}})/\alpha({\mbox{\boldmath$\beta(x_{i})$}})+\mathcal{O}(\epsilon^{3/2}),$
(28)
$\displaystyle(\widehat{{\mbox{\boldmath$P$}}}g)({\mbox{\boldmath$y$}}_{i})$
$\displaystyle=f({\mbox{\boldmath$\beta^{-1}$}}({\mbox{\boldmath$y$}}_{i}))+{{\epsilon}}\triangle\eta({\mbox{\boldmath$\beta^{-1}({\mbox{\boldmath$y$}}_{i})$}})/\alpha({\mbox{\boldmath$\beta(y_{i})$}}+\mathcal{O}(\epsilon^{3/2}),$
(29)

where the functions $\gamma,\eta$ are defined
$\gamma({\mbox{\boldmath$z$}})\stackrel{{\scriptstyle\triangle}}{{=}}g({\mbox{\boldmath$z$}})\alpha({\mbox{\boldmath$z$}}),\eta({\mbox{\boldmath$z$}})\stackrel{{\scriptstyle\triangle}}{{=}}f({\mbox{\boldmath$z$}})\alpha({\mbox{\boldmath$z$}})$.

###### Proof.

The eigenfunction of the operator $\widehat{{\mbox{\boldmath$L$}}}$ is defined
using the functions $f(x)$ and $g(y)$ by concatenating the vectors such that

${\mbox{\boldmath$h$}}=[{f}({\mbox{\boldmath$x$}}_{1}),{f}({\mbox{\boldmath$x$}}_{2}),...,{f}({\mbox{\boldmath$x$}}_{M}),{g}({\mbox{\boldmath$y$}}_{1}),{g}({\mbox{\boldmath$y$}}_{2}),...,{g}({\mbox{\boldmath$y$}}_{M})]\in\mathbb{R}^{2M}.$

By expanding the single view construction presented in [5, 33]. The limit of
the characteristic equation is

$\underset{\epsilon\rightarrow
0}{\underset{M\rightarrow\infty}{\text{lim}}}(\widehat{L}h_{i})=\underset{\epsilon\rightarrow
0}{\underset{M\rightarrow\infty}{\text{lim}}}{h}_{i}-\frac{\sum\limits_{j=1}^{2M}{{\widehat{K}_{i,j}}}h_{j}}{\sum\limits_{j=1}^{2M}{\widehat{K}_{i,j}}}=\underset{\epsilon\rightarrow
0}{\underset{M\rightarrow\infty}{\text{lim}}}f({\mbox{\boldmath$x$}}_{i})-\frac{\sum\limits_{j=1}^{M}\sum\limits_{\ell=1}^{M}{{{K}^{x}_{i,\ell}}}{{{K}^{y}_{\ell,j}}}g({\mbox{\boldmath$y$}}_{j})}{\sum\limits_{j=1}^{M}\sum\limits_{\ell=1}^{M}{{{K}^{x}_{i,\ell}}}{{{K}^{y}_{\ell,j}}}},i=1,...,M.$
(30)

We approximate the summation based on a Riemann integral. Thus, the
denominator becomes

$\frac{1}{M^{2}\epsilon^{d}}{\sum\limits_{j=1}^{M}\sum\limits_{\ell=1}^{M}{{{K}^{x}_{i,\ell}}}{{{K}^{y}_{\ell,j}}}}\underset{\epsilon\rightarrow
0}{\underset{M\rightarrow\infty}{\longrightarrow}}\frac{1}{\epsilon^{d}}\int_{\mathbb{R}^{d}}\int_{\mathbb{R}^{d}}K\Big{(}\frac{{\mbox{\boldmath$s$}}-{\mbox{\boldmath$x$}}}{\sqrt{\epsilon}}\Big{)}K\Big{(}\frac{{\mbox{\boldmath$y$}}-{\mbox{\boldmath$\beta$}}(s)}{\sqrt{\epsilon}}\Big{)}{\alpha({\mbox{\boldmath$y$}})}{\mbox{\boldmath$dsdy$}}.$

Using a change of variables
${\mbox{\boldmath$z$}}=\frac{{\mbox{\boldmath$y-\beta(s)$}}}{\sqrt{\epsilon}},{\mbox{\boldmath$y$}}={\mbox{\boldmath$\beta$}}({\mbox{\boldmath$s$}})+\sqrt{\epsilon}{{\mbox{\boldmath$z$}}},{\mbox{\boldmath$dz=dy$}}\epsilon^{d/2}$
we get

$\frac{1}{\epsilon^{d}}\int_{\mathbb{R}^{d}}\int_{\mathbb{R}^{d}}K\Big{(}\frac{{\mbox{\boldmath$s$}}-{\mbox{\boldmath$x$}}}{\sqrt{\epsilon}}\Big{)}K\Big{(}\frac{{\mbox{\boldmath$y$}}-{\mbox{\boldmath$\beta$}}(s)}{\sqrt{\epsilon}}\Big{)}\alpha({\mbox{\boldmath$y$}}){\mbox{\boldmath$dsdy$}}=\frac{1}{\epsilon^{d/2}}\int_{\mathbb{R}^{d}}\int_{\mathbb{R}^{d}}K\Big{(}\frac{{\mbox{\boldmath$s$}}-{\mbox{\boldmath$x$}}}{\sqrt{\epsilon}}\Big{)}K({\mbox{\boldmath$z$}}){\alpha}({\mbox{\boldmath$\beta$}}({\mbox{\boldmath$s$}})+\sqrt{\epsilon}{{\mbox{\boldmath$z$}}}){\mbox{\boldmath$dsdz$}}.$

Using a first order Taylor expansion of ${\alpha}$ we get

$\approx\frac{1}{\epsilon^{d/2}}\int_{\mathbb{R}^{d}}\int_{\mathbb{R}^{d}}K\Big{(}\frac{{\mbox{\boldmath$s$}}-{\mbox{\boldmath$x$}}}{\sqrt{\epsilon}}\Big{)}K({\mbox{\boldmath$z$}})[{\alpha}({\mbox{\boldmath$\beta$}}({\mbox{\boldmath$s$}}))+\frac{\sqrt{\epsilon}}{2}{\mbox{\boldmath$z$}}^{T}\nabla{\alpha}({\mbox{\boldmath$\beta$}}({\mbox{\boldmath$s$}}))+\mathcal{O}(\epsilon)]{\mbox{\boldmath$dsdz$}},$

using the symmetry of the kernel ${K{\mbox{\boldmath$(z)$}}}$ we get

$\frac{\sqrt{\epsilon}}{2}\int_{\mathbb{R}^{d}}K({\mbox{\boldmath$z$}}){\mbox{\boldmath$z$}}^{T}\nabla{\alpha}({\mbox{\boldmath$\beta$}}({\mbox{\boldmath$s$}})){\mbox{\boldmath$dz$}}=0.$

Applying the change of variables
${\mbox{\boldmath$t$}}=\frac{{\mbox{\boldmath$s$}}-{\mbox{\boldmath$x$}}}{\sqrt{\epsilon}},{\mbox{\boldmath$s$}}=\sqrt{\epsilon}{\mbox{\boldmath$t$}}+{\mbox{\boldmath$x$}},{\mbox{\boldmath$dt=ds$}}\epsilon^{d/2}$
we get

$\approx\int_{\mathbb{R}^{d}}K({\mbox{\boldmath$t$}})[{\alpha}({\mbox{\boldmath$\beta$}}({\mbox{\boldmath$x$}}+\sqrt{\epsilon}{\mbox{\boldmath$t$}}))+\mathcal{O}(\epsilon)]{\mbox{\boldmath$dt$}}\approx{\alpha}({\mbox{\boldmath$\beta$}}({\mbox{\boldmath$x$}}))+\mathcal{O}(\epsilon).$

The last transition is based on a Taylor expansion and zeroing out odd moments
of $K(t)$. The Riemann integral for the nominator from Eq. (30) takes the
following form

$\frac{1}{M^{2}\epsilon^{d}}{\sum\limits_{j=1}^{M}\sum\limits_{\ell=1}^{M}{{{K}^{x}_{i,\ell}}}{{{K}^{y}_{\ell,j}}}g({\mbox{\boldmath$y$}}_{j})}\underset{\epsilon\rightarrow
0}{\underset{M\rightarrow\infty}{\longrightarrow}}\frac{1}{\epsilon^{d}}\int_{\mathbb{R}^{d}}\int_{\mathbb{R}^{d}}K\Big{(}\frac{{\mbox{\boldmath$s$}}-{\mbox{\boldmath$x$}}}{\sqrt{\epsilon}}\Big{)}K\Big{(}\frac{{\mbox{\boldmath$y$}}-{\mbox{\boldmath$\beta$}}(s)}{\sqrt{\epsilon}}\Big{)}g({\mbox{\boldmath$y$}})\alpha({\mbox{\boldmath$y$}}){\mbox{\boldmath$dsdy$}}.$

By applying a change of variables
${\mbox{\boldmath$z$}}=\frac{{\mbox{\boldmath$y-\beta(s)$}}}{\sqrt{\epsilon}},{\mbox{\boldmath$y$}}={\mbox{\boldmath$\beta$}}({\mbox{\boldmath$s$}})+\sqrt{\epsilon}{{\mbox{\boldmath$z$}}},{\mbox{\boldmath$dz=dy$}}\epsilon^{d/2}$
we get

$\frac{1}{\epsilon^{d/2}}\int_{\mathbb{R}^{d}}\int_{\mathbb{R}^{d}}K\Big{(}\frac{{\mbox{\boldmath$s$}}-{\mbox{\boldmath$x$}}}{\sqrt{\epsilon}}\Big{)}K({\mbox{\boldmath$z$}})\gamma({\mbox{\boldmath$\beta$}}({\mbox{\boldmath$s$}})+\sqrt{\epsilon}{\mbox{\boldmath$z$}}){\mbox{\boldmath$dsdz$}}.$

By using Taylor’s expansion of $\gamma{\mbox{\boldmath$(\beta(s))$}}$ we get

$\underbrace{\approx\frac{1}{\epsilon^{d/2}}\int_{\mathbb{R}^{d}}\int_{\mathbb{R}^{d}}K\Big{(}\frac{{\mbox{\boldmath$s$}}-{\mbox{\boldmath$x$}}}{\sqrt{\epsilon}}\Big{)}K({\mbox{\boldmath$z$}})[\gamma({\mbox{\boldmath$\beta$}}({\mbox{\boldmath$s$}}))+\frac{\sqrt{\epsilon}}{2}{\mbox{\boldmath$z$}}^{T}\nabla\gamma({\mbox{\boldmath$\beta$}}({\mbox{\boldmath$s$}}))+\frac{\epsilon}{2}{\mbox{\boldmath$z$}}^{T}{\mbox{\boldmath$H$}}{\mbox{\boldmath$z$}}+\mathcal{O}(\epsilon^{3/2})]{\mbox{\boldmath$dsdz$}}\rule[-12.0pt]{0.0pt}{5.0pt}}_{\mbox{L}}$

where
${H}_{i,j}\stackrel{{\scriptstyle\triangle}}{{=}}\frac{\partial\gamma({\mbox{\boldmath$\beta(s)$}})}{\partial{s_{i}}\partial
s_{j}}$ is the Hessian. The first term is the integral over
${K{\mbox{\boldmath$(z)$}}}$, while the second

$\frac{\sqrt{\epsilon}}{2}\int_{\mathbb{R}^{d}}K({\mbox{\boldmath$z$}}){\mbox{\boldmath$z$}}^{T}\nabla\gamma({\mbox{\boldmath$\beta$}}({\mbox{\boldmath$s$}})){\mbox{\boldmath$dz$}}=0$

due to the symmetry of the kernel ${K{\mbox{\boldmath$(z)$}}}$. The last term
becomes

$\int_{\mathbb{R}^{d}}K({\mbox{\boldmath$z$}}){\mbox{\boldmath$z$}}^{T}\frac{\partial\gamma({\mbox{\boldmath$\beta(s)$}})}{\partial{s_{i}}\partial
s_{j}}z{\mbox{\boldmath$dz$}}=\sum_{i,j}\frac{\partial\gamma({\mbox{\boldmath$\beta(s)$}})}{\partial{s_{i}}\partial
s_{j}}\int_{\mathbb{R}^{d}}z_{i}z_{j}K({\mbox{\boldmath$z$}}){\mbox{\boldmath$dz$}}=\sum_{i}\frac{\partial^{2}\gamma({\mbox{\boldmath$\beta(s)$}})}{\partial{s_{i}}^{2}}\int_{\mathbb{R}^{D}}z_{i}^{2}K({\mbox{\boldmath$z$}}){\mbox{\boldmath$dz$}}=\triangle\gamma({\mbox{\boldmath$\beta(s)$}}).$

We substitute the results in ($\rm{L}$) to get

$\frac{1}{\epsilon^{d/2}}\int_{\mathbb{R}^{d}}K\Big{(}\frac{{\mbox{\boldmath$s$}}-{\mbox{\boldmath$x$}}}{\sqrt{\epsilon}}\Big{)}[\gamma({\mbox{\boldmath$\beta$}}({\mbox{\boldmath$s$}}))+\frac{{\epsilon}}{2}\triangle\gamma({\mbox{\boldmath$\beta(s)$}})+\mathcal{O}(\epsilon^{3/2})]{\mbox{\boldmath$ds$}}.$

By applying a change of variables
${\mbox{\boldmath$t$}}=\frac{{\mbox{\boldmath$s$}}-{\mbox{\boldmath$x$}}}{\sqrt{\epsilon}},{\mbox{\boldmath$s$}}=\sqrt{\epsilon}{\mbox{\boldmath$t$}}+{\mbox{\boldmath$x$}},{\mbox{\boldmath$dt=ds$}}\epsilon^{d/2}$
and
$\gamma({\mbox{\boldmath$y$}})=g({\mbox{\boldmath$y$}})\alpha({\mbox{\boldmath$y$}})$
we get

$\int_{\mathbb{R}^{d}}K({\mbox{\boldmath$t$}})[\gamma({\mbox{\boldmath$\beta$}}({\mbox{\boldmath$x+\sqrt{\epsilon}{\mbox{\boldmath$t$}}$}}))+\frac{{\epsilon}}{2}\triangle\gamma({\mbox{\boldmath$\beta({\mbox{\boldmath$x+\sqrt{\epsilon}{\mbox{\boldmath$t$}}$}})$}})+\mathcal{O}(\epsilon^{3/2})]{\mbox{\boldmath$dt$}}.$

By using Taylor’s expansion again we get

$\approx\int_{\mathbb{R}^{d}}K({\mbox{\boldmath$t$}})[\gamma({\mbox{\boldmath$\beta$}}({\mbox{\boldmath$x$}}))+\frac{{\epsilon}}{2}\triangle\gamma({\mbox{\boldmath$\beta({\mbox{\boldmath$x$}})$}})+\frac{{\epsilon}}{2}{\mbox{\boldmath$t$}}^{T}{\mbox{\boldmath$H$}}{\mbox{\boldmath$t$}}+\mathcal{O}(\epsilon^{3/2})]{\mbox{\boldmath$dt$}}.$

We neglected the order terms when $\epsilon$ is raised to a power higher than
$3/2$. Terms with odd order of $t$ are zeroed due to the symmetry of the
kernel $K$. Using the same argument as in the integral (L) we get that the
nominator is

$\gamma({\mbox{\boldmath$\beta$}}({\mbox{\boldmath$x$}}))+{{\epsilon}}\triangle\gamma({\mbox{\boldmath$\beta({\mbox{\boldmath$x$}})$}})+\mathcal{O}(\epsilon^{3/2}),$

dividing by the denominator we get

$(\widehat{{\mbox{\boldmath$P$}}}f)({\mbox{\boldmath$x$}}_{i})=g({\mbox{\boldmath$\beta(x_{i})$}})+{{\epsilon}}\triangle\gamma({\mbox{\boldmath$\beta({\mbox{\boldmath$x$}}_{i})$}})/\alpha({\mbox{\boldmath$\beta(x_{i})$}})+\mathcal{O}(\epsilon^{3/2})$

In the same way, we compute the convergence on $g({\mbox{\boldmath$y$}}_{i})$

$(\widehat{{\mbox{\boldmath$P$}}}g)({\mbox{\boldmath$y$}}_{i})=f({\mbox{\boldmath$\beta^{-1}$}}({\mbox{\boldmath$y$}}_{i}))+{{\epsilon}}\triangle\eta({\mbox{\boldmath$\beta^{-1}({\mbox{\boldmath$y$}}_{i})$}})/\alpha({\mbox{\boldmath$\beta(y_{i})$}}+\mathcal{O}(\epsilon^{3/2}).$

∎

We ignored in the above computation the following

  * •

Error due to approximating the sum by an integral, a bound for such error in
the single view DM is introduced in [32].

  * •

Deformation due to the fact that the data is sampled from a non uniform
density. This changes the result by some constant.

  * •

The data lies on some manifold. This could be dealt by changing the coordinate
system and integrating on the manifold.

  * •

When assuming that the data lies on some manifold, the Euclidean distance
should be replaced by the geodesic distance along the manifold. As in the
analysis of [5], this introduces a factor to the integral.

###  IV-G The convergence rate

In Theorem 7, we assume the number of data points $M\rightarrow\infty$ while
the scale parameter $\epsilon\rightarrow 0$. In practice we cannot expect to
have an infinite number of data points. It was shown in [5, 36] and others
that a single view graph Laplacian converges to the laplacian operator on a
manifold. It is demonstrated in [37, 38] that the variance of the error for
such operator decreases as $M\rightarrow\infty$, but increases as
$\epsilon\rightarrow 0$. The study in [37] proves that for a uniform
distribution of data points, the variance of the error is bounded by
$\mathcal{O}(\frac{1}{M^{1/2}\epsilon^{1+d/4}},\epsilon^{1/2})$. This bound
was improved in [38] by an asymptotic factor of $\sqrt{\epsilon}$ based on the
correlation between ${\mbox{\boldmath$D$}}^{-1}$ and $K$.

We now turn our attention to the variance of the multi-view kernel for a
finite number of points. Given
${\mbox{\boldmath$x$}}_{1},....,{\mbox{\boldmath$x$}}_{M}$ independent
uniformly distributed data points sampled from a bounded domain in
$\mathbb{R}^{d}$. Define the multi-view Parzen Window density estimator by

$\dot{{\mbox{\boldmath$K$}}}_{M,\epsilon}({\mbox{\boldmath$x$}})\stackrel{{\scriptstyle\triangle}}{{=}}\frac{1}{M^{2}}\sum_{\ell=1}^{M}\sum^{M}_{j=1}\frac{1}{\epsilon^{d}}K(\frac{{\mbox{\boldmath$x$}}-{\mbox{\boldmath$x$}}_{\ell}}{\sqrt{\epsilon}})K(\frac{{\mbox{\boldmath$y$}}_{\ell}-{\mbox{\boldmath$y$}}_{j}}{\sqrt{\epsilon}}).$
(31)

We are interested in finding a bound for the variance of
$\dot{{\mbox{\boldmath$K$}}}_{M,\epsilon}({\mbox{\boldmath$x$}})$ for a finite
value of data points.

$Var(\dot{{\mbox{\boldmath$K$}}}_{M,\epsilon}({\mbox{\boldmath$x$}}))=\frac{1}{{M}^{4}\epsilon^{2d}}\cdot
M\cdot
Var\bigg{[}\sum^{M}_{\ell}K(\frac{{\mbox{\boldmath$x$}}-{\mbox{\boldmath$x$}}_{\ell}}{\sqrt{\epsilon}})K(\frac{{\mbox{\boldmath$y$}}_{\ell}-{\mbox{\boldmath$y$}}_{j}}{\sqrt{\epsilon}})\bigg{]}\leq$
$\frac{1}{{M}^{4}\epsilon^{2d}}\cdot M^{3}\cdot
Var\big{[}K^{x}_{\epsilon}K^{y}_{\epsilon}\big{]}\leq\frac{1}{{M}\epsilon^{2d}}\big{[}Var\big{(}K^{x}_{\epsilon}\big{)}\cdot||K^{y}_{\epsilon}||_{\infty}+Var\big{(}K^{y}_{\epsilon}\big{)}\cdot||K^{x}_{\epsilon}||_{\infty}\big{]}\leq$
$\frac{1}{{M}\epsilon^{2d}}\cdot[{\epsilon^{d/2}}\cdot m_{1}\cdot
1+\epsilon^{d/2}\cdot
m_{2}\cdot\alpha({\mbox{\boldmath$x$}})\big{]}\leq\frac{m_{1}+m_{2}\cdot\alpha({\mbox{\boldmath$x$}})}{M\cdot\epsilon^{1.5d}}.$

The constants $m_{1}\text{ and }m_{2}$ are functions of the kernels choice,
and the function $\alpha$ of the density of points
${\mbox{\boldmath$y$}}_{i},i=1,...,M$. This bound helps to choose an optimal
value for the scaling factor $\epsilon$ given the number of data points $M$
and the intrinsic dimension $d$.

###  IV-H Generalized multi-view kernel

One can consider a more general multi-view kernel such that it enables a
transition within views $X$ and $Y$ in each time step. Such a kernel will take
the following form

${\mbox{\boldmath$\widehat{\widehat{K}}$}}=\begin{bmatrix}(1-\alpha)\cdot({\mbox{\boldmath$K$}}^{x})^{2}&\alpha\cdot{\mbox{\boldmath$K$}}^{x}{\mbox{\boldmath$K$}}^{y}\\\
\alpha\cdot{\mbox{\boldmath$K$}}^{y}{\mbox{\boldmath$K$}}^{x}&(1-\alpha)\cdot({\mbox{\boldmath$K$}}^{y})^{2}\end{bmatrix},$
(32)

where the parameter $\alpha\in[0,1]$ provides a bias for the within view
transition probability. This kernel is normalized using the sum of rows
diagonal matrix $\widehat{\widehat{{\mbox{\boldmath$D$}}}}$, such that
${\mbox{\boldmath$\widehat{\widehat{P}}$}}=\widehat{\widehat{{\mbox{\boldmath$D$}}}}^{-1}{\mbox{\boldmath$\widehat{\widehat{K}}$}}$.
For a small value of $\alpha$, the kernel favors the within view transition
probability. Therefore share similar properties with the single view diffusion
process. For a large value of $\alpha$, the kernel behaves empirically like
the multi-view kernel $\widehat{K}$ (Eq. (5)).

##  V Related work

In this section, we describe alternative frameworks that incorporate multiple
views. The first two are related to the diffusion process, however, the
proposed kernels are not symmetric thus they do not guarantee real eigenvalues
and eigenvectors.

###  V-A Unsupervised metric fusion by cross diffusion

The framework in [13] suggests to construct two matrices for each view
${\mbox{\boldmath$P$}}^{1},{\mbox{\boldmath$P$}}^{2},\text{ and
}{\mbox{\boldmath$\cal{P}$}}^{1},{\mbox{\boldmath$\cal{P}$}}^{2}$. The first
pair is defined as in Eq. (1). The second pair is a stochastic matrix computed
using only $K^{NN}$ nearest neighbors for each instance. The kernels are fused
such that

${\mbox{\boldmath$P$}}^{1}_{t+1}={{\mbox{\boldmath$\mathcal{P}$}}}^{1}\cdot{{\mbox{\boldmath$P$}}}^{2}_{t}\cdot({{\mbox{\boldmath$\mathcal{P}$}}}^{1})^{T},$
(33)
${\mbox{\boldmath$P$}}^{2}_{t+1}={{\mbox{\boldmath$\mathcal{P}$}}}^{2}\cdot{{\mbox{\boldmath$P$}}}^{1}_{t}\cdot({{\mbox{\boldmath$\mathcal{P}$}}}^{2})^{T}.$
(34)

The diffusion process incorporates two steps (between the view) in each time
unit. A convergence of the induced diffusion distance is proved for
$t\rightarrow\infty$ in [13].

###  V-B Common manifold learning using alternating-diffusion

An alternating diffusion process is proposed in [39]. The construction is
based on fusing the stochastic matrices ${\mbox{\boldmath$P$}}^{1}\text{and
}{\mbox{\boldmath$P$}}^{2}$ by multiplying the matrices such that
${\mbox{\boldmath$P$}}^{AD}={\mbox{\boldmath$P$}}^{1}\cdot{\mbox{\boldmath$P$}}^{2}$.
Assuming that a common random variable exists in both views, new results
regarding the extraction of underlying hidden random parameters are described
in [39]. The study in [39] was inspired by our work by giving a reference to
the current paper.

###  V-C Kernel Canonical Correlation Analysis (KCCA)

The frameworks [40, 41] extend the well know Canonical Correlation Analysis
(CCA) by applying a kernel function prior to the application of CCA. Kernels
${\mbox{\boldmath$K$}}^{1}\text{and }{\mbox{\boldmath$K$}}^{2}$ are
constructed for each view as in Eq. (4) and the canonical vectors
${\mbox{\boldmath$v$}}_{1}\text{and }{\mbox{\boldmath$v$}}_{2}$ are computed
by solving the following generalized eigenvalue problem

$\begin{bmatrix}{\mbox{\boldmath$0$}}_{M\times
M}&{{\mbox{\boldmath$K$}}^{1}\cdot{\mbox{\boldmath$K$}}^{2}}\\\
{{{\mbox{\boldmath$K$}}^{2}\cdot{\mbox{\boldmath$K$}}^{1}}}&{\mbox{\boldmath$0$}}_{M\times
M}\end{bmatrix}\begin{pmatrix}{{\mbox{\boldmath$v$}}_{1}}\\\
{{\mbox{\boldmath$v$}}_{2}}\end{pmatrix}=\rho\cdot\begin{bmatrix}({\mbox{\boldmath$K$}}^{1}+\gamma{\mbox{\boldmath$I$}})^{2}&{{\mbox{\boldmath$0$}}_{M\times
M}}\\\ {{\mbox{\boldmath$0$}}_{M\times
M}}&({\mbox{\boldmath$K$}}^{2}+\gamma{\mbox{\boldmath$I$}})^{2}\end{bmatrix}\begin{pmatrix}{{\mbox{\boldmath$v$}}_{1}}\\\
{{\mbox{\boldmath$v$}}_{2}}\end{pmatrix},$ (35)

where $\gamma{\mbox{\boldmath$I$}}$ are regularization terms which guarantee
that the matrices
$({\mbox{\boldmath$K$}}^{1}+\gamma{\mbox{\boldmath$I$}})^{2}$ and
$({\mbox{\boldmath$K$}}^{2}+\gamma{\mbox{\boldmath$I$}})^{2}$ are invertible.
Usually the Incomplete Cholesky Decomposition (ICD) [40, 41, 42] is used to
reduce the run time required for solving (35). For clustering tasks, K- means
is applied to the set of generalized eigenvectors.

###  V-D Spectral clustering with two views

The approach in [18] generalizes the traditional normalized graph Laplacian
for two views. Kernels ${\mbox{\boldmath$K$}}^{1}\text{and
}{\mbox{\boldmath$K$}}^{2}$ are computed in each view as in Eq. (4). The
kernels are multiplied such that
${\mbox{\boldmath$W$}}={\mbox{\boldmath$K$}}^{1}\cdot{\mbox{\boldmath$K$}}^{2}$
and

${\mbox{\boldmath$A$}}=\begin{bmatrix}{\mbox{\boldmath$0$}}_{M\times
M}&{{\mbox{\boldmath$W$}}}\\\
{{\mbox{\boldmath$W$}}^{T}}&{\mbox{\boldmath$0$}}_{M\times M}\end{bmatrix}.$
(36)

Finally, normalization is done by using $\bar{D}$ where
${\bar{D}}_{i,i}=\underset{j}{\sum}{{{W}}_{i,j}}$, such that the normalized
fused kernel is defined as

${\mbox{\boldmath$\bar{A}$}}={\mbox{\boldmath$\bar{D}$}}^{-0.5}\cdot{\mbox{\boldmath$A$}}\cdot{\mbox{\boldmath$\bar{D}$}}^{-0.5}.$
(37)

Assuming that the number of clusters in the data is $N_{C}$, denoting the
eigenvectors of $A$ as $\phi_{i},i=1,...,2M$. K-Means algorithm is applied to
the mapping

$\Phi[i]\stackrel{{\scriptstyle\triangle}}{{=}}[\phi^{2}_{1}[i],...,\phi^{2}_{1}[N_{C}]]/s[i],$
(38)

where $s[i]=\sum^{N_{C}}_{j}(\phi^{2}_{j}[i])$. The paper in [18] is focused
on spectral clustering, however, a similar version of the kernel from Eq. (37)
is suited for manifold learning as we demonstrate in this study. We use a
stochastic version of the kernel and extend the construction to multiple
views. The stochastic version $\widehat{{\mbox{\boldmath$P$}}}$ (Eq. (6)) is
useful as it provides various theoretical justifications for the multi-view
diffusion process. In section VI this approach is referred as De Sa’s.

##  VI Experimental results

In this section, we present the experimental results which evaluate our
framework. We focus the experiments on three tasks in machine learning:
clustering, classification and manifold learning.

###  VI-A Empirical evaluations of theoretical aspects

In the first group of experiments we provide empirical evidence which support
the theoretical analysis from Section IV.

####  VI-A1 Spectral decay

In Section IV-D, an upper bound on the eigenvalues’ decay rate for our multi-
view-based approach (matrix $\widehat{{\mbox{\boldmath$P$}}}$ Eq. (6)) is
presented. In order to empirically evaluate the decay rate, synthetic datasets
are generated accompanied by comparison to other approaches. To evaluate the
spectral decay of $\widehat{{\mbox{\boldmath$P$}}}$ (Eq. (6)),
${{\mbox{\boldmath$P$}}}^{\circ}$ (Eq. (7) and [5]) and
${{\mbox{\boldmath$P$}}}^{+}$ (Eq. (9)) we compare the spectral decay rate
between various frameworks on synthetic clustered data drawn from Gaussian
distributions. The following steps describe the generation of both views
denoted by $({\mbox{\boldmath$X,Y$}})$ and referred as View-I ($X$) and View-
II ($Y$), respectively:

  1. 1.

6 vectors ${\mbox{\boldmath$\mu$}}_{j}\in{\mathbb{R}}^{9},~{}j=1,\ldots,6)$
were drawn from a Gaussian distribution
$N({\mbox{\boldmath$0$}},8\cdot{\mbox{\boldmath$I_{9\times 9}$}})$. These
vectors are the center of masses of the generated classes.

  2. 2.

100 data points were drawn for each cluster $j$ by using
${\mbox{\boldmath$\mu$}}_{j},1\leq j\leq 6$, from a Gaussian distribution
$N({\mbox{\boldmath$\mu$}}_{j},2\cdot{\mbox{\boldmath$I_{9\times 9}$}})$.
Denote these 600 data points by $X$.

  3. 3.

100 data points were drawn for each cluster $j$ by using
${\mbox{\boldmath$\mu$}}_{j},1\leq j\leq 6$, from a Gaussian distribution
$N({\mbox{\boldmath$\mu$}}_{j},2\cdot{\mbox{\boldmath$I_{9\times 9}$}})$.
Denote these 600 data points by $Y$.

The first 3 dimensions of both views are presented in Fig. 4. We compute the
probability matrix for each view ${\mbox{\boldmath$P$}}^{x}$ and
${\mbox{\boldmath$P$}}^{y}$ (Eq. (1)), the Kernel Sum approach probability
matrix ${\mbox{\boldmath$P$}}^{+}$ (Eq. (9)), the Kernel Product approach
${\mbox{\boldmath$P$}}^{\circ}$ (Eq. (7)) and the proposed approach
$\widehat{P}$. The eigendecomposition is computed for all matrices. The
resulting eigenvalues’ decay rate are compared with the eigenvalues product
from both views. To get a fair comparison between all the methods, we set the
Gaussian scale parameter $\sigma_{x}$ and $\sigma_{y}$ in each view and then
use these scales in all the methods. The vectors’ variance in the
concatenation approach is the sum of variances since we assume statistical
independence. Therefore, the following scale parameters
$\sigma_{\circ}^{2}=\sigma_{x}^{2}+\sigma_{y}^{2}$ are used.

The experiment is repeated but this time $X$ contains 6 clusters whereas $Y$
contains only 3. For $Y$, we use only the first 3 center of masses and
generate 200 points in each cluster. Figure 5 presents a logarithmic scale of
the spectral decay for eigenvalues extracted from all methods. It is evident
that our proposed kernel has the strongest spectral decay.

Figure 4: The first 3 dimensions of the Gaussian mixture. Both views share the
center of masses of the Gaussian spread. Top: first view denoted as $X$.
Bottom: second view denoted as $Y$. The variance of the Gaussian in each
dimension is 8.

Figure 5: Eigenvalues decay rate. Comparison between different mapping
methods. Top: 6 clusters in each view. Bottom: 6 clusters in $X$ and 3
clusters in $Y$.

####  VI-A2 Cross view diffusion distance

In this section, we examine the proposed Cross View Diffusion Distance
(Section IV-C). A swiss roll is generated by using the function

$\text{View I: }{\mbox{\boldmath$X$}}=\begin{bmatrix}{x_{i}}[1]\\\
{x_{i}}[2]\\\ {x_{i}}[3]\\\
\end{bmatrix}=\begin{bmatrix}{6\theta[i]\cos(\theta[i])}\\\ {h[i]}\\\
{6\theta[i]\sin(\theta[i])}\\\ \end{bmatrix}+{\mbox{\boldmath$N$}}_{i}^{1},$
(39)

${\theta_{i}}=(1.5\pi)s_{i}$, $i=1,2,3,...,1000$, where $s_{i}$ are 1000 data
points that spread linearly within the line ${s_{i}}\rightarrow[1,3]$. The
second view is generated by the application of an orthonormal transformation
to the swiss roll and adding Gaussian noise. The function in Eq. (40)
describes the representation of the second view

$\text{View II: }{\mbox{\boldmath$Y$}}=\begin{bmatrix}{y_{i}}[1]\\\
{y_{i}}[2]\\\ {y_{i}}[3]\\\
\end{bmatrix}={\mbox{\boldmath$R$}}\begin{bmatrix}{6\theta_{i}\cos(\theta_{i})}\\\
{h_{i}}\\\ {6\theta_{i}\sin(\theta_{i})}\\\
\end{bmatrix}+{\mbox{\boldmath$N$}}_{i}^{2},$ (40)

where ${\mbox{\boldmath$R$}}\in\mathbb{R}^{3\times 3}$ is a random orthonormal
transformation matrix. It is generated by drawing values from i.i.d Gaussian
variables and applying the Graham-Schmidt process. $h_{i},i=1,...,1000$ are
drawn from a uniform distribution within the interval $[0,100]$. Each
component of
${\mbox{\boldmath$N$}}_{i}^{1},{\mbox{\boldmath$N$}}_{i}^{2}\in\mathbb{R}^{3\times
1}$ is drawn from a Gaussian distribution with zero mean and a variance of
$\sigma_{N}^{2}$. An example for both Swiss rolls is presented in Fig. 6.

Figure 6: The two Swiss Rolls, Top- generated by Eq. (39), Bottom- generated
by Eq. (40).

A standard DM is applied to each view and a 2-dimensional embedding of the
Swiss roll is extracted. The sum of distances between all the data points in
the embedding spaces is denoted as a single view diffusion distance (SVDD).
The distance is computed using the following measure

${{{{{\cal{D}}_{t}}^{(SV)}}^{2}(X,Y)=\sum\limits_{i=1}^{M}||{\Psi_{t}{({\mbox{\boldmath$x$}}_{i})}}-{\Psi_{t}{({\mbox{\boldmath$y$}}_{i})}}||^{2}}},$
(41)

where
$\Psi_{t}{({\mbox{\boldmath$x$}}_{i})},\Psi_{t}{({\mbox{\boldmath$y$}}_{i})},i=1,...,M$
a the single view diffusion mappings. Then, the proposed framework is applied
to extract the coupled embedding. A Cross View Diffusion Distance (CVDD) is
computed using Eq. (20). This experiment was executed 100 times for various
values of the Gaussian noise variance $\sigma_{N}^{2}$.

In about 10% of the single view simulations the embeddings’ axis are flipped.
This generates a large SVDD although the embeddings share similar structures.
In order to remove these type of errors we use the Median of 100 simulations.
The median of the results are presented in Fig. 7.

Figure 7: Comparison between two cross view diffusion based distances.
Simulated on two Swiss rolls with additive Gaussian noise. The results are the
median of 100 simulations.

###  VI-B Multi-view clustering

The task of clustering has been in the core of machine learning for many
years. The goal is to divide a given data set into subsets based on the
inherited structure of the data. We use the multi-view construction to extract
low dimensional mappings from multiple sets of high dimensional data points.
In the following experiments we demonstrate the advantage of the proposed
approach on both artificial and real data sets. For the real data sets
applying the multi-view approach requires an eigen decomposition of large
matrices. To reduce the runtime of experiments we us an approximate matrix
decomposition based on sparse random projections [43].

####  VI-B1 Two circles clustering

Spectral properties of data sets are useful for clustering since they reveal
information about the unknown number of clusters. The characteristic of the
eigenvalues of $\widehat{P}$ (Eq. (6)) can provide insight into the number of
clusters within the data set. The study in [44] relates the number of clusters
to the multiplicity of the eigenvalue 1. A different approach in [45] provides
an analysis about the relation between the eigenvalue drop to the number of
clusters. In this section, we evaluate how our proposed method captures the
clusters’ structure when two views are available.

We generate two circles that represent the original clusters using the
function

${\mbox{\boldmath$Z$}}=\begin{bmatrix}{z_{i}}[1]\\\ {z_{i}}[2]\\\
\end{bmatrix}=\begin{bmatrix}{r\cdot\cos(\theta_{i}))}\\\
{r\cdot\sin(\theta_{i})}\\\ \end{bmatrix},$ (42)

where 1600 points $\theta_{i},1\leq i\leq 1600$, are spread linearly within
the line $[0,4\pi]$. The clusters are created by changing the radius as
follows:
$r=2,1\leq i\leq 800$ (first cluster) , $r=4,801\leq i\leq 1600$ (second
cluster). The views $X$ (Eq. (43)) and $Y$ (Eq. (44)) are generated by the
application of the following non-linear functions that produce the distorted
views

$x_{i}[1]=\begin{Bmatrix}{z_{1}}[i]+1+n_{i}[2]|{z_{i}[2]}\geq 0\\\
{z_{1}}[i]+n_{i}[3]|{z_{i}[2]}<0\\\
\end{Bmatrix},x_{i}[2]={z_{i}}[2]+n_{i}[1]$ (43)

and

$y_{i}[1]={z_{i}}[1]+n_{i}[4],y_{i}[2]=\begin{Bmatrix}{z_{i}}[2]+1+n_{i}[6]|{z_{i}}[1]\geq
0\\\ {z_{i}}[2]+n_{i}[6]|{z_{i}}[1]<0\\\ \end{Bmatrix},$ (44)

where $n_{i}[l],1\leq l\leq 6$, are i.i.d random variables drawn from a
Gaussian distribution with $\mu=0$ and $\sigma^{2}_{n}\in[0.03,0.6]$. This
data is referred as the Coupled Circles dataset.

Figure 8: Left: first view $X$. Right: second view $Y$. The ground truth
clusters are represented by the marker’s shape and color.

In Fig. 8, the views $X$ and $Y$, which were generated by Eqs. (43) and (44),
are presented. Color and shape indicate the ground truth clusters. Initially,
DM is applied to each view and clustering is performed using K-means ($K=2$)
within the first diffusion coordinate. The kernel bandwidths $\sigma_{x}\text{
and }\sigma_{y}$ for all methods are set using the min-max method described in
Eq. (16). We use $t=1$ since it is optimal for clustering tasks. For the
kernel product method we use
$\sigma_{\circ}=\sqrt{\sigma_{x}^{2}+\sigma_{y}^{2}}$. We further extract a
1-dimensional representation using the proposed multi-view framework (Eq.
(13)), the Kernel Sum DM (Eq. (9)), Kernel Product DM (Eq. (7)), De Sa’s
approach (Eq. (37)) and Kernel CCA (Eq. (35)) described in Section V. The
regularization parameter is $\gamma=0.01$ for KCCA and we use 100 components
for the Incomplete Cholesky Decomposition [40, 41]. Clustering is performed in
the representation space by the application of K-means where $K=2$.

Figure 9: Clustering results from averaging 200 trials vs. the variance of the
Gaussian noise. The simulation performed on the Coupled Circles data (Eqs.
(42), (43) and (44)).

To evaluate the performance of our proposed map 100 simulations with various
values of the Gaussian’s noise variance (all with zero mean) were performed.
The average clustering success rate is presented in Fig. 9. It is evident that
the multi-view based approach outperforms the DM-based single view and the
Kernel Product approaches.

The performance of kernel methods is highly dependent on setting an
appropriate kernel bandwidth $\sigma_{x},\sigma_{y}$, in Algorithm 1 we have
presented method for setting such parameters. To evaluate the influence of
such parameters on the clustering quality we set $\sigma_{n}=0.16$ and extract
the multi-view, Kernel Sum and Kernel Product diffusion mapping for various
values of $\sigma_{x},\sigma_{y}$. The average clustering performance using
Kmeans $K=2$ are presented in Fig. 10.

Figure 10: Clustering results from averaging 20 trails using various values of
$\sigma_{x},\sigma_{y}$ based on different mappings. The standard deviation of
the noise is $\sigma_{n}=0.16$. Left- Kernel Sum DM, middle- Kernel Product
DM, right- Multi View DM.

####  VI-B2 Handwritten digits

For the following clustering experiment, we use the Multiple Features database
[46] from the UCI repository. The data set consists of 2000 handwritten digits
from 0 to 9 that are equally spread. The features extracted from these images
are the profile correlations (FAC), Karhunen-love coefficients (KAR), Zerkine
moment (ZER), morphological (MOR), pixel averages in $2\times 3$ windows and
the Fourier coefficients (Fou) as our feature spaces
${\mbox{\boldmath$X$}}^{1},{\mbox{\boldmath$X$}}^{2}$,${\mbox{\boldmath$X$}}^{3},{\mbox{\boldmath$X$}}^{4},{\mbox{\boldmath$X$}}^{5},{\mbox{\boldmath$X$}}^{6}$
respectively. We apply dimensionality reduction using a single view DM, Kernel
Product DM, Kernel Sum DM and the proposed Multi-view. We apply K-means to the
reduced mapping using 6 to 20 coordinates. The clustering performance is
measured using the Normalized Mutual Information [47] (NMI). Figure 11
presents the average clustering results using K-Means (K=1).

Figure 11: Average clustering accuracy running 100 simulations on the
Handwritten data set. Accuracy is measured using the Normalized Mutual
Information (NMI).

####  VI-B3 Isolet data set

The data set was constructed by recording 150 people pronouncing each letter
twice for all 26 letters. The feature vector available is a concatenation of
the following features: spectral coefficients, contour, sonorant, pre-sonorant
and post-sonorant. The authors do not provide the feature’s separation,
therefore, the dimension of the feature vector is 617. We use a subset of the
data with 1599 instances, thus the features space is
${\mbox{\boldmath$X$}}\in\mathbb{R}^{1559\times 617}$. To apply the multi-view
approach we compute 3 different kernels and fuse them together. The first
kernel ${\mbox{\boldmath$K$}}^{1}$ is the standard Gaussian kernel defined in
Eq. (4). ${\mbox{\boldmath$K$}}^{2}$ is a Laplacian kernel defined by

$K^{2}_{i,j}\stackrel{{\scriptstyle\triangle}}{{=}}exp\\{\frac{-|{\mbox{\boldmath$x$}}_{i}-{\mbox{\boldmath$x$}}_{j}|}{\sigma_{2}}\\}.$
(45)

The third kernel ${\mbox{\boldmath$K$}}^{3}$ is an exponent with a correlation
distance as the affinity measure, given by

$K^{3}_{i,j}\stackrel{{\scriptstyle\triangle}}{{=}}\text{exp}\left\\{\frac{T_{i,j}-1}{2\sigma^{2}}\right\\},i,j=1,...,M,$
(46)

where $T_{i,j}$ is the correlation coefficient between the $i$-th and $j$-th
feature vectors, computed by

$T_{i,j}\stackrel{{\scriptstyle\triangle}}{{=}}\frac{{{\mbox{\boldmath$\tilde{x}$}}_{i}}^{T}\cdot{\mbox{\boldmath$\tilde{x}$}}_{j}}{\sqrt{({{\mbox{\boldmath$\tilde{x}$}}_{i}}^{T}\cdot{\mbox{\boldmath$\tilde{x}$}}_{i})({{\mbox{\boldmath$\tilde{x}$}}_{j}}^{T}\cdot{\mbox{\boldmath$\tilde{x}$}}_{j})}},i,j=1,...,M.$
(47)

The average subtracted features are
$\tilde{{\mbox{\boldmath$x$}}}_{i}\stackrel{{\scriptstyle\triangle}}{{=}}{\mbox{\boldmath$x$}}_{i}-\eta_{i}\cdot{\mbox{\boldmath$1$}}$,
where $\eta_{i}$ is the average of the features for instance $i$. We fuse the
kernels using multi-view, kernel product and kernel sum approach, we then
apply K-Means to the extracted space. The average NMI for 26 classes is
presented in Fig. 12.

Figure 12: Clustering accuracy measured with Normalized Mutual Information
(NMI) on the Isolet data set by using 3 different kernel matrices. Clustering
was performed in the $r$ dimensional embedding space.

###  VI-C Manifold learning

The power of manifold learning appears when the data is sampled in a high
dimensional space but actually lies on a low dimensional surface. Extracting
the underlying surface provides insight into the physical process creating the
data. Examples in vision [48], audio [49], medical [50] and more. In this
section we demonstrate the proposed approach on an artificial manifold and on
a toy example of video sequence.

####  VI-C1 Artificial manifold learning

In the general DM approach, there is an assumption that the sampled space
describes a low dimensional manifold. However, this assumption can be
incorrect since the sampled space can describe the existence of redundancy in
the manifold, or more generally, the sampled space can describe two or more
manifolds generated by a common physical process. In this section, we examine
the extracted embedding computed using our method and compare it to the Kernel
Product approach (section III-B).

Helix A
Two coupled manifolds with a common underlying open circular structure are
generated. The helix shaped manifolds were generated by the application of a 3
dimensional function to 1000 data points that spread linearly within the lines
${a_{i}}\rightarrow[0,2\pi]$ and ${b_{i}}=a_{i}+0.5\pi\mod 2\pi$,
$i=1,2,3,...,1000$. The functions in Eqs. (48) and (49) are used to generate
the datasets for View-I and View-II denoted as $X$ and $Y$, respectively:

$\text{View I: }{\mbox{\boldmath$X$}}=\begin{bmatrix}{x_{i}}[1]\\\
{x_{i}}[2]\\\ {x_{i}}[3]\\\
\end{bmatrix}=\begin{bmatrix}{4\cos(0.9a_{i})+0.3\cos(20a_{i})}\\\
{4\sin(0.9a_{i})+0.3\sin(20a_{i})}\\\ {0.1(6.3a_{i}^{2}-a_{i}^{3})}\\\
\end{bmatrix},i=1,2,3,...,1000,$ (48)

$\text{View II: }{\mbox{\boldmath$Y$}}=\begin{bmatrix}{y_{i}}[1]\\\
{y_{i}}[2]\\\ {y_{i}}[3]\\\
\end{bmatrix}=\begin{bmatrix}{4\cos(0.9b_{i})+0.3\cos(20b_{i})}\\\
{4\sin(0.9b_{i})+0.3\sin(20b_{i})}\\\ {0.1(6.3b_{i}-b_{i}^{2})}\\\
\end{bmatrix},i=1,2,3,...,1000.$ (49)

The 3-dimensional Helix shaped manifolds $X$ and $Y$ are presented in Fig. 13.

Figure 13: Top: first Helix $X$ (Eq. (48)). Bottom: second Helix $Y$ (Eq.
(49)). Both manifolds have some circular structure governed by the angle
parameter $a[i]$ and $b[i]$, $i=1,2,3,...,1000$ colored by the points index
$i$.

Figure 14: Top: Multi-View based embedding of the first view
$\widehat{{\mbox{\boldmath$\Psi$}}}({\mbox{\boldmath$X$}})$. Bottom: Multi-
View based embedding of the second view
$\widehat{{\mbox{\boldmath$\Psi$}}}({\mbox{\boldmath$Y$}})$. They were
computed by using Eq. (13)), respectively. Figure 15: 2-dimensional DM-based
mapping of the Helix computed using the concatenated vector from both views
that correspond to the kernel ${\mbox{\boldmath$P$}}^{\circ}$ (Eq.(7)).

The Kernel Product mapping (Eq. (7)) separates the manifold to a bow and a
point as shown in Fig. 15. This structure neither represents any of the
original structures nor reveals the underlying parameters $a_{i},b_{i}$. On
the other hand, our embedding (Eq. (13)) captures the two structures one for
each view. As shown in Fig. 14, one structure represents the angle of $a_{i}$
while the other represents the angle of $b_{i}$. The Euclidean distance in the
new spaces preserves the mutual relations between data points based on the
geometrical relation in both views. Moreover, both manifolds are in the same
coordinate system and this is a strong advantage as it enables us to compare
between the manifolds in the lower dimensional space. The Euclidean distance
in the new spaces preserves the mutual relations between data points that are
based on the geometrical structure of both views.

Helix B
The previous experiment was repeated with the functions in Eqs. (50) and (51)
to generate datasets for View-I and View-II denoted by $X$ and $Y$,
respectively.

$\text{View I: }{\mbox{\boldmath$X$}}=\begin{bmatrix}{x_{i}}[1]\\\
{x_{i}}[2]\\\ {x_{i}}[3]\\\ \end{bmatrix}=\begin{bmatrix}{4\cos(5a_{i})}\\\
{4\sin(5a_{i})}\\\ {4a_{i}}\\\ \end{bmatrix},$ (50)

$\text{View II: }{\mbox{\boldmath$Y$}}=\begin{bmatrix}{y_{i}}[1]\\\
{y_{i}}[2]\\\ {y_{i}}[3]\\\ \end{bmatrix}=\begin{bmatrix}{4\cos(5b_{i})}\\\
{4\sin(5b_{i})}\\\ {4b_{i}}\\\ \end{bmatrix}.$ (51)

Again, 1000 points were generated using ${a_{i}}\rightarrow[0,2\pi]$,
${b_{i}}=a_{i}+0.5\pi\mod 2\pi$, $i=1,2,3,...,1000$. The generated manifolds
are presented in Fig. 16.

Figure 16: Top: first Helix $X$ (Eq. (50)). Bottom: second Helix $Y$ (Eq.
(51)). Both manifolds have some circular structure governed by the angle
parameter $a[i]$ and $b_{i}$, $i=1,2,3,...,1000$, as colored by the point’s
index $i$.

Figure 17: The coupled mappings computed using our proposed parametrization in
Eq. 13 Figure 18: A 2-dimensional mapping, extracted based on
${\mbox{\boldmath$P$}}^{\circ}$ (Eq. (7)).

As can be viewed in Fig. 17, the proposed embeddings (Eq. (13) has
successfully captured the governing parameters $a_{i}$ and $b_{i}$. The Kernel
Product based embedding (Eq. (7)) is presented in Fig. 18. The Kernel Product
based embedding again separated the data points into two unconnected
structures that do not represent well the parameters.

####  VI-C2 MultiView video sequence

Various examples such as images, audio, MRI [28], [8] and [51] have
demonstrated the power of DM for extracting from real datasets the underlying
changing physical parameters. In this experiment, the multi-view approach is
tested on a real data. Two web cameras and a toy train with a pre-designed
path are used. The train’s path has an “eight” shape structure. Extracting the
underlying manifold from the set of images enables us to organize the images
according to the location along the train’s path and thus reveals the true
underlying parameters of the processes.

The setting of the experiment is as follows: each camera records a set of
images from a different angle. A sample frame from each view is presented in
Fig. 19. The video is sampled at 30 frames per second with a resolution of
640$\times$480 pixels per frame. $M=220$ images were collected from each view
(camera). Then, the R,G,B values were averaged and downsampled to 160X120
pixels resolution. The matrices were reshaped into column vectors. The
resulted set of vectors are denoted by $X$ and $Y$ where
${\mbox{\boldmath$x$}}_{i},{\mbox{\boldmath$y$}}_{i}\in R^{19200},~{}1\leq
i\leq 220$. The sequential order of the images is not important for the
algorithm. In a normal setting, one view is sufficient to extract the
parameters that govern the movement of the train and thus extract the natural
order of the images. However, we use two types of interferences to create a
scenario in which each view by itself is insufficient for the extraction of
the underlying parameters. The first interference is a gap in the recording of
each camera. We remove 20 consecutive frames from each view at different time
locations. By doing it, the bijective correspondence of some of the images in
the sequence is broken. However, even an approximated correspondence is
sufficient for our proposed manifold extraction. A standard 2-dimensional DM
base mapping of each view was extracted. The results are bow shaped manifolds
as presented in Fig. 20. Applying DM separately to each view extracts the
correct order of the data points (images) along the path. However, the
“missing” data points broke the circular structure of the expected manifold
and resulted in a bow shaped embedding. We use the multi-view based
methodology to overcome this interference by application of the multi-view
framework to extract two coupled mapping (Eq. (13)). The results are presented
in Fig. 21. The proposed approach overcomes the interferences by smoothing the
gap inherited in each view through the use of connectivities from the
“undistracted” view. Finally, we concatenate the vectors from both views and
compute the Kernel Product embedding The results are presented in Fig. 22.
Again, the structure of the manifold is distorted and incomplete due to the
missing images.

Figure 19: Top: a sample image from the first camera ($X$). Bottom: a sample
image from the second camera ($Y$).

Figure 20: Top: DM-based single view mapping $\Psi({\mbox{\boldmath$X$}})$.
Bottom: DM-based single view mapping $\Psi({\mbox{\boldmath$Y$}})$). The
removed images caused a bow shaped structure.

Figure 21: Top: Mapping $\hat{\Psi}({\mbox{\boldmath$X$}})$. Bottom: Mapping
$\hat{\Psi}({\mbox{\boldmath$Y$}})$ as extracted by the multi-view based
framework. Two small gaps, which correspond to the removed images, are
visible. Figure 22: A standard diffusion mapping (Kernel Product-based) that
was computed by using the concatenated vector from both views that correspond
to kernel ${\mbox{\boldmath$K$}}^{\circ}$.

This experiment was repeated while replacing 10 frames from each view with a
Gaussian noise that has the parameters $\mu=0$ and $\sigma^{2}=10$ that are
average and variance, respectively. A single view DM-based mapping was
computed. The Kernel Product-based DM and the multi-view based DM mappings
were computed as well. As presented in Fig. 23, the Gaussian noise distorted
the manifolds extracted in each view. The multi-view approach extracted two
circular structures presented in Fig. 24. Again, the data points are ordered
according to the position along the path. This time, the circular structure is
unfolded and the gaps are visible in both embeddings. Applying the Kernel
Product approach (Eq. 7) has yielded a distorted manifold as presented in Fig.
25.

Figure 23: Top: DM-based single view mapping $\Psi({\mbox{\boldmath$X$}})$.
Bottom: DM-based single view mapping $\Psi({\mbox{\boldmath$Y$}})$). The
Gaussian noise deformed the circular structure

Figure 24: Top: Mapping $\hat{\Psi}({\mbox{\boldmath$X$}})$. Bottom: Mapping
$\hat{\Psi}({\mbox{\boldmath$Y$}})$ as extracted by the multi-view framework.
Two gaps are visible that correspond to Gaussian noise. Figure 25: Computation
of a standard diffusion mapping (Kernel Product) by using the concatenation
vector from both views (corresponding to kernel
${\mbox{\boldmath$P$}}^{\circ}$ Eq.(7)).

###  VI-D Classification in the embedding space

Besides improving classification results, dimensionality reduction can reduce
the execution time. Studies such as [52], [53] and [54] focus on the role of
dimensionality reduction for classification. Applications have been studied in
diverse fields [55] [8] [56].

####  VI-D1 Classification of seismic events

Various studies have used machine learning for seismic events classification.
Some of the methods used are: artificial neural networks [57], [58], [59],
self-organizing maps [60], [61], hidden Markov models [62], [63] and support
vector machines [64]. We use a data set collected from a seismic catalog by
the Geophysical Institute of Israel. The data set includes $46$ earthquakes,
$62$ explosions and $62$ noise waveforms. Each waveform was sampled at a
frequency of $40$ Hz. The length of each waveform is one minute, thus each
consists of $2400$ samples. Data was collected from two stations. Each station
uses a three component seismometer concluding a total number of 6 views.

The features extracted from the waveform are termed Sonograms [65]. First, a
Spectrogram is computed by using the short time Fourier transform (STFT). The
frequency scale is rearranged to be equally tempered on a logarithmic scale,
such that the final spectrogram contains $11$ frequency bands. The bins are
normalized such that the sum of energy in every frequency band is equal to
$1$. The resulting set of sonograms denoted
${\mbox{\boldmath$X$}}^{1},{\mbox{\boldmath$X$}}^{2},{\mbox{\boldmath$X$}}^{3},{\mbox{\boldmath$X$}}^{4},{\mbox{\boldmath$X$}}^{5},{\mbox{\boldmath$X$}}^{6}$.
These are the input views for our framework.

We apply the proposed framework, as well as the single view DM, kernel product
DM and kernel sum DM. Classification is performed by using K-NN (K=1), based
on 3 or 4 coordinates from the reduced mapping. The results are presented in
table I.

To evaluate the multi-view classification performance on subsets of the $L=6$
views we use subsets of only two view. We evaluate the classification results
based on all the pairs of view
${\mbox{\boldmath$X$}}^{l},{\mbox{\boldmath$X$}}^{m},l,m=1,...,6,l\neq m$. The
accuracy of classification based on the multi-view representation
${\mbox{\boldmath$\widehat{\Psi}$}}({\mbox{\boldmath$X$}}^{l}),l=1,...,6$
given that ${\mbox{\boldmath$X$}}^{m},m=1,...,6,m\neq l$ is presented in Fig.
26.

TABLE I: Classification accuracy using 1-fold cross validation. $r$ is the number of coordinates used in the embedding space. Method | Accuracy [%] ($r=3$) | Accuracy [%] ($r=4$)
---|---|---
Single View DM $({\mbox{\boldmath$X$}}^{1})$ | 89.9 | 93
Single View DM $({\mbox{\boldmath$X$}}^{2})$ | 88.6 | 92.4
Single View DM $({\mbox{\boldmath$X$}}^{3})$ | 89.3 | 91.1
Single View DM $({\mbox{\boldmath$X$}}^{4})$ | 89.3 | 89.2
Single View DM $({\mbox{\boldmath$X$}}^{5})$ | 89.3 | 90.5
Single View DM $({\mbox{\boldmath$X$}}^{6})$ | 88.6 | 91.1
Kernel Sum DM | 93.7 | 94.9
Kernel Product DM | 94.3 | 93
Multi-view DM | 97.5 | 98.1
Figure 26: Classification accuracy using K-nn (K=1) for all pairs of views
${\mbox{\boldmath$X$}}^{l},{\mbox{\boldmath$X$}}^{m},l\neq m$. The y-axis is
the number of the first view used, while the x-axis is the number of the
second view. Classification is performed in the multi-view low dimensional
embedding ($r=4$). The diagonal terms are presented as zero since we did not
simulate for $l=m$.

##  VII Discussion

In this paper, we presented a framework for dimensionality reduction that is
multi-view based. The method enables us to extract simultaneous embeddings
from coupled embeddings. We enforce a cross domain probabilistic model at a
single time step. The transition probabilities depend on the connectivities in
both views. We derived various theoretical aspects of the proposed method and
demonstrated their applicabilities to both artificial and real data. The
experimental results demonstrate the strength of the proposed framework in
cases where data is missing in each view or each of the manifolds is deformed
by an unknown function. The framework is applicable to various real life
machine learning tasks that consist of multiple views or multiple modalities.

## References

  * [1] I. Jolliffe, _Principal component analysis_ , 2005, vol. 21.
  * [2] J. B. Kruskal and W. M, “Multidimensional scaling,” _Sage Publications. Beverly Hills_ , 1977.
  * [3] S. T. Roweis and L. K. Sau, “Nonlinear dimensionality reduction by local linear embedding,” _Science_ , vol. 290.5500, pp. 2323–2326, 200.
  * [4] M. Belkin and P. Niyogi, “Laplacian eigenmaps and spectral techniques for embedding and clustering,” in _NIPS_ , vol. 14, no. 14, 2001, pp. 585–591.
  * [5] R. R. Coifman and S. Lafon, “Diffusion maps,” _Applied and computational harmonic analysis_ , vol. 21, no. 1, pp. 5–30, 2006.
  * [6] W. Luo, “Face recognition based on laplacian eigenmaps,” 2011, pp. 416 – 419\.
  * [7] A. Singer and R. R. Coifman, “Non linear independent component analysis with diffusion maps,” _Applied and Computational Harmonic Analysis_ , vol. 25(2), pp. 226–239, 2008.
  * [8] O. Lindenbaum, A. Yeredor, and I. Cohen, “Musical key extraction using diffusion maps,” _Signal Processing_ , 2015.
  * [9] W. T. Freeman and J. B. Tenenbaum, “Learning bilinear models for two-factor problems in vision,” in _Computer Vision and Pattern Recognition,Proceedings., IEEE Computer Society Conference on_. IEEE, 1997, pp. 554–560.
  * [10] I. S. Helland, “Partial least squares regression and statistical models,” _Scandinavian Journal of Statistics_ , pp. 97–114, 1990.
  * [11] K. Chaudhuri, S. M. Kakade, K. Livescu, and K. Sridharan, “Multi-view clustering via canonical correlation analysis,” in _Proceedings of the 26th annual international conference on machine learning_. ACM, 2009, pp. 129–136.
  * [12] A. Kumar, P. Rai, and H. Daume, “Co-regularized multi-view spectral clustering,” in _Advances in Neural Information Processing Systems_ , 2011, pp. 1413–1421.
  * [13] D. Zhou and C. Burges, “Spectral clustering and transductive learning with multiple views,” _Proceedings of the 24th international conference on Machine learning_ , pp. 1159–1166, 2007.
  * [14] B. Wang, J. Jiang, W. Wang, Z.-H. Zhou, and Z. Tu, “Unsupervised metric fusion by cross diffusion,” in _Computer Vision and Pattern Recognition (CVPR), 2012 IEEE Conference on_. IEEE, 2012, pp. 2997–3004.
  * [15] A. Kumar and H. Daumé, “A co-training approach for multi-view spectral clustering,” in _Proceedings of the 28th International Conference on Machine Learning (ICML-11)_ , 2011, pp. 393–400.
  * [16] B. Boots and G. Gordon, “Two-manifold problems with applications to nonlinear system identification,” 2012.
  * [17] H. Hotelling, “Relations between two sets of variates,” _Biometrika_ , pp. 321–377, 1936.
  * [18] V. R. de Sa, “Spectral clustering with two views,” in _ICML workshop on learning with multiple views_ , 2005.
  * [19] W. Wang and M. A. Carreira-Perpinán, “The role of dimensionality reduction in classification.” in _AAAI_ , 2014, pp. 2128–2134.
  * [20] N. D. Lawrence, “Gaussian process latent variable models for visualisation of high dimensional data.” in _Nips_ , vol. 2, 2003, p. 5.
  * [21] R. Navaratnam, A. W. Fitzgibbon, and R. Cipolla, “The joint manifold model for semi-supervised multi-valued regression,” in _Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on_. IEEE, 2007, pp. 1–8.
  * [22] A. P. Shon, K. Grochow, A. Hertzmann, and R. P. Rao, “Learning shared latent structure for image synthesis and robotic imitation,” _Advances in neural information processing systems_ , vol. 18, p. 1233, 2006.
  * [23] C. H. Ek, P. H. Torr, and N. D. Lawrence, “Gaussian process latent variable models for human pose estimation,” in _International workshop on machine learning for multimodal interaction_. Springer, 2007, pp. 132–143.
  * [24] L. Sigal, R. Memisevic, and D. J. Fleet, “Shared kernel information embedding for discriminative inference,” in _Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on_. IEEE, 2009, pp. 2852–2859.
  * [25] A. Klami, S. Virtanen, and S. Kaski, “Bayesian canonical correlation analysis,” _Journal of Machine Learning Research_ , vol. 14, no. Apr, pp. 965–1003, 2013.
  * [26] A. Klami and S. Kaski, “Probabilistic approach to detecting dependencies between data sets,” _Neurocomputing_ , vol. 72, no. 1, pp. 39–46, 2008.
  * [27] M. Salzmann, C. H. Ek, R. Urtasun, and T. Darrell, “Factorized orthogonal latent spaces.” in _AISTATS_ , 2010, pp. 701–708.
  * [28] S. Lafon, Y. Keller, and R. Coifman, “Data fusion and multicue data matching by diffusion maps,” _IEEE Trans. Pattern Anal. Mach. Intell._ , vol. 28 no. 11, p. 1784–1797, 2006.
  * [29] M. Hirn and R. Coifman, “Diffusion maps for changing data,” _Applied and computational harmonic analysis_ , 2013.
  * [30] S. Lafon, “Diffusion maps and geometric harmonics,” _Ph.D dissertation Yale_ , 2004.
  * [31] Y. Keller, R. R. Coifman, S. Lafon, and S. W. Zucker, “Audio-visual group recognition using diffusion maps,” _IEEE Transactions on Signal Processing_ , vol. 58, no. 1, pp. 403–413, 2010.
  * [32] A. Singer, R. Erban, I. G. Kevrekidis, and R. R. Coifman, “Detecting intrinsic slow variables in stochastic dynamical systems by anisotropic diffusion maps,” _Proceedings of the National Academy of Sciences_ , vol. 106, no. 38, pp. 16 090–16 095, 2009.
  * [33] Y. Shkolinsky. Lecture notes on spectral methods in data anlisys, https://sites.google.com/site/yoelshkolnisky/teaching.
  * [34] T. Ando, “Majorization relations for hadamard products.” _Linear Algebra and its Applications_ , pp. 57–64, 1995.
  * [35] G. Visick, “A weak majorization involving the matrices a ◦ b and ab.” _Linear Algebra and its Applications_ , vol. 224/224, pp. 731–744, 1995.
  * [36] M. Belkin and P. Niyogi, “Convergence of laplacian eigenmaps,” in _NIPS_ , 2006, pp. 129–136.
  * [37] M. Hein, J.-Y. Audibert, and U. Von Luxburg, “From graphs to manifolds–weak and strong pointwise consistency of graph laplacians,” in _International Conference on Computational Learning Theory_. Springer, 2005, pp. 470–485.
  * [38] A. Singer, “From graph to manifold laplacian: The convergence rate,” _Applied and Computational Harmonic Analysis_ , vol. 21, no. 1, pp. 128–134, 2006.
  * [39] R. R. Lederman and R. Talmon, “Common manifold learning using alternating-diffusion,” submitted, Tech. Report YALEU/DCS/TR1497, Tech. Rep., 2014.
  * [40] P. L. Lai and C. Fyfe, “Kernel and nonlinear canonical correlation analysis,” _International Journal of Neural Systems_ , vol. 10, no. 05, pp. 365–377, 2000.
  * [41] S. Akaho, “A kernel method for canonical correlation analysis,” _arXiv preprint cs/0609071_ , 2006.
  * [42] D. S. Kershaw, “The incomplete cholesky—conjugate gradient method for the iterative solution of systems of linear equations,” _Journal of Computational Physics_ , vol. 26, no. 1, pp. 43–65, 1978.
  * [43] Y. Aizenbud and A. Averbuch, “Matrix decompositions using sub-gaussian random matrices,” _arXiv preprint arXiv:1602.03360_ , 2016.
  * [44] A. Y. Ng, M. I. Jordan, and Y. Weiss, “On spectral clustering1 analysis and an algorithm,” _Proceedings of Advances in Neural Information Processing Systems. Cambridge, MA: MIT Press_ , vol. 14, pp. 849–856, 2001.
  * [45] M. Polito and P. Perona, “Grouping and dimensionality reduction by locally linear embedding,” in _NIPS_ , 2001, pp. 1255–1262.
  * [46] M. Lichman, “UCI machine learning repository,” 2013. [Online]. Available: http://archive.ics.uci.edu/ml
  * [47] P. A. Estévez, M. Tesmer, C. A. Perez, and J. M. Zurada, “Normalized mutual information feature selection,” _IEEE Transactions on Neural Networks_ , vol. 20, no. 2, pp. 189–201, 2009.
  * [48] A. Elgammal and C.-S. Lee, “Inferring 3d body pose from silhouettes using activity manifold learning,” in _Computer Vision and Pattern Recognition, 2004. CVPR 2004. Proceedings of the 2004 IEEE Computer Society Conference on_ , vol. 2. IEEE, 2004, pp. II–681.
  * [49] R. Talmon, I. Cohen, and S. Gannot, “Relative transfer function identification using convolutive transfer function approximation,” _IEEE Transactions on audio, speech, and language processing_ , vol. 17, no. 4, pp. 546–555, 2009\.
  * [50] C. Wachinger, M. Yigitsoy, E.-J. Rijkhorst, and N. Navab, “Manifold learning for image-based breathing gating in ultrasound and mri,” _Medical image analysis_ , vol. 16, no. 4, pp. 806–818, 2012.
  * [51] G. Piella, “Diffusion maps for multimodal registration,” _Sensors_ , vol. 14, no. 6, pp. 10 562–10 577, 2014.
  * [52] W. Wang and M. A. Carreira-Perpinán, “The role of dimensionality reduction in classification.” in _AAAI_ , 2014, pp. 2128–2134.
  * [53] T. S. Tian, “Dimensionality reduction for classification with high-dimensional data,” Ph.D. dissertation, Citeseer, 2009.
  * [54] F. Plastria, S. De Bruyne, and E. Carrizosa, “Dimensionality reduction for classification,” in _International Conference on Advanced Data Mining and Applications_. Springer, 2008, pp. 411–418.
  * [55] B. Li, C.-H. Zheng, D.-S. Huang, L. Zhang, and K. Han, “Gene expression data classification using locally linear discriminant embedding,” _Computers in Biology and Medicine_ , vol. 40, no. 10, pp. 802–810, 2010.
  * [56] X. He, S. Yan, Y. Hu, P. Niyogi, and H.-J. Zhang, “Face recognition using laplacianfaces,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 27, no. 3, pp. 328–340, 2005.
  * [57] T. Tiira, “Discrimination of nuclear explosions and earthquakes from teleseismic distances with a local network of short period seismic stations using artificial neural networks,” _Physics of the earth and planetary interiors_ , vol. 97, no. 1, pp. 247–268, 1996.
  * [58] E. Del Pezzo, A. Esposito, F. Giudicepietro, M. Marinaro, M. Martini, and S. Scarpetta, “Discrimination of earthquakes and underwater explosions using neural networks,” _Bulletin of the Seismological Society of America_ , vol. 93, no. 1, pp. 215–223, 2003.
  * [59] A. Esposito, F. Giudicepietro, S. Scarpetta, L. D’Auria, M. Marinaro, and M. Martini, “Automatic discrimination among landslide, explosion-quake, and microtremor seismic signals at stromboli volcano using neural networks,” _Bulletin of the Seismological Society of America_ , vol. 96, no. 4A, pp. 1230–1240, 2006.
  * [60] B. Sick, M. Guggenmos, and M. Joswig, “Chances and limits of single-station seismic event clustering by unsupervised pattern recognition,” _Geophysical Journal International_ , vol. 201, pp. 1801–1813, 2015.
  * [61] A. K’́ohler, M. Ohrnberger, and F. Scherbaum, “Unsupervised pattern recognition in continuous seismic wavefields records using self-organizing maps,” _Geophysical Journal International_ , vol. 185, pp. 1619–1630, 2010\.
  * [62] M. Beyreuther, C. Hammer, M. Wassermann, M. Ohrnberger, and M. Megies, “Constructing a hidden markov model based earthquake detector: Application to induced seismicity,” _Geophysical Journal International_ , vol. 189, pp. 602–610, 2012.
  * [63] C. Hammer, M. Ohrnberger, and D. F’́ah, “Classifying seismic waveforms from scratch: A case study in the alpine environment,” _Geophysical Journal International_ , vol. 192, pp. 425–439, 2013.
  * [64] J. Kortstr’́om, U. Marja, and T. Tiira, “Automatic classification of seismic events within a regional seismograph network,” _Comuters and Geosciences_ , vol. 87, pp. 22–30, 2016.