# Deep Distribution-preserving Incomplete Clustering with Optimal Transport

Mingjie Luo, Siwei Wang, Xinwang Liu, Wenxuan Tu, Yi Zhang, Xifeng Guo, Sihang
Zhou and En Zhu  M. Luo, S. Wang, X. Liu, W. Tu, Y. Zhang, X. Guo, S. Zhou and
E. Zhu are with School of Computer, National University of Defense Technology,
Changsha, China, 410073 (e-mail: {luomingjie13, wangsiwei13, xinwangliu,
enzhu}@nudt.edu.cn).

###### Abstract

Clustering is a fundamental task in the computer vision and machine learning
community. Although various methods have been proposed, the performance of
existing approaches drops dramatically when handling incomplete high-
dimensional data (which is common in real world applications). To solve the
problem, we propose a novel deep incomplete clustering method, named Deep
Distribution-preserving Incomplete Clustering with Optimal Transport (DDIC-
OT). To avoid insufficient sample utilization in existing methods limited by
few fully-observed samples, we propose to measure distribution distance with
the optimal transport for reconstruction evaluation instead of traditional
pixel-wise loss function. Moreover, the clustering loss of the latent feature
is introduced to regularize the embedding with more discrimination capability.
As a consequence, the network becomes more robust against missing features and
the unified framework which combines clustering and sample imputation enables
the two procedures to negotiate to better serve for each other. Extensive
experiments demonstrate that the proposed network achieves superior and stable
clustering performance improvement against existing state-of-the-art
incomplete clustering methods over different missing ratios.

##  1 Introduction

Clustering is one of the fundamental and important unsupervised learning tasks
in data science, image analysis and machine learning community [15, 14, 21,
27, 9, 33, 16, 29, 32]. A wide variety of data clustering methods have been
proposed to organise similar items into same groups and achieve promising
performance, e.g., $k$-means clustering, Gaussian Mixture Model (GMM),
spectral clustering and deep clustering recently. However, existing clustering
approaches all hold one premise that the data themselves are complete while
data with missing features are quite common in reality. Data incompleteness
occurs due to many factors, e.g. sensor failure, unfinished collection and
data storage corruption. For example, face images are covered with masks
leading to missing features during COVID-19 [5]. When facing with various
types of missing features, incomplete data clustering has draw increasing
attention in recent years [24, 13, 25, 30, 15, 14](see Figure. 1).

Figure 1: (a) Image with missing features due to obstruction or shadow [11];
(b) Text data occupied with imperfect storage. (c) Data matrix with missing
values.

Existing incomplete clustering can be roughly categorized into two mechanisms,
heuristic-based and learning-based respectively. Both of them firstly impute
the missing features and then the full data matrix can be applied with
traditional clustering algorithms. The heuristic imputation methods often rely
on statistic property, e.g., zero-filling (ZF) and mean-filling (MF) after
normalizing. Median values are also popular for imputation in genetic study.
Particularly, the KNN-filling method considers the local reliable partners
which fills the missing entries with the mean value of $k$-closest neighbors.
When facing with complex high-dimensional data, heuristic-based methods
perform poorly since the simple imputations cannot obtain enough information
to precisely recover data.

Recently, learning-based imputation methods receive enormous attention and
become to be the mainstream. Existing work can be categorized into shallow and
deep learning framework. The shallow representatives normally assume that the
data are low-rank and therefore apply iterative methods to recover missing
values [20, 8, 26, 17, 3]. Moreover, the Expectation-Maximum (EM) algorithm
iteratively estimates the maximum likelihood and then inferences the missing
variables until convergent. With the improvements of deep learning
architectures, various deep networks have been proposed to handle
incompleteness. A desirable attribute for deep approaches is that they should
accurately inference the joint and marginal distributions of the data.
Therefore, variants of generation-style networks are introduced including
Generative Adversarial Networks (GAN) and Variational Auto-Encoder (VAE). In
[31], a generator utilizes the observed features to generate ’complete’ data
and the discriminator attempts to determine which components are actually
observed or imputed. With the adversary training strategy, the generated
missing features could approximate the real data distribution. Followed this
line, enormous GAN and VAE-based approaches are put forward to minimizing the
distances between real values and imputed matrices.

Although these aforementioned methods offer solutions for incomplete data
clustering, several drawbacks in existing mechanism cannot be neglected: i)
Existing incomplete clustering methods follow a two-step manner, where the
imputation stage and the clustering stage are separated from each other. In
other words, the imputed features are not designed for clustering task, which
may heavily degrade the clustering performance in return. ii) When facing with
high-dimensional data (e.g., images, text), both of the shallow and deep
methods perform poorly due to the insufficient observed information with
inaccurate imputation. These results in sharp degradation in clustering task
performance.

In this paper, we propose a novel deep incomplete clustering method, which we
refer as Deep Distribution-preserving Incomplete Clustering with Optimal
Transport (DDIC-OT), that generalizes the well-known Deep Embedding Clustering
network (DEC) to handle missing features. Different from existing pixel-by-
pixel reconstruction in traditional autoencoder, we propose to minimize the
Wasserstain distance between observed data and the reconstructed data with
optimal transport. Moreover an addition clustering layer is added into the
embedded representation level with KL-divergence for measuring clustering
loss. By optimizing the novel network, the distribution of original data can
be well-preserved and in return the missing features can be more accurately
imputed by guidance of latent clustering structures. Thus, the proposed DDIC-
OT simultaneously utilizes the imputation and the embedded clustering
procedures so that they can be jointly negotiated with each other and reach
consensus best serving for clustering task. Finally, the proposed DDIC-OT is
showcased in extensive experiments on a wide variety of benchmarks with
different missing ratios, to evaluate its effectiveness. As demonstrated, the
proposed network enjoys superior clustering performance in comparison with
existing state-of-the-art imputation methods by large margins.

Figure 2: The framework of the proposed DDIC-OT. Instead of pixel-to-pixel
reconstruction, we impute features by minimizing the distribution distance
with optimal transport. Moreover, the latent embedding representations are
regularized with clustering loss to ensure intra-cluster discrimination. The
joint loss functions seamlessly negotiate incomplete imputation and clustering
tasks as a unified framework to improve the performance of each other.

The contributions of our DDIC-OT are summarized as follows,

  1. 1.

We mathematically analyze the failures of existing incomplete clustering
methods in theory when facing with high-dimensional data. To avoid
insufficient training brought by the spareness of full-observed data, a novel
end-to-end deep clustering network is proposed to minimize the wasserstain
distances between original and reconstructed distribution.

  2. 2.

We regularize the latent distribution with more discriminate separation to
further enhance task performance. By the guidance of the unified loss
function, the network decodes the informative latent representations
contributing to better recovery and clustering. To the best of our knowledge,
this could be the first work of end-to-end deep incomplete clustering network.

  3. 3.

Comprehensive experiments are conducted on six high-dimensional benchmarks
datasets with various incomplete ratios. As the experimental results show, the
proposed network significantly outperforms state-of-the-art incomplete
clustering methods by large margins.

##  2 Notion and Related Work

###  2.1 Notion

Throughout this paper, we use boldface uppercase letters and lowercase letters
to denote matrices and vectors respectively. The $(i,j)$-th elements of a
matrix $\mathbf{U}$ is referred as $\mathbf{U}_{ij}$.

Let $\mathbf{X}\in\mathbb{R}^{n\times d}$ be the data matrix with $n$ samples
$d$ dimension. Then we define a missing index matrix
$\mathbf{M}\in\\{0,1\\}^{n\times d}$ as follows,

$\mathbf{M}_{ij}=\left\\{\begin{array}[]{ll}1&\text{ if the entry }(i,j)\text{
of }\mathbf{X}\text{ can be observed, }\\\ 0&\text{ otherwise.
}\end{array}\right.$ (1)

With the defined mask matrix $\mathbf{M}$, the incomplete data matrix we
observed can be defined as

$\mathbf{X}^{(obs)}=\mathbf{X}\circ\mathbf{M}+NaN\circ(\mathbf{1}_{n\times
d}-\mathbf{M}),$ (2)

where the $\circ$ denotes the Hadamard (elementwise) product and $NaN$ means
Not a Number throughout the paper.

###  2.2 Related Work

Statistical imputation. Basic statistical methods try to utilize information
from the missing data by the means of numerical property. Most of them use
statistical attributes to estimate the missing feature values, rather than
directly discard incomplete feature information. Incomplete entries are filled
with constants to obtain complete data so that they can be directly applied to
machine learning tasks, e.g., zero, mean and median. Additionally, KNN
imputation method has been considered as an alternative estimating the missing
features with the mean of $k$ nearest reliable neighbors [1].

The Bayesian framework is different from the previous method in that it
considers the joint and conditional distribution for dealing with incomplete
features. These frames are generally expressed in terms of a maximum-
likelihood method, which estimate missing values with the most probable
numbers. The most popular method of Bayesian framework is the Expectation
Maximization (EM) algorithm [2, 4].

Deep incomplete clustering. Although deep clustering mechanism has received
much attention in recent years, none of existing methods has considered to
cluster with incomplete features in an end-to-end manner yet. The typical
methods follow the two-step strategy:imputation and clustering separately.
They propose to fill missing values through neural networks and then apply
clustering algorithms on the estimated dataset. GAIN [31] firstly proposes to
impute incomplete features with GAN. Different from the traditional GAN
networks, the goal of the discriminator in GAIN is to accurately distinguish
whether the data are imputed or real, so as to force the samples generated by
the generator to be close to the real data distribution. Unfortunately, the
same problems as common GANs, these models are generally difficult to train
since the optimization processes are hardly stable. Apart from GAN-like
networks, VAEAC [7] proposes a neural probabilistic model based on variational
autoencoder, which can estimate the observed features using stochastic
gradient variational inference [10]. However these VAE-based method may lead
to poor results when the posterior approximation of variational inference is
far from the actual posterior approximation. In addition, based on fitting the
conditional distribution of the missing data, a Markov chain Monte Carlo
(MCMC) scheme has been developed in [23].

Optimal transport and sinkhorn divergence. Let
$\alpha=\sum_{i=1}^{n}a_{i}\delta_{\mathbf{X}_{i}}$,
$\beta=\sum_{i=1}^{n}b_{i}\delta_{\mathbf{Y}_{i}}$ be two discrete
distributions formed by empirical given data samples $\mathbf{X,Y}$, and their
supports $\mathbf{X}\in\mathbb{R}^{n\times
d},\mathbf{Y}\in\mathbb{R}^{n^{\prime}\times d}$ and frequency vectors
$\mathbf{a},\mathbf{b}$. It can be easily obtained that
$\mathbf{a}^{\top}\mathbf{1}=1,\mathbf{a}\geq
0,\mathbf{b}^{\top}\mathbf{1}=1,\mathbf{b}\geq 0$.The $q$-th Wasserstein
distance corresponds to these two distributions $\alpha$ and $\beta$ is
denoted as follows,

$W_{q}(\alpha,\beta)\stackrel{{\scriptstyle\text{ def
}}}{{=}}\min_{\mathbf{P}\in
U(\mathbf{a},\mathbf{b})}\langle\mathbf{F},\mathbf{C}\rangle,$ (3)

where $U(\mathbf{a},\mathbf{b})\stackrel{{\scriptstyle\text{ def
}}}{{=}}\left\\{\mathbf{F}\in\mathbb{R}^{n\times
n^{\prime}}_{+}:\mathbf{F}\mathbf{1}=\mathbf{a},\mathbf{F}^{\top}\mathbf{1}_{n}=\mathbf{b}\right\\}$
and
$\mathbf{C}=\left(\left\|x_{i}-y_{j}\right\|^{q}\right)_{ij}\in\mathbb{R}^{n\times
n^{\prime}}$ denotes as the cost matrix of pairwise squared distances between
the support sets. In our paper, we set $q=2$. The Wasserstein distance denoted
in Eq. (3) is often jointly introduced with an entropy regularization,

$W_{q}^{\epsilon}(\alpha,\beta)\stackrel{{\scriptstyle\text{ def
}}}{{=}}\min_{\mathbf{F}\in
U(\mathbf{a},\mathbf{b})}\langle\mathbf{F},\mathbf{C}\rangle-\epsilon
h(\mathbf{F}),$ (4)

where $h(\mathbf{F})\stackrel{{\scriptstyle\text{ def
}}}{{=}}-\sum_{ij}f_{ij}\log f_{ij}$ denotes the entropy regularization. Eq.
(4) can be efficiently optimized using Sinkhorn algorithm [22]. Based on Eq.
(4), a symmetric divergence can be represented as

$S_{\epsilon}(\alpha,\beta)\stackrel{{\scriptstyle\text{ def
}}}{{=}}\mathrm{OT}_{\epsilon}(\alpha,\beta)-\frac{1}{2}\left(\mathrm{OT}_{\epsilon}(\alpha,\alpha)+\mathrm{OT}_{\epsilon}(\beta,\beta)\right).$
(5)

The Sinkhorn divergence in Eq. (5) offers a tractable alternative for
Wasserstein distance calculations, and easily be accelerated by GPU. In our
paper, we use the sinkhorn divergence to measure the OT distance of two
distributions.

##  3 DDIC-OT

###  3.1 Motivation

Problem analysis Although the aforementioned methods have been proposed to
solve incomplete data clustering to some extent, most of them are evaluated
with very small-dimensional data and make them unpractical in real scenarios.
When facing with high-dimensional data (e.g., images, text), both of the
existing shadow and deep methods perform poorly due to the insufficient
observed information with inaccurate imputation. We theoretically analyze this
phenomenon with the following Theorem 1.

###### Theorem 1

Suppose the data are i.i.d (independently and identically distributed), a
fully-observed high-dimensional data sample exists with low probability when
facing incompleteness.

###### Proof 1

Suppose the missing ratio is $p(0\leq p\leq 1)$. Given a matrix
$\mathbf{X}\in\mathbb{R}^{n\times d}$. For each sample $x_{i}$, we can obtain
the following equation.

$\begin{split}P\left(\mathbf{X}_{i1},\ldots,\mathbf{X}_{id}\right)=P\left(\mathbf{X}_{i1}\right)\cdots
P\left(\mathbf{X}_{id}\right)=\left(1-p\right)^{d},\end{split}$ (6)

where $P\left(\mathbf{X}_{i1}\right)$ denotes the probability
$\mathbf{X}_{i1}$ can be observed.

Taking $p=0.1,d=300$ as an example, with $10^{-14}$ probability the sample
$x_{i}$ can be fully-observed. With the increasing dimension $d$, the
probability becomes smaller and approximates 0. This completes the proof.

The Theorem 1 illustrates that very few samples are fully complete when the
dimensions are relatively high. Therefore, the traditional statistical and
deep generative methods fail to impute proper values lacking of sufficient
information, e.g., knn-filling and GAN-style solutions. In [19], the
Wasserstain distance is firstly applied to impute missing features where the
assumption is to minimize the discrepancy of missing data distribution and the
complete data distribution. In the low-dimensional incomplete setting (less
than 50), the experiments results are promising and proven to show more stable
along with change of the incomplete ratios. However, as confronting with much
higher dimension data types (e.g., images, videos and text), very few fully-
complete data can be obtained making the empirical estimation of target
distribution (complete data distribution) difficult and inaccurate. Therefore
these methods perform poorly in downstream clustering tasks (see results in
Table. I).

Different from existing assumptions, we propose to jointly solve the two
processes in a unified framework: reconstruction and clustering. The natural
way of reconstruction is to apply autoencoder models. The observed values can
be regraded as ’supervised’ signals for the reconstruction. However, with few
informative information, it is not reasonable to only reconstruct the missing
counterparts since the reconstruction may destroy the geometry distribution
features for the data and the clustering performance is heavily affected. In
this paper, we decide to recover the latent distribution instead of pixel-
level approximation. Specially, we adopt the latent variable models defined by
an encoder-decoder manner, where we firstly encode original data $x_{i}$ into
the latent code $z_{i}$ in the latent space $\mathcal{Z}$ and then $z_{i}$ is
decoded to the reconstructed image $\hat{x}_{i}$. This process can be
expressed as,

$p_{\hat{X}}(\hat{x}):=\int_{\mathcal{Z}}p_{p_{\hat{X}}(\hat{x}|z)}(\hat{x}|z)p_{z}(z)dz,\quad\forall
x\in\mathcal{X}$ (7)

where $p_{x}(z|x),p_{\hat{X}}(\hat{x}|z)$ are parameterized with the encoder
$f_{e}$ and decoder $f_{d}$ network. Then the distribution-preserving loss can
be measured with Eq. (5) respecting to $p_{X}$and $p_{\hat{X}}$,

$L_{s}(\mathbf{X},\mathbf{\hat{X}})=S_{\epsilon}(\mathbf{X},f_{d}(f_{e}(\mathbf{X}))).$
(8)

###  3.2 Overall Network Architecture

In this section, we leverage the one-stage deep incomplete clustering
introduced in the previous section as a basis to demonstrate the process of
the proposed learning algorithm, the overall flowchart is illustrated in
Figure 2. The proposed clustering model consists of three parts, an encoder, a
decoder, and a soft clustering layer, specifically, the method relies on a
linear combination based on two objective functions, representing the optimal
transport distance and clustering loss respectively. The joint optimization
process can be described as follows:

$L=L_{s}+\gamma L_{c},$ (9)

where $L_{s}$ is the sinkhorn divergence shown in Eq. (5) and $L_{c}$ is the
clustering loss. $\gamma$ is a hyper-parameter, which is used to balance the
two costs. Consider a dataset $\mathbf{X}$ with $n$ samples, and each $x_{i}$
$\in$ $\mathbb{R}^{d}$ where $d$ is the dimension. The number of clusters $k$
is known, for each input data $x_{i}$ we denote the nonlinear mapping
$f_{e}:x_{i}\rightarrow z_{i}$ and $f_{d}:z_{i}\rightarrow\hat{x_{i}}$ where
$z_{i}$ is the low dimensional feature space, $\hat{x_{i}}$ is the complete
data learned through the network.

The clustering loss is defined as KL divergence between distributions $P$ and
$Q$ proposed in[28], where $P$ is the soft assignment of the distribution $z$:

$p_{ij}=\frac{\left(1+\left\|z_{i}-\mu_{j}\right\|^{2}\right)^{-1}}{\sum_{j}\left(1+\left\|z_{i}-\mu_{j}\right\|^{2}\right)^{-1}},$
(10)

and then the cluster assignment can be obtained
$s_{i}=\mathop{\arg\max}_{j}p_{ij}$. Then $Q$ is the target distribution
derived from $P$,

$q_{ij}=\frac{p_{ij}^{2}/\sum_{i}p_{ij}}{\sum_{j}\left(p_{ij}^{2}/\sum_{i}p_{ij}\right)}.$
(11)

Therefore, the clustering loss is defined as

$L_{c}=KL(Q\|P)=\sum_{i}\sum_{j}q_{ij}\log\frac{q_{ij}}{p_{ij}}.$ (12)

We summarize the merits of our proposed framework with the following factors:
i) more naturally handle with incomplete clustering in high-dimensional space.
The $L_{s}$ loss accomplishes the reconstruction samples with preserving
geometry characteristics. ii) more flexible that does not require the prior
distribution of $\mathbf{X}$ or $\mathbf{Z}$. Instead of explicit distribution
formulation, our encoder and decoder network implicitly estimate the latent
distribution with more flexibility; iii) regularizing the latent distribution
$q$ with more discriminate separation to further enhance task performance. As
the empirical experimental results show, the guidance of the joint loss
function updates the network leading to the improvement of clustering
performance.

###  3.3 Model Training

The training phase of the model consists of two phases: the pre-training phase
where the network only contains reconstruction loss and the fine-tune phase
where both optimal transport distance and clustering loss are optimized. Our
encoder consists of a fully-connected multi-layer perceptron with dimensions
$d$-500-500-1000/2000-10 and the decoder is a mirrored version of the encoder.
The details of the network architecture are provided in the supplementary
materials. The optimizer Adam with init learning rate $\eta$ = 0.001 is
applied for all datasets, and the batch size is set to 256. After pre-
training, we provide two options of the parameter $\lambda$ 150 and 100.
Furthermore, for sinkhorn divergence, we set entropy regularization parameters
$\epsilon$ as 0.01. In addition, we will stop training if the percentage of
label distribution change between two consecutive updates for target
distribution is less than the threshold $\delta$ or the number of iterations
meets $MaxIter$. Then the convergence threshold $\delta$ and $MaxIter$ are set
to 0.1 and 200 separately. The full training procedure is summarized in
Algorithm 1.

Algorithm 1 DDIC-OT

Input: Missing data $\mathbf{X}_{m}$; Cluster number $k$; Hyper-parameter
$\lambda$; Batchsize $N$; Maximum iterations $MaxIter$; Stopping threshold
$\delta$; Learning rate $\eta$.
Output: Clustering Assignment $S$.

1:Initialize $\mathbf{X}_{m}$ with mean filling.

2:Initialize clustering centroids $u$.

3:for $iter=0$ to $Maxiter$ do

4: for $i=0$ to $\lfloor n/N\rfloor$ do

5: Sample a minibatch $\left\\{x_{i}\right\\}_{i=1}^{m}$ from $\mathbf{X}$.

6: Compute related variables by $z_{i}$ = $f_{e}(x_{i})$, $\hat{x_{i}}$ =

7: $f_{d}(z_{i})$.

8: Compute $P_{i}$, $Q_{i}$ using Eq. (10) and Eq. (11)

9: Compute clustering assignment for $\left\\{x_{i}\right\\}_{i=1}^{m}$.

10: Compute overall loss $L$ by Eq. (9).

11: Back-propagation and update model weights.

12: end for

13: Compute $Z$ = $f_{e}(\mathbf{X})$.

14: Compute $P$ and $Q$.

15: Compute clustering assignment $S$.

16: if $sum(S_{iter+1}\neq S_{iter})/n$ <$\delta$ then

17: Stop training.

18: end if

19:end for

TABLE I: The aggregated ACC, NMI and Purity comparison (mean$\pm$std) of
different algorithms on benchmark datasets. ’-’ means out of the GPU memory.
The detailed results are omitted due to space limit and provided in
supplementary materials.

Method | Shallow | Deep
---|---|---
Dataset | MF | ZF | LRC | MNC | FSGR | GAIN | VAEAC | MIWAE | MDIOT | Ours
ACC$(\%)$
Mnist | $54.66\pm 3.13$ | $52.48\pm 3.33$ | $51.82\pm 3.46$ | $53.28\pm 3.08$ | $53.22\pm 2.97$ | $52.05\pm 3.06$ | $53.73\pm 3.63$ | - | $54.31\pm 3.46$ | $\mathbf{84.31\pm 0.0}$
Usps | $61.63\pm 3.92$ | $60.72\pm 3.24$ | $61.78\pm 3.63$ | $61.80\pm 3.61$ | $60.22\pm 3.38$ | $60.20\pm 3.11$ | $61.90\pm 3.51$ | $48.75\pm 4.73$ | $63.63\pm 4.07$ | $\mathbf{74.48\pm 0.0}$
Fmnist | $51.14\pm 3.87$ | $49.56\pm 3.84$ | $51.70\pm 3.75$ | $51.56\pm 3.44$ | $52.12\pm 4.16$ | $50.75\pm 4.39$ | $52.04\pm 4.05$ | - | $50.91\pm 3.54$ | $\mathbf{58.88\pm 0.0}$
Reuters | $56.26\pm 11.67$ | $50.96\pm 9.15$ | $53.79\pm 5.48$ | $54.17\pm 5.27$ | $53.72\pm 5.47$ | $51.25\pm 9.49$ | $60.22\pm 8.62$ | $54.51\pm 10.00$ | $52.18\pm 8.21$ | $\mathbf{76.06\pm 0.0}$
COIL20 | $54.33\pm 4.95$ | $42.77\pm 5.86$ | $58.73\pm 4.56$ | $59.10\pm 4.47$ | $55.00\pm 4.74$ | $55.10\pm 4.42$ | $60.21\pm 4.22$ | $57.87\pm 5.13$ | $58.95\pm 4.67$ | $\mathbf{66.40\pm 0.0}$
Letter | $35.77\pm 1.22$ | $33.40\pm 1.47$ | $36.95\pm 1.36$ | $33.68\pm 1.53$ | $37.34\pm 1.05$ | $35.54\pm 1.23$ | $36.11\pm 1.32$ | $27.42\pm 0.91$ | $35.40\pm 1.39$ | $\mathbf{47.15\pm 0.0}$
NMI$(\%)$
Mnist | $47.82\pm 1.42$ | $45.48\pm 1.53$ | $46.07\pm 1.59$ | $46.55\pm 1.36$ | $46.57\pm 1.27$ | $46.06\pm 1.31$ | $47.62\pm 1.19$ | - | $49.62\pm 1.07$ | $\mathbf{76.84\pm 0.0}$
Usps | $58.51\pm 3.92$ | $55.89\pm 3.24$ | $57.56\pm 3.63$ | $58.02\pm 3.61$ | $56.21\pm 3.38$ | $57.54\pm 1.51$ | $58.32\pm 1.25$ | $44.60\pm 4.38$ | $62.33\pm 1.37$ | $\mathbf{74.48\pm 0.0}$
Fmnist | $49.83\pm 3.87$ | $47.03\pm 3.84$ | $49.98\pm 3.75$ | $50.07\pm 3.44$ | $50.19\pm 4.16$ | $50.55\pm 1.16$ | $49.93\pm 1.08$ | - | $49.49\pm 1.03$ | $\mathbf{61.28\pm 0.0}$
Reuters | $26.37\pm 11.67$ | $21.41\pm 9.15$ | $26.43\pm 5.48$ | $27.37\pm 5.27$ | $25.82\pm 5.47$ | $21.26\pm 9.94$ | $31.99\pm 8.04$ | $23.71\pm 9.67$ | $22.28\pm 11.42$ | $\mathbf{44.92\pm 0.0}$
COIL20 | $68.89\pm 4.95$ | $55.75\pm 5.86$ | $73.38\pm 4.56$ | $74.05\pm 4.47$ | $70.22\pm 4.74$ | $69.14\pm 2.67$ | $74.36\pm 2.38$ | $71.72\pm 2.64$ | $73.43\pm 2.10$ | $\mathbf{77.72\pm 0.0}$
Letter | $37.58\pm 1.22$ | $34.79\pm 1.47$ | $39.18\pm 1.36$ | $35.06\pm 1.53$ | $39.43\pm 1.05$ | $37.98\pm 0.57$ | $38.56\pm 0,57$ | $30.04\pm 0.63$ | $37.45\pm 0.72$ | $\mathbf{52.29\pm 0.0}$
Purity$(\%)$
Mnist | $58.37\pm 1.62$ | $56.64\pm 2.21$ | $57.35\pm 1.79$ | $57.96\pm 1.83$ | $58.09\pm 1.81$ | $56.78\pm 1.89$ | $57.91\pm 1.57$ | - | $59.28\pm 1.47$ | $\mathbf{84.31\pm 0.0}$
Usps | $69.40\pm 2.47$ | $67.74\pm 2.74$ | $69.11\pm 2.47$ | $69.55\pm 2.00$ | $67.70\pm 2.29$ | $67.72\pm 2.34$ | $69.36\pm 2.45$ | $55.40\pm 5.35$ | $71.35\pm 2.77$ | $\mathbf{80.19\pm 0.0}$
Fmnist | $56.09\pm 2.20$ | $53.03\pm 2.84$ | $56.71\pm 2.22$ | $56.61\pm 2.42$ | $57.15\pm 1.52$ | $55.98\pm 2.16$ | $56.62\pm 1.87$ | - | $56.27\pm 1.88$ | $\mathbf{63.47\pm 0.0}$
Reuters | $74.71\pm 5.10$ | $74.21\pm 4.97$ | $78.41\pm 4.08$ | $\mathbf{78.97\pm 3.59}$ | $77.79\pm 3.91$ | $73.78\pm 5.12$ | $78.18\pm 3.94$ | $74.43\pm 4.99$ | $73.67\pm 4.76$ | $75.72\pm 0.0$
COIL20 | $58.03\pm 5.49$ | $45.63\pm 4.97$ | $63.25\pm 3.93$ | $63.96\pm 4.09$ | $59.38\pm 3.83$ | $58.77\pm 4.19$ | $64.63\pm 4.16$ | $61.30\pm 4.04$ | $63.48\pm 3.67$ | $\mathbf{70.94\pm 0.0}$
Letter | $37.90\pm 1.01$ | $35.23\pm 1.89$ | $39.30\pm 1.02$ | $35.49\pm 1.67$ | $39.76\pm 0.99$ | $38.12\pm 0.99$ | $38.68\pm 0.88$ | $29.04\pm 0.83$ | $37.66\pm 1.14$ | $\mathbf{49.56\pm 0.0}$

##  4 Experiments

###  4.1 Experiments Setup

Datasets In this paper, we conduct extensive experiments on the six widely-
used large-scale benchmark datasets. (1) MNIST-full and Fashion-MNIST[12]:
70000 images including the training and testing split are combined into a
unified dataset. (2)USPS[6]: This dataset contains a total of 9298 grayscale
samples with 16 $\times$ 16 pixels. (3)
COIL-20111https://www.cs.columbia.edu/CAVE/software/softlib/:COIL-20 consists
of 1440 images of 20 objects taken by cameras from varying angles.
(4)Reuters-10K: We used 4 root categories: corporate/industrial,
government/social, markets and economics as labels and excluded all documents
with multiple labels. We randomly sampled a subset of 10000 examples and
computed tf-idf features on the 2000 most frequent words. We term this dataset
as Reuters-10K.(5)Letter 222https://www.nist.gov/itl/products-and-
services/emnist-dataset: The Letter dataset merges a balanced set of the 26
letters with 800 images each class.

Followed by existing incomplete clustering task setting, we set seven groups
of incomplete ratios as $\\{0.1,0.2,0.3,\cdots 0.6,0.7\\}$ for each dataset in
our experiments. Incomplete ration means the percentage of missing features in
all samples.

TABLE II: Benchmark dataset description. Dataset | Samples | Dimensions | Classes
---|---|---|---
Mnist | 70000 | 784 | 10
USPS | 9298 | 256 | 10
FMNIST | 70000 | 784 | 10
Reuters-10k | 10000 | 2000 | 4
COIL-20 | 1440 | 1024 | 20
Letter | 20800 | 784 | 26

Evaluation Metrics In our experiements, we used three standard clustering
performance metrics for evaluation: (1) Accuracy (ACC) is computed by
assigning each cluster with the dominating class label and taking the average
correct classification rate as the final score, (2) Normalised Mutual
Information (NMI) quantifies the normalised mutual dependence between the
predicted labels and the ground-truth, and (c) Purity measures the proportion
of the number of samples correctly clustered to the total number of samples.
All of these metrics scale from 0 to 1 and higher values indicate better
performance. Specially, we report the mean values and standard derivations of
10 independent runs to avoid the randomness brought by the different
initializations of $k$-means.

###  4.2 Compared SOTA methods

(1) Mean-Filling (MF): The missing features are imputed with the mean of the
observed values in the corresponding dimensions.(2) Mean-Filling (MF): The
missing features are imputed with zeros in the normalized data matrix.(3) Low-
rank Completion(LRC)[20]: The method attempts to recover data matrix with low-
rank assumption. (4) Max Norm Completion (MNC)[3]: MNC adopts the max-norm to
complete missing features.(5)Factor Group-Sparse Regularization for Efficient
Low-Rank Matrix Recovery(FSGR)333https://github.com/udellgroup/Codes-of-FGSR-
for-effecient-low-rank-matrix-recovery[3] The author proposes factor group-
sparse regularizers to accomplish low-rank matrix completion
task.(6)GAIN444https://github.com/jsyoon0823/GAIN[31]: Missing data imputing
using Generative Adversarial Nets. It proposes a method that uses GAN to
estimate and complete the work of filling missing values. (7)
VAEAC:555https://github.com/tigvarts/vaeac[7]Variational Autoencoder with
Arbitrary Conditioning. It is a latent variable model trained using stochastic
gradient variational Bayes.(8)MIVAE666https://github.com/pamattei/miwae[18]:
MIWAE is based on the importance-weighted autoencoder, and maximises a
potentially tight lower bound of the log-likelihood of the observed data.
(9)MDIOT777https://github.com/BorisMuzellec/MissingDataOT[19]: Missing Data
Imputing using Optimal Transport. This paper leverages OT to define a loss
function for missing data distribution and complete data distribution. The
hyper-parameters used in all our comparative experiments follow their
corresponding papers.

For all the compared methods above, we have downloaded their public
implementations with Matlab and Pytorch. All our experiments are conducted on
desktop computer with Intel i7-9700K CPU @ 3.60GHz$\times$12, 64 GB RAM and
GeForce RTX 3090 25GB.

Figure 3: The clustering results of ACC metric on the benchmark datasets with
different incomplete ratios. The results of Purity are provided in
supplementary materials due to space limit.

###  4.3 Results Comparisons to Alternative Methods

Table I shows the aggregated clustering comparison of the above algorithms on
the benchmark datasets. The best results are highlighted with boldface and ’-’
means the out of GPU memory failure. Based on the results, we have the
following observations:

  * •

Our proposed method outperforms all the SOTA imputation competitors in
clustering performance by large margins. For example, our algorithm surpasses
the second best by 50.4%, 17%, 12%, 26%, 10%and 30%, in terms of ACC on all
benchmark datasets. In particular, the margins for the four datasets (Mnist,
Usps, Reuters and Letter) are very impressive. These results clearly verify
the effectiveness of the proposed network.

  * •

Comparing with the generative-style methods, the proposed DDIC-OT consistently
further improves the clustering performance and achieves better results among
the benchmark datasets. GAIN, VAEAC and MIWAE are the chosen representative
methods. As can be seen, they concentrate on the generation or imputation task
while ignoring the impacts of downstream clustering procedure. The joint
optimization framework further contributes to improving performance.

  * •

MDIOT has been considered as a strong baseline for incomplete data imputation.
It outperforms other competitors among most of the datasets. Our proposed
algorithm surpasses MDIOT by 55.2%, 17.1%, 15.7%, 45.8%, 12.6%and 33.2% in
terms of ACC on all benchmark datasets. The phenomenon demonstrates the
effectiveness of the our proposed architecture. Regardless of directly
computing distribution distances in original space, the bottleneck of our
embedding layer serves for clustering task and make distributions more
discriminate.

Figure 4: The clustering results of NMI metric on the benchmark datasets with
different incomplete ratios.

###  4.4 Qualitative Study

In this section, we deeply analyze the clustering performance regarding to
various ratios and the evolution of the learned representation. In order to
show the comparison between different methods more clearly, we draw the ACC
and NMI of compared methods under different missing rates as line graphs as
shown in Figure. 3 and 4.

From the figure, we can obtain the following observations:(1) As can be seen,
with the incomplete ratios increasing, all the methods suffers the degradation
of clustering performance due to more unavailable information. Especially for
the generative-based methods (VAEAC and MDIOT), their performance drops
sharply due to inaccurate imputations. (2) The results of our proposed method
in terms of ACC are higher than all the competing algorithms for different
incomplete ratios. Moreover, our method achieves stable performance against
the increasing incomplete ratios. These results clearly demonstrates the
effectiveness of DDIC-OT. (3) We also show the relative NMI performance of the
compared methods in Figure. 4. As can be seen, the clustering performance
results are consistent with the ACC observations.

###  4.5 Ablation Study

Loss Ablation Study

We first investigate how the clustering loss and the distribution-preserving
loss affect the clustering performance on Mnist/Usps/Reuters, and the results
are shown in Table III. In this experiment, we uniformly adopt datasets with
10$\%$ missing ratio. It seems that the $L_{c}$ has more contributions than
$L_{s}$ on Mnist/Usps for clustering, and inversely on Reuters. We also
conclude that the joint of two counterpart losses further contributes to
better performance.

TABLE III: Loss ablation study with 10$\%$ missing ratio.

Dataset | Mnist | Usps | Reuters
---|---|---|---
Loss | ACC | NMI | ACC | NMI | ACC | NMI
$L_{s}$ | 72.24 | 62.36 | 55.59 | 53.29 | 76.47 | 44.58
$L_{c}$ | 86.84 | 77.7 | 74.81 | 73.88 | 72.42 | 43.09
$L_{s}$ \+ $L_{c}$ | $\mathbf{92.16}$ | $\mathbf{85.77}$ | $\mathbf{77.5}$ | $\mathbf{77.35}$ | $\mathbf{77.7}$ | $\mathbf{47.93}$

Sensitivity to initialization imputed values

The initialization of imputed values has been demonstrated to be an essential
part of incomplete clustering. We tested its sensitivity in our DDIC-OT,
w.r.t. model performance on Mnist/Usps/Reuters. We evaluated two commonly-used
initialization values: zero-filling (ZF) and mean-filling (MF). Table V shows
that DDIC-OT can work stably without clear variation in the overall
performance when using different initializations. This verifies that our
method is insensitive to network initialization.

TABLE IV: Model sensitivity to different initializations of imputed values of
three different missing ratios (10%/30%50%) on three benchmarks. Metric:ACC.

Dataset | Mnist | Usps | Reuters
---|---|---|---
Initializations | ZF | MF | ZF | MF | ZF | MF
10% | 90.75 | 92.16 | 74.19 | 77.5 | 74.03 | 77.7
30% | 83.36 | 86.74 | 72.46 | 75.65 | 72.47 | 77.23
50% | 78.61 | 82.15 | 71.77 | 73.77 | 72.03 | 75.53

##  5 Conclusion

In this paper, we propose a novel incomplete clustering methods termed DDIC-
OT, which jointly performs clustering and missing data imputation into a
unified framework. Extensive experiments are conducted to demonstrate the
effectiveness of optimal transport for clustering tasks. In the future, we
will consider to construct more advanced network to further improve incomplete
clustering performance.

## References

  * [1] Nicholas L Crookston and Andrew O Finley.  yaimpute: an r package for knn imputation.  Journal of Statistical Software. 23 (10). 16 p., 2008.
  * [2] Arthur P Dempster, Nan M Laird, and Donald B Rubin.  Maximum likelihood from incomplete data via the em algorithm.  Journal of the Royal Statistical Society: Series B (Methodological), 39(1):1–22, 1977.
  * [3] Jicong Fan, Lijun Ding, Yudong Chen, and Madeleine Udell.  Factor group-sparse regularization for efficient low-rank matrix recovery.  In 33rd Conference on Neural Information Processing Systems (NeurIPS 2019), 2019.
  * [4] Zoubin Ghahramani and Michael I Jordan.  Supervised learning from incomplete data via an em approach.  In Advances in neural information processing systems, pages 120–127, 1994.
  * [5] Trisha Greenhalgh, Manuel B Schmid, Thomas Czypionka, Dirk Bassler, and Laurence Gruer.  Face masks for the public during the covid-19 crisis.  Bmj, 369, 2020.
  * [6] Jonathan J. Hull.  A database for handwritten text recognition research.  IEEE Transactions on pattern analysis and machine intelligence, 16(5):550–554, 1994.
  * [7] O Ivanov, M Figurnov, and D Vetrov.  Variational autoencoder with arbitrary conditioning.  In 7th International Conference on Learning Representations, ICLR 2019, 2019.
  * [8] Prateek Jain, Praneeth Netrapalli, and Sujay Sanghavi.  Low-rank matrix completion using alternating minimization.  In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 665–674, 2013.
  * [9] Zhao Kang, Xinjia Zhao, Chong Peng, Hongyuan Zhu, Joey Tianyi Zhou, Xi Peng, Wenyu Chen, and Zenglin Xu.  Partition level multiview subspace clustering.  Neural Networks, 122:279–288, 2020.
  * [10] Diederik P Kingma and Max Welling.  Stochastic gradient vb and the variational auto-encoder.  In Second International Conference on Learning Representations, ICLR, volume 19, 2014.
  * [11] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  Advances in neural information processing systems, 25:1097–1105, 2012.
  * [12] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [13] Shao-Yuan Li, Yuan Jiang, and Zhi-Hua Zhou.  Partial multi-view clustering.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 28, 2014.
  * [14] Xinwang Liu, Miaomiao Li, Chang Tang, Jingyuan Xia, Jian Xiong, Li Liu, Marius Kloft, and En Zhu.  Efficient and effective regularized incomplete multi-view clustering.  IEEE transactions on pattern analysis and machine intelligence, 2020\.
  * [15] Xinwang Liu, Xinzhong Zhu, Miaomiao Li, Lei Wang, Chang Tang, Jianping Yin, Dinggang Shen, Huaimin Wang, and Wen Gao.  Late fusion incomplete multi-view clustering.  IEEE transactions on pattern analysis and machine intelligence, 41(10):2410–2423, 2018.
  * [16] Xinwang Liu, Xinzhong Zhu, Miaomiao Li, Lei Wang, En Zhu, Tongliang Liu, Marius Kloft, Dinggang Shen, Jianping Yin, and Wen Gao.  Multiple kernel $k$ k-means with incomplete kernels.  IEEE transactions on pattern analysis and machine intelligence, 42(5):1191–1204, 2019.
  * [17] Si Lu, Xiaofeng Ren, and Feng Liu.  Depth enhancement via low-rank matrix completion.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3390–3397, 2014.
  * [18] Pierre-Alexandre Mattei and Jes Frellsen.  Miwae: Deep generative modelling and imputation of incomplete data sets.  In International Conference on Machine Learning, pages 4413–4423. PMLR, 2019.
  * [19] Boris Muzellec, Julie Josse, Claire Boyer, and Marco Cuturi.  Missing data imputation using optimal transport.  In International Conference on Machine Learning, pages 7130–7140. PMLR, 2020.
  * [20] Feiping Nie, Heng Huang, and Chris Ding.  Low-rank matrix recovery via efficient schatten p-norm minimization.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 26, 2012.
  * [21] Xi Peng, Jiashi Feng, Shijie Xiao, Wei-Yun Yau, Joey Tianyi Zhou, and Songfan Yang.  Structured autoencoders for subspace clustering.  IEEE Transactions on Image Processing, 27(10):5076–5086, 2018.
  * [22] Gabriel Peyré, Marco Cuturi, et al.  Computational optimal transport: With applications to data science.  Foundations and Trends® in Machine Learning, 11(5-6):355–607, 2019.
  * [23] Trevor W. Richardson, Wencheng Wu, Lei Lin, Beilei Xu, and Edgar A. Bernal.  Mcflow: Monte carlo flow models for data imputation.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), June 2020.
  * [24] Yuandong Tian, Wei Liu, Rong Xiao, Fang Wen, and Xiaoou Tang.  A face annotation framework with partial clustering and interactive labeling.  In 2007 IEEE Conference on Computer Vision and Pattern Recognition, pages 1–8. IEEE, 2007.
  * [25] Qianqian Wang, Zhengming Ding, Zhiqiang Tao, Quanxue Gao, and Yun Fu.  Partial multi-view clustering via consistent gan.  In 2018 IEEE International Conference on Data Mining (ICDM), pages 1290–1295. IEEE, 2018.
  * [26] Zaiwen Wen, Wotao Yin, and Yin Zhang.  Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm.  Mathematical Programming Computation, 4(4):333–361, 2012.
  * [27] Jianlong Wu, Keyu Long, Fei Wang, Chen Qian, Cheng Li, Zhouchen Lin, and Hongbin Zha.  Deep comprehensive correlation mining for image clustering.  In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 8150–8159, 2019.
  * [28] Junyuan Xie, Ross Girshick, and Ali Farhadi.  Unsupervised deep embedding for clustering analysis.  In International conference on machine learning, pages 478–487. PMLR, 2016.
  * [29] Congyuan Yang, Daniel Robinson, and Rene Vidal.  Sparse subspace clustering with missing entries.  In International Conference on Machine Learning, pages 2463–2472. PMLR, 2015.
  * [30] Liu Yang, Chenyang Shen, Qinghua Hu, Liping Jing, and Yingbo Li.  Adaptive sample-level graph combination for partial multiview clustering.  IEEE Transactions on Image Processing, 29:2780–2794, 2019.
  * [31] Jinsung Yoon, James Jordon, and Mihaela Schaar.  Gain: Missing data imputation using generative adversarial nets.  In International Conference on Machine Learning, pages 5689–5698. PMLR, 2018.
  * [32] Changqing Zhang, Yajie Cui, Zongbo Han, Joey Tianyi Zhou, Huazhu Fu, and Qinghua Hu.  Deep partial multi-view learning.  IEEE transactions on pattern analysis and machine intelligence, 2020\.
  * [33] Changqing Zhang, Huazhu Fu, Si Liu, Guangcan Liu, and Xiaochun Cao.  Low-rank tensor constrained multiview subspace clustering.  In Proceedings of the IEEE international conference on computer vision, pages 1582–1590, 2015.

##  6 Appendix

In this section, we mainly supplement our work from two aspects, namely the
specific settings of the experiment and the display of more experimental
results.

###  6.1 Model Training

We summarize in Table. VI the dataset specific optimal values of the
hyperparameter $\gamma$ which trades off between the optimal transport and the
clustering loss, as well as the full connection of two different node numbers
selected due to the difference in the dimensional of the dataset, in
particular, we only change the last layer of the encoder and the corresponding
decoding layer.

###  6.2 More Experimental Results

####  6.2.1 Sensitivity to initialization imputed values

The initialization of imputed values has been demonstrated to be an essential
part of incomplete clustering. We further tested its sensitivity in our DDIC-
OT, w.r.t. model performance on Fmnist/COIL20/Letter. Experimental results
show that not all the datasets that perform with mean-filling are better than
that with zero-filling, for example, when Fmnist with 10% missing ratio, the
effect of zero-filling is much better. Then the Table. V shows that when
different initializations are used, DDIC-OT can run stably without significant
changes in overall performance.

TABLE V: Model sensitivity to different initializations of imputed values of
three different missing ratios (10%/30%50%) on three benchmarks. Metric:ACC.

Dataset | Fmnist | COIL20 | letter
---|---|---|---
Initializations | ZF | MF | ZF | MF | ZF | MF
10% | 62.92 | 63.79 | 70.49 | 71.58 | 47.44 | 51.12
30% | 62.59 | 59.03 | 70.56 | 71.67 | 47.37 | 52.14
50% | 60.21 | 59.5 | 65.35 | 64.51 | 47.75 | 48.32

####  6.2.2 Comprehensive Experimental Results

To provide more comprehensive experimental results about the performance of
our algorithm under different missing ratios, we list the ACC, NMI, PUR of
each dataset with a missing ratio ranging from 10% to 70% in Table. VII, VIII,
IX, X, XI and XII. It is clearly to see that our algorithm has achieved a
apparent lead among almost all the missing proportions of the six benchmarks.
In order to show the comparison between different methods more clearly, we
draw the Purity of compared methods under different missing rates as line
graphs as shown in Figure 5. We observe that our algorithm has advantages for
all data sets except Reuters. Moreover, we can find that the performance of
our algorithm on Reuters has obvious advantages on the two indicators of ACC
and MNI. By analyzing the situation where ACC and MNI are much smaller than
PUR, we can clearly see that our comparison algorithm classifies most samples
into one cluster instead of achieving really fine clustering results.

Figure 5: The clustering results of Purity metric on the benchmark datasets
with different incomplete ratios.

###  6.3 Evolution and Convergence

(a) Mnist (b) Fmnist (c) Usps

Figure 6: The clustering performance evolution with respecting to training
epochs when missing ratio is $0.1$.

A large number of experimental results above have proved the effectiveness of
the proposed algorithm. In order to demonstrate more clearly about how our
model converges to the target, the clustering performance evolution with
respecting to training epochs is shown in Figure 6. Specifically, we show in
the figure the changes of ACC, MNI, and PUR with the training epoch when the
missing rate of the three datasets is 10%. It is obviously that our algorithm
achieves fast down convergence and satiafactory evolution.

####  6.3.1 Qualitative Study

Figure 7 illustrates the complete data and the imputation performance of the
competing method with 30% missing rate on the Mnist. Images along rows (a) and
(b) contains the complete data images and initialized data images which
represents mean-imputed data at 30% missing rate, respectively. The compared
imputation methods take the observed images (b) for input, and the complete
images are shown for reference. Images along rows (c), (d) include the imputed
results after using GAIN, MIDOT respectively. Compared with GAIN and MIDOT, it
can be seen from row (e) that our method is visually impressive. More
importantly, different from the pixel-level reconstruction used in GAIN and
MIDOT, our work is better at preserving the structure of the intended image
which is benefit for clustering task. Specifically, the embedding layer has
learned the structural information and removed the noise from our network, and
this is why our method can obtain leading clustering effects in the face of
missing data. The experimental results in Table. VII also verify our
statement.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)  (l)  (m)  (n)  (o)  (p)  (q)  (r)  (s)  (t)  (v)  (w)  (x)  (y)  (z)
(aa)  (ab)  (ac)  (ad)  (af)  (ag)  (ah)  (ai)  (aj)  (ak)  (al)  (am)  (an)
(ap)  (aq)  (ar)  (as)  (at)  (au)  (av)  (aw)  (ax)

(a) Complete data images

(b) Initialized data images

(c) GAIN

(d)MIDOT

(e)Ours

(k)

(u)

(ae)

(ao)

Figure 7: Sample imputation results for Mnist at 0.3 missing rate: (a)
Complete data images, (b) Initialized data images, (c) GAIN-imputed data
images, (d) MIDOT-imputed data images, (e) The reconstruction data of proposed
network.  TABLE VI: The dataset specific optimal values of the hyperparameter
$\gamma$ a and the size of autoencoder.

Dataset | Mnist | Usps | Fmnist | Reuters | COIL20 | Letter
---|---|---|---|---|---|---
$\gamma$ | 100 | 100 | 100 | 150 | 150 | 150
Encoder Size | 500/500/1000 | 500/500/1000 | 500/500/1000 | 500/500/2000 | 500/500/2000 | 500/500/2000
Decoder Size | 1000/500/500 | 1000/500/500 | 1000/500/500 | 2000/500/500 | 2000/500/500 | 2000/500/500

TABLE VII: The performance comparison (mean) of different algorithms on Mnist,
where ’-’ means out of the GPU memory.

Mnist
---
Method | Shallow | Deep
Missing Rate | Metrics | MF | ZF | LRC | MNC | FSGR | GAIN | VAEAC | MIWAE | MDIOT | Ours
10% | ACC | 54.63 | 55.55 | 54.57 | 53.13 | 53.13 | 54.37 | 54.53 | - | 55.09 | $\mathbf{92.16}$
NMI | 48.97 | 49.13 | 49.08 | 48.24 | 47.87 | 48.90 | 49.36 | - | 49.16 | $\mathbf{85.77}$
PUR | 58.71 | 59.24 | 59.49 | 58.48 | 57.96 | 58.70 | 59.38 | - | 59.09 | $\mathbf{92.16}$
20% | ACC | 53.41 | 53.94 | 52.68 | 52.04 | 52.86 | 53.36 | 53.57 | - | 52.52 | $\mathbf{87.43}$
NMI | 48.65 | 48.49 | 47.20 | 47.34 | 47.41 | 48.70 | 48.58 | - | 48.83 | $\mathbf{82.98}$
PUR | 58.88 | 58.65 | 57.99 | 58.48 | 58.00 | 59.31 | 58.31 | - | 58.71 | $\mathbf{87.43}$
30% | ACC | 55.25 | 52.95 | 53.42 | 51.45 | 53.75 | 51.76 | 53.98 | - | 53.09 | $\mathbf{86.74}$
NMI | 48.79 | 47.24 | 46.97 | 46.16 | 47.18 | 47.22 | 48.30 | - | 48.69 | $\mathbf{81.61}$
PUR | 59.06 | 57.48 | 58.08 | 56.85 | 58.06 | 57.23 | 58.11 | - | 58.63 | $\mathbf{86.74}$
40% | ACC | 54.88 | 55.87 | 52.82 | 51.72 | 52.25 | 53.16 | 55.38 | - | 53.15 | $\mathbf{85.66}$
NMI | 48.30 | 47.79 | 46.66 | 46.29 | 46.64 | 47.72 | 48.32 | - | 48.92 | $\mathbf{79.44}$
PUR | 58.91 | 58.98 | 58.10 | 57.43 | 58.16 | 57.81 | 58.75 | - | 58.84 | $\mathbf{85.66}$
50% | ACC | 54.19 | 52.29 | 52.65 | 52.95 | 54.56 | 49.65 | 52.87 | - | 54.53 | $\mathbf{82.15}$
NMI | 47.27 | 45.51 | 46.26 | 46.35 | 46.87 | 45.50 | 47.15 | - | 50.66 | $\mathbf{74.94}$
PUR | 58.10 | 57.04 | 57.81 | 58.11 | 58.63 | 55.96 | 57.71 | - | 60.22 | $\mathbf{82.15}$
60% | ACC | 52.70 | 52.00 | 52.01 | 51.61 | 50.46 | 50.97 | 51.61 | - | 54.81 | $\mathbf{80.86}$
NMI | 45.87 | 42.25 | 44.78 | 44.85 | 44.34 | 45.06 | 46.07 | - | 50.52 | $\mathbf{71.25}$
PUR | 56.81 | 54.23 | 56.89 | 56.76 | 56.50 | 56.45 | 57.07 | - | 60.04 | $\mathbf{80.86}$
70% | ACC | 52.32 | 50.33 | 50.36 | 49.89 | 49.83 | 47.75 | 50.27 | - | 54.88 | $\mathbf{75.15}$
NMI | 44.47 | 39.26 | 43.55 | 43.01 | 43.27 | 39.88 | 43.89 | - | 49.09 | $\mathbf{61.92}$
PUR | 56.96 | 52.55 | 56.08 | 55.42 | 55.65 | 52.59 | 55.53 | - | 59.74 | $\mathbf{75.15}$

TABLE VIII: The performance comparison (mean) of different algorithms on Usps.

Usps
---
Method | Shallow | Deep
Missing Rate | Metrics | MF | ZF | LRC | MNC | FSGR | GAIN | VAEAC | MIWAE | MDIOT | Ours
10% | ACC | 63.96 | 63.63 | 62.70 | 66.14 | 62.15 | 63.91 | 64.69 | 65.09 | 62.49 | $\mathbf{77.5}$
NMI | 61.28 | 61.00 | 60.62 | 61.71 | 60.87 | 61.22 | 61.98 | 62.18 | 61.61 | $\mathbf{77.35}$
PUR | 71.69 | 70.85 | 70.97 | 73.12 | 69.82 | 71.46 | 72.20 | 72.79 | 71.08 | $\mathbf{84.34}$
20% | ACC | 64.04 | 63.23 | 64.55 | 63.63 | 64.01 | 64.33 | 63.54 | 59.12 | 65.86 | $\mathbf{77.5}$
NMI | 60.58 | 60.31 | 60.15 | 60.49 | 60.30 | 61.87 | 61.63 | 54.80 | 63.49 | $\mathbf{77.67}$
PUR | 70.68 | 70.51 | 71.75 | 71.21 | 71.13 | 71.96 | 71.73 | 62.40 | 73.64 | $\mathbf{83.9}$
30% | ACC | 62.99 | 62.83 | 64.55 | 60.25 | 62.60 | 62.11 | 64.63 | 60.49 | 63.52 | $\mathbf{77.65}$
NMI | 60.31 | 59.65 | 59.93 | 58.85 | 58.90 | 60.26 | 61.07 | 59.56 | 62.67 | $\mathbf{75.64}$
PUR | 70.66 | 70.32 | 71.42 | 68.52 | 69.75 | 69.54 | 71.89 | 67.16 | 71.06 | $\mathbf{83.11}$
40% | ACC | 59.60 | 61.08 | 61.64 | 63.94 | 61.52 | 62.08 | 62.48 | 53.26 | 64.02 | $\mathbf{75.54}$
NMI | 58.60 | 57.90 | 57.58 | 59.00 | 57.95 | 59.44 | 59.22 | 49.61 | 62.46 | $\mathbf{73.63}$
PUR | 68.54 | 69.20 | 68.92 | 70.75 | 69.33 | 69.24 | 69.41 | 56.68 | 70.61 | $\mathbf{81.86}$
50% | ACC | 60.55 | 60.66 | 61.32 | 60.81 | 60.53 | 59.61 | 62.73 | 48.96 | 63.73 | $\mathbf{73.77}$
NMI | 58.24 | 55.44 | 56.50 | 57.46 | 55.54 | 58.14 | 58.49 | 44.48 | 63.02 | $\mathbf{70.52}$
PUR | 69.18 | 67.85 | 68.13 | 68.32 | 67.15 | 67.33 | 70.24 | 51.67 | 70.89 | $\mathbf{80}$
60% | ACC | 61.77 | 56.24 | 62.58 | 63.49 | 56.21 | 57.99 | 60.15 | 57.00 | 63.94 | $\mathbf{73.11}$
NMI | 57.68 | 50.32 | 56.12 | 57.23 | 52.49 | 54.19 | 56.02 | 53.54 | 63.02 | $\mathbf{66.74}$
PUR | 69.07 | 62.59 | 69.45 | 69.36 | 64.03 | 64.94 | 67.77 | 60.15 | 71.29 | $\mathbf{77.64}$
70% | ACC | 58.76 | 51.42 | 58.16 | 58.61 | 52.29 | 53.70 | 56.75 | 55.81 | 61.95 | $\mathbf{68.48}$
NMI | 53.41 | 43.77 | 51.34 | 52.97 | 46.88 | 49.52 | 51.85 | 51.26 | $\mathbf{60.35}$ | 59.95
PUR | 65.55 | 57.14 | 65.03 | 66.04 | 59.65 | 60.28 | 64.11 | 61.70 | 69.98 | $\mathbf{70.5}$

TABLE IX: The performance comparison (mean) of different algorithms on Fmnist,
where ’-’ means out of the GPU memory.

Fmnist
---
Method | Shallow | Deep
Missing Rate | Metrics | MF | ZF | LRC | MNC | FSGR | GAIN | VAEAC | MIWAE | MDIOT | Ours
10% | ACC | 52.28 | 51.07 | 52.46 | 51.95 | 49.56 | 51.01 | 53.32 | - | 51.55 | $\mathbf{63.79}$
NMI | 50.65 | 50.04 | 51.09 | 50.41 | 50.11 | 50.83 | 51.07 | - | 50.27 | $\mathbf{64.04}$
PUR | 56.81 | 56.70 | 57.27 | 56.88 | 55.74 | 57.05 | 57.66 | - | 56.96 | $\mathbf{68.28}$
20% | ACC | 51.81 | 52.31 | 51.70 | 49.93 | 50.31 | 51.80 | 50.99 | - | 55.98 | $\mathbf{63.03}$
NMI | 50.46 | 49.61 | 50.18 | 50.09 | 49.47 | 50.70 | 50.51 | - | 50.53 | $\mathbf{63.28}$
PUR | 57.09 | 56.18 | 56.69 | 56.42 | 55.86 | 56.63 | 56.29 | - | 58.45 | $\mathbf{67.45}$
30% | ACC | 53.11 | 51.75 | 50.31 | 54.34 | 50.16 | 53.61 | 50.26 | - | 51.38 | $\mathbf{59.03}$
NMI | 50.97 | 49.55 | 50.02 | 50.67 | 49.83 | 51.41 | 49.99 | - | 49.84 | $\mathbf{62.26}$
PUR | 57.56 | 56.06 | 56.42 | 58.11 | 56.43 | 57.42 | 56.37 | - | 56.55 | $\mathbf{63.52}$
40% | ACC | 53.04 | 50.32 | 52.72 | 52.72 | 51.25 | 50.88 | 53.94 | - | 50.62 | $\mathbf{61.67}$
NMI | 49.98 | 49.16 | 51.09 | 50.10 | 50.53 | 50.77 | 50.37 | - | 49.38 | $\mathbf{62.32}$
PUR | 56.73 | 55.68 | 57.95 | 57.46 | 56.90 | 56.31 | 57.59 | - | 56.03 | $\mathbf{66.06}$
50% | ACC | 50.58 | 51.14 | 52.48 | 52.28 | 51.53 | 50.72 | 52.90 | - | 51.84 | $\mathbf{59.5}$
NMI | 50.13 | 48.88 | 50.83 | 50.50 | 49.78 | 49.88 | 50.27 | - | 49.72 | $\mathbf{62.71}$
PUR | 56.17 | 54.68 | 57.74 | 57.34 | 56.65 | 55.70 | 57.35 | - | 56.34 | $\mathbf{64.48}$
60% | ACC | 50.36 | 44.51 | 52.59 | 51.88 | 53.73 | 51.25 | 51.21 | - | 51.95 | $\mathbf{54.5}$
NMI | 49.51 | 42.57 | 50.33 | 49.66 | 50.05 | 50.79 | 49.12 | - | 49.88 | $\mathbf{58.57}$
PUR | 55.71 | 47.26 | 57.17 | 56.65 | 57.44 | 56.28 | 56.20 | - | 56.27 | $\mathbf{59.4}$
70% | ACC | 46.72 | 41.76 | 51.30 | $\mathbf{53.78}$ | 49.43 | 49.34 | 52.17 | - | 51.60 | 50.61
NMI | 48.21 | 38.28 | 49.24 | 50.67 | 48.68 | 50.82 | 49.42 | - | 48.54 | $\mathbf{55.7}$
PUR | 52.28 | 43.94 | 55.89 | $\mathbf{57.76}$ | 55.55 | 54.32 | 56.85 | - | 55.81 | 55.11

TABLE X: The performance comparison (mean) of different algorithms on Reuters.

Reuters
---
Method | Shallow | Deep
Missing Rate | Metrics | MF | ZF | LRC | MNC | FSGR | GAIN | VAEAC | MIWAE | MDIOT | Ours
10% | ACC | 54.42 | 50.22 | 54.84 | 59.12 | 50.20 | 54.18 | 66.01 | 58.43 | 56.45 | $\mathbf{77.7}$
NMI | 26.44 | 24.83 | 29.55 | 32.78 | 27.06 | 30.24 | 38.17 | 32.80 | 33.02 | $\mathbf{47.93}$
PUR | 79.13 | 76.61 | 79.29 | $\mathbf{84.46}$ | 73.98 | 78.46 | 81.17 | 77.95 | 79.56 | 77.98
20% | ACC | 53.14 | 59.05 | 53.26 | 56.63 | 50.44 | 60.33 | 59.92 | 55.71 | 56.96 | $\mathbf{77.7}$
NMI | 28.17 | 33.63 | 29.46 | 31.38 | 25.28 | 33.57 | 34.93 | 29.03 | 32.44 | $\mathbf{47.9}$
PUR | 77.25 | 78.25 | 79.93 | 80.57 | 76.27 | 77.10 | $\mathbf{80.87}$ | 75.61 | 78.87 | 78.14
30% | ACC | 62.01 | 51.13 | 54.70 | 57.28 | 56.09 | 55.89 | 56.51 | 66.75 | 54.74 | $\mathbf{77.23}$
NMI | 35.11 | 26.12 | 29.44 | 30.51 | 27.94 | 26.04 | 30.36 | 39.30 | 26.81 | $\mathbf{47.74}$
PUR | 78.76 | 74.97 | 78.97 | $\mathbf{80.97}$ | 80.46 | 75.37 | 79.40 | 77.21 | 74.82 | 77.69
40% | ACC | 50.96 | 48.91 | 52.17 | 55.06 | 53.73 | 50.26 | 57.72 | 54.49 | 56.09 | $\mathbf{77.18}$
NMI | 21.12 | 16.63 | 26.58 | 25.21 | 24.70 | 20.08 | 28.95 | 26.09 | 27.39 | $\mathbf{47.26}$
PUR | 72.09 | 70.82 | 78.57 | 77.85 | 78.70 | 72.87 | $\mathbf{78.96}$ | 77.30 | 75.89 | 77.21
50% | ACC | 55.84 | 52.30 | 55.16 | 52.43 | 53.12 | 57.10 | 60.13 | 49.54 | 51.08 | $\mathbf{75.53}$
NMI | 26.23 | 19.95 | 26.82 | 25.09 | 25.96 | 26.13 | 33.13 | 19.71 | 19.95 | $\mathbf{44.92}$
PUR | 75.20 | 74.20 | 76.50 | 77.22 | 77.54 | 72.47 | $\mathbf{77.59}$ | 70.13 | 71.52 | 75.71
60% | ACC | 48.79 | 47.71 | 51.43 | 53.42 | 53.53 | 45.06 | 68.67 | 46.71 | 52.87 | $\mathbf{72.89}$
NMI | 14.51 | 12.34 | 21.21 | 25.61 | 25.61 | 11.27 | 37.41 | 14.16 | 16.12 | $\mathbf{42.53}$
PUR | 70.50 | 69.94 | 75.01 | 79.22 | 78.80 | 67.96 | $\mathbf{80.21}$ | 70.25 | 69.90 | 73.3
70% | ACC | 43.62 | 44.04 | 51.63 | 50.57 | 55.51 | 43.08 | 61.54 | 44.53 | 48.94 | $\mathbf{74.18}$
NMI | 7.20 | 7.43 | 22.95 | 22.88 | 25.36 | 6.43 | 31.32 | 8.17 | 13.76 | $\mathbf{36.19}$
PUR | 67.31 | 69.06 | 76.41 | 75.53 | $\mathbf{78.01}$ | 68.17 | 75.86 | 68.23 | 67.65 | 70.01

TABLE XI: The performance comparison (mean) of different algorithms on COIL20.

COIL20
---
Method | Shallow | Deep
Missing Rate | Metrics | MF | ZF | LRC | MNC | FSGR | GAIN | VAEAC | MIWAE | MDIOT | Ours
10% | ACC | 58.03 | 57.26 | 56.25 | 58.10 | 59.19 | 58.13 | 57.99 | 56.60 | 58.61 | $\mathbf{71.58}$
NMI | 73.16 | 71.52 | 72.52 | 73.82 | 74.00 | 73.94 | 73.59 | 72.99 | 73.09 | $\mathbf{79.97}$
PUR | 63.01 | 62.64 | 61.12 | 63.39 | 63.27 | 62.63 | 63.14 | 61.49 | 62.88 | $\mathbf{73.96}$
20% | ACC | 58.56 | 57.21 | 58.85 | 57.21 | 55.69 | 58.30 | 55.63 | 57.28 | 59.51 | $\mathbf{71.94}$
NMI | 73.32 | 71.31 | 73.91 | 73.24 | 71.96 | 73.11 | 72.64 | 73.55 | 73.89 | $\mathbf{80.78}$
PUR | 63.03 | 62.39 | 64.06 | 62.91 | 60.38 | 62.35 | 60.44 | 62.01 | 63.99 | $\mathbf{74.93}$
30% | ACC | 57.62 | 55.13 | 60.90 | 60.09 | 59.20 | 53.03 | 59.33 | 58.15 | 57.29 | $\mathbf{71.67}$
NMI | 72.04 | 69.28 | 75.28 | 74.28 | 73.21 | 71.14 | 74.29 | 72.17 | 72.13 | $\mathbf{80.11}$
PUR | 61.65 | 59.65 | 65.51 | 64.35 | 63.16 | 58.73 | 64.44 | 62.22 | 61.91 | $\mathbf{74.24}$
40% | ACC | 55.89 | 48.82 | 60.67 | 59.42 | 57.74 | 56.25 | 59.40 | 59.33 | 57.72 | $\mathbf{61.18}$
NMI | 70.31 | 62.11 | 74.57 | 74.51 | 71.57 | 72.30 | 73.86 | 72.84 | 72.68 | $\mathbf{77.23}$
PUR | 59.60 | 50.96 | 64.13 | 63.99 | 62.29 | 61.08 | 63.77 | 63.07 | 62.33 | $\mathbf{75.21}$
50% | ACC | 57.05 | 37.79 | 60.74 | 60.23 | 56.53 | 54.84 | 57.38 | 54.98 | 57.67 | $\mathbf{64.51}$
NMI | 69.83 | 51.89 | 75.09 | 74.88 | 70.84 | 71.07 | 72.73 | 67.72 | 73.18 | $\mathbf{76.53}$
PUR | 60.40 | 39.17 | 65.14 | 64.54 | 60.88 | 59.29 | 62.54 | 57.08 | 62.88 | $\mathbf{67.36}$
60% | ACC | 52.08 | 22.10 | 60.78 | 64.35 | 57.03 | 52.00 | 58.16 | 56.32 | 58.83 | $\mathbf{63.19}$
NMI | 65.95 | 35.31 | 74.72 | 76.08 | 69.71 | 65.28 | 72.62 | 69.58 | 73.69 | $\mathbf{76.14}$
PUR | 55.22 | 22.61 | 65.22 | $\mathbf{68.43}$ | 61.02 | 54.99 | 62.56 | 58.45 | 63.40 | 67.36
70% | ACC | 43.41 | 15.71 | 58.33 | $\mathbf{62.19}$ | 50.13 | 44.51 | 57.51 | 53.50 | 59.52 | 60.76
NMI | 57.13 | 24.58 | 72.32 | $\mathbf{74.37}$ | 61.95 | 53.63 | 71.95 | 68.26 | 73.98 | 71.21
PUR | 44.79 | 16.19 | 63.00 | $\mathbf{66.48}$ | 52.59 | 45.91 | 61.74 | 56.11 | 64.49 | 62.99

TABLE XII: The performance comparison (mean) of different algorithms on
Letter.

Letter
---
Method | Shallow | Deep
Missing Rate | Metrics | MF | ZF | LRC | MNC | FSGR | GAIN | VAEAC | MIWAE | MDIOT | Ours
10% | ACC | 36.72 | 36.38 | 37.38 | 36.91 | 36.73 | 37.24 | 36.99 | 36.56 | 36.39 | $\mathbf{51.12}$
NMI | 39.47 | 39.00 | 39.59 | 39.53 | 39.56 | 39.51 | 39.61 | 38.86 | 39.18 | $\mathbf{54.82}$
PUR | 39.27 | 39.00 | 39.91 | 39.68 | 39.08 | 39.68 | 39.55 | 38.69 | 39.05 | $\mathbf{52.95}$
20% | ACC | 36.01 | 36.19 | 36.16 | 35.29 | 36.98 | 36.91 | 36.77 | 33.91 | 37.26 | $\mathbf{48.5}$
NMI | 38.95 | 38.52 | 39.24 | 38.10 | 39.49 | 39.24 | 39.54 | 36.73 | 39.01 | $\mathbf{54.83}$
PUR | 38.59 | 38.62 | 38.89 | 37.74 | 39.60 | 39.18 | 39.26 | 36.22 | 39.26 | $\mathbf{51.26}$
30% | ACC | 35.96 | 35.94 | 37.27 | 34.99 | 36.77 | 36.59 | 36.87 | 30.18 | 36.01 | $\mathbf{52.14}$
NMI | 38.74 | 37.91 | 39.66 | 37.81 | 39.71 | 39.17 | 39.45 | 33.16 | 38.63 | $\mathbf{56.03}$
PUR | 38.62 | 38.19 | 39.90 | 37.53 | 39.43 | 39.18 | 39.54 | 32.16 | 38.57 | $\mathbf{54.68}$
40% | ACC | 35.65 | 35.13 | 36.48 | 34.82 | 37.00 | 36.69 | 36.49 | 26.83 | 35.86 | $\mathbf{49.93}$
NMI | 38.18 | 36.88 | 39.07 | 37.06 | 39.46 | 38.87 | 38.94 | 29.64 | 38.01 | $\mathbf{55.26}$
PUR | 38.12 | 37.54 | 39.11 | 37.22 | 39.53 | 39.20 | 39.04 | 28.12 | 38.22 | $\mathbf{52.65}$
50% | ACC | 35.67 | 33.83 | 36.98 | 35.08 | 37.48 | 36.03 | 36.51 | 23.28 | 35.11 | $\mathbf{48.32}$
NMI | 38.02 | 34.82 | 39.34 | 35.51 | 39.50 | 38.10 | 38.90 | 26.34 | 37.59 | $\mathbf{53.05}$
PUR | 37.98 | 35.54 | 39.48 | 36.50 | 39.66 | 38.45 | 38.89 | 24.55 | 37.41 | $\mathbf{50.54}$
60% | ACC | 35.38 | 31.15 | 36.99 | 31.82 | 37.51 | 34.57 | 35.75 | 22.51 | 35.25 | $\mathbf{43.47}$
NMI | 36.41 | 30.72 | 38.87 | 31.17 | 39.17 | 36.70 | 38.22 | 23.98 | 36.66 | $\mathbf{49.02}$
PUR | 37.37 | 32.00 | 39.24 | 32.49 | 39.83 | 37.01 | 38.47 | 23.79 | 37.20 | $\mathbf{45.88}$
70% | ACC | 32.46 | 25.04 | $\mathbf{37.18}$ | 27.34 | 37.11 | 32.27 | 35.31 | 20.14 | 33.07 | 36.58
NMI | 33.19 | 24.47 | 38.36 | 26.32 | 38.59 | 34.35 | 36.93 | 22.03 | 33.85 | $\mathbf{41.62}$
PUR | 34.15 | 25.45 | 39.54 | 27.76 | $\mathbf{39.38}$ | 34.99 | 37.62 | 20.80 | 34.46 | 38.97


# The Alexander method for infinite-type surfaces

Jesús Hernández Hernández, Israel Morales, Ferrán Valdez

###### Abstract

We prove that for any infinite-type orientable surface $S$ there exists a
collection of essential curves $\Gamma$ in $S$ such that any homeomorphism
that preserves the isotopy classes of the elements of $\Gamma$ is isotopic to
the identity. The collection $\Gamma$ is countable and has infinite complement
in $\mathcal{C}(S)$, the curve complex of $S$. As a consequence we obtain that
the natural action of the extended mapping class group of $S$ on
$\mathcal{C}(S)$ is faithful.

##  1 Introduction

Let $S$ be an orientable surface and ${\rm MCG^{*}}(S)$ the _extended mapping
class group_ of $S$, that is the group of _all_ homeomorphisms of $S$ modulo
isotopy. There is a natural non-trivial action of ${\rm MCG^{*}}(S)$ on
$\mathcal{C}(S)$, the curve complex of $S$. This is the abstract simplicial
complex whose vertices are the (isotopy classes of) essential curves in S, and
whose simplices are multicurves of finite cardinality, see [5] for a detailed
discussion. It is well-known that this action is faithful whenever $S$ has
finitely generated fundamental group (except for the closed surface of genus
2), see [7], [9], [8]. The proof of this fact follows from the so-called
_Alexander method_ (see [5], §2.3 for details). Roughly speaking, this
“method” states that the isotopy class of a homeomorphism of $S$ is often
determined by its action on a well-chosen collection of curves and arcs in S.

The main purpose of this article is to extend the Alexander method for _all_
infinite-type surfaces, _i.e._ when $\pi_{1}(S)$ _is not_ finitely generated.
More precisely, we prove:

######  Theorem 1.1.

Let $S$ be an orientable surface of infinite topological type, with possibly
non-empty boundary. There exists a collection of essential arcs and simple
closed curves $\Gamma$ on $S$ such that any orientation-preserving
homeomorphism fixing pointwise the boundary of $S$ that preserves the isotopy
classes of the elements of $\Gamma$, is isotopic to the identity.

As a matter of fact, we give a recipe to construct the collection $\Gamma$ in
§3, from which it is easy to see that $\Gamma$ is a “small” countable
collection of curves (_i.e._ $\mathcal{C}^{0}(S)\setminus\Gamma$ is infinite).
Moreover, we prove that there are uncountably many different examples of this
kind of collections, see lemma 3.8. Recall that any homeomorphism of $S$ that
reverses orientation does not act trivially on $\mathcal{C}(S)$, see [10]. As
an immediate consequence of Theorem 1.1 we obtain:

######  Corollary 1.2.

Let $S$ be an orientable surface of infinite topological type with empty
boundary. Then the natural action of the extended mapping class group of $S$
on the curve complex $\mathcal{C}(S)$ is faithful.

It is important to remark that the preceding corollary was already known for
infinite type surfaces $S$ for which all ends111See §2 below for details on
the space of ends of a surface. carry (infinite) genus, see [6]. However, the
methods used in that paper to prove that a homeomorphism $h\in{\rm Homeo(S)}$
is isotopic to the identity require that $h$ fixes _all_ isotopy classes in
$\mathcal{C}(S)$. Therefore the results we present here are both an extension
and a refinement of the results obtained in [_Ibid._]. Moreover, corollary 1.2
will be used in a second paper222We decided to write a second paper since the
methods used to prove that any simplicial automorphism of $\mathcal{C}(S)$ is
geometric are very different from the ones we present here.  to prove that the
group of simplicial automorphisms of $\mathcal{C}(S)$ is naturally isomorphic
to ${\rm MCG^{*}}(S)$ for _any_ infinite-type surface. This result is used in
[1] to prove that every automorphism of a certain subgroup 333These are called
by the authors _asymtotically rigid mapping class groups._ of ${\rm
MCG^{*}}(S)$ is induced by a homeomorphism of $S$, when $S$ is a genus $g\geq
0$ closed surface from which a Cantor set has been removed.

Reader’s guide. In §2 we make a short discussion on infinite-type surfaces and
the generalities about curves, arcs and continuous deformations of elements in
${\rm Homeo}^{+}(S)$. The real content of the paper is found in §3 where we
prove Theorem 1.1. At the end we added an appendix to address some technical
aspects of the proofs we present in section 3.

Acknowledgements. The first author was supported during the creation of this
article by the UNAM Post-Doctoral Scholarship Program 2016 at the CCM-UNAM.
The second author was generously supported by CONACYT and CCM-UNAM. The third
author was generously supported by LAISLA and PAPIIT IN100115.

##  2 Preliminaries

Let $S$ be an orientable surface. We say $S$ is a finite-type surface if its
fundamental group is finitely generated; otherwise, we say $S$ is of infinite
type.

An infinite-type surface $S$ is determined, up to homeomorphism, by two
invariants: its genus $g(S)\in\mathbb{N}\cup\\{\infty\\}$ and a pair of nested
topological spaces $\rm Ends_{\infty}(S)\subset Ends(S)$ forming what is known
as _the space of ends_ of $S$. Roughly speaking, the space $\rm Ends(S)$
codifies the different ways in which a surface tends to infinity and $\rm
Ends_{\infty}(S)$ is the subspace formed by all those ends that carry
(infinite) genus. The spaces $\rm Ends(S)_{\infty}\subset Ends(S)$ are
homemorphic to a pair of nested closed subsets of the standard triadic Cantor
set. Conversely, every infinite-type topological surface can be constructed
from such a pair $X_{\infty}\subset X$ as follows: think of $X_{\infty}\subset
X$ as living in the unit interval used to construct the standard triadic
Cantor set. Think of the unit interval as a subset of the sphere
$\mathbb{S}^{2}$ and imagine that this sphere lives in $\mathbb{R}^{3}$. Push
points in $X$ infinitely away from the origin. The resulting surface
$S^{\prime}$ has a space of ends homeomorphic to $X$. Now, for each $x\in
X_{\infty}\subset X$ add a divergent sequence of handles to $S^{\prime}$ that
accumulates to $x$. This produces a surface $S$ whose space of ends is
homeomorphic to $X_{\infty}\subset X$.

We refer the reader to the work of Ian Richards [12] for a more detailed
discussion on the topological classification of infinite-type surfaces. We do
not discuss these results further on since we do not need them for the proof
of our results.

If $S$ is a finite-type surface of genus $g$, $n$ punctures and $b$ boundary
components, we denote by $\kappa(S)=3g-3+n+b$ the complexity of $S$. If $S$ is
an infinite-type surface, we define its complexity as infinity.
A curve on $S$ is a topological embedding $\alpha:\mathbb{S}^{1}\rightarrow
S$. We say a curve is essential if it is not isotopic to the boundary curve of
a neighbourhood of a puncture, to a point, nor to a boundary component. All
curves are considered to be essential unless otherwise specified.
An arc on $S$ is a topological embedding $\alpha:I\rightarrow S$, where $I$ is
the closed unit interval, and $\alpha(\partial I)\subset\partial S$. We
consider all isotopies between arcs to be relative to $\partial I$, _i.e._ the
isotopies are not allowed to move the endpoints. We say an arc is essential if
it is not isotopic to an arc whose image is completely contained in $\partial
S$. In this work, all arcs are considered to be essential unless otherwise
specified.
We often abuse notation and use the terms “curve” and “arc” to refer to both
the topological embeddings and the corresponding images on $S$. The context
makes clear the meaning in each case.
Let $[\alpha]$ and $[\beta]$ be two isotopy classes of essential curves or
arcs. The (geometric) intersection number of $\alpha$ and $\beta$ is defined
as follows:

$i([\alpha],[\beta])\mathrel{\mathop{:}}=\min\\{|(\gamma\cap\delta)\cap\mathrm{int}(S)|:\gamma\in[\alpha],\delta\in[\beta]\\}.$

Let $\alpha$ and $\beta$ be two essential curves or arcs on $S$, we say
$\alpha$ and $\beta$ are in minimal position if
$|(\alpha\cap\beta)\cap\mathrm{int}(S)|=i([\alpha],[\beta])$.

We denote $\rm Homeo^{+}(S;\partial S)$ the group of orientation-preserving
homeomorphisms of $S$ which fix the boundary pointwise.

We conclude this section with a remark that is be fundamental for the rest of
the article:

######  Remark 2.1 (Equivalence between homotopy and isotopy).

Let $S$ be an infinite-type surface and $f,g\in\rm Homeo(S;\partial S)$. Then
$f$ is homotopic to $g$ relative to the boundary if and only if $f$ is
isotopic to $g$ relative to the boundary.

To simplify the exposition, henceforth we suppose that all homotopies and
isotopies in this text are relative to the boundary.

For surfaces of finite-topological type the result is well-known, see [2], [4]
and Theorem 1.12 in [5]. For infinite-type surfaces, the results follow from
the work of Cantwell and Conlon, see [3].

##  3 Alexander method

We begin this section by introducing the notion of an _Alexander system_ and
then some technical lemmas. We then introduce the notion of a _stable_
Alexander system. These are collections of arcs and curves such that any
$f\in{\rm Homeo^{+}(S;\partial S)}$ that preserves the isotopy classes of
their elements is isotopic to the identity. In the last part of this section
we prove theorem 1.1, which states that stable Alexander systems exist for
infinite type surfaces. We finish the section by showing that for any
infinite-type surface $S$ there are actually _uncountably_ many different
stable Alexander systems in $S$.

######  Definition 3.1.

Let $\Gamma=\\{\gamma_{i}\\}_{i\in I}$ be a collection of essential curves and
arcs on $S$. We say $\Gamma$ is an Alexander system if it satisfies the
following conditions:

  1. 1.

The elements in $\Gamma$ are in pairwise minimal position.

  2. 2.

For $\gamma_{i},\gamma_{j}\in\Gamma$ with $i\neq j$, we have that $\gamma_{i}$
is not isotopic to $\gamma_{j}$.

  3. 3.

For all distinct $i,j,k\in I$, at least one of the following sets is empty:
$\gamma_{i}\cap\gamma_{j}$, $\gamma_{j}\cap\gamma_{k}$,
$\gamma_{k}\cap\gamma_{i}$.

Note that any subset of an Alexander system is also an Alexander system and
that we do not require the surface $S$ in the preceding definition to be of
infinite type. The following result is the infinite-type surface version of
Proposition 2.8 in [5], to the point that its proof is also completely
analogous.

######  Lemma 3.2.

Let $S$ be a connected orientable surface of infinite topological type with
possibly nonempty boundary, and $\Gamma=\\{\gamma_{1},\ldots,\gamma_{k}\\}$ be
a finite Alexander system on $S$. If $h\in\mathrm{Homeo}^{+}(S,\partial S)$ is
such that for all $i=1,\ldots,k$ we have that $h(\gamma_{i})$ is isotopic to
$\gamma_{i}$, then there exists $f\in\mathrm{Homeo}^{+}(S,\partial S)$
isotopic to the identity on $S$ relative to $\partial S$, such that
$f|_{\Gamma}=h|_{\Gamma}$.

######  Remark 3.3.

Note that if $S$ is not connected and $\Gamma$ has only finitely many elements
on each connected component of $S$, we can apply either Proposition 2.8 in [5]
or Lemma 3.2 above to each connected component.

Both Lemma 3.2 and Remark 3.3 are used repeatedly in the proofs that we
present.

One of the ideas in these proofs is to use convenient families of subsurfaces
that exhaust a fixed infinite-type surface. We introduce these below.

######  Definition 3.4.

Let $\\{S_{i}\\}$ be an (set-theoretical) increasing sequence of subsurfaces
of $S$. We say $\\{S_{i}\\}$ is a principal exhaustion of $S$ if
$S=\displaystyle\bigcup_{i\geq 1}S_{i}$ and for all $i\geq 1$ it satisfies the
following conditions:

  1. 1.

$S_{i}$ is a surface of finite topological type,

  2. 2.

$S_{i}$ is contained in the interior of $S_{i+1}$,

  3. 3.

$\partial S_{i}-\partial S$ is the finite union of pairwise disjoint essential
curves on $S$, and

  4. 4.

each connected component of $S_{i+1}\backslash S_{i}$ has complexity at least
6.

Note that these exhaustions always exist in any infinite-type surface. See
Figures 1 and 2 for examples.

Figure 1: An example of a principal exhaustion for the “Loch Ness Monster”,
i.e. the surface of infinite genus and one end.

Figure 2: On the left, an example of a principal exhaustion for the surface of
genus $4$ minus a Cantor set. On the right, an example of a principal
exhaustion for a surface of infinite genus, and whose space of ends that carry
genus is a Cantor set.

Let $\\{S_{i}\\}$ be a principal exhaustion of $S$. For each $i\geq 1$, we
denote by $B_{i}$ the set of the boundary curves of $S_{i}$ that are essential
curves on $S$. Note that for $i\neq j$ we have that $B_{i}\cap
B_{j}=\varnothing$. We define the boundaries of $\\{S_{i}\\}$, denoted by $B$,
as $\displaystyle B\mathrel{\mathop{:}}=\bigcup_{i\geq 1}B_{i}$.
The first step of the proof of Theorem 1.1 is the following.

######  Lemma 3.5.

Let $S$ be an orientable surface of infinite topological type, $\\{S_{i}\\}$ a
principal exhaustion of $S$, and $B$ be the boundaries of $\\{S_{i}\\}$. If
$h\in\mathrm{Homeo}^{+}(S;\partial S)$ is such that $h(\gamma)$ is isotopic to
$\gamma$ for every $\gamma\in B$, then $h$ is isotopic to a homeomorphism
$g\in\mathrm{Homeo}^{+}(S;\partial S)$ for which
$g|_{B}=\mathrm{id}_{S}|_{B}$.

###### Proof.

We divide the proof into two parts. In the first part we construct the
homeomorphism $g$ using Lemma 3.2 and Remark 3.3. As a consequence of the
construction we have that $g|_{B}=\mathrm{id}_{S}|_{B}$. In the second part,
using classical results from obstruction theory (see the appendix and
references therein), we show that $h$ and $g$ are isotopic.
First part: the construction of $g$. Remark that for each integer $i\geq 1$,
$B_{i}$ is a finite Alexander system, both on $S$ and on $S\backslash S_{k}$
for each $k<i$. Since both $h$ and $B_{1}$ satisfy the conditions of Lemma
3.2, there exists $f_{1}\in\mathrm{Homeo}^{+}(S;\partial S)$ isotopic to
$\mathrm{id}_{S}$ such that $f|_{B_{1}}=h|_{B_{1}}$. Let
$g_{1}\mathrel{\mathop{:}}=f_{1}^{-1}\circ h$. Then
$g_{1}|_{B_{1}}=\mathrm{id}_{S}|_{B_{1}}$. As a consequence, we have that
$g_{1}(S_{1})=S_{1}$, and $g_{1}$ also fixes the isotopy classes of $B$. This
implies that both the restriction to $S\backslash\mathrm{int}(S_{1})$ of
$g_{1}$, and $B_{2}$ satisfy the conditions of Remark 3.3 on
$S\backslash\mathrm{int}(S_{1})$.
Let
$\widetilde{g}_{1}\mathrel{\mathop{:}}=g_{1}|_{S\backslash\mathrm{int}(S_{1})}$,
then by Remark 3.3, there exists
$\widetilde{f}_{2}\in\mathrm{Homeo}^{+}(S\backslash\mathrm{int}(S_{1});\partial
S)$ isotopic to $\mathrm{id}_{S\backslash\mathrm{int}(S_{1})}$ relative to
$\partial(S\backslash\mathrm{int}(S_{1}))$ such that
$\widetilde{f}_{2}|_{B_{2}}=\widetilde{g}_{1}|_{B_{2}}$. Thus, we define the
following:

$f_{2}(s)=\left\\{\begin{tabular}[]{ll}$s$&if $s\in S_{1}$,\\\
$\widetilde{f}_{2}(s)$&otherwise.\end{tabular}\right.$

Note that $f_{2}$ is also isotopic to $\mathrm{id}_{S}$. Then, we define
$g_{2}\mathrel{\mathop{:}}=f_{2}^{-1}\circ
g_{1}\in\mathrm{Homeo}^{+}(S;\partial S)$.
By construction, $g_{2}$ satisfies that
$g_{2}|_{B_{2}}=\mathrm{id}_{S}|_{B_{2}}$, and
$g_{2}|_{S_{1}}=g_{1}|_{S_{1}}$. Moreover, $g_{2}$ preserves the connected
components of $S\backslash S_{2}$, and $g_{2}$ is isotopic to $g_{1}$.
In this manner, we inductively define for each $n>2$ a homeomorphism
$g_{n}\in\mathrm{Homeo}^{+}(S;\partial S)$ such that:

  1. 1.

$g_{n}$ is isotopic to $g_{n-1}$,

  2. 2.

$g_{n}|_{B_{n}}=\mathrm{id}_{S}|_{B_{n}}$,

  3. 3.

for all $m<n$, we have that $g_{n}|_{S_{m}}=g_{m}|_{S_{m}}$.

We define the following map:

$g:$ | $S$ | $\rightarrow$ | $S$
---|---|---|---
| $s$ | $\mapsto$ |  $g_{n}(s)$ if $s\in S_{n}$.

This map is well-defined since all $g_{n}$ satisfy (3) above. Also, by
construction we have that $g\in\mathrm{Homeo}^{+}(S;\partial S)$ and
$g|_{B}=\mathrm{id}_{S}|_{B}$.
Second part: the map $g$ is isotopic to $h$. We claim that for every $n\geq 1$
the map $g_{n}$ is homotopic to $g_{n+1}$ relative to $S_{n}$, that is, there
exist a homotopy $H_{n}:S\times I\rightarrow S$ satisfying:

  * (a)

$H_{n}|_{S\times\\{0\\}}=g_{n}$,

  * (b)

$H_{n}|_{S\times\\{1\\}}=g_{n+1}$ and

  * (c)

$H_{n}(x,t)=g_{n}(x)=g_{n+1}(x)\hskip 5.69054pt\text{for every $t\in I$ and
$x\in S_{n}$}$.

We postpone the proof of this claim to the appendix.

For each $n\geq 1$, we define the homeomorphism

$\zeta_{n}$: | $\left[\frac{n-1}{n},\frac{n}{n+1}\right]$ | $\rightarrow$ | $\left[0,1\right]$
---|---|---|---
| $t$ | $\mapsto$ |  $n\left(n+1\right)\left(t-\frac{n-1}{n}\right)$.

By conditions (a) and (b) over the family of homotopies $\\{H_{n}\\}$ the map
$H:S\times\left[0,1\right]\to S$ given by

$H(s,t)=\left\\{\begin{tabular}[]{ll}$H_{n}\left(s,\zeta_{n}\left(t\right)\right)$&if
$t\in\left[\frac{n-1}{n},\frac{n}{n+1}\right]$,\\\ $g(s)$&if
$t=1$.\end{tabular}\right.$

is well-defined. We claim that $H$ is a homotopy between $g_{1}$ and $g$.
First, we note that for all $s\in S$,
$H(s,0)=H_{1}(s,\zeta_{1}(0))=H_{1}(s,0)=g_{1}(s)$ and $H(s,1)=g(s)$. It
remains to prove that $H$ is continuous. If $(s,t)\in S\times[0,1)$, then by
definition, for some $n\geq 1$, $H$ and $H_{n}$ coincide in some open
neighborhood of $(s,t)$. By the continuity of $H_{n}$, $H$ is continuous at
$(s,t)$. Now, let $(s,1)\in S\times\\{1\\}$. Then there exists $n\geq 1$ such
that $s\in\mathrm{int}(S_{m})$ for all $m\geq n$. Choose $U_{s}$ an open
neighborhood of $s$ properly contained in $\mathrm{int}(S_{m})$. By condition
(c), for all $m\geq n$ and $(s^{\prime},t^{\prime})\in
U_{s}\times\left(\frac{n-1}{n},1\right]$, we have that
$H(s^{\prime},t^{\prime})=H_{m}(s^{\prime},t^{\prime})=g_{m}(s^{\prime})=g(s^{\prime})$.
Thus, $H$ coincides with $g$ in some open neighborhood of $(s,1)$ and we
deduce that $H$ is continuous at $(s,1)$.

Finally, since $h$ is isotopic to $g_{1}$, we obtain that $h$ is homotopic to
$g$. From Remark 2.1 we conclude that $h$ is isotopic to $g$, as desired. ∎

Let $N$ be a subsurface of $S$, and $A$ be a collection of curves and arcs on
$S$ whose image is contained in $N$. We say $A$ _fills_ $N$ if
$\mathrm{int}(N\backslash A)$ is the disjoint union of open discs and once-
punctured open discs.

######  Definition 3.6.

Let $\Gamma$ be an Alexander system on $S$. We say $\Gamma$ is a stable
Alexander system if $\Gamma$ fills $S$ and every
$f\in\mathrm{Homeo}^{+}(S;\partial S)$ that preserves the isotopy classes of
elements in $\Gamma$ is isotopic relative to the boundary, to the identity.

######  Remark 3.7.

In the preceding definition we do not require $S$ to be of infinite type. Also
note that not every Alexander system that fills $S$ is stable. See Figures 3
and 4 for a counterexamples and an example of stable Alexander systems on
finite-type surfaces respectively.

Figure 3: An Alexander system that fills $S$ but is not stable.

Figure 4: On the left, an example of a stable Alexander system for a surface
of genus $4$, with $4$ punctures and $3$ boundary components. On the right, an
example of a stable Alexander system for a surface of genus $0$ with $9$
boundary components.

###### Proof of Theorem 1.1.

First we construct an Alexander system $\Gamma$ that fills $S$ and then we
show that this system is stable.

Let $\\{S_{n}\\}$ be a principal exhaustion of $S$, and $B$ be the boundaries
of $\\{S_{n}\\}$. For each $n\geq 1$, choose a finite stable Alexander system
$C_{n}$ for $\mathrm{int}(S_{n}\backslash S_{n-1})$ (with $S_{0}=\varnothing$)
and let $C$ be the union of the collection of $\\{C_{n}\\}$. See figure 4 for
examples of stable Alexander systems.

Note that $B\cup C$ is not a stable Alexander system. There are homeomorphism
which are not homotopic to the identity but that fix all the (isotopy classes
of) elements in this collection, _e.g._ any representative of a Dehn-twists
along a curve in $B$. As we prove below, these are the only homeomorphisms
showing this behaviour.

Let $B^{*}$ be a collection of curves, and $f:B\rightarrow B^{*}$ a bijection
satisfying that for all $\gamma\in B$ and all $\delta\in
B\backslash\\{\gamma\\}$, $i([\gamma],[f(\gamma)])\neq 0$ and
$i([\delta],[f(\gamma)])=0$. Remark that we can choose $B^{*}$ so that
$\Gamma:=B\cup B^{*}\cup C$ is an Alexander system. Figure 5 illustrates how
to choose the collection $B^{*}$. We finish this proof by showing that
$\Gamma$ is a _stable_ Alexander system.

Figure 5: On the left, an example of $\Gamma$ for the surface of genus $4$
minus a Cantor set. On the right, an example of $\Gamma$ for a surface of
infinite genus, and whose space of ends that carry genus is a Cantor set.

Let $h\in\mathrm{Homeo}^{+}(S;\partial S)$ be such that $h$ fixes the isotopy
class of every curve in $\Gamma$. We claim that $h$ is isotopic to the
identity on $S$.

First, since $h$ fixes the isotopy class of elements in $B\subset\Gamma$, by
the Lemma 3.5, $h$ is isotopic to some $g\in\mathrm{Homeo}^{+}(S;\partial S)$
such that $g|_{B}=\mathrm{id}_{S}|_{B}$. In particular, $g$ also fixes all the
isotopy classes of elements in $\Gamma$.

Observe that for $n\geq 1$, $S_{n}\backslash\mathrm{int}(S_{n-1})$ is a
disjoint union of a finite number of finite-type surfaces with boundary, and
by construction $\left(S_{n}\backslash\mathrm{int}(S_{n-1})\right)\cap\Gamma$
is a finite stable Alexander system on $S_{n}\backslash\mathrm{int}(S_{n-1})$.
Then by definition of stable Alexander systems, the restriction of $g$ to
$S_{n}\backslash\mathrm{int}(S_{n-1})$ is isotopic to the identity on
$S_{n}\backslash\mathrm{int}(S_{n-1})$ relative to the boundary
$\partial(S_{n}\backslash\mathrm{int}(S_{n-1}))$. Given that
$g|_{B}=\mathrm{id}_{S}|_{B}$, the homeomorphism $g$ is isotopic to the
identity on $S$. ∎

######  Lemma 3.8.

Let $S$ be an orientable connected surface of infinite topological. Then there
exists uncountably many isotopy classes of stable Alexander systems on $S$.

###### Proof.

Fix $\\{S_{i}\\}$ a principal exhaustion of $S$, and let $\Gamma=B\cup C\cup
B^{*}$ be as in the proof of Theorem 1.1. For each $i\geq 1$ let
$\varphi_{i}\in\mathrm{Homeo}^{+}(\mathrm{int}(S_{i}\backslash
S_{i-1});\partial S)$ (with $S_{0}=\varnothing$) be a map that preserves each
connected component of $\mathrm{int}(S_{i}\backslash S_{i-1})$ and whose
restriction to each connected component is a pseudo-Anosov map.

Let $\mathcal{A}$ denote the set of all isotopy classes of stable Alexander
systems of $S$. Note that $\mathcal{A}$ is invariant under the action of
$\mathrm{Homeo}^{+}(S;\partial S)$; hence we can define the following map:

$\Phi:$ | $\\{0,1\\}^{\mathbb{Z}^{+}}$ | $\rightarrow$ | $\mathcal{A}$
---|---|---|---
| $(\epsilon_{i})_{i\geq 1}$ | $\mapsto$ |  $\displaystyle\left[B\cup\left(\bigcup_{i\geq 1}\varphi_{i}^{\epsilon_{i}}(C_{i})\right)\cup\left(\bigcup_{i\geq 1}\varphi_{i}^{\epsilon_{i}}(f(B_{i}))\right)\right]$;

where $f$ is the bijection between $B$ and $B^{*}$. Since each $\varphi_{i}$
is a pseudo-Anosov map, the map $\Phi$ is injective. Thus, $\mathcal{A}$ is an
infinitely uncountable set. ∎

##  Appendix A Appendix.

In this appendix we explain how classical results of obstruction theory are
used to assure the existence of the homotopies $H_{n}$ used in the proof of
lemma 3.5. Our discussion is based on the work of P. Olum [11] and adapted to
the context of orientable surfaces with boundary.

_The extension problem_. Let $S$ be an orientable surface444$S$ is not
necessarily compact, nor necessarily of finite-type and its boundary might be
non-empty. and $S^{\prime}\subset S$ a subsurface. Consider two continuous
functions $f_{0},f_{1}:S\to S$ such that $f_{0}(s)=f_{1}(s)$ for all $s\in
S^{\prime}$. Following [11], let $\overline{S}_{01}^{\prime}$ be the subset of
$S\times I$ formed by $S\times{0}\cup S^{\prime}\times I\cup S\times\\{1\\}$.
Define $F:\overline{S}_{01}^{\prime}\to S$ by:

$F(s,t)=\begin{cases}f_{0}(s)\hskip 8.53581pt\text{for $(s,t)\in
S\times\\{0\\}\cup S^{\prime}\times I$}\\\ f_{1}(s)\hskip 8.53581pt\text{for
$(s,t)\in S\times\\{1\\}$}\end{cases}$ (1)

We say that _$f_{0}$ is homotopic to $f_{1}$ relative to $S^{\prime}$_ if $F$
defined above has a continuos extension to $S\times I$. The following result
is an adaptation of theorem 25.2 in [_Ibid._] to the context of orientable
surfaces with boundary; it gives criteria to determine when $f_{0}$ and
$f_{1}$ are homotopic relative to $S^{\prime}$. We state the result first,
then explain its content and finally show how to apply to the proof of lemma
3.5.

######  Theorem A.1.

Let $f_{0},f_{1}:S\to S$ be two continuous functions such that
$f_{0}(s)=f_{1}(s)$ for all $s\in S^{\prime}$. Let $s_{0}\in S^{\prime}$ and
$\theta_{i}:\pi_{1}(S,s_{0})\to\pi_{1}(S,f_{i}(s_{0}))$ be the homomorphism
induced by $f_{i}$, for $i=1,2$. For $k\in\\{0,1,2\\}$ fixed the following
statements are equivalent:

  1. 1.

(For $k=2$) $\mathbf{O}^{k}(f_{0},f_{1})\hskip 2.84526pt\rm rel.\hskip
2.84526ptS^{\prime}$ is non-void and contains the zero element.

  2. 2.

(For $1\leq k$) $f_{0}\simeq f_{1}\hskip 2.84526pt\text{\rm dim $k$ (rel
$S^{\prime}$)}$ .

  3. 3.

(For $1\leq k$) $\mathbf{O}^{k+1}(f_{0},f_{1})\hskip 2.84526pt\rm rel.\hskip
2.84526ptS^{\prime}$ is non-void.

  4. 4.

The homomorphism $\theta_{0}$ and $\theta_{1}$ induced by $f_{0}$ and $f_{1}$
are equal.

We now explain the content of this theorem. Let $\tau$ be a triangulation of
$S$ and $\tau^{k}$ its $k$-skeleton (in particular $\tau^{2}=S$). Two
functions $f_{0}$ and $f_{1}$ satisfying the hypothesis of the preceding
theorem are _homotopic in dimension $k$ relative to $S^{\prime}$_, written
$f_{0}\simeq f_{1}\hskip 2.84526pt\text{\rm dim $k$ (rel $S^{\prime}$)}$, if
$f_{0}$ restricted to $S^{\prime}\cup\tau^{k}$ is homotopic to $f_{1}$
restricted to $S^{\prime}\cup\tau^{k}$ relative to $S^{\prime}$. This is
precisely the content of point (2) above. In points (1) and (3) appears
$\mathbf{O}^{k}(f_{0},f_{1})\hskip 2.84526pt\rm rel.\hskip
2.84526ptS^{\prime}$, the _$k^{th}$ obstruction to a homotopy of $f_{0}$ to
$f_{1}$ relative to $S^{\prime}$_. This is a subset of the cohomology group
$H^{k}(S,S^{\prime},\theta^{*}_{0}\pi_{n})$. Here $\theta^{*}_{0}\pi_{k}$ is
the system of (twisted) local groups $\theta^{*}_{0}\pi_{k}(S,s_{0})$, where
$\pi_{k}(S,s_{0})$ is the $k^{th}$-homotopy group of $S$ with based at
$s_{0}$. The definition of both the obstruction and the cohomology groups is
well explained in [_Ibid._], but as we will see we do not need them because in
our context all these objects are trivial.

_Constructing the homotopies $H_{n}$_. Recall from the proof of lemma 3.5 that
for each $n\in\mathbb{N}$ we have two isotopic maps $g_{n},g_{n+1}\in{\rm
Homeo}^{+}(S;\partial S)$ which coincide in $S_{n}\subset S$. Since the maps
are isotopic, the isomorphisms that they induce in a fundamental group of $S$
with basepoint in $S_{n}$ are equal. In other words, these maps satisfy (4) in
theorem A.1.

By (3) above we have that $\mathbf{O}^{2}(f_{0},f_{1})\hskip 2.84526pt\rm
rel.\hskip 2.84526ptS^{\prime}$ is non-void. Since $S$ is not a sphere, the
cohomology groups $H^{2}(S,S_{n},\theta_{0}^{*}\pi_{n})$ are trivial because
all local coefficients $\pi_{2}(S,s_{0})$ are trivial. Therefore,
$\mathbf{O}^{2}(f_{0},f_{1})$ only contains the zero element, satisfying thus
(1) for $k=2$. In particular, by (2) above we can conclude that $g_{n}$ and
$g_{n+1}$ are homotopic in dimension 2 relative to $S^{\prime}$, which is
precisely what we wanted.

## References

  * [1] J. Aramayona and L. Funar. Asymptotic mapping class groups of closed surfaces punctured along Cantor sets. arXiv:1701.08132
  * [2] R. Baer. Isotopien von Kurven auf orientierbaren, geshlossenen Fächen. Journal für die Reine und Angewandte Mathematik. 159, p.p. 101–116 (1928)
  * [3] J. Cantwell, L. Conlon. Hyperbolic geometry and homotopic homeomorphisms of surfaces. Geom. Dedicata, vol. 177, no. 1, p.p. 27-42. (2015).
  * [4] D.B.A. Epstein. Curves on 2-manifolds and isotopies. Acta Math. 115, p.p. 83–107 (1966)
  * [5] B. Farb, D. Margalit. A primer on mapping class groups. Princeton Mathematical Series, Princeton University Press. (2011).
  * [6] J. Hernández and F. Valdez. Automorphism groups of simplicial complexes of infinite-type surfaces. Publ. Mat. 61 (2017), no. 1, 51–82.
  * [7] N. Ivanov. Automorphism of complexes of curves and of Teichmüller spaces. Internat. Math. Res. Notices 1997, no. 14, 651–666.
  * [8] M. Korkmaz. Automorphisms of complexes of curves on punctured spheres and on punctured tori. Topology Appl. 95 (1999), no. 2, 85–111.
  * [9] F. Luo, Automorphisms of the complex of curves. Topology 39 (2000), no. 2, 283–298.
  * [10] J. McCarthy, A. Papadopoulos. Simplicial actions of mapping class groups. Handbook of Teichmüller theory. Volume III, IRMA Lect. Math. Theor. Phys., Vol 17, Eur. Math. Soc., Zürich, 2012, 297–423.
  * [11] P. Olum. Obstructions to extensions and homotopies. Annals of Mathematics, vol. 52, no. 1, p.p. 1-50 (1950)
  * [12] I. Richards. On the classification of noncompact surfaces. Trans. Amer. Math. Soc. 106 259–269. (1963)