#  MAESTRO: Matched Speech Text Representations through Modality Matching

###### Abstract

We present Maestro, a self-supervised training method to unify representations
learnt from speech and text modalities. Self-supervised learning from speech
signals aims to learn the latent structure inherent in the signal, while self-
supervised learning from text attempts to capture lexical information.
Learning aligned representations from unpaired speech and text sequences is a
challenging task. Previous work either implicitly enforced the representations
learnt from these two modalities to be aligned in the latent space through
multi-tasking and parameter sharing or explicitly through conversion of
modalities via speech synthesis. While the former suffers from interference
between the two modalities, the latter introduces additional complexity. In
this paper, we propose Maestro, a novel algorithm to learn unified
representations from both these modalities simultaneously that can transfer to
diverse downstream tasks such as Automated Speech Recognition (ASR) and Speech
Translation (ST). Maestro learns unified representations through sequence
alignment, duration prediction and matching embeddings in the learned space
through an aligned masked-language model loss. We establish a new state-of-
the-art (SOTA) on VoxPopuli multilingual ASR with a 8% relative reduction in
Word Error Rate (WER), multi-domain SpeechStew ASR (3.7% relative) and 21
languages to English multilingual ST on CoVoST 2 with an improvement of 2.8
BLEU averaged over 21 languages.

Index Terms: Speech Recognition, Speech Translation, Speech-Text, Self-
supervised, Representation learning

##  1 Introduction

In recent years, self-supervised learning (aka pretraining) has become an
effective and scalable paradigm to learn representations from speech and text.
These representations of language learnt without labeled data have shown
impressive performance in multiple speech and natural language processing
tasks [1, 2, 3, 4]. Auto-regressive, contrastive and multi-task learning
objectives have been proposed in the literature to pre-train such models [5,
6, 3, 7, 8, 9], followed by fine-tuning with labeled data to the task of
interest, namely, speech recognition, translation, voice conversion and spoken
language understanding. These diverse tasks require that the learned
representations capture acoustic, prosodic, speaker and linguistic
characteristics as well as the semantics of the spoken language. Thus, joint
pre-training of representations from both speech and text modalities is a
natural extension for improved generalization.

Central to the problem of jointly learning shared speech and text
representation is the challenging task of combining two very different
modalities. Recent methods proposed in literature have addressed this
challenge through two very different approaches. One approach uses multi-task
training which trains a single model with different objectives for each
modality [10, 5, 11], while another uses modality conversion where text is
directly converted to speech [12] via text-to-speech (TTS) approaches or
viceversa [13] prior to self-supervised training.

Maestro (Section 3) lies at the intersection of these two lines of work. It
retains the advantage of a common latent space and alignment between the
speech and text representations without explicitly converting text to speech
or viceversa, thereby learning a computationally efficient and aligned
representation of the two modalities. The main contributions of this paper
are:

  * •

A novel modality matching algorithm, Maestro, that can effectively use small
amounts of transcribed speech data to unify representations learnt from
unlabeled speech and text.

  * •

A new algorithm to use additional sources of supervision, namely, Machine
Translation (MT) and Speech Translation (ST), to improve multilingual joint
representations learnt during pre-training.

  * •

Establishing a new state-of-the-art (SOTA) on the VoxPopuli multilingual ASR
task with a 8% relative reduction in WER and on CoVoST-2 21 languages-to-
English speech translation (ST) with an absolute improvement of 2.8 BLEU.

##  2 Related Work

With the convergence of architectures [14, 15, 16] and objectives [9, 17] used
for learning representations in speech and natural language processing, there
has been growing interest in learning joint speech and text representations.
One set of approaches pursue multi-task training [10, 5]. However, given the
very different natures of the two modalities and their training objectives,
these approaches can suffer from interference and capacity limitations. In
contrast, alternative approaches utilize Text-To-Speech (TTS) synthesis to
augment natural speech data, avoiding inter-modal interference and improving
downstream performance, at the cost of requiring a complete TTS model [12, 18]
despite utilizing only the intermediate feature representations between text
and speech for augmentation [19, 20, 12, 21]. Maestro bridges these approaches
by implicitly aligning text representations with speech in the latent
representation space. Utilizing recent advances in end-to-end speech synthesis
that allow explicit duration modeling and control [22, 23], we show that we
can use the duration predictions for alignment while enforcing similarity to
natural speech representations.

Representation learning approaches can be extended to multilingual settings
for text [4, 2], speech [24] and joint models [11]. Learnt representations can
also be improved by utilizing additional supervised data, joint unsupervised
and supervised training on transcribed speech [25] or paired Masked Language
Modeling (MLM) objectives on Machine Translation (MT) [26] or Speech
Translation (ST) data [27]. We apply Maestro to train both, monolingual and
massively multilingual models of speech and text. We also develop approaches
to utilize cross-lingual supervision from MT and ST data during pre-training.
Our work improves upon existing work on utilizing TTS models for speech
representation learning by: (i) Developing an iterative and self-supervised
approach for duration modeling, (ii) Circumventing the need for explicit
speaker and prosody modeling by aligning resampled text representations with
speech, (iii) Extending joint speech and text representation learning to
massively multilingual datasets and tasks.

##  3 Proposed method

###  3.1 Architecture

The proposed framework to pretrain one model from untranscribed speech,
unspoken text and any available labeled data (paired speech and text) is
presented in Figure 1. It comprises of separate speech and text encoders to
encode speech and text input signals, and a shared, multi-modal latent space
encoder to learn the joint representation from these two modalities. The
modality matching objective, $\mathscr{L}_{\text{MM}}$ is used to explicitly
enforce speech-text modality matching while the $\mathscr{L}_{\text{A-MLM}}$
objective in the joint embedding space is used to learn representations from
unspoken text. The framework allows for task-dependent additional RNN-T (or
any other) decoders that predict grapheme, phoneme, word-piece or word targets
from the shared representations.

Figure 1: Proposed architecture of Maestro to learn unified representations
from speech and text. The purple and red boxes denote differences from mSLAM
[11]. The Text Encoder block utilizes alignments to explicitly resample text
representations $\mathfrak{e}_{\mathbf{t}}$ to match speech encoder output
$\mathfrak{e}_{\mathbf{s}}$.

###  3.2 Modality Matched Training

In this Section, we describe the overall training process using available
paired speech and text data, unspoken text and modality matching. We propose a
modality matching mechanism (MM) to explicitly unify the representation space
learned from text and speech. Specifically, we try to link the two modalities
in the phonetic level and learn a mapping between text units and speech
representations independent of speaker, prosody and other acoustic
characteristics.

####  3.2.1 Learning Initial Embeddings

The speech encoder $\theta_{s}$ is trained on speech input using a within-
utterance contrastive loss focusing on local acoustic and phonetic information
[3, 9]. In contrast, the text embedding extractor $\theta_{t}$ captures the
embedded lexical information from the input text signal.

####  3.2.2 Learning Aligned Embeddings

The initial speech $\mathfrak{e}_{\mathbf{s}}$ and text
$\mathfrak{e}_{\mathbf{t}}$ embeddings learned are not expected to be aligned.
Merging the two independently learned representations without attention to
alignment can result in poor knowledge sharing and require extra model
capacity. We hypothesize that this also limits the ability to jointly learn
from the two tightly-coupled modalities representing any language. The self-
alignment process described below learns alignments from the model itself in
an iterative fashion.

Paired Speech and Text input: We utilize an RNN-T decoder (See Figure 1) and
the available labeled data to first learn an RNN-T model.When learning from
paired speech and text, the Text Encoder block in the figure uses this RNN-T
model to generate alignments between the predicted text targets $\mathbf{t}$
and the speech encoder output $\mathfrak{e}_{\mathbf{s}}$. The Resampler and
Refiner layers replicate the initially learned text embeddings to match the
duration of the speech embedding using this alignment information and a Mean-
Squared Error (MSE) training objective given in Equation 1 below.

$\displaystyle\begin{aligned}
&\mathfrak{e}_{\mathbf{s}}=\theta_{s}(\mathbf{s}),\
\mathfrak{e}_{\mathbf{t}}=\theta_{t}(\mathbf{t}),\quad(\mathbf{t},\mathbf{s})\in\mathcal{X}_{\text{paired}}\\\
&\hat{\mathfrak{e}}_{\mathbf{t}}=\theta_{\text{Refiner}}\Big{(}\text{Resample}\big{(}\mathfrak{e}_{\mathbf{t}},\text{Align}_{\tt
Rnnt}(\mathfrak{e}_{\mathbf{s}},\mathbf{t})\big{)}\Big{)}\\\
&\mathscr{L}_{\text{MM}}=\text{MSE}(\mathfrak{e}_{\mathbf{s}},\hat{\mathfrak{e}}_{\mathbf{t}})+\mathscr{L}_{\tt
Rnnt}(\mathbf{t}\mid\mathfrak{e}_{\mathbf{s}})\end{aligned}$ (1)

Unpaired text input: When learning from unspoken text, the speech-text
alignment information is unavailable. We substitute it with durations
predicted from a duration prediction model in a fashion similar to speech
synthesis [22]. This model is trained on any available paired data to predict
the duration of each token. The predicted duration on unspoken text is
subsequently used to resample the initially learned text embeddings.

####  3.2.3 Aligned Masked Language Model training objective

With the introduction of speech-aligned and resampled text embeddings
($\hat{\mathfrak{e}}_{\mathbf{t}}$), we can use the same RNN-T loss for both,
unpaired text (aligned embedding $\hat{\mathfrak{e}}_{\mathbf{t}}$, text) and
paired (speech embedding $\mathfrak{e}_{\mathbf{s}}$, text) data. We replace
the original MLM/BERT loss used in prior work [1, 11] with the aligned masked
language model training objective ($\mathscr{L}_{\text{A-MLM}}$). This is the
RNN-T loss applied over the masked, resampled text embeddings with masking in
frequency and time domain similar to SpecAugment [28]. This new objective
allows for the use of the same RNN-T objective on speech embedding or unspoken
text with no associated speech embedding. Motivated by [18] to enforce
consistency between text and speech modalities, we also include the A-MLM loss
when training with paired speech and text input. We summarize this training in
Equation 2.

$\displaystyle\mathfrak{e}_{\mathbf{t}}=\theta_{t}(\mathbf{t}),\hat{\mathfrak{e}}_{\mathbf{t}}=\theta_{\text{Refiner}}\Big{(}\text{Resample}\big{(}\mathfrak{e}_{\mathbf{t}},\theta_{\tt
Duration}(\mathfrak{e}_{\mathbf{t}})\big{)}\Big{)}$
$\displaystyle\mathscr{L}_{\text{A-MLM}}=\mathscr{L}_{\tt
Rnnt}\Big{(}\mathbf{t}\mid\text{Mask}(\hat{\mathfrak{e}}_{\mathbf{t}})\Big{)},\quad\mathbf{t}\in\mathcal{X}_{\text{text}}$
(2)

###  3.3 Untranscribed Speech

Similar to W2v-BERT [9], we use contrastive loss on the speech encoder outputs
and a masked language model (MLM) loss on the shared encoder output to
pretrain our model on untranscribed speech data.

##  4 Data and Experimental Setup

###  4.1 Pre-training Data

We explore pre-training Maestro on both monolingual (English) and multilinugal
scenarios as well as ASR and translation tasks.

Monolingual ASR: We use unlabeled English-only speech from the LibriLight
corpus [29] to pre-train monolingual models. Our unspoken text corpus consists
of the text corpora from TEDLIUM [30] and Librispeech [31]. We use SpeechStew
[32] as the labeled, paired speech and text corpus.

Multilingual ASR: Following [11], we use 429k hours of public unlabeled speech
corpora: VoxPopuli [33], CommonVoice [34], MLS [35] and BABEL [36] to pre-
train multilingual ASR models. Our transcribed data draws from VoxPopuli
transcribed dataset (VP-P), MLS and Babel, following [11]. We use three
different setups to study the effectiveness of unlabeled text corpora: (1)
VoxPopuli text dataset (VP-T, 3GB) (2) mC4 [2] spanning 101 languages (15TB)
and (3) VP-T and mC4.

Speech Translation: We explore the use of MT and ST supervised data in
pretraining for downstream tasks such as ST (Section 4.4). We use the source
speech and text data from CoVoST 21 languages to English ST corpus as
transcribed speech. We concatenate paired MT text sequences from CoVoST, WMT
and TED datasets[11] and use them as unspoken text for pretraining.

###  4.2 Architecture Details

Speech encoder and shared encoder : The encoders in Figure 1 are a stack of
“Conformer blocks”. We use the Conformer XL architecture described in [12]
with $24$ layers of full-context Conformer blocks (600M parameters) where 6 of
the lower layers are assigned as speech encoder and the upper 18 layers are
the speech-text shared encoder.

Text encoder : The text embedding extractor $\theta_{t}$(Section 3.2) includes
3 convolutional layers of $512$ filters with kernel size $(5,1)$, followed by
a 6-layer Transformer with positional embedding. The upsampling is done by
copying the original text embedding to the target length of specified duration
with positional embeddings to capture frame positions within text units as
described in [22]. The Refiner $\theta_{\text{Refiner}}$ includes 2 layers of
8-headed self-attention blocks with $17\times 1$ lightweight convolutions
[37]. The duration model includes four blocks of $3\times 1$ lightweight
convolutions taking the original text embedding to predict the duration.

RNN-T decoder : We use a 2-layer, 1280-dim LSTM with a joint network of 640
dims as the RNN-T decoder. While we use an RNN-T decoder in this paper, the
proposed framework allows for the use of any decoder (CTC, LAS, etc.). We use
both phoneme and grapheme decoders for monolingual pre-training. When
switching to multilingual pre-training, we use a single decoder with 4k
sentence-pieces as targets to cover 101 languages in the mC4 dataset. We also
consider variants using grapheme and phoneme targets with vocabulary sizes of
100 and 256 respectively on the VoxPopuli corpora for comparison.

###  4.3 Pretraining hyper-parameters

We include untranscribed speech, unspoken text, transcribed speech in each
batch with a fixed ratio. To stabilize training, we use, (1) exponential-
moving-averaged (EMA) with decay rate $0.9999$ to all prediction steps during
alignment of transcribed speech, duration prediction and resampling of
unspoken text; (2) a curriculum learning schedule to start from untranscribed
speech-only training, include transcribed speech after 500k steps and unspoken
text after another 15k steps. The joint training of three types of data lasts
for another 300K steps with a learning rate schedule and optimizer given in
[7]. We use an effective batch size of (256, 512, 256) for (untranscribed
speech, unspoken text and paired data) in SpeechStew. It increases to (1024,
1024, 256) in VoxPopuli and (1024, 8192, 512) when including mC4 to increase
text throughput.

###  4.4 Downstream Tasks

Speech Recognition We evaluate our monolingual Maestro on multi-domain ASR
using the SpeechStew [32] task. All fine-tuning data and parameters follow
[7]. We also initialize the RNNT decoder from Maestro, which means both
encoder and decoder are pretrained. Multilingual versions of Maestro are fine-
tuned and evaluated on the 14-language VoxPopuli [33] multilingual ASR task
using grapheme targets [11].

Speech Translation Our multilingual speech translation evaluation on the
CoVoST-2 multilingual XX-to-English task that covers translation from 21
source languages into English [38] closely follows [11]. For joint fine-tuning
we utilize the text translation datasets composed of CoVoST 2, WMT and TED.

Figure 2: Breakdown of the improvement from Maestro on VoxPopuli and the
comparison between phoneme and grapheme pretrain. The languages are sorted by
the amount of data from high to low.

##  5 Experiments and Results

###  5.1 Monolingual Multi-domain Speech Recognition

Table 1:  Multi-domain ASR: SpeechStew results on 5 domains. All the models
use 0.6B parameters.

Method | LS-test | AMI | TED | SWB | CV
---|---|---|---|---|---
|  clean other |  ihm sdm |  |  swb chm |
Wav2vec2 | 1.7 | 3.3 | 9.6 | 23.8 | 5.7 | 4.9 | 10.8 | 8.5
W2v-BERT | 1.6 | 3 | 9.1 | 23.1 | 5.4 | 4.5 | 9 | 8.6
\+ LM | 1.5 | 2.8 |  |  |  |  |  |
SLAM | 1.6 | 3.1 | 9.3 | 23.5 | 5.6 | 4.6 | 9.1 | 8.6
TTS4Pretrain2 | 1.6 | 2.8 | 8.7 | 21.9 | 5 | 4.5 | 8.5 | 8.4
Maestro | 1.5 | 2.8 | 8.5 | 21.9 | 4.9 | 4.3 | 8 | 8.1
\+ LM | 1.5 | 2.7 |  |  |  |  |  |

Table 1 presents the results from fine-tuning monolingual Maestro on multi-
domain ASR. The first two blocks present baselines from speech-only
pretraining methods, Wav2vec2 and W2v-BERT and previous speech-text
pretraining methods, TTS4Pretrain 2.0 and SLAM [10] respectively. Maestro
clearly outperforms speech-only pretraining and further improves over previous
speech-text pretraining, TTS4Pretrain 2.0 (upto 6% relative) and SLAM (upto
12% relative) reduction in WER. Comparing Maestro with TTS4Pretrain 2.0, the
text encoder here is learnt from all the SpeechStew data while TTS model used
in TTS4Pretrain 2.0 is only trained on Librispeech. We believe this is the
reason we see better performance. On Librispeech, Maestro closes the gap with
LM shallow fusion (Row 3) and yields additional wins with LM fusion (last
row). Both use a neural Conformer language model trained from Librispeech text
corpora.

###  5.2 Multilingual Speech Recognition

Table 2:  Multilingual ASR: VoxPopuli results on 14 languages. All systems are
finetuned with the same 1.3k hours of multilingual VoxPopuli data (VP-P). In
pretrain, 2.4k hours refer to VP-P+MLS+BABEL. Maestro uses 4k SPM during
pretrain. (XLS-R uses 8k extra hours of untranscribed speech from VoxLingua
[39].)

| Model | Paired | Speech | Text | Avg
---|---|---|---|---|---
Method | size | (hours) | (hours) |  | WER
XLS-R [24] | 1B | - | 437k | - | 10.6
W2v-BERT [9] | 0.6B | - | 429k | - | 8.8
mSLAM [11] | 0.6B | 2.4k | 429k | mC4 | 9.2
mSLAM [11] | 2B | 2.4k | 429k | mC4 | 9.1
Maestro | 0.6B | 1.3k | 429k | VP-T | 8.2
Maestro | 0.6B | 2.4k | 429k | mC4 | 8.3
Maestro | 0.6B | 2.4k | 429k |  +VP-T | 8.1

We evaluate Maestro on multilingual speech recognition on the VoxPopuli
benchmark in Table 2 and include several best-performing systems as
comparison. Using in-domain unspoken text (VP-T) and paired data (VP-P)
provided by VoxPopuli release, the proposed method Maestro in the first row of
the third block outperforms all the previous systems using either in-domain or
out-domain unsupervised data. A slight degradation (Row 6) is seen with the
inclusion of massive amounts of out-of-domain unspoken text such as mc4 [2].
Combining both mC4 and VP-T corpora (last row) yields the best performance,
improving over speech-only W2v-BERT by 8% relative and create a new state of
the art.

To understand the improvement w.r.t. data sizes, Figure 2 illustrates the
language-wise breakdown corresponding to Row 5 in Table 2. Most of languages
show improvements including Slovenian with only 10 hours of supervised speech.
This shows that the proposed method can learn meaningful speech-text
representations even from small amounts of supervised data. Figure 2 also
compares the use of phoneme and grapheme targets during pretraining. Notably,
regardless of different units used in pretraining, graphemes are always used
in the supervised finetune. The overall performances are similar.

###  5.3 Speech Translation

We evaluate the potential of Maestro to serve as a foundation model for
several speech recognition and understanding tasks. We use the same pretrained
ASR encoder from Section 5.2 to evaluate speech translation performance. Table
3 demonstrates that Maestro also advances SOTA results on the speech
translation CoVoST 2 benchmark. With 0.6B parameters and the same pretrain and
finetune data setups as mSLAM, Maestro (second last row) outperforms most of
the previous systems except the larger, 2B parameter mSLAM model. To minimize
the mismatch in the text encoder outputs between pretraining and finetuning,
we include MT and ST data into pretraining with the procedure described in
Section 4.1 yielding the best performance (last row). Overall, the resulting
system outperforms mSLAM (0.6B) by 2.8 BLEU scores and creates a new SOTA on
this benchmark with 30% of the parameters. We hypothesize that the extra
efficiency stems from improved knowledge sharing between the two modalities
that can be attributed to the proposed modality matching.

Table 3:  Speech Translation (ST): CoVoST 2 X$\rightarrow$En results on 21
language pairs.

|  | Pretrain | Avg
---|---|---|---
Method | Size | Speech Text | ASR ST MT | BLEU
Finetune: ST-only; mBART decoder init [40] |
XLS-R [24] | 1B | 437k | $\times$ | $\times$ | $\times$ | $\times$ | 19.3
XLS-R [24] | 2B | 437k | $\times$ | $\times$ | $\times$ | $\times$ | 22.1
Finetune: ST and MT jointly |  |  |  |
W2v-BERT[9] | 0.6B | 429k | $\times$ | $\times$ | $\times$ | $\times$ | 21.0
mSLAM [11] | 0.6B | 429k | mC4 | $\checkmark$ | $\times$ | $\times$ | 22.4
mSLAM [11] | 2B | 429k | mC4 | $\checkmark$ | $\times$ | $\times$ | 24.8
Maestro | 0.6B | 429k | mC4 | $\checkmark$ | $\times$ | $\times$ | 24.3
Maestro | 0.6B | 429k | mC4 | $\checkmark$ | $\checkmark$ | $\checkmark$ | 25.2

##  6 Conclusions

We have described Maestro, a new technique for joint speech and text
representation learning that outperforms the state of the art on speech
recognition and speech translation tasks. Maestro addresses the joint
representation problem by first aligning text to speech and then training a
text representation to match a W2v-BERT speech representation. This results in
significant improvements by 8% on ASR and 2.8 BLEU on ST.

## References

  * [1] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “BERT: Pre-training of deep bidirectional transformers for language understanding,” _arXiv preprint arXiv:1810.04805_ , 2018.
  * [2] L. Xue, N. Constant, A. Roberts, M. Kale, R. Al-Rfou, A. Siddhant, A. Barua, and C. Raffel, “mT5: A massively multilingual pre-trained text-to-text transformer,” _arXiv preprint arXiv:2010.11934_ , 2020.
  * [3] A. Baevski _et al._ , “wav2vec 2.0: A framework for self-supervised learning of speech representations,” _arXiv preprint arXiv:2006.11477_ , 2020\.
  * [4] A. Conneau, K. Khandelwal, N. Goyal, V. Chaudhary, G. Wenzek, F. Guzmán, E. Grave, M. Ott, L. Zettlemoyer, and V. Stoyanov, “Unsupervised cross-lingual representation learning at scale,” _arXiv preprint arXiv:1911.02116_ , 2019.
  * [5] J. Ao, R. Wang, L. Zhou, S. Liu, S. Ren, Y. Wu, T. Ko, Q. Li, Y. Zhang, Z. Wei _et al._ , “SpeechT5: Unified-modal encoder-decoder pre-training for spoken language processing,” _arXiv preprint arXiv:2110.07205_ , 2021.
  * [6] Y.-A. Chung, H. Tang, and J. Glass, “Vector-quantized autoregressive predictive coding,” _arXiv preprint arXiv:2005.08392_ , 2020.
  * [7] Y. Zhang _et al._ , “Pushing the limits of semi-supervised learning for automatic speech recognition,” _arXiv preprint arXiv:2010.10504_ , 2020.
  * [8] W.-N. Hsu, Y.-H. H. Tsai, B. Bolte, R. Salakhutdinov, and A. Mohamed, “HuBERT: How much can a bad teacher benefit ASR pre-training?” in _Proc. ICASSP_ , 2021, pp. 6533–6537.
  * [9] Y.-A. Chung _et al._ , “W2v-BERT: Combining contrastive learning and masked language modeling for self-supervised speech pre-training,” _arXiv preprint arXiv:2108.06209_ , 2021.
  * [10] A. Bapna, Y.-a. Chung, N. Wu, A. Gulati, Y. Jia, J. H. Clark, M. Johnson, J. Riesa, A. Conneau, and Y. Zhang, “SLAM: A unified encoder for speech and language modeling via speech-text joint pre-training,” _arXiv preprint arXiv:2110.10329_ , 2021.
  * [11] A. Bapna, C. Cherry, Y. Zhang, Y. Jia, M. Johnson, Y. Cheng, S. Khanuja, J. Riesa, and A. Conneau, “mSLAM: Massively multilingual joint pre-training for speech and text,” _arXiv preprint arXiv:2202.01374_ , 2022\.
  * [12] Z. Chen, Y. Zhang, A. Rosenberg, B. Ramabhadran, G. Wang, and P. Moreno, “Injecting text in self-supervised speech pretraining,” _arXiv preprint arXiv:2108.12226_ , 2021.
  * [13] R. Kuhn and R. De Mori, “A cache-based natural language model for speech recognition,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 12, no. 6, pp. 570–583, 1990.
  * [14] A. Vaswani _et al._ , “Attention is all you need,” in _Advances in neural information processing systems_ , 2017, pp. 5998–6008.
  * [15] A. Gulati, J. Qin, C.-C. Chiu _et al._ , “Conformer: Convolution-augmented Transformer for speech recognition,” _arXiv preprint arXiv:2005.08100_ , 2020.
  * [16] A. Jaegle, F. Gimeno, A. Brock, O. Vinyals, A. Zisserman, and J. Carreira, “Perceiver: General perception with iterative attention,” in _International Conference on Machine Learning_. PMLR, 2021, pp. 4651–4664.
  * [17] A. Baevski, W.-N. Hsu, Q. Xu, A. Babu, J. Gu, and M. Auli, “Data2vec: A general framework for self-supervised learning in speech, vision and language,” _arXiv preprint arXiv:2202.03555_ , 2022.
  * [18] Z. Chen, Y. Zhang, A. Rosenberg, B. Ramabhadran, P. Moreno, and G. Wang, “Tts4pretrain 2.0: Advancing the use of text and speech in ASR pretraining with consistency and contrastive losses,” in _Proc. ICASSP_ , 2022.
  * [19] A. Renduchintala, S. Ding, M. Wiesner, and S. Watanabe, “Multi-modal data augmentation for end-to-end ASR,” _arXiv preprint arXiv:1803.10299_ , 2018\.
  * [20] G. Wang, A. Rosenberg, Z. Chen, Y. Zhang, B. Ramabhadran, Y. Wu, and P. Moreno, “Improving speech recognition using consistent predictions on synthesized speech,” in _ICASSP_ , 2020.
  * [21] S. Ueno, M. Mimura, S. Sakai, and T. Kawahara, “Data augmentation for asr using TTS via a discrete representation,” _ASRU_ , 2021.
  * [22] I. Elias, H. Zen, J. Shen, Y. Zhang, Y. Jia, R. J. Weiss, and Y. Wu, “Parallel Tacotron: Non-autoregressive and controllable TTS,” in _Proc. ICASSP_ , 2021, pp. 5709–5713.
  * [23] Y. Ren, Y. Ruan, X. Tan, T. Qin, S. Zhao, Z. Zhao, and T.-Y. Liu, “Fastspeech: Fast, robust and controllable text to speech,” _Advances in Neural Information Processing Systems_ , vol. 32, 2019.
  * [24] A. Babu, C. Wang, A. Tjandra, K. Lakhotia, Q. Xu, N. Goyal, K. Singh, P. von Platen, Y. Saraf, J. Pino _et al._ , “XLS-R: Self-supervised cross-lingual speech representation learning at scale,” _arXiv preprint arXiv:2111.09296_ , 2021.
  * [25] J. Bai, B. Li, Y. Zhang, A. Bapna, and T. N. Sainath, “Joint unsupervised and supervised training for multilingual ASR,” _arXiv preprint arXiv:2111.08137_ , 2021.
  * [26] G. Lample and A. Conneau, “Cross-lingual language model pretraining,” _arXiv preprint arXiv:1901.07291_ , 2019.
  * [27] R. Zheng _et al._ , “Fused acoustic and text encoding for multimodal bilingual pretraining and speech translation,” _arXiv preprint arXiv:2102.05766_ , 2021.
  * [28] D. S. Park, W. Chan, Y. Zhang, C.-C. Chiu, B. Zoph, E. D. Cubuk, and Q. V. Le, “SpecAugment: A simple data augmentation method for automatic speech recognition,” _Proc. Interspeech 2019_ , pp. 2613–2617, 2019.
  * [29] J. Kahn, M. Rivière, W. Zheng _et al._ , “Libri-Light: A benchmark for asr with limited or no supervision,” in _Proc. ICASSP_ , 2020, pp. 7669–7673.
  * [30] A. Rousseau, P. Deléglise, and Y. Esteve, “TED-LIUM: an automatic speech recognition dedicated corpus.” in _Proc. LREC_ , 2012, pp. 125–129.
  * [31] V. Panayotov, G. Chen, D. Povey, and S. Khudanpur, “Librispeech: An ASR corpus based on public domain audio books,” in _Proc. ICASSP_ , 2015.
  * [32] W. Chan _et al._ , “SpeechStew: Simply mix all available speech recognition data to train one large neural network,” _arXiv preprint arXiv:2104.02133_ , 2021.
  * [33] C. Wang, M. Riviere, A. Lee, A. Wu, C. Talnikar, D. Haziza, M. Williamson, J. Pino, and E. Dupoux, “Voxpopuli: A large-scale multilingual speech corpus for representation learning, semi-supervised learning and interpretation,” _arXiv preprint arXiv:2101.00390_ , 2021.
  * [34] R. Ardila _et al._ , “Common Voice: A massively-multilingual speech corpus,” _arXiv preprint arXiv:1912.06670_ , 2019.
  * [35] V. Pratap, Q. Xu, A. Sriram, G. Synnaeve, and R. Collobert, “MLS: A large-scale multilingual dataset for speech research,” _arXiv preprint arXiv:2012.03411_ , 2020.
  * [36] M. J. Gales, K. M. Knill, A. Ragni, and S. P. Rath, “Speech recognition and keyword spotting for low-resource languages: Babel project research at cued,” in _Fourth International workshop on spoken language technologies for under-resourced languages (SLTU-2014)_ , 2014, pp. 16–23.
  * [37] F. Wu, A. Fan, A. Baevski, Y. N. Dauphin, and M. Auli, “Pay less attention with lightweight and dynamic convolutions,” _arXiv preprint arXiv:1901.10430_ , 2019.
  * [38] C. Wang, A. Wu, and J. Pino, “CoVoST 2 and massively multilingual speech-to-text translation,” _arXiv preprint arXiv:2007.10310_ , 2020.
  * [39] J. Valk and T. Alumäe, “VoxLingua107: A dataset for spoken language recognition,” in _2021 IEEE Spoken Language Technology Workshop (SLT)_. IEEE, 2021, pp. 652–658.
  * [40] Y. Tang, C. Tran, X. Li, P.-J. Chen, N. Goyal, V. Chaudhary, J. Gu, and A. Fan, “Multilingual translation from denoising pre-training,” in _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , 2021, pp. 3450–3466.


# Morse-Smale complexes on convex polyhedra

Balázs Ludmány  ,  Zsolt Lángi  and  Gábor Domokos  MTA-BME Morphodynamics
Research Group and Department of Control Engineering and Information
Technology, Magyar Tudósok körútja 2., Budapest, Hungary 1117
<EMAIL_ADDRESS>MTA-BME Morphodynamics Research Group and
Department of Geometry, Budapest University of Technology, Egry József utca
1., Budapest, Hungary, 1111<EMAIL_ADDRESS>MTA-BME Morphodynamics
Research Group and Department of Mechanics, Materials & Structures, Budapest
University of Technology, Műegyetem rakpart 1-3., Budapest, Hungary, 1111
<EMAIL_ADDRESS>
###### Abstract.

Motivated by applications in geomorphology, the aim of this paper is to extend
Morse-Smale theory from smooth functions to the radial distance function
(measured from an internal point), defining a convex polyhedron in
$3$-dimensional Euclidean space. The resulting polyhedral Morse-Smale complex
may be regarded, on one hand, as a generalization of the Morse-Smale complex
of the smooth radial distance function defining a smooth, convex body, on the
other hand, it could be also regarded as a generalization of the Morse-Smale
complex of the piecewise linear parallel distance function (measured from a
plane), defining a polyhedral surface. Beyond similarities, our paper also
highlights the marked differences between these three problems and it also
includes the design, implementation and testing of an explicit algorithm
computing the Morse-Smale complex on a convex polyhedron.

###### Key words and phrases:

Morse-Smale complexes, polyhedral surfaces, static equilibrium points, radial
function

###### 2010 Mathematics Subject Classification:

57Q70, 52B70, 52B10

The research reported in this paper was supported by the BME Water Sciences &
Disaster Prevention TKP2020 Institution Excellence Subprogram, grant no.
TKP2020 BME-IKA-VIZ, the NKFIH grant K134199, the János Bolyai Research
Scholarship of the Hungarian Academy of Sciences, and the ÚNKP-20-5 New
National Excellence Program by the Ministry of Innovation and Technology.

##  1\. Introduction

Morse theory, the investigation of the critical points of a smooth function
defined on a smooth manifold, has been in the focus of research since the
middle of the 20th century [15]. This area has received especially much
attention since the seminal paper of Witten [21] directly relating Morse
theory to quantum field theory, and has gained applications in many
disciplines both within and outside mathematics (cf. e.g. [19]).

Following the rapid development of computer graphics, the description of
smooth functions on a smooth manifold was extended both to discrete systems
[11, 12] as well as to the investigation of polyhedral surfaces in the
$3$-dimensional Euclidean space $\mathbb{R}^{3}$, regarded as simplicial
complexes. In [2, 10] the polyhedral surface has been equipped with the so-
called _parallel distance function_ (also called the _height function_), i.e.
the distance measured from a fixed Euclidean plane $\mathbb{R}^{2}$. The
restriction of the height function to a polyhedral surface is piecewise
linear, so all critical points of the function are located at vertices and the
algorithm presented in [10] relies on this fact. We will briefly refer to this
case as the _piecewise linear_ problem. Using the theory developed in [2, 10].

The aim of the present paper is the to extend this theory by equipping a
convex polyhedral surface with the so-called _radial distance function_ , i.e.
the distance measured from a fixed, internal reference point. The radial
distance function is neither smooth nor piecewise linear, leading to
significant differences in comparison with both theories. In particular,
critical points may appear not only at vertices (as in the piecewise linear
case) or at smooth points (as in the smooth case), but both at vertices and in
the interiors of edges and faces of the simplicial complex. Similarly, while
ascending integral curves are defined on infinite domains in the smooth case
and on finite domains in the piecewise linear case, they are defined, as we
will see, on a semi-infinite domain in the polyhedral case. In addition, it is
worth noting that the natural duality by switching the roles of ascent and
descent, (which is present both in the smooth and the piecewise linear
theories) appears to be missing in the polyhedral case.

Despite these differences, the piecewise linear and the polyhedral problem are
also closely related: in the polyhedral (radial) case, if we let the reference
point approach infinity, the radial distance function will approach the
parallel distance function and all critical points will approach vertices. (We
remark that the transition between the polyhedral and piecewise linear case is
far from trivial: if the reference point is not in the interior but at finite
distance from the polyhedron, then neither the polyhedral nor the piecewise
linear theories will apply.)

While the piecewise linear and the polyhedral problems are mathematically
closely related, the applications driving these two models are somewhat
different. While parallel distance functions can be efficient models in image
processing and serve as good approximations in local cartography [10], radial
distance functions are the only option in case of particle shape models in
geomorphology and planetology [3, 4, 9, 14]. Also, for global cartography,
spherical geometry has to be taken into account.

Our current paper is primarily motivated by particle shape modelling in
geomorphology. Traditional geological shape descriptors (e.g. axis ratios,
roundness) have been recently complemented [4, 9] by a new class, called
_mechanical shape descriptors_ which proved to be rather efficient not only in
determining the provenance of sedimentary particles [16] but also served
surprising well in the identification of the shapes of asteroids [4, 7].
Mechanical descriptors rely on the radial distance function measured from the
center of mass to which we briefly refer as the mechanical distance function.
The number of stable, unstable and saddle-type critical points are called
_first order_ mechanical descriptors [9, 20] whereas Morse-Smale complexes
belong to _second order_ mechanical descriptors [4, 8]. While the mathematical
properties of Morse-Smale complexes associated with a smooth mechanical
distance function have been investigated in detail [5, 8], so far there has
been little experimental data to test this theory. The main obstacle in
obtaining field data is the identification of Morse-Smale complexes on scanned
images of particles [14]. These scans can be regarded as compact, polyhedral
surfaces which we associate with the radial (mechanical) distance function.

In this paper we present the mathematical background to describe these
complexes leading, in a natural way, to an algorithm to perform the above
task, i.e. to identify Morse-Smale complexes on the surfaces of polyhedra
equipped with the radial distance function. We remark that a Morse-Smale
complex on a surface is naturally associated to the topological graph whose
vertices and edges are those of the complex. This graph, called Morse-Smale
graph, often appears in applications [5], and by the above correspondence,
information on one provides equivalent information on the other one.

The structure of the paper is as follows. In Section 2 we give a brief summary
of the elementary properties of Morse-Smale complexes defined by a smooth
convex body in $\mathbb{R}^{3}$. The next two sections deal with the main goal
of the paper: by investigating the properties of the radial distance function
defined on a polyhedral surface, we build up a theory leading to the
definition of a Morse-Smale complex and the related Morse-Smale graph on the
surface (cf. Definitions 13 and 16). These definitions may appear, at least at
first glance, rather similar to their smooth counterparts (Definitions 5 and
6). Also, as we will see, Morse-Smale graphs on polyhedra and Morse-Smale
graphs on smooth convex bodies share most, but not all of their combinatorial
properties. Still, there also exist fundamental and significant differences
between the smooth, the piecewise linear and the polyhedral problems, so each
of these cases require different tools leading to these definitions. We
present our mathematical results in two sections: in particular, in Section 3,
we find an analogue of the gradient vector field on the polyhedron, and in
Section 4 we define ascending integral curves generated by this vector field
and explore their properties, yielding the notion of Morse-Smale complex on a
polyhedral surface. Then in Section 5 we present an algorithm that computes
the Morse-Smale complex generated by a generic convex polyhedron. Finally, in
Section 6 we collect our additional remarks and open questions.

In the paper we denote by $\mathbb{R}^{3}$ the $3$-dimensional Euclidean
space. We regard this space as a $3$-dimensional real vector space equipped
with the usual Euclidean norm, denoted by $|\cdot|$ or $N(\cdot)$. We denote
the origin of this space by $o$, and the unit sphere centered at $o$ by
$\mathbb{S}^{2}=\\{x\in\mathbb{R}^{3}:|x|=1\\}$. We use the notation
$\operatorname{int}(\cdot)$ and $\partial$ to the interior and the boundary of
a set, respectively, and for points $x,y\in\mathbb{R}^{3}$, we denote the
closed segment with endpoints $x,y$ by $[x,y]$. Let $K$ be a convex body (i.e.
a compact, convex set with nonempty interior) in $\mathbb{R}^{3}$, containing
$o$ in its interior. The _radial function
$\rho_{K}:\mathbb{S}^{2}\to(0,\infty)$_ of $K$ (cf. [17]) is defined by

$\rho_{K}(x)=\max\\{\lambda:\lambda x\in K\\}.$

This function, often appearing in the literature, is the reciprocal of the
gauge function of $K$ [17], and it clearly determines the convex body $K$
[20]. We note that while our considerations are valid if $o$ is an arbitrary
interior point of $K$ chosen as reference point, in applications in mechanics
and geology, it usually coincides with the center of gravity of $K$.

##  2\. Morse-Smale complex generated by a smooth convex body

In this section we consider only convex bodies with $C^{\infty}$-class
boundary. In this case the mapping $u\mapsto\rho_{K}(u)$ is a
$C^{\infty}$-diffeomorphism between $\mathbb{S}^{2}$ and $\partial K$, and
hence, we assume that $\rho_{K}$ is infinitely many times differentiable on
$\mathbb{S}^{2}$. This diffeomorphism establishes a natural correspondence
between topological properties of the Morse-Smale complex on $\mathbb{S}^{2}$
defined by $\rho_{K}$ and the Morse-Smale complex on $\partial K$ defined by
Euclidean norm in the sense that central projection from $\mathbb{S}^{2}$ to
$\partial K$ maps the first complex to the second one, and vice versa, making
possible to introduce these complexes in two equivalent ways. In this section
we follow the first approach as it is more convenient for those familiar with
Morse theory. Nevertheless, in Sections 3 and 4, since our considerations are
usually based on the geometric properties of the convex polyhedron under
investigation, we use the second approach.

######  Definition 1.

A point $x\in\mathbb{S}^{2}$ is called a _critical point_ of $\rho_{K}$, if
the derivative of $\rho_{K}$ at $x$ is zero, that is if
$(\nabla\rho_{K})(x)=0$. A noncritical point of $\rho_{K}$ is called a
_regular point_ of $\rho_{K}$. A value $\alpha\in\mathbb{R}$ is called a
_critical value_ of $\rho_{K}$ if there is a critical point of $\rho_{K}$
satisfying $\rho_{K}(x)=\alpha$. A critical point $x$ is _nondegenerate_ , if
the Hessian of $\rho_{K}$ at $x$ is not singular.

Recall the well-known fact that if the Hessian of $\rho_{K}$ at a
nondegenerate critical point $x$ has $0$, $1$ or $2$ negative eigenvalue, then
$x$ is a local maximum, a saddle point or a local minimum of $\rho_{K}$,
respectively.

######  Remark 1.

If $x$ is a critical point of $\rho_{K}$, then the point
$\rho_{K}(x)x\in\partial K$ is usually called a (static) equilibrium point of
$K$ (with respect to $o$). Furthermore, for any nondegenerate critical point
$x$ of $\rho_{K}$, the point $\rho_{K}(x)x$ is called a _stable_ , or a
_saddle-type_ or an _unstable_ equilibrium point of $K$ if $x$ is a local
minimum, a saddle point or a local maximum of $\rho_{K}$, respectively [8].

######  Definition 2.

The function $\rho_{K}$ is called a _Morse function_ if it is
$C^{\infty}$-class, and all its critical points are nondegenerate.

In this paper we assume that $\rho_{K}$ is a Morse function. This implies that
any critical point of $\rho_{K}$ has a neighborhood in $\mathbb{S}^{2}$ that
does not contain any other critical point, and thus, by the compactness of
$\mathbb{S}^{2}$, $\rho_{K}$ has only finitely many critical points.

######  Definition 3.

An _integral curve_ $c:\mathbb{R}\to\mathbb{S}^{2}$ is a curve, maximal with
respect to inclusion, whose derivative at every point coincides with the value
of the gradient of $\rho_{K}$ at that point; that is,
$c^{\prime}(t)=(\nabla\rho_{K})(c(t))$ for all $t\in\mathbb{R}$. We call
$\operatorname{org}(c)=\lim_{t\to-\infty}c(t)$ the _origin_ , and
$\operatorname{dest}(c)=\lim_{t\to\infty}c(t)$ the _destination_ of $c$ [10].

We remark that our smoothness conditions and the Picard-Lindelöf Theorem yield
that any regular point $x$ belongs to exactly one integral curve, all integral
curves consists of only regular points, and two integral curves are either
disjoint or coincide. Furthermore, the origin and the destination of every
integral curve are critical points of $\rho_{K}$ (cf. e.g. [1, 10]).

######  Definition 4.

The _descending (resp. ascending) manifold_ of a critical point $x$, denoted
by $D(x)$ (resp. $A(x)$) is the union of $x$ and all integral curves with $x$
as their destination (resp. origin).

The function $\rho_{K}$ is called _Morse-Smale_ if all ascending and
descending manifolds of $\rho_{K}$ intersect only transversally; or
equivalently, if any pair of intersecting ascending and descending
$1$-manifolds cross.

######  Definition 5.

The cells of the _Morse-Smale complex generated by $\rho_{K}$_ are the sets
obtained by intersecting a descending and an ascending manifold. The $2$-,
$1$-, and $0$-dimensional cells of this complex are called _faces, edges_ ,
and _vertices_ , respectively.

Observe that if $x\neq y$ are critical points of $\rho_{K}$, then $A(x)\cap
D(x)=\\{x\\}$, and $A(x)\cap D(y)$ is the union of all integral curves with
origin $x$ and destination $y$. Clearly, the vertices of the Morse-Smale
complex of $\rho_{K}$ are the critical points of $\rho_{K}$, and if $x$ is a
stable and $y$ is an unstable point, then $A(x)\cap D(y)$ is an open set in
$\mathbb{S}^{2}$, implying that it is a face of the complex. On the other
hand, the same does not hold if $x$ or $y$ is a saddle point since every
saddle point is the origin, and also the destination, of exactly two integral
curves, corresponding to edges of the complex. It is well known (cf. e.g.
Lemma 1 in [10]) that every face of the Morse-Smale complex is bounded by four
edges, and the four critical points in the boundary are a stable, a saddle, an
unstable and a saddle point, in this cyclic order, where the two saddle points
may coincide.

######  Definition 6.

The topological graph $G$ on $\mathbb{S}^{2}$, whose vertices are the critical
points of $\rho_{K}$, and whose edges are the edges of the Morse-Smale
complex, is called the _Morse-Smale graph_ generated by $\rho_{K}$ [5]. This
graph is usually regarded as a _$3$ -colored_ quadrangulation of
$\mathbb{S}^{2}$, where the ‘colors’ of the vertices are the three types of a
critical point.

##  3\. Generating the gradient vector field on a polyhedral surface: local
properties of the function $N_{\partial P}$

In the remaining part of the paper we deal with a convex polyhedron
$P\subset\mathbb{R}^{3}$ containing $o$ in its interior. We note that the
concepts of equilibrium points and nondegeneracy of convex polyhedra are
already established in the literature [6, 13]. The following definition is
from [6].

######  Definition 7.

Let $P\subset\mathbb{R}^{3}$ be a convex polyhedron and let
$o\in\operatorname{int}(P)$. We say that $q\in\partial P$ is an _equilibrium
point_ of $P$ (with respect to $o$) if the plane $H$ through $q$ and
perpendicular to $[o,q]$ supports $P$ at $q$. In this case $q$ is
_nondegenerate_ , if $H\cap P$ is the (unique) face, edge or vertex of $P$
that contains $q$ in its relative interior; here, by the relative interior of
a vertex we mean the vertex itself. A nondegenerate equilibrium point $q$ is
called _stable, saddle-type_ or _unstable_ , if $\dim(H\cap P)=2,1$ or $0$,
respectively. We call $P$ _nondegenerate_ if all its equilibrium points are
nondegenerate. The points of $\partial P$ which are not equilibrium points are
called _regular points_ of $\partial P$.

In our investigation, we deal only with nondegenerate convex polyhedra. For
any set $S\subset\mathbb{R}^{3}$, we denote the restriction of the Euclidean
norm function onto $S$ by $N_{S}$, and denote the affine hull of $S$ by $<S>$.
Note that since $\partial P$ is piecewise smooth, the gradient of the function
$N_{\partial P}$ exists only at interior points of the faces of $P$. To extend
this notion to nonsmooth points of $\partial P$, we intend to find the
‘direction and rate of steepest ascent’ for all nonsmooth points $q$ among all
unit tangent vectors at $q$. The aim of Section 3 is to generalize the notion
of gradient vector field by following this approach, and examine the
properties of our generalization. In Section 4 we generalize the notion of
integral curves and Morse-Smale complex for our setting.

######  Definition 8.

Let $q\in\partial P$. If, for some vector $v\neq o$, the half line
$\\{q+tv:t\geq 0\\}$ intersects $\partial P$ in a nondegenerate segment
starting at $q$, we say that $v$ is a _tangent vector_ of $P$ at $q$. If $X$
is a face or an edge of $P$ containing $q$, and the gradient $(\nabla
N_{<X>})(q)$ is a tangent vector of $P$ at $q$, we say that this vector is a
_candidate gradient_ at $q$.

Note that by definition, if $v=(\nabla N_{<X>})(q)$ is a candidate gradient at
$q$ and $v_{0}=\frac{v}{|v|}$, then the one-sided directional derivative
$\lim_{t\to 0^{+}}\frac{|q+tv_{0}|}{t}=|v|$ is strictly positive. Furthermore,
the maximum of the one-sided directional derivatives of $N_{\partial P}$ at
$q$ is the maximum of the lengths of the candidate gradients at $q$. The main
result of this section is the following.

######  Theorem 1.

Let $q\in\partial P$. If $q$ is an equilibrium point of $P$, then there is no
candidate gradient at $q$. If $q$ is a regular point of $P$, then there is at
least one candidate gradient at $q$, and there is a unique candidate gradient
at $q$ with maximal length.

###### Proof.

We distinguish three cases.

Case 1: $q$ is an interior point of a face $F$ of $P$. If $q$ is the
orthogonal projection of $o$ onto the plane $<F>$, then $q$ is clearly a
stable equilibrium point of $P$, and there is no candidate gradient at $q$. In
the opposite case there is a unique candidate gradient at $q$, namely $(\nabla
N_{<F>})(q)$, which clearly has maximal length among all candidate gradients.

Case 2: $q$ is a relative interior point of an edge $E$ of $P$. Let $F_{1}$
and $F_{2}$ denote the two faces of $P$ that contain $E$, and for $i=1,2$, let
$H_{i}$ denote the open half plane in $<F_{i}>$ that is bounded by the line
$<E>$, and whose closure contains $F_{i}$. Furthermore, let $o_{i}$ denote the
orthogonal projection of $o$ onto the plane $<H_{i}>$, and let $o_{E}$ be the
orthogonal projection of $o$ onto $<E>$.

Observe that $o_{i}\in E$ yields, by the convexity of $P$, that $o_{i}$ is a
degenerate equilibrium point of $P$, which contradicts our assumptions. Thus,
we have $o_{1},o_{2}\notin E$. Similarly, if $o_{1}\notin H_{1}$ and
$o_{2}\notin H_{2}$, then the coplanarity of $o,o_{1},o_{2},o_{E}$ implies
that the dihedral angle of $P$ at $E$ is $(\pi-(o_{1}o_{E}o)+(\pi-
o_{2}o_{E}o))>\pi$, which contradicts the convexity of $P$. Thus, we have
$o_{i}\in H_{i}$ for at least one value of $i$. Since the gradient of
$N_{<H_{i}>}$ at any $x\neq o_{i}$ points in the direction of $x-o_{i}$, this
implies that at most one of $(\nabla N_{<F_{i}>})(q)$ is a candidate gradient.

First, assume that $o_{1}\in H_{1}$ and $o_{2}\in H_{2}$. Then $(\nabla
N_{<F_{i}>})(q)$ is not a candidate gradient for $i=1,2$. On the other hand,
$(\nabla N_{<E>})(q)$ is a tangent vector of $P$ at $q$ if and only if $q\neq
o_{E}$. Thus, this vector is the unique candidate gradient for $q\neq o_{E}$,
and there is no candidate gradient at $q$ if $q=o_{E}$.

Now we consider the case that exactly one of the $o_{i}$s lies in $H_{i}$;
say, we have $o_{1}\in H_{1}$ and $o_{2}\notin H_{2}$. Then, since
$o_{2}\in<E>$ yields $o_{2}\in<E>\setminus E$, $(\nabla N_{<F_{2}>})(q)$ is a
tangent vector of $P$ at $q$. On the other hand, in this case $|(\nabla
N_{<E>})(q)|$, if it exists, is a directional derivative of the function
$N_{<F_{2}>}$ at $q$, implying that $|(\nabla N_{<E>})(q)|\leq|(\nabla
N_{<F_{2}>})(q)|$, with equality if and only if $o_{2}\in<E>\setminus E$ and
$(\nabla N_{<E>})(q)=(\nabla N_{<F_{2}>})(q)$.

Case 3: $q$ is a vertex of $P$. Let $F_{1},F_{2},\ldots,F_{k}$ denote the
faces of $P$ containing $q$ such that $k\geq 3$, and for $i=1,2,\ldots,k$, the
set $E_{i}=F_{i}\cap F_{i+1}$ is an edge of $P$. Then the edges of $P$
containing $q$ are $E_{1},E_{2},\ldots,E_{k}$. First, observe that if $q$ is
an equilibrium point of $P$, then for every tangent vector $v$ of $P$ at $q$,
the one-sided directional derivative of $N_{\partial P}$ in the direction of
$v$ is negative, which yields that there is no candidate gradient at $q$.
Thus, we may assume that $q$ is a regular point of $P$, which yields that
$(\nabla N_{<E_{i}>})(q)$ is a candidate gradient for at least one value of
$i$.

We show that there is at most one value of $i$ such that $(\nabla
N_{<F_{i}>})(q)$ is a candidate gradient. Indeed, suppose for contradiction
that $(\nabla N_{<F_{i}>})(q)$ and $(\nabla N_{<E_{j}>})(q)$ are candidate
gradients at $q$, where $i\neq j$. Let $E=<F_{i}>\cap<F_{j}>$, and let $H_{i}$
(resp. $H_{j}$) denote the open half plane in $<F_{i}>$ (resp. $<F_{j}>$) that
is bounded by the line $E$, and whose closure contains $F_{i}$ (resp.
$F_{j}$). Similarly like in Case 2, we may observe that the fact that $(\nabla
N_{<F_{i}>})(q)$ and $(\nabla N_{<F_{j}>})(q)$ are tangent vectors of $P$ at
$q$ yields that the orthogonal projection of $o$ onto $<F_{i}>$ (resp.
$<F_{j}>$) is not contained in $H_{i}$ (resp. $H_{j}$), and thus, the dihedral
angle between $<\\{o\\}\cup E>$ and $H_{i}$ (resp. $H_{j}$) is at least
$\frac{\pi}{2}$. But this contradicts the fact that the intersection of the
two supporting half spaces of $P$, containing $F_{i}$ and $F_{j}$,
respectively, is a convex polyhedral region.

Consider the case that for some value of $i$, $v=(\nabla N_{<F_{i}>})(q)$ is a
candidate gradient, i.e. it is a tangent vector of $P$ at $q$. Then, clearly,
the convexity of $P$ implies that for any unit tangent vector
$v^{\prime}\neq\frac{v}{|v|}$ of $P$ at $q$, the one-sides directional
derivative of $N_{\partial P}$ at $q$ in the direction of $v^{\prime}$ is
strictly less than $|v|$. Thus, in this case $v=(\nabla N_{<F_{i}>})(q)$ has
maximal length among all candidate gradients at $q$.

Finally, we deal with the case that $(\nabla N_{<F_{i}>})(q)$ is not a tangent
vector of $P$ at $q$ for any value of $i$, but there are more than one values
of $i$ such that $(\nabla N_{<E_{i}>})(q)$ is a candidate gradient of maximal
length. Let $i_{1}\neq i_{2}$ be such values. For $j=1,2$, consider the closed
half line $R_{i_{j}}=\\{q+tv_{i_{j}}:t\geq 0\\}$ where $v_{i_{j}}$ is the unit
vector pointing from $q$ towards the other endpoint of $E_{i_{j}}$, and let
$H=<E_{i_{1}}\cup E_{i_{2}}>$. Note that $|(\nabla N_{<E_{i_{j}}>})(q)|$ is
the directional derivative of $N_{H}$ in the direction of $v_{i_{j}}$, and
hence, the equality $|(\nabla N_{<E_{i_{1}}>})(q)|=|(\nabla
N_{<E_{i_{2}}>})(q)|$ implies that $(\nabla N_{H})(q)$ points in the direction
of $v_{i_{1}}+v_{i_{2}}$. On the other hand, the half line
$\\{q+t(v_{i_{1}}+v_{i_{2}}):t\geq 0\\}$ intersects $P$ in a nondegenerate
segment, and thus, there is a unit tangent vector $v$ of $P$ at $q$ such that
the one-sided directional derivative of $N_{\partial P}(q)$ in the direction
of $v$ is strictly greater than $|(\nabla N_{<E_{i_{j}}>})(q)|$ ($j=1,2$),
contradicting the assumption that the latter two vectors have maximal length.
∎

######  Remark 2.

By the argument in the last paragraph, for any vertex $q$ of $P$, the set of
tangent vectors $v$ of $P$ at $q$ with the property that in the direction of
$v$ the one-sided derivative of the distance function increases is connected,
implying the same statement for the set of tangent vectors in which the
distance function decreases.

######  Definition 9.

If $q$ is a regular point of $P$, then we call the unique candidate gradient
at $q$ with maximal length the _extended gradient_ of $N_{\partial P}$ at $q$.
If $q$ is an equilibrium point of $P$, we say that the extended gradient of
$N_{\partial P}$ at $q$ is $0$. We denote the extended gradient of
$N_{\partial P}$ at $q$ by $(\nabla^{\text{ext}}N_{\partial P})(q)$.

Our analysis in Case 2 of the proof of Theorem 1 leads to Definition 10.

######  Definition 10.

Let $E$ be an edge of $P$, and let $F_{1}$ and $F_{2}$ be the two faces of $P$
containing $E$. For $i=1,2$, let $H_{i}$ denote the open half plane in
$<F_{i}>$ that is bounded by the line $<E>$, and whose closure contains
$F_{i}$, and let $o_{i}$ be the orthogonal projection of $o$ onto $<F_{i}>$.
If $o_{1}\in H_{1}$ and $o_{2}\in H_{2}$, then for any regular point $q$ in
the relative interior of $E$, the extended gradient at $q$ is parallel to $E$.
In this case we say that $E$ is a _followed edge_ of $P$. If either
$o_{1}\notin H_{1}$ or $o_{2}\notin H_{2}$, then we say that $E$ is a
_crossed_ edge. In particular, if $E$ is a crossed edge with $o_{1}\notin
H_{1}$, then for every point $q$ in the relative interior of $E$, the extended
gradient at $q$ points towards the interior of $F_{1}$. In this case we say
that $E$ is _crossed from $F_{2}$ to $F_{1}$_.

$F_{1}$$F_{2}$$E$$o_{1}$$o_{2}$ (a) Followed edge

$F_{1}$$F_{2}$$E$$o_{1}$$o_{2}$ (b) Crossed edge

Figure 1. Possible types of edges. The extended gradient field on faces is
also shown.

We need the following remark in Section 4.

######  Remark 3.

Let $q$ be a vertex of $P$ and let $F_{1},F_{2},\ldots,F_{k}$ be the faces of
$P$ containing $q$ such that for $i=1,2,\ldots,k$, $E_{i}=F_{i-1}\cap F_{i}$
is an edge of $P$. Assume that all edges $E_{i}$ are crossed edges. Then there
is some value of $i$ such that $E_{i}$ is crossed from $F_{i}$ to $F_{i+1}$,
and a value of $i$ such that $E_{i}$ is crossed from $F_{i+1}$ to $F_{i}$.
Indeed, if $d_{i}$ denotes the distance of $o$ and $<F_{i}>$, then the fact
that $E_{i}$ is crossed from $F_{i}$ to $F_{i+1}$ implies that
$d_{i}<d_{i+1}$. Thus, if $t$ is a value of $i$ such that $d_{i}$ is minimal,
then $E_{t-1}$ is crossed from $F_{t}$ to $F_{t-1}$, and $E_{t}$ is crossed
from $F_{t}$ to $F_{t+1}$.

######  Remark 4.

As a summary, we collect the following rules to find the extended gradient at
any given boundary point $q$ of $P$.

  * •

If $q$ is an interior point of a face $F$, then
$(\nabla^{\text{ext}}N_{\partial(P)})(q)=(\nabla N_{<F>})(q)$.

  * •

If $q$ is a relative interior point of an edge $E$ of $P$, where $F_{1}$ and
$F_{2}$ denotes the two faces of $P$ containing $E$, then:

    * –

if $E$ is a followed edge, then
$(\nabla^{\text{ext}}N_{\partial(P)})(q)=(\nabla N_{<E>})(q)$;

    * –

if $E$ is a crossed edge from $F_{1}$ to $F_{2}$, then
$(\nabla^{\text{ext}}N_{\partial(P)})(q)=(\nabla N_{<F_{2}>})(q)$.

  * •

If $q$ is a vertex of $P$, then:

    * –

if $q$ is an unstable point of $P$, then
$(\nabla^{\text{ext}}N_{\partial(P)})(q)=0$;

    * –

if there is a face $F$ containing $q$ such that $(\nabla N_{<F>})(q)$ is a
tangent vector of $P$ at $q$, then
$(\nabla^{\text{ext}}N_{\partial(P)})(q)=(\nabla N_{<F>})(q)$;

    * –

in the remaining case there is a followed edge $E$ with endpoint $q$ such that
$(\nabla^{\text{ext}}N_{\partial(P)})(q)=(\nabla N_{<E>})(q)$.

It is also worth noting that for any face $F$, the gradient vector $(\nabla
N_{<F>})(q)$ is a positive scalar multiple of the vector pointing from the
orthogonal projection of $o$ onto $<F>$ to $q$.

The consequence of Remark 4 is that after the classification of edges as
crossed or followed, we can always determine which candidate gradient is the
extended gradient. There is no need to compute more than one candidate, which
makes our algorithm quicker and also less prone to numerical errors.

##  4\. Morse-Smale complex on a polyhedral surface: global properties of the
function $N_{\partial P}$

So far, we have defined a variant of the gradient vector field on the boundary
of $P$. This vector field, as already $\partial P$, is not smooth, implying
that the definition of integral curve cannot be applied to our case without
any change. Our definition is as follows, where we denote the interval
$(-\infty,0)$ by $\mathbb{R}^{-}$.

######  Definition 11.

An _ascending curve_ $c:\mathbb{R}^{-}\to\partial P$ is a curve maximal with
respect to inclusion, such that for any point $q=c(\tau)$ of $c$ the right-
hand side derivative of $c$ is equal to the extended gradient at $q$, namely
$c_{+}^{\prime}(\tau)=(\nabla^{\text{ext}}N_{\partial(P)})(q)$. We call
$\lim_{\tau\to-\infty}c(\tau)$ the _origin_ and $\lim_{\tau\to 0^{-}}c(\tau)$
the _destination_ of the ascending curve $c$.

As we will see, the origin (resp. destination) of any ascending curve is a
stable or a saddle point (resp. a saddle or an unstable point) of $P$. Thus,
for any ascending curve $c$ with origin $s$, the first segment of $c$ is a
segment on a line perpendicular to $[o,s]$, and, in particular, the derivative
$c^{\prime}(\tau)$ tends to zero as the point tends to $s$. From this, an
elementary computation shows that the curve $c$ is parameterized on an
interval unbounded from below. On the other hand, if $s$ is the destination of
$c$, then the last segment in $c$ is one not perpendicular to $[o,s]$. Thus,
$c$ is parameterized on an interval bounded from above. This shows that every
ascending curve can be parameterized on the interval $\mathbb{R}^{-}$ in a
unique way.

$s$$u$$x$$y$$z$ Figure 2. One of the infinitely many ascending curves between
the stable point $s$ and the unstable point $u$ on a cube

To study the properties of the ascending curves, we start with some
preliminary observations.

######  Remark 5.

Clearly, any point of an ascending curve is regular. On the other hand, to any
regular point $q\in\partial P$, one can assign a ‘direction of greatest
descent’ as a direction in which the one-sided directional derivative
$\lim_{t\to 0^{+}}\frac{|q+tv_{0}|}{t}=|v|$ is minimal among all unit tangent
vectors $v_{0}$ of $P$ at $q$. Similarly like in case of extended gradient, it
can be shown that this direction exists, with the corresponding derivative
being strictly negative, and also that it is the opposite of a candidate
gradient $(\nabla N_{<X>})(q)$ for some face or edge $X$ of $P$ containing
$q$. This implies that every regular point of $P$ belongs to the relative
interior of at least one ascending curve of $P$. Note that unlike in the
smooth case, a regular point may belong to more than one ascending curve. This
is true, for example, for any regular point in the relative interior of a
followed edge, where, in general, three ascending curves meet.

######  Remark 6.

By their definition, no two ascending curves can cross or split. On the other
hand, as we have seen in Remark 5, they can merge (cf. Figure 3).

$E$$c_{1}$$c_{2}$$p_{1}$$p_{2}$ Figure 3. Two ascending curves $c_{1}$ and
$c_{2}$ merging along a followed edge $E$ at $p_{2}$

Note that every ascending curve is the union of some segments in the interiors
of faces or on followed edges of $P$. Our next theorem is an important tool to
describe the geometric properties of such a curve.

######  Theorem 2.

Let $S_{1},S_{2},\ldots,S_{k}$ be a sequence of consecutive segments in an
ascending curve such that $S_{i}$ lies in the face or followed edge $X_{i}$ of
$P$, where $X_{i}\neq X_{i+1}$. Let $d_{i}$ denote the distance of $<X_{i}>$
from $o$. Then $d_{1},d_{2},\ldots,d_{k}$ is a strictly increasing sequence.

###### Proof.

For $i=1,2,\ldots,k-1$, let $H_{i}$ denote the plane spanned by $S_{i}\cup
S_{i+1}$, where the existence of $H_{i}$ follows from the condition that
$S_{i}$ and $S_{i+1}$ are not contained in the same face or edge. For
$i=1,2\ldots,k$, let $o_{i}$ denote the orthogonal projection of $o$ onto
$H_{i}$, and set $S_{i}=[q_{i-1},q_{i}]$. Let $C_{i}$ be the convex angular
region bounded by the two half lines starting at $q_{i}$ and containing
$S_{i}$ and $S_{i+1}$, respectively. By the definition of extended gradient,
the plane through $<S_{i}>$ and perpendicular to the plane $<\\{o\\}\cup
S_{i}>$ supports $P$. This implies that $o_{i}$ and $q_{i+1}$ lie in the same
open half plane of $H_{i}$ bounded by $<S_{i}>$. We obtain similarly that
$o_{i}$ and $q_{i-1}$ lie in the same open half plane of $H_{i}$ bounded by
$<S_{i+1}>$. Thus, we have that $o_{i}$ is an interior point of $C_{i}$.

We show that for any value of $i$, the distance of $<S_{i}>$ from $o$ is equal
to $d_{i}$. Indeed, this is trivial if $X_{i}$ is a followed edge. On the
other hand, if $X_{i}$ is a face, then our observation follows from the fact
that by the properties of extended gradient, the orthogonal projection $o_{i}$
of $o$ onto $<X_{i}>$ lies on $<S_{i}>$.

Now we prove the assertion. Let $1\leq i\leq k-1$. Since $S_{i}$ and $S_{i+1}$
are consecutive segments on an ascending curve, moving a point $q$ at a
constant velocity from $q_{i-1}$ to $q_{i+1}$ along $S_{i}\cup S_{i+1}$, the
distance of $q$ from $o$ strictly increases. By the Pythagorean Theorem, the
same property holds for the distance of $q$ and $o_{i}$. Thus, $q_{i}$ does
not separate the orthogonal projection of $o_{i}$ onto $<S_{i}>$ from
$q_{i-1}$, while it strictly separates the orthogonal projection of $o_{i}$
onto $<S_{i+1}>$ from $q_{i+1}$. Since $o_{i}\in C_{i}$, this yields that
$o_{i}$ is strictly closer to $<S_{i}>$ than to $<S_{i+1}>$ (Figure 4
illustrates this arrangement). Thus, the inequality $d_{i}<d_{i+1}$ follows
from the observation in the previous paragraph.

$S_{i+1}$$q_{i+1}$$S_{i}$$q_{i-1}$$C_{i}$$q_{i}$$o_{i}$ Figure 4. Segments
$S_{i}$ and $S_{i+1}$ of an ascending curve.

∎

In the following we give an upper bound for the number of segments in any
ascending curve.

######  Theorem 3.

Every ascending curve is a polygonal curve whose origin and destination are
equilibrium points of $P$, and it intersects every face and edge of $P$ in at
most one segment.

###### Proof.

First, we show that every ascending curve is rectifiable. To do it, it is
sufficient to observe that the intersection of every face $F$ of $P$ with an
ascending curve is a union of segments contained on lines passing through the
orthogonal projection $o_{F}$ of $o$ onto $<F>$. Since the Euclidean norm $N$
strictly increases along an ascending curve, this implies that the total
length of these segments is not more than the distance of the farthest point
of $F$ from $o_{F}$.

Next, we show that every ascending curve is the union of finitely many
segments. To do it, it is sufficient to show that it intersects the interior
of every face of $P$ in finitely many segments. Suppose for contradiction that
there is an ascending curve $c$ and a face $F$ such that
$\operatorname{int}(F)\cap c(\mathbb{R}^{-})$ has infinitely many components.
Since $c(\mathbb{R}^{-})$ is rectifiable, this implies that $F$ has a vertex
$q$ such that every neighborhood of $q$ contains infinitely many components of
$\operatorname{int}(F)\cap c(\mathbb{R}^{-})$. Also by rectifiability, this
implies that for some closed interval $I$, the arc $c(I)$ starts at an
interior point of $F$, crosses each edge of $P$ starting at $q$, and ends up
at an interior point of $F$. Note that this implies that each edge of $P$
starting at $q$ is a crossed edge, and the direction of the crossing
corresponds to the cyclic order of the faces around $q$. But this contradicts
Remark 3.

Finally, the fact that an ascending curve intersects every face and edge in at
most one segment follows from Theorem 2 and the fact that it is a polygonal
curve. ∎

Now we are ready to define the ascending and the descending manifolds.

######  Definition 12.

The _ascending (resp. descending) polyhedral manifold_ of an equilibrium point
$x$ is the union of $x$ and all ascending curves with $x$ as their origin
(resp. destination). We denote the ascending (resp. descending) manifold of
$x$ by $A(x)$ (resp. $D(x)$).

Our first result is Theorem 4.

######  Theorem 4.

If $P\subset\mathbb{R}^{3}$ is a nondegenerate convex polyhedron, then for any
unstable point $y\in\partial P$, the descending manifold $A(s)$ is open in
$\partial P$.

The proof of Theorem 4 is based on Lemma 1.

######  Lemma 1.

Let $P$ be nondegenerate, and let $q$ be a vertex of $P$ which is not an
equilibrium point. Let $q^{\prime}$ be a point on the ascending curve through
$q$ such that $q^{\prime}$ is not a vertex of $P$, and $[q,q^{\prime}]$
belongs to $\partial P$. Then, for every neighborhood $U$ of $q^{\prime}$ in
$\partial P$ there is a neighborhood $V\subset\partial P$ of $q$ such that the
ascending curve through a point of $V$ intersects $U$.

###### Proof.

First, we show that there is a unique candidate gradient at $q$. Let
$F_{1},\ldots,F_{k}$ denote the faces of $P$ containing $q$ in cyclic order.
Let $E_{i}=F_{i-1}\cap F_{i}$ for $i=1,2,\ldots,k$. Let us call an edge
$E_{i}$ _descending_ if the one-sided directional derivative at $q$ in the
direction of $E_{i}$ is negative, and let us call it nondescending otherwise.
We have seen in the proof of Theorem 1 that if some $(\nabla N_{<F_{i}>})(q)$
is a candidate gradient, then $(\nabla N_{<F_{i}>})(q)$ is the extended
gradient at $q$, and there is no candidate gradient generated by any other
face $F_{j}$. Now we show more, namely that apart from the face/edge
generating the extended gradient, all nondescending edges are crossed edges.
Before doing it, recall that by Remark 2, we may assume that the nondescending
edges of $P$ at $q$ are $E_{1},E_{2},\ldots,E_{j}$ for some $1\leq j<k$.

_Case 1_ : $(\nabla^{ext}N_{\partial(P)})(q)=(\nabla N_{<F_{i}>})(q)$ for some
value of $i$. Then at least one of $E_{i}$ and $E_{i+1}$ is nondescending, and
hence, we may assume that $1\leq i\leq j$. First, observe that since $(\nabla
N_{<F_{i}>})(q)$ points towards the interior of $F_{i}$, the lines through
$E_{i}$ and $E_{i+1}$ separate this vector from the orthogonal projection of
$o$ onto $<F_{i}>$. Thus, $E_{i}$ is a crossed edge from $F_{i-1}$ to $F_{i}$,
and $E_{i+1}$ is a crossed edge from $F_{i+1}$ to $F_{i}$, respectively.

We show by induction on $t$ that $E_{t}$ is a crossed edge from $F_{t-1}$ to
$F_{t}$, for $t=1,2,\ldots,i$. Note that we have already shown it for $t=i$.
Assume that $E_{t+1}$ is a crossed edge from $F_{t}$ to $F_{t+1}$ for some
$t\geq 1$. Let $o_{t}$ denote the orthogonal projection of $o$ onto $<F_{t}>$.
The fact that $E_{t+1}$ is crossed from $F_{t}$ to $F_{t+1}$ implies that
$<E_{t+1}>$ does not separate $o_{t}$ and $F_{t}$. Furthermore, the fact that
both $E_{t+1}$ and $E_{t}$ are nondescending yields that the angle between
$E_{t+1}$ and $[o_{t},q]$, as well as the angle between $E_{t}$ and
$[o_{t},q]$, are both non-acute. But from this we have that $<E_{t}>$
separates $o_{t}$ and $F_{t}$, which yields that $E_{t}$ is crossed from
$F_{t-1}$ to $F_{t}$ (see Figure 5 for reference.). Repeating this argument
for $i+1\leq t\leq j$, we obtain that all nondescending edges at $q$ are
crossed.

$q$$<E_{t+1}>$$<E_{t}>$$F_{t+1}$$F_{t}$$F_{t-1}$$o_{t}$ Figure 5. A single
step of the induction

_Case 2_ : $(\nabla^{ext}N_{\partial(P)})(q)=(\nabla N_{<E_{i}>})(q)$ for some
value of $i$. In this case a similar argument yields the desired statement.

We remark that the argument in Case 1 also shows that there are no two
consecutive edges $E_{t}$, $E_{t+1}$ which are both descending, and $E_{t}$ is
crossed from $F_{t}$ to $F_{t-1}$, and $E_{t+1}$ is crossed from $F_{t}$ to
$F_{t+1}$. This observation, combined with the properties of nondescending
edges proved above, yields the assertion. ∎

###### Proof of Theorem 4.

Let $c:\mathbb{R}^{-}\to\partial P$ be an ascending curve with the unstable
point $y$ as its destination, and let $q=c(\tau)$ be a point of $c$. We need
to show that $q$ has a neighborhood $V$ such that for any point $q^{\prime}\in
V$, the destination of the ascending curve through $q^{\prime}$ is $y$. By
Theorem 3, $c([\tau,0))\cup\\{y\\}$ is the union of finitely many closed
segments such that

  1. (i)

each segment is a subset of a face or a followed edge of $P$

  2. (ii)

the endpoint of each segment, apart from $q$, is either a relative interior
point of an edge, or a vertex of $P$.

Thus, it is sufficient to show that if $[x_{j},x_{j+1}]$ is one of these
segments with $x_{j}$ preceding $x_{j+1}$ on $c$, then for every neighborhood
$U$ of $x_{j+1}$ there is a neighborhood $V$ of $x_{j}$ such that for any
$q^{\prime}\in V$, the ascending curve through $q^{\prime}$ intersects $U$.
This statement is trivial if $x_{j}$ is a relative interior point of an edge.
Assume that $x_{j}$ is a vertex, and let $x^{\prime}$ be a relative interior
point of $[x_{j},x_{j+1}]$. Then, by the above observation, for any
neighborhood $U$ of $x_{j}$ there is a neighborhood $V^{\prime}$ of
$x^{\prime}$ such that any ascending curve intersecting $V^{\prime}$
intersects $U$, and by Lemma 1, the same statement holds for $x_{j}$ and
$x^{\prime}$ in place of $x^{\prime}$ and $x_{j+1}$, respectively. ∎

######  Definition 13.

The intersection of an ascending and a descending polyhedral manifold, i.e. a
set of the form $A(x)\cap D(y)$ for some (not necessarily distinct)
equilibrium points $x,y$ of $P$, is called a _cell_ of the Morse-Smale complex
of $P$. The _Morse-Smale complex of $P$_ is defined as the family consisting
of its cells.

######  Definition 14.

An ascending curve is _isolated_ if it does not belong to both a descending
and an ascending polyhedral manifold.

Recall that for generic smooth convex bodies, isolated integral curves
correspond to integral curves starting or ending at saddle points of the body.
The following example shows that the same statement does not hold for every
nondegenerate convex polyhedron $P$.

######  Example 1.

Let $H^{+}$ and $H^{-}$ be two closed half planes in $\mathbb{R}^{3}$ such
that their intersection is the line $L=\\{(1,t,0):t\in\mathbb{R}\\}$, they are
symmetric to the $(x,y)$-plane, and their convex hull $P_{0}$ contains $o$.
Let $s_{1}=(1,0,0)$, and let $H$ be a plane parallel to the $z$-axis such that
it intersects the $x$-axis at a point $(1+\varepsilon,0,0)$ with some
sufficiently small $\varepsilon>0$, and passes through the point $q=(1,1,0)$.
Let $s_{2}=(x,y,0)$ be a point of $H$ with $y>1$, and let $H^{\prime}$ be a
plane containing the line through $s_{2}$, parallel to the $z$-axis, such that
$s_{2}$ is a saddle point of the truncation of $P_{0}$ with $H$ and
$H^{\prime}$. Then the polygonal curve $[s_{1},q]\cup[q,s_{2}]$ is an
ascending curve from $s_{1}$ to $s_{2}$, corresponding to a saddle-saddle
connection. Furthermore, if $o_{+}$ is the orthogonal projection of $o$ onto
$H^{+}$, then $\operatorname{conv}\\{o_{+},s_{1},q\\}$ is contained in
$D(s_{2})$.

$s_{1}$$q$$s_{2}$$o_{+}$$x$$y$$z$ Figure 6. The polyhedron bounded by one
possible choice of $H^{+},H^{-},H$ and $H^{\prime}$ in Example 1.

######  Remark 7.

Clearly, for any nondegenerate convex polyhedron $P$ every saddle point $s$ is
a relative interior point of a followed edge $E$, implying that all ascending
curves ending at $s$ reach it in one of the two directions perpendicular to
$E$, and all ascending curves starting at $s$ start along the edge $E$. Thus,
for any nondegenerate convex polyhedron, the ascending and the descending
manifolds at any saddle point cross.

Based on Example 1 and Remark 7, we introduce the following notion. Before
that, we recall that a _simplicial_ convex polyhedron $P\subset\mathbb{R}^{3}$
is defined as a convex polyhedron having only triangular faces, and observe
that if $P=\operatorname{conv}\\{q_{1},q_{2},\ldots,q_{k}\\}$ is a
nondegenerate convex polyhedron with equilibrium points
$s_{1},s_{2},\ldots,s_{m}$, and for any sufficiently small perturbation
$P^{\prime}=\operatorname{conv}\\{q^{\prime}_{1},q^{\prime}_{2},\ldots,q^{\prime}_{k}\\}$,
with the point $q_{i}^{\prime}$ being the perturbation of $q_{i}$,
$P^{\prime}$ is a nondegenerate convex polyhedron with $m$ equilibrium points
$s^{\prime}_{1},s^{\prime}_{2},\ldots,s^{\prime}_{m}$, and for a suitable
choice of indices, $s^{\prime}_{j}$ has the same type as that of $s_{j}$, and
their distance is small.

######  Definition 15.

Let $P\subset\mathbb{R}^{3}$ be a simplicial, nondegenerate convex polyhedron,
and let the set of equilibrium points of $P$ be $\operatorname{Eq}(P)$. If,
for any vertex $q$ of $P$ with $q\in A(x)\cap D(y)$ and
$x,y\in\operatorname{Eq}(P)$, and any sufficiently small perturbation
$P^{\prime}$ of $P$, we have $q^{\prime}\in A(x^{\prime})\cap D(y^{\prime})$,
where $q^{\prime}$ is the vertex of $P$ corresponding to $q$, and
$x^{\prime},y^{\prime}$ are the equilibrium points of $P^{\prime}$
corresponding to $x$ and $y$, respectively, then we say that $P$ is _generic_
, or _Morse-Smale_.

######  Theorem 5.

Let $P\subset\mathbb{R}^{3}$ be a generic polyhedron. Then the following
holds:

  1. (i)

the descending manifold of any saddle point $s$ of $P$ contains no vertex of
$P$;

  2. (ii)

the descending manifold of any saddle point consists of exactly two ascending
curves;

  3. (iii)

the $2$-dimensional cells of the Morse-Smale complex of $P$ are bounded by
four ascending curves, and the four endpoints of these curves are a stable, a
saddle, an unstable and a saddle point in this cyclic order.

  4. (iv)

the isolated ascending curves are exactly those starting or ending at a saddle
point;

###### Proof.

Let $P$ be generic. Suppose for contradiction that there is an ascending curve
$c$ of $P$ ending at a saddle point $s$ that contains a vertex. Let us denote
the open segments of $c(\mathbb{R}^{-})$ by $S_{1},S_{2},\ldots,S_{k}$ in
consecutive order. Let the endpoints of $S_{i}$ be $q_{i}$ and $q_{i+1}$. By
the properties of saddle points, $S_{k}$ lies in the interior of a face of
$P$. Thus, $q_{k}$ is either a vertex or a relative interior point of a
crossed edge. In the latter case $S_{k-1}$ lies in the interior of a face of
$P$. Again, $q_{k-1}$ is either a vertex, or a relative interior point of a
crossed edge of $P$. Repeating this argument we obtain that the last vertex
$q_{i}$ of $P$ on $c$ has the property that for all $i<j\leq k$, the point
$q_{j}$ is a relative interior point of a crossed edge of $P$. Now, let
$F^{\prime}$ be the face containing the segment $[q_{i},q_{i+1}]$, and let
$o^{\prime}$ denote the orthogonal projection of $o$ onto $<F^{\prime}>$. Let
us perturb $q_{i}$ by moving it in the plane $<F^{\prime}>$ to a point
$q^{\prime}_{i}$ such that $q_{i}$, $q_{i}^{\prime}$ and $o^{\prime}$ are not
collinear. Then it is easy to see that the ascending curve through
$q^{\prime}_{i}$ on the perturbed polyhedron meets the edge of $s$ at a point
different from $s$, and thus, it cannot end at $s$. But this contradicts our
assumption that $P$ is generic, implying (i).

Now, assume that $P$ is a simplicial convex polyhedron with the property that
the descending manifold of any saddle point $s$ contains no vertex other than
$s$. Note that any saddle point $s$ is a relative interior point of a followed
edge. Thus, there are exactly two ascending curves starting at $s$, and they
run on the edge of $s$ until they reach the endpoints of this edge, implying
that any ascending curve starting at a saddle point contains a vertex of $P$.
On the other hand, the ascending curves ending at $s$ reach it along the two
segments in $\partial P$ perpendicular to the edge of $P$. By our assumption
and the consideration in the previous paragraph, these segments belong to
unique ascending curves whose all vertices lie on crossed edges of $P$. Thus,
for any saddle point $s$ there are exactly two ascending curves starting at
$s$, and these contain vertices of $P$, and exactly two ascending curves
ending at $s$, and these do not contain vertices of $P$. This implies, in
particular, that the other endpoints of these curves are not saddle points.
Thus, the ascending curves starting at $s$ end at unstable, and the ones
ending at $s$ start at stable points of $P$. From this, (ii) readily follows.

Note that since ascending curves cannot split, the two ascending curves ending
at $s$ are necessarily disjoint, but the two curves starting at $s$ may merge
later. Nevertheless, the above facts are sufficient to show that, after
removing all these curves from $\partial P$, any component is bounded by four
arcs of such curves, whose endpoints are a stable, a saddle, an unstable and a
saddle point in this cyclic order. Clearly, any such region $R$ is bounded by
$4k$ arcs for some $k\in\mathbb{Z}^{+}$, and the sequence of the types of the
endpoints of the corresponding curves are stable, saddle, unstable and saddle
repeated $k$ times. Observe that by its definition, $R$ is an open subset of
$\partial P$. On the other hand, by Theorem 4 and since $R$ is open, $R\cap
D(y)$ is an open subset of $R$ for any unstable point $y$ being the
destination of an ascending curve in $\partial P$. Thus, the connectedness of
$R$ yields that $k=1$ and (iii) holds, implying also (iv). ∎

######  Corollary 1.

By Theorem 5, the Morse-Smale complex of a generic convex polyhedron $P$
consists of the following types of cells.

  1. (1)

The equilibrium points of $P$, called the _vertices_ of the Morse-Smale
complex.

  2. (2)

The closures of the isolated ascending curves, namely the curves starting or
ending at a saddle point. These cells are called _edges_ of the complex.

  3. (3)

for a stable point $s$ and an unstable point $u$, the union of all ascending
curves starting at $s$ and ending at $u$, and also the four isolated ascending
curves intersecting the boundary of this union in an arc. These cells are
called _faces_ of the complex.

We note that a face of a Morse-Smale complex is not necessarily homeomorphic
to a disc. This happens if two ascending curves in the boundary of the face
merge. The existence of such a face in a Morse-Smale complex is equivalent to
the property that the complex is not a CW-decomposition of
$\operatorname{bd}P$.

######  Definition 16.

Let $P\subset\mathbb{R}^{3}$ be a generic convex polyhedron. The topological
graph $G$ on $\partial P$ whose vertices are the equilibrium points of $P$,
and whose edges are the isolated ascending curves of $P$, is called the
_Morse-Smale graph_ generated by $P$. This graph can be regarded as a _$3$
-colored_ quadrangulation of $\mathbb{S}^{2}$, where the ‘colors’ of the
vertices are the three types of a critical point.

##  5\. An algorithm to compute Morse-Smale complex

It is a natural problem to determine the Morse-Smale graph $G$ of a generic
convex polyhedron $P$. Our results in Sections 3 and 4 provide an algorithmic
answer for this problem:

  1. Step 1

: Find the orthogonal projections of $o$ onto the line of each edge of $P$.

  2. Step 2

: Find which edge is followed, which edge is crossed.

  3. Step 3

: Find the saddle points of $P$.

  4. Step 4

: For each saddle point, find the ascending curves ending there. Note that by
genericity, there are exactly two such curves for each saddle point, and they
intersect only crossed edges.

  5. Step 5

: For each saddle point, find the ascending curves starting there.

We implemented the above algorithm and we illustrate it on the following
example. Let $P_{\text{ex}}$ be a polyhedron constructed as follows:

  1. (1)

Consider a regular octagon $O_{1}\subset\mathbb{R}^{3}$ with diameter $d=2$,
lying in a plane parallel to the $(x,y)$ plane and with center $(0,0,1)$.
Denote the vertices of $O_{1}$ by $v_{i}$, $(i=1,2,\ldots,8)$.

  2. (2)

Project $O_{1}$ orthogonally onto the plane $z=-1$ to obtain $O_{2}$.

  3. (3)

Rotate $O_{2}$ by $\varphi=\frac{\pi}{20}$ clockwise and denote the vertices
of the rotated octagon by $v_{i}$, $(i=9,10,\ldots,16)$.

  4. (4)

Add the points $v_{0}=(0,0,1.2),v_{17}=(0,0,-1.2)$.

  5. (5)

Define $P_{\text{ex}}$ as the convex hull of the points $\\{v_{i}\\}$,
$(i=0,1,\ldots,17)$.

To equip $P_{\text{ex}}$ with a radial distance function, we select the point
$o_{\text{ex}}=(0.5,0.5,0.5)$ as origin (in this case the origin, as a center
of mass, corresponds to inhomogeneous material distribution). Figure 7 shows
the ascending curves of $P_{\text{ex}}$ and we can see that $P_{\text{ex}}$ is
generic.

Figure 7. Isolated ascending curves on $P_{\text{ex}}$ with respect to
$o_{\text{ex}}$. Red, green and blue points represent unstable, stable and
saddle/̄type equilibria, respectively. Stable/̄saddle isolated ascending
curves are shown in green, saddle/̄unstable isolated ascending curves are
shown in red.

##  6\. Concluding remarks and summary

Before summarizing our results we make some general remarks and state an open
question.

###  6.1. Some remarks and a question

######  Remark 8.

We have seen in Theorem 4 that for any nondegenerate convex polyhedron, the
descending manifold of any unstable point is open. Nevertheless, there are
even generic convex polyhedra with stable points whose ascending manifolds are
not open. This happens, for example, if two ascending curves in the boundary
of a $2$-cell of the Morse-Smale complex merge. Figure 8 shows a face of $P$
where this situation can arise.

$s$$h_{1}$$h_{2}$$q$ Figure 8. The saddle points $h_{1}$ and $h_{2}$ are
destinations of two isolated ascending curves from the stable point $s$. They
are also origins of isolated ascending curves passing through the vertex $q$.
If $q$ is unstable then the $2$-cell bounded by the previously mentioned
isolated ascending curves is open, otherwise it is not.

Before our next remark, let us recall a few concepts from Baire category
theory. A topological space is called a _Baire space_ , if the union of every
countably many closed sets with empty interior has empty interior. In
particular, the family of convex polyhedra with at most $n$ vertices is a
complete metric space, and thus, it is a Baire space [17]. A set in a complete
metric space is called _typical_ or _residual_ if its complement is a
countable union of nowhere dense sets. In particular, if a set in a complete
metric space is open and everywhere dense, it is typical.

######  Remark 9.

Let $\mathcal{P}_{m}$ denote the family of convex polyhedra in
$\mathbb{R}^{3}$ with at most $m$ vertices. Observe that $\mathcal{P}_{m}$ is
a complete metric space with respect to Hausdorff distance, and thus, it is a
Baire space. Furthermore, a sufficiently small perturbation of the vertices of
a generic convex polyhedron with $m$ vertices yields a generic polyhedron with
$m$ vertices, and any convex polyhedron with at most $m$ vertices can be
approximated arbitrarily well by such a polyhedron. Thus, in Baire category
sense, a typical convex polyhedron in $\mathcal{P}_{m}$ with at most $m$
vertices is a generic convex polyhedron with $m$ vertices.

######  Remark 10.

The computation of Morse-Smale complexes is a fast growing area in data
visualization and some algorithms have even benefited from GPU acceleration
[18]. Apparently, the speed of such algorithms is essential, we make some
simple observations about our algorithm. Note that if $P$ has $n$ vertices, it
has at most $2n-4$ faces and $3n-6$ edges, and each vertex, edge, face
contains at most one equilibrium point. Thus, Steps 1-3 in our algorithm can
be carried out in $O(n)$ time, and by Theorem 3, Steps 4-5 can be carried out
in $O(n^{2})$ time. Clearly, at least $\Omega(n)$ steps are necessary to find
the Morse-Smale graph of $P$. While the exact magnitude of a fastest algorithm
that solves this problem is an open question (see below), we note that on all
test examples (with a couple hundred vertices per polyhedron on average) our
algorithm, running on a single core of a standard laptop CPU, computed the
Morse-Smale complex well under a second.

######  Problem 1.

Find the exact magnitude of a fastest algorithm that finds the Morse-Smale
graph of any generic convex polyhedron.

###  6.2. Summary

Motivated by geophysical applications, in this paper we extended Morse-Smale
theory to a convex polyhedron $P$, interpreted as a scalar (radial) distance
measured from a point $o$ in its interior. We defined the polyhedral Morse-
Smale complex and the Morse-Smale graph $G$ associated with $P$ and $o$ and we
built an algorithm to compute $G$. In geophysical applications, $o$ is the
center of mass of the particle and the scanned image of the particle is a
polyhedron, so this algorithm associates one topological graph to a scanned
particle.

In classical Morse-Smale theory the Morse-Smale complex is defined by a
function $f:\mathcal{M}\to\mathbb{R}$, acting on the compact manifold
$\mathcal{M}$ and in the classical case $f$ is considered to be smooth. From
the abstract point of view, the natural extension of this theory is to extend
the class of functions $f$ to be considered and this path was followed in [2]
and [10] where the authors considered piecewise linear functions. Here we took
a slightly different approach: instead of defining a new class of functions we
would discuss, we considered the geometric image of the function as a given
object. In our case, this image was a convex polyhedron and the function $f$
was defined on the sphere as a radial distance, measured from a point. We hope
that this geometric approach may lead to other potential generalizations of
Morse-Smale theory.

## References

  * [1] Vladimir Arnold, _Topological classification of Morse functions and generalisations of Hilbert’s 16-th problem_ , Mathematical Physics, Analysis and Geometry 10 (2007), no. 3, 227–236.
  * [2] Thomas Francis Banchoff, _Critical points and curvature for embedded polyhedral surfaces_ , The American Mathematical Monthly 77 (1970), no. 5, 475–485.
  * [3] G. Domokos, A. Á. Sipos, Gy. M. Szabó, and P. L. Várkonyi, _Formation of sharp edges and planar areas of asteroids by polyhedral abrasion_ , The Astrophysical Journal 699 (2009), no. 1, L13–L16.
  * [4] Gábor Domokos, _Natural numbers, natural shapes_ , Axiomathes (2018).
  * [5] Gábor Domokos, Philip Holmes, and Zsolt Lángi, _A genealogy of convex solids via local and global bifurcations of gradient vector fields_ , J. Nonlinear Sci. 26 (2016), no. 6, 1789–1815. MR 3562394
  * [6] Gábor Domokos, Flórián Kovács, Zsolt Lángi, Krisztina Regős, and Péter T. Varga, _Balancing polyhedra_ , Ars Math. Contemp. 19 (2020), no. 1, 95–124. MR 4173667
  * [7] Gábor Domokos and Zsolt Lángi, _The isoperimetric quotient of a convex body decreases monotonically under the Eikonal abrasion model_ , Mathematika 65 (2019), no. 1, 119–129.
  * [8] Gábor Domokos, Zsolt Lángi, and Tímea Szabó, _A topological classification of convex bodies_ , Geometriae Dedicata 182 (2016), no. 1, 95–116.
  * [9] Gábor Domokos, András Sipos, Tímea Szabó, and Péter Várkonyi, _Pebbles, shapes and equilibria_ , Mathematical Geosciences 42 (2010), Article No. 29.
  * [10] Herbert Edelsbrunner, John Harer, and Afra Zomorodian, _Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds_ , Discrete & Computational Geometry 30 (2003), no. 1, 87–107.
  * [11] Robin Forman, _A user’s guide to discrete Morse theory_ , Seminaire Lotharingien de Combinatoire 48 (2002), B48c.
  * [12] Attila Gyulassy, Peer-Timo Bremer, Bernd Hamann, and Valerio Pascucci, _A practical approach to Morse-Smale complex computation: Scalability and generality_ , IEEE Transactions on Visualization and Computer Graphics 14 (2008), no. 6, 1619–1626.
  * [13] Zsolt Lángi, _A solution to some problems of Conway and Guy on monostable polyhedra_ , 2020.
  * [14] Balázs Ludmány and Gábor Domokos, _Identification of primary shape descriptors on 3d scanned particles_ , Periodica Polytechnica Electrical Engineering and Computer Science 62 (2018), no. 2, 59–64.
  * [15] J. Milnor, _Morse theory_ , Based on lecture notes by M. Spivak and R. Wells. Annals of Mathematics Studies, No. 51, Princeton University Press, Princeton, N.J., 1963. MR 0163331
  * [16] Tímea Novák-Szabó, András Árpád Sipos, Sam Shaw, Duccio Bertoni, Alessandro Pozzebon, Edoardo Grottoli, Giovanni Sarti, Paolo Ciavola, Gábor Domokos, and Douglas J. Jerolmack, _Universal characteristics of particle shape evolution by bed-load chipping_ , Science Advances 4 (2018), no. 3.
  * [17] Rolf Schneider, _Convex bodies: the Brunn-Minkowski theory_ , expanded ed., Encyclopedia of Mathematics and its Applications, vol. 151, Cambridge University Press, Cambridge, 2014. MR 3155183
  * [18] Varshini Subhash, Karran Pandey, and Vijay Natarajan, _GPU parallel computation of Morse-Smale complexes_ , 2020 IEEE Visualization Conference (VIS), 2020, pp. 36–40.
  * [19] K. Uhlenbeck, _Morse theory by perturbation methods with applications to harmonic maps_ , Trans. Amer. Math. Soc. 267 (1981), no. 2, 569–583. MR 626490
  * [20] Péter Várkonyi and Gábor Domokos, _Static equilibria of rigid bodies: Dice, pebbles, and the Poincare-Hopf theorem_ , Journal of Nonlinear Science 16 (2006), 255–281.
  * [21] Edward Witten, _Supersymmetry and Morse theory_ , J. Differential Geometry 17 (1982), no. 4, 661–692 (1983). MR 683171