# Detecting Abnormal Health Conditions in Smart Home Using a Drone

Pronob Kumar Barman  Department of Information Systems
University of Maryland Baltimore County
Baltimore, USA

###### Abstract

Nowadays, detecting aberrant health issues is a difficult process. Falling,
especially among the elderly, is a severe concern worldwide. Falls can result
in deadly consequences, including unconsciousness, internal bleeding, and
often times, death. A practical and optimal, smart approach of detecting
falling is currently a concern. The use of vision-based fall monitoring is
becoming more common among scientists as it enables senior citizens and those
with other health conditions to live independently. For tracking,
surveillance, and rescue, unmanned aerial vehicles use video or image
segmentation and object detection methods. The Tello drone is equipped with a
camera and with this device we determined normal and abnormal behaviors among
our participants. The autonomous falling objects are classified using a
convolutional neural network (CNN) classifier. The results demonstrate that
the systems can identify falling objects with a precision of 0.9948.

###### Index Terms:

Ryze Tello, CNN, Fall detection

##  I Introduction

According to the World Health Organization (WHO), over 680,000 fatal falls
occur worldwide each year, with the majority of victims being individuals over
the age of 65[1]. Falls are the leading cause of fatal injuries in older
adults and are especially dangerous for those living independently. In order
to address this issue, the purpose of our study is to detect falls within the
home. With this, we hope to reduce the number of deaths associated with falls
and allowing the elderly and others that are prone to falls to still live
independently.

An unmanned aerial vehice (UVA), often referred to as a drone is an aircraft
without any humans on board. Drones are often used in a number of situations
such as emergency rescue, asset protection, and wildlife monitoring, but they
can do more. Introducing a drone into the home increases vigilance that allows
victims to receive the help that they need in an appropriate amount of time.
More specifically, the Tello drone consists of a built-in camera that will be
used for tracking, surveillance, and rescue. Through our study, we believe
that a drone can be an effective smart home device to help reduce mortality
rates and the need of in-home aids for the elderly and others prone to falls.

###  I-A Proposed Approach

Although our current solution only solves the fall detection aspect, we
envisioned our project to have an end-to-end solution based on person
detection and fall classification.

As seen in Figure 1 below, our solution accounts for all possible outcomes of
person detection and fall classification. The drone will constantly be
scanning the area and taking images and videos and if a person is detected we
move on to feature extraction to gather all relevant information on the
human’s movement. If a fall is detected the user will be asked whether or not
they need help. If the human answers yes or does not give an answer at all, an
alarm will be triggered, contacting emergency personnel along with family
members programmed into the system. However, if a person or a fall is not
detected, the drone will go back to the beginning phase to continue its
analysis. Lastly, if there is any uncertainty, the drone will re-evaluate by
moving to a new location to reassess the situation.

As previously mentioned, our current solution does not offer an end-to-end
solution, but this serves as the framework we envisioned our project to
follow.

Figure 1: Proposed Approach Flowchart

###  I-B Related Work

Previous studies have presented fall detection systems used to detect patient
falls. While other studies have designed a UAV to monitor patients’ behavior
in order to alert emergency personnel for victims of falls. This section
covers previous work related to UAVs and other fall detection systems such as
robots.

####  I-B1 Work Related to UAV Systems

Previous studies have designed UAVs to transport medical supplies and
medication to patients[2]. Other studies have adopted UAVs to have an advanced
first aid system to monitor elderly patients with heart conditions putting
them at risk of falls. These authors proposed a wearable sensor-based fall
detection device (FDD) designed for monitoring HR and detecting falls, and a
call emergency center (CEC) to receive messages from the FDD and plan the
UAV’s path[3]. The FDD is attached to the patient’s upper arm and once it
detects a fall and the HR is measured as abnormal, the FDD sends a message to
the CEC which includes the patient’s personal information. The advanced first
aid system provides first aid to the patients that are prone to falling[3].
The first aid package is then delivered to the patient via the UAV based on
the GPS coordinates of the FDD.

The results illustrated excellent performance where the proposed FDD had an
accuracy of 99.2% when distinguishing between falls and normal activities.
Furthermore, in terms of HR monitoring, results show that the proposed
algorithm for the FDD was successful and can be used for monitoring the
elderly who have atrial fibrillation (irregular heartbeat), which causes
falls[3]. Moreover, the GPS was accurate at determining the patient’s location
at the time of the fall.

In the future, researchers are interested in the development of the entire
system, including the design of a system that works autonomously to receive
patient information and send a UAV without human intervention[3].

####  I-B2 Work Related to Robots

Previous studies have developed mobile robots that monitors one person in a
single view with constant supervision, while other studies proposed a more
robust system. Saturnino Maldonado-Bascon et al., proposed autonomous mobile-
patrol robots that integrate privacy protection and only necessary
supervision. The robot was designed to autonomously patrol an indoor
environment and when a fall is detected, an alarm is activated[4]. This study
also believes that vision-based systems offer more advantages than wearable
sensor-based systems. However, in vision-based systems, cameras play a
critical role. In order to solve the problem of occlusion, the system should
be equipped with multiple cameras in order to monitor and assess a number of
angles[4].This study combines the YOLOv3 algorithm based on a convolutional
neural network (CNN) for person detection and a support vector machine (SVM)
for fall classification[4]. The basis for this study’s fall detection approach
was an assistance robot named LOLA, that was designed entirely by the research
team. This device was developed to monitor and help the elderly and others
with functional disabilities living alone. Not only is LOLA an assistive
robot, but it also serves as a rollator for assistance with walking or as a
table[4].

When evaluating the performance of the end-to-end solution, results show that
the fall classifier detected 390 true positives, 1 false negative, and 0 false
positives, indicating values of 100% and 99.74% for precision and recall,
respectively[4]. Overall, results indicate that the system had a high success
rate in fall detection.

In the future, researchers hope to investigate and improve upon occlusion
detection and possibly merging person detection and fall classification into
one CNN[4].

##  II Data Collection

In our study we utilized two datasets. The first dataset is available to the
public and was used to train our model. The second dataset is our primary
dataset that was collected from two male participants aged 12 and 16 years
old. We collected the data in two locations:

  * •

living room one

  * •

living room two

Furthermore, we followed IRB standards since we were collecting data from
human participants.

(a) Not Fall

(b) Fall

Figure 2: Sample Images of Fall Detection

###  II-A Design of Hardware

We used a Ryze Tello drone as a low-cost hardware platform to perform our
study. The Ryze Tello drone costs approximately 100 USD and is a small and
light weight drone that weighs approximately 80 g (with propellers and
battery). The full specifications are given below:

  * •

Dimensions: 98×92.5×41 mm

  * •

Propeller: 3 inches

  * •

Built-in Functions: Range Finder, Barometer, LED, Vision System, 2.4 GHz
802.11n Wi-Fi, 720p Live View

  * •

Port: Micro USB Charging Port

  * •

Detachable Battery: 1.1Ah/3.8V

Figure 3: Ryze Tello Drone

The drone can be operated both indoors and outdoors. A single camera, an IMU
with a 3-axis gyroscope, 3-axis accelerometer, and 3-axis magnetometer, and a
pressure and IR-based altitude sensors are all incorporated into the drone.
The front-facing camera features an 8-megapixel sensor and can record video at
a resolution of $1280\times 720$ at 30 frames per second.

###  II-B Device Setup and Requirements

The Tello drone is a ready-to-use device that requires no additional setup. In
order to control the drone, a compatible mobile phone is required along with
the ’Tello’ app and wifi. The drone is a battery charged device, lasting
approximately 12-13 minutes.

###  II-C Study Design

As previously mentioned, our study consisted of two male participants, aged 12
and 16 years old. This study took place in a single-family home with
approximately 10 inches ceilings. The images and videos were captured in two
different rooms within the home, one with more open space and one with less
space. The study was carried out over a span of two weeks, with sessions
ranging from 15 minutes to an hour depending on drone complications,
participant poses and assessments, and retakes.

###  II-D Participant Instructions

The instructions that our participants followed were straightforward. Using
our own intuition, we first determined what positions people usually are in
after a fall and took note of it. We then showed our participants an image of
the position and instructed them to reenact it. Once our participants were in
position, we powered up the drone, captured the videos and images, assessed
them and then asked our participants to move on to the next position.

##  III Proposed Methodology

In this section we briefly discuss fall detection systems and methods.

###  III-A Convolutional Neural Network (CNN)

We propose a deep learning-based approach for detecting whether or not a
person has fallen using RGB photographs. For feature extraction, we employ a
CNN algorithm111The proposed idea is taken from [8] with 6 blocks and a
header. Conv2D Layer with ReLU activation and MaxPooling2D are included in
each block. We begin with 16 troops and increase by 2 units every 2 blocks:

$16->16->32->32->64->64$

We flatten the result after feature extraction, add a Dense layer of 32 units,
and utilize sigmoid activation for classification.

The CNN model uses visual representations based on the RGB image and
segmentation and learns high-level embedding features for fall recognition. We
explain the individual components of the conceptual structure in detail below.

Figure 4: CNN Architecture [8]

Figure 5: Overall Architecture[5]

###  III-B Training and Implementation

Initialize the weights of the nodes in the FallNet network model at the start.
The weights for the convolutional layer are started in this model using the
weights from the following embedding layer, which have a zero-mean gaussian
distribution (SD= 0.01 and bias=0) [5]. We utilize the Adam optimizer with a
learning rate of 0.0001 and a loss function of Binary Crossentropy to train
our model. The proposed system is built on the basis of Torch, Keras
libraries[6, 7]. Figure 6 depicts the convolution layers, which range from 1-6
convolutions.

Figure 6: Summary of the FallNet Model [8]

##  IV Experimental Results

###  IV-A Datasets

At first, we utilized this publicly available dataset data to train our model
for fall detection. The acquired data was then used to validate the pre-
trained model. The accuracy and loss plot was obtained after 5 epochs.

###  IV-B Evaluation Metrics

The loss is the value that a neural network tries to minimize in deep
learning: it’s the difference between the ground truth and the forecasts. The
neural network learns to decrease this distance by altering weights and biases
in a way that minimizes the loss.

In regression problems, for example, you have a continuous target, such as
height. The discrepancy between your predictions and the actual height is what
you wish to minimize. You can use mean absolute error as a loss to tell the
neural network what it should be minimizing.

It’s a little more complicated in terms of classification, but it’s still
comparable. Probability is used to predict classes and the neural network
minimizes the possibility of assigning a low probability to the real class in
classification. Typically, the loss is categorical crossentropy.

The difference between loss and validation loss is that the former is applied
to the train set, while the latter is applied to the test set. As a result,
the latter is a useful indicator of how the model performs on data that hasn’t
been seen before. Use validation data=[$x_{test},y_{test}$] or validation
split=0.2 to get a validation set.

To avoid overfitting, it’s advisable to rely on the validation loss. When the
model fits the training data too closely, overfitting occurs, and the loss
continues to decrease while the val loss remains stale or grows. When the
validation loss stops lowering, you can use EarlyStopping in Keras to halt
training.

After performing 5 epochs we get the following accuracy and loss plot from
training and testing data.

Figure 7: Accuracy of CNN Model

Figure 8: Loss Plot

TABLE I: Summary Table Epoch | Loss | Accuracy | Validation Loss | Validation Accuracy
---|---|---|---|---
$0$ | $18.1700$ | $0.4896$ | $0.7963$ | $0.4583$
$1$ | $0.6882$ | $0.5573$ | $0.5742$ | $0.8750$
$2$ | $0.4788$ | $0.8073$ | $0.1549$ | $0.9792$
$3$ | $0.1305$ | $0.9531$ | $0.0089$ | $1.0000$
$4$ | $0.0565$ | $0.9792$ | $0.0018$ | $1.0000$
$5$ | $0.0115$ | $0.9948$ | $0.000012$ | $1.0000$

Table I shows that the model achieves complete accuracy after 5 epochs. Our
model performs better on the unseen data, as seen in figures 7 and 8. On
testing data, our model is more accurate. Furthermore, the loss of model is
minimal. Figure 9 also displays the prediction rate of $100\%$. That means our
model accurately detects the fall.

Figure 9: Model Prediction

##  V Conclusion

###  V-A Challenges and Limitations

During the duration of our study, we faced some challenges and had some
limitations along the way. This may be due to the inexpensive nature of the
Tello drone, however during the initial stages of understanding how to fly the
drone, the propellers would often fall off on it’s own. After flying the drone
several times, we encountered takeoff complications, where the drone could not
takeoff from the ground. Even after re-calibrating the device multiple times,
we could not successfully address the issue, causing us to utilize a secondary
Tello drone.

Secondly, many of the training datasets available publicly required permission
to use and given the time constraint of the project, we could not rely on
waiting to be approved for access.

Also, for a number of poses we wanted our participants to re-enact, we could
not achieve certain angles based on the height limitations of the drone in
order to ensure safe flying.

Lastly, the drone’s camera quality often gave us issues when testing the
images with the CNN model, sometimes being incapable of determining what the
image consisted of.

###  V-B Takeaway

We used a small drone to detect falls in this experiment. We wanted to test if
the Tello drone could be effective in monitoring smart health on a broader
scale. Based on our findings, we can safely conclude that we can deploy a
Tello drone to monitor the residence. There are some drawbacks as well,
because the CNN model requires a large dataset with uniformly distributed
classes. Also, the drone’s range is limited, and the video resolution is only
720p with an 8-megapixel sensor. The weather circumstances contribute to hazy
photos, and we are unable to fly it in strong winds. It is, nevertheless,
quite inexpensive and convenient. We feel that this drone can still be used to
monitor the residence in an interior scenario.

###  V-C Learning Experience

As machine learning and smart home devices, such as a drone are new topics
that we had not previously explored, we learned a great deal throughout the
duration of the project. First and foremost, it was critical to work together
as a team from start to finish. We played on our strengths and assisted the
other when in need of help. Furthermore, we learned the importance of trouble
shooting because although technology is revolutionary, there will still be
some challenges along the way. Being able to turn to one another and other
resources when needed allowed us to achieve the best results that we could.

In terms of the drone, we determined that a drone can be an effective device
to detect falls in the home if created in a robust fashion. Although drones
are initially thought of to be used in the entertainment industry to capture
footage in areas where humans cannot reach, it can be applied to many other
disciplines such as healthcare. A drone can be used in the home to detect
falls, minimize the need for an in-home aid, and reduce unwanted stress.

This project serves as an eye opener that smart home technology can be adapted
to make the world a more safer place.

###  V-D Future Work

In the future, we hope to explore whether the drone is capable alerting
appropriate officials in the event of an incident. Furthermore, we would be
interested in exploring the possibilities of having an autonomous drone,
taking away the burden of having to fly the drone manually. Furthermore, we
would like to introduce the idea of having the drone dock itself when it needs
to be charged. Lastly, since we did not include mask R-CNN in our analysis,
comparing mask R-CNN and CNN algorithms in the future can prove beneficial to
the effectiveness of our system.

## Acknowledgment

I would like to express my deepest gratitude and appreciation to Professor Dr.
Nirmalya Roy for his invaluable guidance, mentorship, and expertise throughout
the course of this research endeavor. Furthermore, I extend my heartfelt
thanks to Mariam Yekini for her diligent and meticulous data collection
efforts. Mariam’s dedication, attention to detail, and competence played a
crucial role in ensuring the quality and accuracy of the data used in this
study. Her tireless work was instrumental in the successful execution of this
research project.

## References

  * [1] World Health Organization. (2021, April 26). Falls. WHO. https://www.who.int/news-room/fact-sheets/detail/falls
  * [2] Eichleay, M., Evens, E., Stankevitz, K., & Parker, C. (2019). Using the unmanned aerial vehicle delivery decision tool to consider transporting medical supplies via drone. Global Health: Science and Practice, 7(4), 500-506. https://doi.org/10.9745/ghsp-d-19-00119
  * [3] Fakhrulddin, S. S., Gharghan, S. K., Al-Naji, A., & Chahl, J. (2019). An advanced first aid system based on unmanned aerial vehicles and a wireless body area sensor network for elderly persons in outdoor environments. Sensors, 19(13), 28. https://doi.org/10.3390/s19132955
  * [4] Maldonado-Bascón, S., Iglesias-Iglesias, C., Martín-Martín, P., & Lafuente-Arroyo, S. (2019). Fallen people detection capabilities using assistive robot. Electronics, 8(9), 20. https://doi.org/10.3390/electronics8090915
  * [5] Sagar Chhetri et al. “Deep learning for a vision-based fall detection system: Enhanced optical dynamic flow”. In: Computational Intelligence 37.1 (2021), pp. 578–595.
  * [6] Campbell G. Zweig MH. “Receiver-operating characteristic (ROC) plots: a fundamental evaluation tool in clinical medicine”. In: Erratum in: Clin Chem 39.4 (1993), pp. 561–77. doi: https://pubmed.ncbi.nlm.nih.gov/8472349/.
  * [7] Francois Chollet et al. Keras. 2015. https://github.com/fchollet/keras.
  * [8] KananMahammadli. (n.d.). Kananmahammadli/fall-detection-using-CNN-architecture: Detecting whether a person has fallen or not based on images. GitHub. https://github.com/KananMahammadli/Fall-Detection-using-CNN-Architecture


# Low-Dispersive Permittivity Measurement Based on Transmitted Power Only

Seyed Hossein Mirjahanmardi  Department of Electrical and Computer Engineering
University of Watreloo
Waterloo, Ontario, Canada
<EMAIL_ADDRESS>
Omar M. Ramahi  Department of Electrical and Computer Engineering
University of Watreloo
Waterloo, Ontario, Canada
<EMAIL_ADDRESS>
###### Abstract

This paper presents a complex permittivity measurement method for low-
dispersive materials as a function of frequency. The introduced method relies
only on transmitted power signals which are collected using a spectrum
analyzer/power meter, removing the need for phase measurements and a vector
network analyzer. This method provides a very good accuracy along with easy
and inexpensive permittivity measurements.

###### Index Terms:

Complex Permittivity, Transmitted Power, Low-Dispersive.

##  I Introduction

Permittivity measurements of materials as a function of frequency finds
applications in numerous fields, including medical imaging, food sciences, and
agriculture [1, 2]. Several techniques have been widely used to determine
material permittivities, such as open-ended coaxial, free-space, cavity
resonant, and waveguides. The open-ended coaxial method covers a wide range of
frequencies and provides easy measurements; however, suffers from low accuracy
[3, 4]. Additionally, reports show that this technique cannot provide reliable
results for heterogeneous medium [4]. The free-space method provides a wide-
band permittivity measurement with high accuracy, but requires costly
measurement setups and large sampling preparation. Cavity resonant techniques
are among the highest accurate methods, but are very narrow-band and can be
only applicable to low-loss materials. Waveguide techniques provide high
accuracy and moderate bandwidth of operation but need cumbersome sample
preparations [1]. These methods mainly rely on both amplitude and phase
measurements which require vector network analyzers. There are only a few
amplitude-only techniques reported in the literature that do not need phase
information [5]. These methods, however, cannot provide high accuracy because
their preciseness rely on a specific amount of loss that should occur in the
sample while signals propagate from the source to the receiver. Additionally,
some of them still require a vector network analyzer to measure signals’
reflections.

In this paper, we apply our previously introduced single-frequency
permittivity reconstruction method [3, 6] to measure the permittivity of low-
dispersive materials as a function of frequency. No phase information is used
in this method and only transmitted power collected at multiple frequencies
are utilized to reconstruct the permittivity values. Therefore, the need for a
vector network analyzer is removed. Measurement results acquired from our
method are compared with the open-ended coaxial method’s, validating the
fidelity of our method.

##  II Methodology

Figure 1: Coaxial line filled with a liquid sample connected to a signal
generator and a spectrum analyzer.

This section briefly discusses our power method applied to a coaxial line
structure. The method can be also applied to other permittivity reconstruction
setups such as the free-space one. Fig. 1 shows a coaxial line connected to a
signal generator with an internal source resistance of $R_{s}$ and to a
spectrum analyzer with a load resistance of $R_{L}$. Solving Maxwell equations
for the transmitted power delivered to the spectrum analyzer analytically
results in:

$\hat{P}_{L}(f_{i},\epsilon_{r}^{\prime},\epsilon_{r}^{\prime\prime})=\frac{1}{2R_{L}}{\left|\frac{V_{s}Z_{in}e^{-\gamma
d}(\Gamma+1)}{(R_{s}+Z_{in})(\Gamma e^{-2\gamma d}+1)}\right|^{2}}$ (1)

where $V_{s}$, $\Gamma$, and $f_{i}$ are the source voltage, reflection
coefficient at the load, and the frequency of excitation, respectively.
$\hat{P}_{L}$ is the power calculated analytically. $Z_{in}$ is the input
impedance seen from the source side toward the load. The coaxial line has an
outer radius of 4.1 mm, inner radius of 1.27 mm, and a length of 3.6 cm. The
space between the inner and outer is filled with the material under test with
the real permittivity of $\epsilon_{r}^{\prime}$ and imaginary part of
$\epsilon_{r}^{\prime\prime}$,
($\epsilon_{r}=\epsilon_{r}^{\prime}-j\epsilon_{r}^{\prime\prime}$). The
material is assumed to be non-magnetic and low-dispersive.

Equation 1 depends non-linearly on the excitation frequency. Therefore,
multiple independent equations can be generated by changing the frequency. If
material under test is not highly dispersive, its permittivity function varies
smoothly versus frequency. Hence, within a finite bandwidth the permittivity
can be approximately considered constant. The following equation is then
defined as an objective function which compares the transmitted power obtained
analytically with the power values obtained from measurements at a specific
frequency:

$\delta(\epsilon_{r}^{\prime},\epsilon_{r}^{\prime\prime},f_{i})=\left|\hat{P}_{L}(f_{i})-P_{L}(f_{i})\right|$
(2)

where $\delta$ is the difference between measured power, $P_{L}$, and
calculated power.

Generating multiple equations based on 2 in a finite bandwidth $\Delta f$
creates a set of objective functions with two unknowns,
$\epsilon_{r}^{\prime}$ and $\epsilon_{r}^{\prime\prime}$. Multiple power
samples, in this paper twenty samples, are selected linearly in this bandwidth
and substituted in 2. Solving these objective functions numerically to
minimize $\delta$ results in determining a unique pair for
$\epsilon_{r}^{\prime}$ and $\epsilon_{r}^{\prime\prime}$. The obtained
permittivity is assigned to the frequency located at the center of this
bandwidth, $f_{c}$. Readers are referred to our previous works for more
details on the permittivity reconstruction procedure [3]. Fig. 2 shows an
example of measured power as a function of frequency. The power samples are
picked up in a window from $f_{1}$ to $f_{2}$ and the permittivity is assigned
to $f_{c}$.

This method can then be applied to determine the permittivity at other
frequencies. If the bandwidth window shown in Fig. 2 is shifted slightly, with
the amount of $\delta f$ in the frequency domain, and the permittivity
reconstruction procedure is repeated, a new permittivity value is obtained and
assigned to $f_{c}+\delta f$.

Figure 2: An example of measured power as a function of frequency. Sampling is
done in a window from $f_{1}$ to $f_{2}$, shown with solid red lines, with a
frequency center of $f_{c}$. The shifted window is shown by dashed red lines
with a frequency center of $f_{c}+\delta f$.

##  III Measurement Results

To validate the method, a low-dispersive liquid, Cyclohexane, is tested. The
coaxial line shown in Fig. 1 is filled with this liquid connected to a signal
generator which has an output signal power level of 0 dBm. The frequency of
excitation varies from 0.05 to 1.05 GHz. Twenty samples are linearly picked up
with a step of 5 MHz within a bandwidth of 95 MHz and the method is applied to
reconstruct the permittivity, $\epsilon_{r}^{\prime}(1)$ and
$\epsilon_{r}^{\prime\prime}(1)$. The window of sampling is then shifted 10
MHz in frequency and a new permittivity is measured for the new bandwidth
window. Fig. 3 shows the result of this permittivity reconstruction for both
the real and imaginary parts.

As a comparison, Cyclohexane liquid is tested with the open-ended coaxial
approach. The results of this measurement are also plotted in Fig. 3,
$\epsilon_{r}^{\prime}(2)$ and $\epsilon_{r}^{\prime\prime}(2)$. This
measurement is done with a vector network analyzer. It can be seen that the
results of these two methods are in close agreement. However, our previous
work showed a higher accuracy of our method compared to the open-ended coaxial
one [3].

Figure 3: Real part and imaginary part of Cyclohexane liquid measured using
our method, $\epsilon^{\prime}(1)$, and the open-ended coaxial method,
$\epsilon^{\prime\prime}(2)$.

##  IV Conclusion

This paper introduced a permittivity measurement method for low-dispersive
materials without the need for phase measurements and a vector network
analyzer. Only the real part of transmitted power values collected by a
spectrum analyzer are used. Comparisons with the open-ended coaxial method
showed that our method provided a very good accuracy.

## References

  * [1] L.-F. Chen, C. Ong, C. Neo, V. Varadan, and V. K. Varadan, _Microwave electronics: measurement and materials characterization_. John Wiley & Sons, Nov. 2004.
  * [2] A. Martellosio, M. Pasian, M. Bozzi, L. Perregrini, A. Mazzanti, F. Svelto, P. E. Summers, G. Renne, L. Preda, and M. Bellomi, “Dielectric properties characterization from 0.5 to 50 ghz of breast cancer tissues,” _IEEE Transactions on Microwave Theory and Techniques_ , vol. 65, no. 3, pp. 998–1011, 2016.
  * [3] S. H. Mirjahanmardi and O. Ramahi, “Highly accurate liquid permittivity measurement using coaxial lines,” in _2019 IEEE International Symposium on Antennas and Propagation and USNC-URSI Radio Science Meeting_. IEEE, 2019, pp. 101–102.
  * [4] P. M. Meaney, A. P. Gregory, N. R. Epstein, and K. D. Paulsen, “Microwave open-ended coaxial dielectric probe: interpretation of the sensing volume re-visited,” _BMC medical physics_ , vol. 14, no. 1, p. 3, 2014.
  * [5] U. Hasar, “Elimination of the multiple-solutions ambiguity in permittivity extraction from transmission-only measurements of lossy materials,” _Microwave and Optical Technology Letters_ , vol. 51, no. 2, pp. 337–341, Feb. 2009.
  * [6] S. H. Mirjahanmardi, A. M. Albishi, and O. M. Ramahi, “Permittivity reconstruction of nondispersive materials using transmitted power at microwave frequencies,” _IEEE Transactions on Instrumentation and Measurement_ , vol. 69, no. 10, pp. 8270–8278, 2020.


# Value Function Based Performance Optimization
of Deep Learning Workloads

Benoit Steiner
Facebook AI Research
<EMAIL_ADDRESS>
Chris Cummins
Facebook AI Research
<EMAIL_ADDRESS>
Horace He
Facebook
<EMAIL_ADDRESS>
Hugh Leather
Facebook AI Research
<EMAIL_ADDRESS>

###### Abstract

As machine learning techniques become ubiquitous, the efficiency of neural
network implementations is becoming correspondingly paramount. Frameworks,
such as Halide and TVM, separate out the algorithmic representation of the
network from the schedule that determines its implementation. Finding good
schedules, however, remains extremely challenging. We model this scheduling
problem as a sequence of optimization choices, and present a new technique to
accurately predict the expected performance of a partial schedule. By
leveraging these predictions we can make these optimization decisions greedily
and rapidly identify an efficient schedule. This enables us to find schedules
that improve the throughput of deep neural networks by $2.6\times$ over Halide
and $1.5\times$ over TVM. Moreover, our technique is two to three orders of
magnitude faster than that of these tools, and completes in seconds instead of
hours.

##  1 Introduction

The rise of deep learning has been accompanied by the development of
frameworks such as PyTorch [1] and TensorFlow [2]. The majority of these tools
provide a set of primitive tensor operators to perform tasks such as matrix
multiplication, convolution and pooling, which are applied in sequence by a
runtime interpreter to derive the outputs of the neural network from its input
tensors.

Though pervasive, this approach has two main downsides. First, it requires the
development, optimization, and maintenance of a large set of operators, which
necessitates scarce human expertise. As a result, frameworks tend to focus on
the most common operators which are only optimized for a limited set of use
cases, leaving a lot of performance on the table. Second, these operators can
only exchange data through global memory. This is a significant bottleneck,
especially in the case of operators of low arithmetic intensity such as
activation functions.

To avoid these problems, projects such as Halide [3] and TVM [4] proposed to
represent tensor computations using a declarative domain specific language
based on Einstein’s notation. This high-level representation is then compiled
into assembly code that can be executed directly on hardware. This approach
abstracts away key implementation choices such as loop ordering, blocking,
vectorization, unrolling, inlining, or parallelization, and leaves it up to
the compiler to figure out which solution, a.k.a. schedule, most efficiently
leverages the available hardware resources.

Previous work [5, 6, 7, 8, 9] has attempted to tackle scheduling by framing
the problem as a search in the space of valid implementations. However, these
approaches rely on an extensive exploration of the optimization landscape,
coupled with aggressive pruning of the solution space. Nevertheless, given the
combinatorial nature of the problem, they take several hours to identify a
solution and often end up generating suboptimal code.

In this work, we propose a method to overcome these limitations. We
iteratively improve a value function capable of predicting, given a partial
set of scheduling decisions, the best achievable performance over all
remaining decisions. This “look-ahead” allows us to incrementally schedule an
entire neural network by making a set of local decisions that are globally
optimal. We show that our technique is able to identify schedules which are on
average $1.5\times$ and $2.6\times$ faster than TVM and Halide respectively.
We also demonstrate that our approach identifies solutions in two or more
orders of magnitude less time.

##  2 Automated Scheduling

Optimization |  Description
---|---
split |  Transform a loop into two nested loops.
reorder |  Exchange two loops.
vectorize |  Use SIMD instructions to encode the loop.
parallel |  Parallelize the computation over multiple CPU cores.
compute_at |  Inline the evaluation of a loop into another one.
store_at |  Store the values generated by a layer into a temporary buffer.
Table 1: Primitive scheduling actions used to optimize each layer of a neural
network.

Input1: NN with n layers $L_{1}$ … $L_{n}$

Input2: Value function $V(s)$

$s_{0}$ = InitialState

for $i=1$ to $n$ do

$C_{i}$ = CandidateActions($L_{i}$, $s_{i-1}$)

$v_{i}$ = $\infty$

for $s$ in $C_{i}$ do

if $V(s)<v_{i}$ then

$v_{i}$ = V($s$)

$s_{i}$ = $s$

end if

end for

end for

Return: $s_{1}$ … $s_{n}$

Algorithm 1 Scheduling

We model the problem of choosing the best schedule amongst all the possible
options as a deterministic Markov Decision Process (MDP) over a finite horizon
with a dynamic action space. In our formulation, a state $s_{i}$ is a partial
schedule – a set of scheduling decisions applied to the first $i$ layers
$L_{i}$ of a neural network. The set of actions $a_{i}$ available in state
$s_{i}$ is the set of valid scheduling options available for layer $L_{i+1}$
given the loop structure for the previous layers imposed by the schedule
$s_{i}$. The set of candidate actions we consider is listed in Table 1.

We solve the MDP by learning an approximation $V(s)$ of the optimal value
function $V^{*}(s)$. In layman’s terms, $V^{*}(s)$ is a function capable of
predicting the lowest runtime achievable from a state $s$ assuming that we
make optimal scheduling decisions for all the subsequent layers of the neural
network. Once we have our value function approximation $V(s)$, we greedily
schedule the neural network layer by layer following the steps outlined in
Algorithm 1.

For a $N$-layer neural network, with an average of $M$ choices available per
layer, we only need to consider $N$*$M$ candidates out of the $M^{N}$
available complete schedules. This enables us to schedule deep learning
workloads extremely quickly as we will see in Section 4.2.

Note that if we could learn the true value function $V^{*}(s)$ instead of an
approximation $V(s)$ our approach would ensure that we find the optimum
solution. We’ll see in section 4.1 how each iteration improve the performance
of the schedules identified by our approach.

##  3 Value Function Estimation

###  3.1 Iterative Approximation

Our technique is inspired from the well known value iteration approach
summarized in [10]. However, we cannot use this approach directly. Indeed, we
face two main hurdles. First, obtaining the reward is very expensive – it
requires compilation of our schedule as well as benchmarking the schedule on
actual hardware. Second, it would be impractical to exhaustively visit all the
states associated with the scheduling of a single neural network for all but
the smallest networks.

Input: set of neural networks N

Input: value function $V_{i-1}(s)$

Initialize $V_{i}(s)$ to $V_{i-1}(s)$

for $n$ in $N$ do

for $k$ in $[0,100]$ do

$s_{0},...s_{n}=\text{BestSchedule}(n,V_{i,\epsilon_{k}})$

for $s_{j}$ in $s_{0},...s_{n}$ do

$t_{j+1},...t_{n}=\text{BeamSearch}(s_{j},V_{i-1}))$

$r=\text{Benchmark}(s_{0},...s_{j},t_{j+1},...t_{n})$

$V_{i}(s_{j})=\min(r,V_{i}(s_{j}))$

end for

end for

end for

Return: $V_{i}(s)$

Algorithm 2 Single iteration of our value function approximation

On the other hand, we can make a few simplifications. First, we do not need to
uniformly sample all the actions available from a state $s$. Although we need
a precise estimate of the value function associated with the “best“ states, we
only need a rough estimate for the less interesting states. Consequently, we
can sample less often the actions that lead to the less interesting states.
Moreover, we can derive an upper bound for the value function for a state $s$
by searching for the best schedule starting from $s$.

Based on these observations, we designed an iterative algorithm, that,
starting from an initial approximation of the value function $V_{0}$, builds
progressively more accurate estimates $V_{i}(s)$.

Algorithm 2 details how we perform each iteration: we extract 100 schedules
for each neural network in our training set. We inject a small amount of
random noise $\epsilon$ to the predictions made by the value function to
ensure that we cover a significant portion of the interesting states of each
pipeline. Starting from each state $s_{i}$ in the previously identified
schedules, we run a beam search guided by our previous estimate of the value
function, and benchmark the resulting schedule. We use the measured runtime to
refine the estimate of the value function V for the state $s_{i}$. To
bootstrap the process, we modify algorithm 2 to generate and benchmark end to
end schedules purely randomly.

###  3.2 Implementation

The throughput of a neural network depends on two main factors: the amount of
computation and data access to be performed, and the overall organization of
the computation. Consequently, we devised two groups of input features to
capture this information: a set of intrinsic features that are invariant to
the schedule, and a collection of schedule dependant features that are
acquired as the process of scheduling a pipeline progresses. In this setting,
the intrinsic features enable our model to predict how fast each stage could
be executed if scheduled optimally, while the acquired features enable us to
capture how well the scheduled stages are expected to perform.

Since the set of scheduling decisions made for the initial layers of a neural
network impact the performance of the yet to be scheduled layers, we
architected our value function around an LSTM, that we feed with the
normalized values of our intrinsic and acquired features. To predict the
expected performance of the whole neural network, we sum the predictions of
each of the timesteps of the LSTM.

##  4 Evaluation

Figure 1: Improvement in our value function through 2 rounds of value
improvement. Each round significantly improves the quality of our generated
schedules.

We ran all our experiments on an Intel Xeon D-2191A CPU running at 1.60GHz
with 48GB of RAM and a NVidia Tesla M40 GPU. We used Halide [3] to compile our
schedules into assembly code.

###  4.1 Value Function

First, we measured the impact of the inductive bias inherent in our model
architecture on its ability to encode the value function. Across our rounds of
value improvement $V_{i}$, our neural network was able to predict the expected
values with an average error inferior to 5% and an $R^{2}$ greater than 0.955.

Next, we would like to demonstrate that our iterative value learning process
is effective. However, we cannot show that our successive value function
approximations $V_{i}(s)$ converge towards the optimal value function
$V^{*}(s)$ since determining the exact value of $V^{*}(s)$ would require an
exhaustive search in a combinatorially large solution space. Instead we show
that with each iteration our value function estimates are better able to guide
a search. In Figure 1, we plot the relative performance of the schedules
selected by our greedy search as well as a standard beam search under the
guidance of three successive estimates V0, V1, and V2 on the 12 models used in
Figure 2. As V0, V1, and V2 refine the estimates of our value function the gap
between the quality of the schedules identified by a greedy and a beam search
decreases, while the overall performance of the schedules increases

###  4.2 Benchmarks

(a) Schedule search time. Lower is better.

(b) Speedup of schedules over PyTorch. Higher is better.

Figure 2:  (2(a)) Time taken to schedule deep learning workloads, and (2(b))
performance of final schedules relative to PyTorch. We plot the search times
on a log scale. We compare our results against the Halide autoscheduler
(Adams2019) and AutoTVM using the published configuration. AutoTVM failed to
load the Transformer and Wavenet models.

We evaluate our search strategy on a diverse set of deep learning workloads
encompassing text, speech, and image processing tasks.

In Figure 2 we compare our implementation against the following systems:
PyTorch 1.6, AutoTVM version 0.6, and the Halide auto-scheduler version 8.0.0.
To run AutoTVM, we followed the steps outlined in its documentation [11]. We
ran the Halide auto-scheduler with its default settings of 5 search passes
with each pass identifying 32 candidate schedule, and benchmarking to do the
final ranking of the 160 candidates.

First, we show the search time of the systems in Figure 2(a). PyTorch is
extremely fast, since it does not search for good solutions. AutoTVM takes
considerable time, requiring 3 hours on average and up to 12 hours to complete
the search. Halide takes an average of 20 minutes and up to 2.5 hours. Our
approach schedules the neural networks in 13 seconds on average, and 47
seconds in the worst case.

However, this significantly faster search time does not come at the cost of
lower quality schedules, as can be seen in Figure 2(b). Our search finds
schedules that outperform PyTorch by a factor of $5.1\times$. We also improve
on AutoTVM and Halide with a speedup of $1.5\times$ and $2.6\times$
respectively.

##  5 Conclusion

Our results demonstrate that automatically learning complex neural network
scheduling policies using reinforcement learning is feasible and lead to
better results in a fraction of the search time. We hope that this will allow
these techniques to be used in a broader range of applications.

## References

  * [1] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In Advances in Neural Information Processing Systems 32, pages 8026–8037. Curran Associates, Inc., 2019.
  * [2] Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Jozefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Levenberg, Dandelion Mané, Rajat Monga, Sherry Moore, Derek Murray, Chris Olah, Mike Schuster, Jonathon Shlens, Benoit Steiner, Ilya Sutskever, Kunal Talwar, Paul Tucker, Vincent Vanhoucke, Vijay Vasudevan, Fernanda Viégas, Oriol Vinyals, Pete Warden, Martin Wattenberg, Martin Wicke, Yuan Yu, and Xiaoqiang Zheng.  TensorFlow: Large-scale machine learning on heterogeneous systems, 2015\.  Software available from tensorflow.org.
  * [3] Jonathan Ragan-Kelley, Andrew Adams, Sylvain Paris, Marc Levoy, Saman Amarasinghe, and Frédo Durand.  Decoupling algorithms from schedules for easy optimization of image processing pipelines.  ACM Transactions on Graphics - TOG, 31, 07 2012.
  * [4] Tianqi Chen, Thierry Moreau, Ziheng Jiang, Lianmin Zheng, Eddie Yan, Haichen Shen, Meghan Cowan, Leyuan Wang, Yuwei Hu, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy.  TVM: An automated end-to-end optimizing compiler for deep learning.  In 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 18), pages 578–594, Carlsbad, CA, October 2018. USENIX Association.
  * [5] Andrew Adams, Karima Ma, Luke Anderson, Riyadh Baghdadi, Tzu-Mao Li, Michaël Gharbi, Benoit Steiner, Steven Johnson, Kayvon Fatahalian, Frédo Durand, and Jonathan Ragan-Kelley.  Learning to optimize halide with tree search and random programs.  ACM Trans. Graph., 38(4):121:1–121:12, July 2019.
  * [6] Tianqi Chen, Lianmin Zheng, Eddie Yan, Ziheng Jiang, Thierry Moreau, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy.  Learning to optimize tensor programs.  In Proceedings of the 32Nd International Conference on Neural Information Processing Systems, NIPS’18, pages 3393–3404, USA, 2018. Curran Associates Inc.
  * [7] Size Zheng, Yun Liang, Shuo Wang, Renze Chen, and Kaiwen Sheng.  Flextensor: An automatic schedule exploration and optimization framework for tensor computation on heterogeneous system.  ASPLOS ’20, page 859–873, New York, NY, USA, 2020. Association for Computing Machinery.
  * [8] Lianmin Zheng, Chengfan Jia, Minmin Sun, Zhao Wu, Cody Hao Yu, Ameer Haj-Ali, Yida Wang, Jun Yang, Danyang Zhuo, Koushik Sen, Joseph E. Gonzalez, and Ion Stoica.  Ansor: Generating high-performance tensor programs for deep learning.  In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20), Banff, Alberta, November 2020. USENIX Association.
  * [9] Savvas Sioutas, Sander Stuijk, Henk Corporaal, Twan Basten, and Lou Somers.  Loop transformations leveraging hardware prefetching.  In Proceedings of the 2018 International Symposium on Code Generation and Optimization, CGO 2018, page 254–264, New York, NY, USA, 2018\. Association for Computing Machinery.
  * [10] Richard S. Sutton and Andrew G. Barto.  Reinforcement Learning: An Introduction.  The MIT Press, second edition, 2018.
  * [11] Yao Wang and Eddie Yan.  Auto-tuning a convolutional network for x86 cpu.  https://tvm.apache.org/docs/tutorials/autotvm/tune_relay_x86.html.  Accessed: 2020-09-30.


# The space of $r$-immersions of a union of discs in $\mathbb{R}^{n}$

Gregory Arone  Department of Mathematics, Stockholm University
<EMAIL_ADDRESS>and  Franjo Šarčević  Department of Mathematics,
University of Sarajevo<EMAIL_ADDRESS>pmf.unsa.ba/franjos

###### Abstract.

For a manifold $M$ and an integer $r>1$, the space of $r$-immersions of $M$ in
${\mathbb{R}}^{n}$ is defined to be the space of immersions of $M$ in
${\mathbb{R}}^{n}$ such that the preimage of every point in ${\mathbb{R}}^{n}$
contains fewer than $r$ points. We consider the space of $r$-immersions when
$M$ is a disjoint union of $k$ $m$-dimensional discs, and prove that it is
equivalent to the product of the $r$-configuration space of $k$ points in
${\mathbb{R}}^{n}$ and the $k^{\text{th}}$ power of the space of injective
linear maps from ${\mathbb{R}}^{m}$ to ${\mathbb{R}}^{n}$. This result is
needed in order to apply Michael Weiss’s manifold calculus to the study of
$r$-immersions. The analogous statement for spaces of embeddings is “well-
known”, but a detailed proof is hard to find in the literature, and the
existing proofs seem to use the isotopy extension theorem, if only as a matter
of convenience. Isotopy extension does not hold for $r$-immersions, so we
spell out the details of a proof that avoids using it, and applies to spaces
of $r$-immersions.

###### Key words and phrases:

$r$-immersions, $r$-configuration spaces

###### 2020 Mathematics Subject Classification:

Primary: 57R42; Secondary: 55R80, 57R40

Acknowledgements. F. Šarčević was partially supported by the grant P20_01109
(JUNTA/FEDER, UE)

##  1\. Introduction

Embedding calculus (also known as manifold calculus) is a method, invented by
M. Weiss [Wei99], for analysing presheaves on manifolds. Suppose $F$ is a
contravariant functor defined on a suitable category of $m$-dimensional
manifolds. Let $D^{m}$ be the open unit disc in ${\mathbb{R}}^{m}$. One of the
main ideas of embedding calculus is to first focus on the value of $F$ on
manifolds of the form $\coprod_{i=1}^{k}D^{m}$, and then extrapolate from
there to get approximations to the value of $F$ on general $m$-dimensional
manifolds. For this approach to be useful, one generally needs a good
understanding of the value of $F$ on disjoint unions of copies of $D^{m}$.

The original motivating example for embedding calculus is, not coincidentally,
the embedding functor $\operatorname{Emb}(-,{\mathbb{R}}^{n})$, were
${\mathbb{R}}^{n}$ is a fixed vector space and the domain of the functor is
considered to be the category of $m$-dimensional manifolds and codimension
zero embeddings, for some fixed $m$. One can also replace ${\mathbb{R}}^{n}$
with a more general manifold $N$, but we will restrict ourselves to embeddings
into a Euclidean space.

In order to apply Weiss’s machinery to the embedding functor, one needs a good
understanding of the homotopy type of spaces of the form
$\operatorname{Emb}(\coprod_{k}D^{m},{\mathbb{R}}^{n})$. Fortunately, the
homotopy type of these spaces is well-understood. To describe it, let
$\operatorname{Conf}(k,{\mathbb{R}}^{n})\subset({\mathbb{R}}^{n})^{k}$ be the
configuration space of ordered $k$-tuples of pairwise distinct points in
${\mathbb{R}}^{n}$. That is, for $\underline{k}=\\{1,...,k\\}$

$\operatorname{Conf}(k,{\mathbb{R}}^{n}):=\operatorname{Emb}(\underline{k},{\mathbb{R}}^{n})\cong\\{(x_{1},...,x_{k})\in({\mathbb{R}}^{n})^{k}:x_{i}\neq
x_{j}\text{ for }i\neq j\\}.$

Also let $\operatorname{L}({\mathbb{R}}^{m},{\mathbb{R}}^{n})$ denote the
space of injective linear maps from ${\mathbb{R}}^{m}$ to ${\mathbb{R}}^{n}$.

There is a natural map

(1)
$\operatorname{Emb}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\xrightarrow{\simeq}\operatorname{Conf}(k,{\mathbb{R}}^{n})\times\operatorname{L}({\mathbb{R}}^{m},{\mathbb{R}}^{n})^{k}.$

The map is defined by evaluating an embedding at the centers of the discs, and
also differentiating at the centers of the discs. It is well-known that the
map (1) is an equivalence.

Recently there has been an emerging interest in applying embedding calculus to
the study of $r$-immersions [DT15, SŠV20]. Given an integer $r>1$, an
$r$-immersion is an immersion with the property that the preimage of each
point consists of fewer than $r$ points. Let $\operatorname{rImm}(M,N)$ denote
the space of $r$-immersions of $M$ into $N$. For $r=2$, a $2$-immersion is the
same thing as an injective immersion. When $M$ is compact, a $2$-immersion of
$M$ is the same as an embedding. More generally, when $M$ is tame (i.e., is
the interior of a compact manifold with boundary), the space of $2$-immersions
is equivalent to the space of embeddings. Thus for practical purposes, we can
identify the space of $2$-immersions with the space of embeddings. In general,
we have inclusions

$\operatorname{Emb}(M,N)\subset
3\operatorname{Imm}(M,N)\subset\cdots\subset\operatorname{rImm}(M,N)\subset\cdots\operatorname{Imm}(M,N).$

In order to apply embedding calculus to the study of $r$-immersions, one would
like to have an analogue of the equivalence (1) for $r$-immersions. Let
$\operatorname{rConf}(k,{\mathbb{R}}^{n})$, called the $r$-configuration
space, also known as non $r$-equal configuration space, of $k$ points in
${\mathbb{R}}^{n}$, is defined to be the space

$\operatorname{rConf}(k,{\mathbb{R}}^{n}):=\operatorname{rImm}(\underline{k},{\mathbb{R}}^{n})\cong\\{(x_{1},...,x_{k})\in({\mathbb{R}}^{n})^{k}:\nexists
1\leq i_{1}<\cdots<i_{r}\leq k\text{ s.t. }x_{i_{1}}=...=x_{i_{r}}\\}.$

There is a natural map

(2)
$\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\simeq\operatorname{rConf}(k,{\mathbb{R}}^{n})\times\operatorname{L}({\mathbb{R}}^{m},{\mathbb{R}}^{n})^{k},$

defined by evaluation at the centers of the discs and differentiation at the
centers of the discs. It is a generalization of (1). Our main result (Theorem
2.1) says that this map is an equivalence. This fact is implicitly assumed in
[SŠV20], and to some extent also in [DT15].

As we mentioned above, the case $r=2$ of our result is well-known. However, we
had trouble finding a detailed proof of it in the literature. Furthermore,
proofs that we did find tend to use at some point the fact that when $M_{0}$
is a closed submanifold of $M$, the restriction maps
$\operatorname{Emb}(M,{\mathbb{R}}^{n})\to\operatorname{Emb}(M_{0},{\mathbb{R}}^{n})$
and
$\operatorname{Imm}(M,{\mathbb{R}}^{n})\to\operatorname{Imm}(M_{0},{\mathbb{R}}^{n})$
are fibrations. This property definitely fails for $r$-immersions when
$2<r<\infty$. Even when $M=\underline{k}$ is a finite set (a zero-dimensional
manifold), and $\underline{k_{0}}\subset\underline{k}$, the restriction map
$\operatorname{rConf}(k,{\mathbb{R}}^{n})\to\operatorname{rConf}(k_{0},{\mathbb{R}}^{n})$
is not a fibration.

Our companion paper [AŠ] relies heavily on the map (2) being an equivalence.
It thus seems prudent to write out a full proof of this assertion. We hope
that the result is interesting enough to stand on its own.

### Topology on spaces of smooth maps

We endow the space $C^{\infty}(M,N)$ of smooth maps from $M$ to $N$ with the
compact-open $C^{\infty}$-topology, a.k.a the weak Whitney topology. Thus a
sequence of smooth functions $f_{n}\colon M\to N$ converges to $f$ if for
every multi-index $\alpha$, the sequence $\partial^{\alpha}\\!f_{n}$ converges
to $\partial^{\alpha}\\!f$ uniformly on every compact subspace of $M$. All
spaces of embeddings, immersions, $r$-immersions, etc. are endowed with the
subspace topology from the space of smooth maps.

##  2\. $r$-immersions of a union of discs

Let $D^{m}$ be the open unit disc in ${\mathbb{R}}^{m}$ and $k$ a natural
number. Let $\operatorname{L}({\mathbb{R}}^{m},{\mathbb{R}}^{n})$ denote the
space of injective linear maps from ${\mathbb{R}}^{m}$ to ${\mathbb{R}}^{n}$.
There is a canonical map

$\operatorname{ev}\colon\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\to\operatorname{rConf}(k,{\mathbb{R}}^{n})\times\operatorname{L}({\mathbb{R}}^{m},{\mathbb{R}}^{n})^{k}.$

The map $\operatorname{ev}$ is defined by evaluating an $r$-immersion
$f\colon\coprod_{k}D^{m}\to{\mathbb{R}}^{n}$ at the center of each disc
$D^{m}$ and also differentiating $f$ at the center of each disc. The main
result of this paper is the following theorem

######  Theorem 2.1.

The map $\operatorname{ev}$ is a weak homotopy equivalence.

The proof of Theorem 2.1 goes through a construction of several intermediate
spaces. To begin with, let us introduce the space of $r$-immersions that are
componentwise embeddings.

######  Definition 2.2.

Let
$\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$
be the subspace of
$\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$ consisting
of those immersions that restrict to an embedding on each copy of $D^{m}$.

We will now define a map that “almost” exhibits
$\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$
as a deformation retract of
$\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$.

######  Definition 2.3.

Let $f\in C^{\infty}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$ and $0\leq
t\leq 1$. Define the map $f_{t}\in
C^{\infty}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$ by the formula
$f_{t}(x)=f(tx)$. It is clear that if $f$ is an $r$-immersion then so is
$f_{t}$ for all $0<t\leq 1$, but not for $t=0$. Define the map

$H\colon\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\times(0,1]\to\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$

by the formula

$H(f,t)=f_{t}.$

It is clear that for all
$f\in\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$ there
exists an $\epsilon>0$ such that for all $0<t\leq\epsilon$,
$H(f,t)\in\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$.
We need to strengthen this observation.

######  Lemma 2.4.

For every
$f\in\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$ there
exists an open neighbourhood $U$ of $f$ and an $\epsilon>0$ such that
$H(U\times(0,\epsilon])\subset\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$.

###### Proof.

Let $f\colon\coprod_{k}D^{m}\to{\mathbb{R}}^{n}$ be an $r$-immersion. For
$0<\epsilon<1$, let $B^{m}_{\epsilon}\subset D^{m}$ denote the closed ball of
radius $\epsilon$. Since $f$ is a local embedding one can find an $\epsilon>0$
so that $f$ restricts to an embedding of $B^{m}_{\epsilon}$ for each copy of
$D^{m}$. This means that the composition of maps

$\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\hookrightarrow
C^{\infty}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\to
C^{\infty}\left(\coprod_{k}B^{m}_{\epsilon},{\mathbb{R}}^{n}\right)$

takes $f$ into the subspace
$\operatorname{Emb}\left(\coprod_{k}B^{m}_{\epsilon},{\mathbb{R}}^{n}\right)\subset
C^{\infty}\left(\coprod_{k}B^{m}_{\epsilon},{\mathbb{R}}^{n}\right)$. It is
well-known that the space of embeddings is open in the space of all smooth
maps with Whitney $C^{\infty}$-topology, hence in this special case
$\operatorname{Emb}\left(\coprod_{k}B^{m}_{\epsilon},{\mathbb{R}}^{n}\right)$
is an open subset of
$C^{\infty}\left(\coprod_{k}B^{m}_{\epsilon},{\mathbb{R}}^{n}\right)$.
Therefore the preimage of
$\operatorname{Emb}\left(\coprod_{k}B^{m}_{\epsilon},{\mathbb{R}}^{n}\right)$
in $\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$ is the
required open neighborhood. ∎

######  Corollary 2.5.

For any compact space $K$ and map
$K\to\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$ there
exists an $\epsilon>0$ such that the composition

$K\times(0,1]\to\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\times(0,1]\xrightarrow{H}\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$

takes $K\times(0,\epsilon]$ into
$\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$.

###### Proof.

Suppose we have a map
$h:K\to\operatorname{rImm}(\coprod_{k}D^{m},{\mathbb{R}}^{n})$. Let $x\in K$.
Then $h(x)$ is an $r$-immersion. By Lemma 2.4, there is an open neighborhood
$V$ of $h(x)$ in $\operatorname{rImm}(\coprod_{k}D^{m},{\mathbb{R}}^{n})$, and
a positive number $\epsilon_{x}$ such that all the elements of
$H(V\times(0,\epsilon_{x}])$ are componentwise embeddings. Let
$U_{x}=h^{-1}(V)$. Thus for every $x\in K$ we found an open neighborhood
$U_{x}$ and a positive number $\epsilon_{x}$ such that every $r$-immersion in
$h(U_{x})$ restricts to an embedding of balls of radius $\epsilon_{x}$. By
compactness of $K$, there is a finite collection of points, say
$x_{1},…,x_{l}$ such that $U_{x_{1}},…,U_{x_{l}}$ cover $K$. Let
$\epsilon=\min\\{\epsilon_{x_{1}},…,\epsilon_{x_{l}}\\}$. Then every
$r$-immersion in $h(K)$ restricts to an embedding of balls of radius
$\epsilon$. But this means that every element of $H(h(K)\times(0,\epsilon])$
is a componentwise embedding. ∎

Now we can complete the first important step toward proving Theorem 2.1.

######  Proposition 2.6.

The inclusion

(3)
$\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\hookrightarrow\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$

is a weak homotopy equivalence.

###### Proof.

Choose a basepoint in
$\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$,
which also will serve as a basepoint for
$\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$. Let
$h\colon
S^{d}\to\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$ be
a pointed map, representing an element of
$\pi_{d}\left(\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\right)$.
By Corollary 2.5, there exists an $0<\epsilon<1$ such that the composition

$S^{d}\times(0,1]\xrightarrow{h\times\mathtt{1}}\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\times(0,1]\xrightarrow{H}\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$

takes $S^{d}\times\\{\epsilon\\}$ into
$\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$.
It follows that by restricting the map to $S^{d}\times[\epsilon,1]$ we obtain
a homotopy of $h$ to a map $h_{\epsilon}$ from
$S^{d}\to\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$,
whose image is contained in
$\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$.
Let’s call this homotopy $\Psi$. By definition, $\Psi$ is a map
$S^{d}\times[\epsilon,1]\to\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$.
Since $\Psi$ is defined using $H$, and
$\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$
is an invariant subspace for $H$, it follows that the restriction of $\Psi$
keeps the basepoint $*$ of $S^{d}$ inside
$\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$
throughout. In other words, the restriction of $\Psi$ to $*\times[\epsilon,1]$
is a path in
$\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$.
$\Psi$ defines a pointed homotopy between $h$ and the conjugation of
$h_{\epsilon}$ by the path $\Psi|_{*\times[\epsilon,1]}$, and the latter lies
entirely in
$\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$.
It follows that as an element of
$\pi_{d}(\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right))$,
$h$ is in the image of
$\pi_{d}(\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right))$.
We have proved that the inclusion (3) is surjective on homotopy groups.

For injectivity, suppose $h\colon
S^{d}\to\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$
represents an element in the kernel. It follows that $h$ extents to a map
$\tilde{h}\colon
D^{d+1}\to\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$.
Using Corollary 2.5, we can find a homotopy $\Phi\colon
D^{d+1}\times[0,1]\to\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$
such that $\Phi|_{D^{d+1}\times\\{0\\}}=\tilde{h}$ and $\Phi(\partial
D^{d+1}\times I\cup
D^{d+1}\times\\{1\\})\subset\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$.
The restriction of $\Phi$ to $\partial D^{d+1}\times I\cup
D^{d+1}\times\\{1\\}$ defines a null homotopy of $h$ inside
$\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$.
We have proved that $h$ represents zero in
$\pi_{d}\left(\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\right)$
whenever $h$ represents an element in the kernel of the homomorphism induced
by the inclusion map in the homotopy. Thus the inclusion (3) induces an
injective homomorphism on homotopy groups. ∎

Let us say that an immersion of $\coprod_{k}D^{m}$ is non-$r$-overlapping if
the intersection of images of every $r$ components is empty. Note that a
componentwise embedding is an $r$-immersion if and only if it is
non-$r$-overlapping.

The following definition is taken from [Gro19].

######  Definition 2.7.

Let $f\colon\coprod_{k}D^{m}\to{\mathbb{R}}^{n}$ be a map. For each $1\leq
i\leq k$, let $0_{i}$ be the center of the $i$-th copy of $D^{m}$ in the
coproduct $\coprod_{k}D^{m}$. For each $r$-tuple of integers
$\vec{i}=(i_{1},\ldots,i_{r})$, where $1\leq i_{1}<i_{2}<\cdots<i_{r}\leq k$,
let

$f_{\vec{i}}=\frac{f(0_{i_{1}})+\cdots+f(0_{i_{r}})}{r}.$

Finally define $sd(f)$ by the following formula

$sd(f)=\frac{1}{\sqrt{r}}\ \underset{1\leq i_{1}<\cdots<i_{r}\leq
k}{\min}\sqrt{\sum_{j=1}^{r}||f(0_{i_{j}})-f_{\vec{i}}||^{2}}.$

The notation $sd$ stands for “safe distance”. It is a distance for which it is
guaranteed that if the radius of each disc is less than the safe distance,
then the immersion is non-$r$-overlapping (as we will prove shortly). The
formula for $sd(f)$ does not give the largest possible safe distance, but it
does not matter. It is important that $sd(f)$ depends continuously on $f$,
which is clearly the case.

Next, let us make precise the notion of a radius of an immersion of a union of
discs.

######  Definition 2.8.

Let $f\colon\coprod_{k}D^{m}\to{\mathbb{R}}^{n}$ be a map. Let $D^{m}_{i}$
denote the $i$-th copy of $D^{m}$ in the coproduct. Define the radius of $f$
to be the following

$R(f)=\sup_{1\leq i\leq k,\,x\in D^{m}_{i}}||f(x)-f(0_{i})||.$

Note that $R(f)$ can be $\infty$. But if, for example, $f$ is the restriction
of a map defined on a union of closed unit discs then $R(f)$ is finite.

The point of the last two definitions is that they give a condition for an
immersion to be non-$r$-overlapping. The following lemma is present implicitly
in [Gro19].

######  Lemma 2.9.

Let $f\colon\coprod_{k}D^{m}\to{\mathbb{R}}^{n}$ be a map. If $R(f)<sd(f)$
then $f$ is non-$r$-overlapping.

###### Proof.

Suppose by contradiction that $f$ is $r$-overlapping. Then there exist an
$r$-tuple $\vec{i}=(i_{1},\ldots,i_{r})$ and points $x_{i_{j}}\in
D^{m}_{i_{j}}$ such that $f(x_{i_{1}})=\cdots=f(x_{i_{r}})$. Let $z$ denote
this common value. Recall that $f_{\vec{i}}$ is the centroid of
$f(0_{i_{1}}),\ldots,f(0_{i_{r}})$. We have the following inequalities

$r\cdot
sd(f)^{2}\leq\sum_{j=1}^{r}||f(0_{i_{j}})-f_{\vec{i}}||^{2}\leq\sum_{j=1}^{r}||f(0_{i_{j}})-z||^{2}\leq
r\cdot R(f)^{2}$

which contradicts the assumption $R(f)<sd(f)$. ∎

We need to define one more invariant of a map of a union of discs. It codifies
the largest possible radius under a certain transformation that we will use.

######  Definition 2.10.

Let $f\colon\coprod_{k}D^{m}\to{\mathbb{R}}^{n}$ be a map. Let $D^{m}_{i}$
denote the $i$-th copy of $D^{m}$ in the coproduct. Define $LR(f)$ by the
following formula

$LR(f)=\sup_{1\leq i\leq k,\,0<t\leq 1,\,x\in
D^{m}_{i}}\frac{||f(tx)-f(0_{i})||}{t}.$

Just as with $R(f)$, $LR(f)$ can be infinite. Indeed, it always holds that
$R(f)\leq LR(f)$. But if, for example, $f$ is the restriction of a function
defined on a union of closed discs then $LR(f)<\infty$. Recall that for $0\leq
s\leq 1$, $f_{s}$ is defined by the formula $f_{s}(x)=f(sx)$. It follows that
if $0\leq s<1$ then $LR(f_{s})<\infty$. Let us record this simple fact in a
lemma.

######  Lemma 2.11.

  1. (1)

Whenever $s<1$, $LR(f_{s})<\infty$.

  2. (2)

$LR(f_{s})\leq s\cdot LR(f)$.

###### Proof.

(1) The case $s=0$ is trivial, because $f_{0}$ is constant on each disc, and
$LR(f_{0})=0$. For $x\in D_{i}^{m}$ and $0<s<1$, $sx\in sD_{i}^{m}$, where
$sD_{i}^{m}$ is the open disc of radius $s$ contained in $D_{i}^{m}$ whose
closure $\overline{sD_{i}^{m}}$ is also contained in $D_{i}^{m}$, so it is
easy to define an extension of $f_{s}$ to a union of closed discs.

(2) The case $s=0$ is trivial again. Let $s>0$. For $x\in D_{i}^{m}$, $sx\in
sD_{i}^{m}$, and if $0_{i}$ is the center of the disc $D_{i}^{m}$, then
$0_{i}$ is also the center of the disc $sD_{i}^{m}$. By definition,

$\displaystyle LR(f_{s})=\sup_{1\leq i\leq k,\,0<t\leq 1,\,sx\in
sD^{m}_{i}}\frac{||f(stx)-f(0_{i})||}{t}$ $\displaystyle=s\cdot\sup_{1\leq
i\leq k,\,0<t\leq 1,\,sx\in sD^{m}_{i}}\frac{||f(stx)-f(0_{i})||}{st}$
$\displaystyle\leq s\cdot\sup_{1\leq i\leq k,\,0<t\leq 1,\,x\in
D^{m}_{i}}\frac{||f(tx)-f(0_{i})||}{t}$ $\displaystyle=s\cdot LR(f)$

∎

We have the following simple but important observation.

######  Lemma 2.12.

Fix an $0<s<1$. Then $LR(f_{s})$ depends continuously on $f$.

###### Proof.

Suppose we have a sequence $f_{n}\in
C^{\infty}(\coprod_{k}D^{m},{\mathbb{R}}^{n})$, converging to $f$. We want to
prove that the sequence $LR((f_{n})_{s})$ converges to $LR(f_{s})$.

To say that $f_{n}$ converges to $f$ means, in particular, that for any multi-
index $\alpha$, $\partial^{\alpha}\\!f_{n}$ converges uniformly to
$\partial^{\alpha}\\!f$ on any compact subset of $\coprod_{k}D^{m}$. In
particular, $\partial^{\alpha}\\!f_{n}$ converges uniformly to
$\partial^{\alpha}\\!f$ on the union of closed discs of radius $s$. This in
turn implies that the sequence $\partial^{\alpha}\\!(f_{n})_{s}$ converges
uniformly to $\partial^{\alpha}\\!f_{s}$ on the entire space
$\coprod_{k}D^{m}$.

Let us define the sequence of functions
$g_{n}\colon\coprod_{k}D^{m}\times[0,1]\to{\mathbb{R}}^{n}$ by the following
formula, where, as usual, $D^{m}_{i}$ denotes the $i$-th copy of $D^{m}$,
$0_{i}$ is the center of $D^{m}_{i}$, and $x\in D^{m}_{i}$:

$g_{n}(x,t)=\left\\{\begin{array}[]{cc}\hskip
19.91684pt\frac{(f_{n})_{s}(xt)-(f_{n})_{s}(0_{i})}{t},&t>0\\\\[5.0pt]
\underset{h\to
0}{\lim}\frac{(f_{n})_{s}(xh)-(f_{n})_{s}(0_{i})}{h},&t=0\end{array}\right.$

Also define $g(x,t)$ similarly, by replacing $f_{n}$ with $f$. Then
$LR((f_{n})_{s})=\sup\\{g_{n}(x,t)\\}$ and $LR(f_{s})=\sup\\{g(x,t)\\}$. We
claim that $g_{n}$ converges uniformly to $g$. The claim implies that the
sequence $LR((f_{n})_{s})$ converges to $LR(f_{s})$, which is what we want.

It remains to prove the claim. Since $(f_{n})_{s}$ converges uniformly to
$f_{s}$, it is clear that for any $\delta>0$, $g_{n}$ converges to $g$
uniformly on the space $\coprod_{k}D^{m}\times[\delta,1]$.

Let $J(f_{n})_{s}$ be the differential of $(f_{n})_{s}$ at $0_{i}$. Using
Taylor theorem we can write for $x\in D^{m}_{i}$

$g_{n}(x,t)=J(f_{n})_{s}x+R_{n}(x,t)$

where the error term $R_{n}(x,t)$ satisfies the inequality

$||R_{n}(x,t)||\leq M_{n}|t|$

where $M_{n}$ is a constant determined by a bounded function of the second
derivatives of $(f_{n})_{s}$.

There is a similar formula for $g(x,t)$ with remainder term $R(x,t)$ and
constant $M$, determined by the second derivatives of $f_{s}$. For all
$\epsilon>0$ we can find a $\delta>0$ and an integer $n_{1}$, such that for
all $0\leq t\leq\delta$ and $n>n_{1}$ and $x\in\coprod_{k}D^{m}$ the following
inequalities hold

$||J(f_{n})_{s}x-J(f_{n})x||<\frac{\epsilon}{3}$
$||R_{n}(x,t)||<\frac{\epsilon}{3}$ $||R(x,t)||<\frac{\epsilon}{3}.$

It follows that for all $n>n_{1}$ and
$(x,t)\in\coprod_{k}D^{m}\times[0,\delta]$

$||g_{n}(x,t)-g(x,t)||<\epsilon.$

We also can find an $n_{2}$ such that for all $n>n_{2}$ and
$(x,t)\in\coprod_{k}D^{m}\times[\delta,1]$ it holds
$||g_{n}(x,t)-g(x,t)||<\epsilon$. Thus for all $n>\max(n_{1},n_{2})$ the
inequality $||g_{n}(x,t)-g(x,t)||<\epsilon$ holds for all $x$ and $t$. This
means that $g_{n}$ converges uniformly to $g$ and we have proved the claim. ∎

######  Definition 2.13.

We say that a function $f\colon\coprod_{k}D^{m}\to{\mathbb{R}}^{n}$ is small,
if $LR(f)<sd(f)$. Let

$\operatorname{rImm}^{\mathrm{sm}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\subset\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$

denote the subspace consisting of $r$-immersions that are componentwise
embeddings and are small.

######  Proposition 2.14.

The space
$\operatorname{rImm}^{\mathrm{sm}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$
is a deformation retract of
$\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$.
In particular, the inclusion is a homotopy equivalence.

###### Proof.

Let us define the function
$\alpha\colon\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\to(0,1)$
by the formula

$\alpha(f)=\min\left(\frac{1}{2},\frac{sd(f)}{4LR(f_{\\!\frac{1}{2}})}\right).$

Notice that $LR(f_{\\!\frac{1}{2}})<\infty$ by Lemma 2.11 (1), and therefore
$\alpha(f)$ is a well-defined positive number smaller than $1$. Also notice
that $sd(f)$ is obviously continuous in $f$, and $LR(f_{\\!\frac{1}{2}})$ is
continuous by Lemma 2.12. Therefore $\alpha$ is a continuous function.

Next, let $j_{f}\colon[0,1]\to[\alpha(f),1]$ be the canonical linear
homeomorphism. Let $j$ be the function

$j\colon\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\times[0,1]\to[0,1]$

defined by the formula $j(f,t)=j_{f}(t)$, then $j$ is continuous in both $f$
and $t$.

Now let us define a homotopy

$H\colon\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\times[0,1]\to\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$

by the formula $H(f,t)=f_{j_{f}(t)}$. Since $j_{f}$ is continuous in $f$ and
$t$, $H$ is continuous. Since $j_{f}(1)=1$ and $j_{f}(0)=\alpha(f)$, $H$ is a
homotopy between the identity function on
$\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$
and the function that sends $f$ to
$f_{\alpha(f)}=f_{\min(\frac{1}{2},\frac{sd(f)}{4LR(f_{\\!\frac{1}{2}})})}$.

Let us check that
$f_{\min(\frac{1}{2},\frac{sd(f)}{4LR(f_{\\!\frac{1}{2}})})}$ is small. This
means to check that

$LR(f_{\min(\frac{1}{2},\frac{sd(f)}{4LR(f_{\\!\frac{1}{2}})})})\leq
sd(f_{\min(\frac{1}{2},\frac{sd(f)}{4LR(f_{\\!\frac{1}{2}})})}).$

Note that $sd(f)$ only depends on the images of the centers of $D^{m}$s under
$f$, and therefore $sd(f_{s})=sd(f)$ for any $s$. So we need to prove that
$LR(f_{\min(\frac{1}{2},\frac{sd(f)}{4LR(f_{\\!\frac{1}{2}})})})\leq sd(f)$.

Suppose first that $\frac{sd(f)}{4LR(f_{\\!\frac{1}{2}})}\leq\frac{1}{2}$.
Then we have the inequalities (here we use Lemma 2.11 (2))

$LR(f_{\min(\frac{1}{2},\frac{sd(f)}{4LR(f_{\\!\frac{1}{2}})})})=LR(f_{\frac{sd(f)}{4LR(f_{\\!\frac{1}{2}})}})\leq\frac{sd(f)}{2LR(f_{\\!\frac{1}{2}})}LR(f_{\frac{1}{2}})=\frac{sd(f)}{2}<sd(f).$

Now suppose that $\frac{1}{2}\leq\frac{sd(f)}{4LR(f_{\\!\frac{1}{2}})}$. Then
we have the inequality $LR(f_{\\!\frac{1}{2}})\leq\frac{sd(f)}{2}$ and

$LR(f_{\min(\frac{1}{2},\frac{sd(f)}{4LR(f_{\\!\frac{1}{2}})})})=LR(f_{\frac{1}{2}})\leq\frac{sd(f)}{2}<sd(f).$

We have shown that $H(f,0)$ is small for every $f$. It is clear that if $f$ is
small, then $H(f,t)$ is small for all $t$. We have shown that $H$ is a
deformation retraction of
$\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$
onto
$\operatorname{rImm}^{\mathrm{sm}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$.
∎

The next step is to show that the space of small $r$-immersions that are
componentwise embeddings is equivalent to the space of $r$-immersions that are
componentwise linear.

######  Definition 2.15.

Let
$\operatorname{rImm}^{\mathrm{lin}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\subset\operatorname{rImm}^{\mathrm{sm}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$
be the subspace consisting of $r$-immersions that are linear on each
component.

######  Proposition 2.16.

The space
$\operatorname{rImm}^{\mathrm{lin}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$
is a deformation retract of
$\operatorname{rImm}^{\mathrm{sm}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$.

###### Proof.

Let us define the map
$H\colon\operatorname{rImm}^{\mathrm{sm}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\times[0,1]\to\operatorname{rImm}^{\mathrm{sm}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$
by the following formula. Suppose $D^{m}_{i}$ is the $i$-th copy of $D^{m}$ in
the coproduct, and $x\in D^{m}_{i}$. Then

$H(f,t)(x)=\left\\{\begin{array}[]{ll}f(0_{i})+\frac{f(tx)-f(0_{i})}{t},&t>0\\\
\hskip 6.82881ptf(0_{i})+D_{0_{i}}f(x),&t=0\end{array}\right.$

Here $D_{0_{i}}f(x)=\lim_{t\to 0}\frac{f(tx)-f(0_{i})}{t}$ is a well-defined
linear function of $x$, because $f$ is differentiable at $0_{i}$. It follows
from the definition of the Whitney topology that the function $H$ is
continuous. It is easy to check from the definitions that

  1. (1)

For every fixed $t$ and
$f\in\operatorname{rImm}^{\mathrm{sm}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$,
the function $x\mapsto H(f,t)(x)$ is an element of
$\operatorname{rImm}^{\mathrm{sm}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$.

  2. (2)

If $f$ is linear on each component, then for every fixed $t$ the function
$x\mapsto H(f,t)(x)$ is linear on each component.

  3. (3)

For every $f$ the function $x\mapsto H(f,0)(x)$ is linear on each component.

It follows that $H$ defines a deformation retraction of
$\operatorname{rImm}^{\mathrm{sm}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$
onto
$\operatorname{rImm}^{\mathrm{lin}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$.
∎

Next, we can prove that the evaluation map restricted to
$\operatorname{rImm}^{\mathrm{lin}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$
is an equivalence.

######  Lemma 2.17.

The map

$\operatorname{ev}\colon\operatorname{rImm}^{\mathrm{lin}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\to\operatorname{rConf}(k,{\mathbb{R}}^{n})\times\operatorname{L}({\mathbb{R}}^{m},{\mathbb{R}}^{n})^{k}$

defined by evaluating at the center of each disc $D^{m}$ and also
differentiating at the center of each disc, is a homotopy equivalence.

###### Proof.

A linear map is determined by its derivative and a single value, so it almost
looks as if the map is a homeomorphism. But remember that we defined
$\operatorname{rImm}^{\mathrm{lin}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$
to be a subspace of
$\operatorname{rImm}^{\mathrm{sm}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$.
I.e., it is the space of componentwise linear $r$-immersions that are also
small. For linear maps, the smallness condition amounts to the following
inequality, that has to hold for each $i$ between $1$ and $k$:

$||D_{0_{i}}f||\leq sd(f).$

Here $||D_{0_{i}}f||$ denotes the operator norm of $D_{0_{i}}f$. It is easy to
show that the space
$\operatorname{rConf}(k,{\mathbb{R}}^{n})\times\operatorname{L}({\mathbb{R}}^{m},{\mathbb{R}}^{n})^{k}$
deformation retracts onto the image of small linear $r$-immersions. One has to
multiply the linear transformations from ${\mathbb{R}}^{m}$ to
${\mathbb{R}}^{n}$ by a factor that will make their norms smaller than
$sd(f)$. ∎

Finally we can prove the main result.

###### Proof of Theorem 2.1.

We have constructed the following composition of maps

$\operatorname{rImm}^{\mathrm{lin}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\hookrightarrow\operatorname{rImm}^{\mathrm{sm}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\hookrightarrow\operatorname{rImm}^{\mathrm{ce}}\\!\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\hookrightarrow\\\
\hookrightarrow\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\xrightarrow{\operatorname{ev}}\operatorname{rConf}(k,{\mathbb{R}}^{n})\times\operatorname{L}({\mathbb{R}}^{m},{\mathbb{R}}^{n})^{k}.$

We have shown that each one of the inclusions is an equivalence, and that the
composition is an equivalence. It follows that the map marked
$\operatorname{ev}$ is an equivalence. ∎

######  Corollary 2.18.

Choose a basepoint in
$\operatorname{Imm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$, and let
$\overline{\operatorname{rImm}}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$
be the homotopy fiber of the map
$\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\to\operatorname{Imm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)$.
Then the following composition

$\overline{\operatorname{rImm}}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\to\operatorname{rImm}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\to\operatorname{rConf}(k,{\mathbb{R}}^{n})$

is an equivalence, i. e.

$\overline{\operatorname{rImm}}\left(\coprod_{k}D^{m},{\mathbb{R}}^{n}\right)\simeq\operatorname{rConf}(k,{\mathbb{R}}^{n})$

## References

  * [AŠ] Arone, Gregory and Šarčević, Franjo.  Homological convergence of the manifold calculus Taylor tower for $r$-immersions in $\mathbb{R}^{n}$.  In preparation.
  * [DT15] Dobrinskaya, Natalya and Turchin, Victor.  Homology of non-$k$-overlapping discs.  Homology Homotopy Appl. 17(2):261–290, 2015.
  * [Gro19] Grossnickle, Keely.  Non-k-Equal Configuration and Immersion Spaces.  ProQuest LLC, Ann Arbor, MI. Thesis (Ph.D.)–Kansas State University
  * [SŠV20] Schreiner, Bridget and Šarčević, Franjo and Volić, Ismar.  Low stages of the Taylor tower for $r$-immersions.  Involve, a J. of Math. 13(1):51–75, 2020.
  * [Wei99] Weiss, Michael S.  Embeddings from the point of view of immersion theory I.  Geom. Topol. 3:67–101 (electronic), 1999.