# Blessing of High-Order Dimensionality: from Non-Convex to Convex
Optimization for Sensor Network Localization

Mingyu Lei<EMAIL_ADDRESS>Shanghai Jiao Tong University  Jiayu Zhang
<EMAIL_ADDRESS>Shanghai Jiao Tong University  Yinyu Ye
<EMAIL_ADDRESS>Standford University

###### Abstract

This paper investigates the Sensor Network Localization (SNL) problem, which
seeks to determine sensor locations based on known anchor locations and
partially given anchors-sensors and sensors-sensors distances. Two primary
methods for solving the SNL problem are analyzed: the low-dimensional method
that directly minimizes a loss function, and the high-dimensional semi-
definite relaxation (SDR) method that reformulates the SNL problem as an SDP
(semi-definite programming) problem. The paper primarily focuses on the
intrinsic non-convexity of the loss function of the low-dimensional method,
which is shown in our main theorem. The SDR method, via second-order dimension
augmentation, is discussed in the context of its ability to transform non-
convex problems into convex ones; while the first-order direct dimension
augmentation fails. Additionally, we will show that more edges don’t
necessarily contribute to the better convexity of the loss function. Moreover,
we provide an explanation for the success of the SDR+GD (gradient descent)
method which uses the SDR solution as a warm-start of the minimization of the
loss function by gradient descent. The paper also explores the parallels among
SNL, max-cut, and neural networks in terms of the blessing of high-order
dimension augmentation.

Keywords— Semi-definite Programming, Sensor Network Localization, High-Order
Dimension Augmentation, Graph Realization

##  1 Introduction

A sensor network is a network made up of devices equipped with rangefinders.
The nodes of the network are bipartite, comprising anchors and sensors. The
positions of the anchors are fixed and known. The sensor network localization
(SNL) problem aims to determine sensor locations based on actual anchor
locations and partially given anchors-sensors and sensors-sensors distances,
taking into account possible noise.

In this paper, we explore two important methods for solving the SNL problem.
The first method involves minimizing a certain loss function without
constraints using an iterative optimization algorithm; see, e.g., [4, 5, 29,
38, 41]. The second method, known as the semi-definite relaxation (SDR)
method, transforms the original non-convex optimization problem into a convex
one by second-order dimension augmentation; see, e.g., [5, 6, 7, 37, 41]. We
should emphasize here that the loss function has different forms. The
differences among different forms are the degrees of the terms. One of the
forms is a polynomial, where the inside degree and the outside degree are both
$2$. For each form of the loss function, we can augment its dimension. The
well-studied SDR method is the dimension augmentation of the form with inside
degree $2$ and outside degree $1$.

While extensive research has been done on the algorithmic aspect of both
methods, the geometric landscape of their optimization formulations remains
largely unexplored, particularly for the first method. In this paper, we focus
on the non-convex property of the loss function, which is important for the
analysis of the first method.

The SDR method involves increasing the problem’s dimension to transform it
into a convex optimization problem. This allows for the resolution of the
original non-convex problem. Notably, the SDR+GD (gradient descent) method,
which employs the SDR solution as a warm-start for the loss function method
solved by GD, exhibits superior performance in practice [4, 5, 41].

To simplify the discussion, we will refer to the first method as the “loss
function method” since our primary focus lies in analyzing the non-convex
property of the loss function that is used by this method. Additionally, we
emphasize that the loss function method is low-dimensional compared to the SDR
method, which is high-dimensional. The “low-dimensional” here has two
meanings. The first is that the loss function method has fewer optimization
variables than the SDR method. For instance, the phrase “dimension
augmentation” in our paper means that one considers a new optimization problem
that has more optimization variables compared with the original low-
dimensional optimization problem. The second is the geometric meaning of the
solutions provided by the two methods. It is shown by [37] that the solution
to the SDR optimization problem, which has more variables, can be considered
as a graph realization of the original SNL problem in a higher-dimensional
space.

Additionally, the dimension augmentation employed by the SDR method is a
product-type dimension augmentation, therefore a second-order dimension
augmentation. Here, the order of the dimension augmentation is determined by
the highest number of original variables that are multiplied together to form
the augmented variables. In the works of Lasserre [20, 21], the benefits of
high-order dimension augmentation are outlined. Lasserre proved that as the
order of the dimension augmentation of the original general polynomial
optimization increases, the solution to the dimension-augmented optimization
problem will converge to the solution to the original polynomial optimization
problem. Here, the dimension augmentation of the original polynomial
optimization is always an SDP. Furthermore, under certain circumstances,
finite convergence is guaranteed [20, 21, 24]. The second-order dimension
augmentation, i.e., the SDR method, of the loss function method has the same
solution as the loss function method under certain circumstances as we will
show in Section 4.2. Therefore, this is an example of finite convergence,
although our original optimization problem is slightly different from a
polynomial optimization problem. In the context of SNL, Nie proposed a fourth-
order dimension augmentation of the polynomial form of the loss function
method [23]. This is also an SDP and the finite convergence is guaranteed
under certain circumstances. However, as mentioned above, finite convergence
can be guaranteed using only second-order dimension augmentation; that is,
second-order is enough in the context of SNL. Nonetheless, the direct
dimension augmentation, or the first-order dimension augmentation of the loss
function method, remains non-convex. This will be proved in Section 3.3.

Similar findings have also been observed in the field of neural networks.
Large neural networks increase the dimension of the problem and extract more
information from the dataset; transfer learning can also be considered as
generating a warm-start for new models, with probably less trainable
parameters or a cheaper training process. Both increasing the size of neural
networks and transfer learning contribute to the good performance of the
neural networks. Therefore, we will give a comparison of the two scenarios for
SNL and neural networks.

Related works

Biswas and Ye [7] reformulated sensor network localization (SNL) as a semi-
definite programming (SDP) problem. Their pioneering work involved the
development of the semi-definite relaxation (SDR) technique for SNL, which
transforms the SNL problem into a convex optimization problem and exhibits
outstanding performance. However, the SDR solutions to SNL problems that are
nearly ill-posed or affected by noise are sometimes inaccurate. Furthermore,
from an algorithmic point of view, solving the SDP given by the SDR method
remains to be time-consuming today. We refer the readers to [6, 38, 41, 29]
for some methods to accelerate the standard SDR proposed in [7].

Later, several methods were presented to improve the accuracy and speed of SDR
in SNL problems affected by noise. For instance, heuristics such as reusing
the SDR solution to regularize the problem or using a warm-start showed
outstanding performance [5, 4]. Research such as [42, 37, 36] gave good
theoretical results on the original version of SDR [7]. However, their results
cannot fully explain why the regularized SDR works in noisy cases. It is also
not clear when the minimization (for example, gradient descent) will converge
to the global minimizer during the stage of minimizing the loss function.

The literature on source localization suggested that, in the one-sensor case
of SNL, the loss function is non-convex in general [1, 26]. Additionally,
better performance of minimizing the loss function when a warm-start is used
was reported in [5]. However, no rigorous results on the commonly encountered
SNL loss functions have been presented and the geometric landscape of the loss
function remains largely unexplored.

Another line of work involves implementing multidimensional scaling (MDS)
techniques, as seen in works such as [17, 31, 33, 40]. MDS methods can provide
a rough estimation for further minimization of the loss function; see, e.g.,
[15]. However, benchmarks in [15] and figures in [33, 40] indicated that MDS
accuracy is lower than SDR for cases with limited connectivity. Nonetheless,
MDS is faster [15] and has already been applied to various fields [31].

Our contributions

  * •

In Section 5, we conduct a comprehensive analysis of the SNL loss function
landscape. Our main theorem 3.2 establishes that, with a high probability
dependent on the number of sensors, the loss function is non-convex. We also
demonstrate that directly augmenting the problem’s dimension does not yield a
convex loss function. However, the second-order dimension augmentation, in
other words, the SDR method, is always convex. Together with Nie’s fourth-
order dimension augmentation [23], we can highlight the blessing of high-order
dimension augmentation.

  * •

It was thought that more edges (information) contribute to a better loss
function of SNL and if sufficient edges are given, the loss function will be
convex. This is correct intuitively because more information usually yields
better problems and if sufficient edges are given, the graph of the SNL
problem can even be a complete graph, meaning that the SNL problem has the
best rigidity. However, more edges don’t always contribute to a better loss
function and even if all edges are given, the loss function can still be non-
convex as we will show. Specifically, we will provide an example where if more
edges are given, the originally convex loss function will become non-convex.
Additionally, following our main theorem, we will prove that when anchors are
relatively few, even if all edges are given, the loss function is non-convex
with high probability.

  * •

Prior works (e.g., [5, 4, 41]) have reported practical success using the SDR
solution as a warm-start for minimization, but a comprehensive theoretical
explanation for this success has been lacking. Building on a deeper
understanding of the loss function landscape, we provide a more rigorous
explanation for the effectiveness of this method, referred to as SDR+GD in our
paper. The explanation draws upon insights from graph rigidity theory,
offering valuable insights into the reasons behind the success of SDR+GD.

  * •

Some perspectives are provided in this paper. First and most importantly, the
success of the second-order and the fourth-order dimension augmentation and
the failure of the first-order dimension augmentation in the context of SNL,
and the success of the second-order dimension augmentation in the context of
max-cut indicates the blessing of high-order dimensionality. Second, the
advantage of specific dimension augmentation and the advantage of the scenario
that uses the high-dimensional solution as the warm-start of the new model are
observed in both the SNL and the neural network fields. The reasons for the
advantages in the SNL field and in the neural networks field may have common
explanations.

Outline of the paper

The rest of the paper is organized as follows. In Section 2 we define some key
concepts. In Section 3 we prove that the loss function (2) is non-convex with
high probability in our main Theorem 3.2 and provide an example where as more
edges are given, the originally convex loss function becomes non-convex. We
also show that direct dimension augmentation cannot improve the loss function
method. In Section 4 we discuss the convexity of the SDR’s optimization
problem obtained by a product-type dimension augmentation of the loss function
method. In Section 5 we provide an explanation for why the regularized SDR+GD
method in [5, 4] works. In Section 6, we discuss the relation between our
findings and some similar methods in neural networks, including dimension
augmentation and projecting warm-starts. Finally, in Section 7, we give our
conclusions and some future work.

##  2 Preliminaries

We will define the concepts and notations that we will discuss in this paper.
The notation in this paper is mostly standard.

First of all, we use $\|\cdot\|$ to denote the $L_{2}$ norm and
$\|\cdot\|_{1}$ to denote the $L_{1}$ norm. Moreover, the distance we refer to
in this paper is the Euclidean distance. We use $\overline{A}$ to denote the
complement of a set $A$ and $\sqcup$ to denote the disjoint union. Given
symmetric matrices $X$ and $Y$, we use $X\succeq Y$ to indicate that $X-Y$ is
positive semi-definite.

Graph $G=(V,E)$ in this paper is first a finite, simple, and undirected graph.
Additionally, the vertices of it are divided into two types of vertices or two
colors. One is “anchor”. The other is “sensor”. Finally, there is no edge
between anchors and anchors. In this paper, we always use $s_{i}$ to denote
sensors and $a_{i}$ to denote anchors. Therefore, if $G$ has $n$ sensors and
$m$ anchors, we have $G$’s vertices set
$V=\\{s_{1},\dots,s_{n},a_{1},\dots,a_{m}\\}$. We also use $V_{s}$ to denote
all sensors and $V_{a}$ to denote all anchors. Therefore, we have
$V_{s}=\\{s_{1},\dots,s_{n}\\}$ and $V_{a}=\\{a_{1},\dots,a_{m}\\}$.

Framework is defined to be a graph $G$ together with an embedding
$p:V\to\mathbb{R}^{d}$ mapping the vertices into an Euclidean space. Every
vertex in $V$ is mapped to its position by the map $p$. Therefore, we can
calculate every Euclidean distance between two vertices.

$N_{x},N_{a}$ are defined to be the known edges of a graph $G$. They are a
bipartition of the set $E$ of $G$’s edges. $N_{x}$ is the set of all edges
between different sensors; $N_{a}$ is the set of all edges between sensors and
anchors. Therefore, if $V=\\{s_{1},\dots,s_{n},a_{1},\dots,a_{m}\\}$, we have
$N_{x}=\\{\\{s_{i},s_{j}\\}|\\{s_{i},s_{j}\\}\in E\\}$ and
$N_{a}=\\{\\{a_{i},s_{j}\\}|\\{a_{i},s_{j}\\}\in E\\}$. To simplify notation,
we can rewrite $N_{x}=\\{\\{i,j\\}|\\{s_{i},s_{j}\\}\in E\\}$ and
$N_{a}=\\{(i,j)|\\{a_{i},s_{j}\\}\in E\\}$. Here, “$\\{\cdot\\}$” means an
unordered set and “$(\cdot)$” means an ordered set.

An SNL problem $(G,d,\tilde{d},a)$ is defined to be a problem where we know
$\xi=(G,d,\tilde{d},a)$ and want to find frameworks with proper positions of
sensors. Among them, $G$ is a graph of sensors and anchors, $d$ is a mapping
$N_{x}\to\mathbb{R}^{+}$ meaning all given distances between different
sensors, $\tilde{d}$ is a mapping $N_{a}\to\mathbb{R}^{+}$ meaning all given
distances between sensors and anchors, and $a$ is a mapping
$V_{a}\to\mathbb{R}^{d}$ meaning all positions of the anchors. To simplify
notation, we use $d_{ij}$ to denote $d(\\{s_{j},s_{j}\\})$, $\tilde{d}_{ij}$
to denote $\tilde{d}(\\{a_{i},s_{j}\\})$, and the same symbol $a_{i}$ to
denote the position of the anchor $a_{i}$. We call an SNL problem
$d$-dimensional if the dimension of its anchors is $d$. We define a framework
to be the solution to the SNL problem if the framework has the same graph $G$
and the same positions of anchors as the SNL problem and generates equal
distances to the SNL problem. Equivalently, to solve an SNL problem is to find
$x_{i}$’s that satisfy the following equations,

$\begin{cases}\|a_{i}-x_{j}\|=\tilde{d}_{ij}\quad\forall(i,j)\in N_{a},\\\
\|x_{i}-x_{j}\|=d_{ij}\quad\forall\\{i,j\\}\in N_{x}.\end{cases}$ (1)

Therefore, we also say that $(x_{1}^{T}\ x_{2}^{T}\ \dots\
x_{n}^{T})^{T}\in\mathbb{R}^{dn}$ is a solution to the SNL problem.
Furthermore, a framework can generate a unique SNL problem to which the
framework is a solution.

Directly increasing or augmenting the dimension of the SNL problem
$(G,d,\tilde{d},a)$ from $d$-dimension to $d^{\prime}$-dimension means
increasing the dimension of the anchors $a$ by adding zeros in the augmented
coordinates of the anchors’ positions. Therefore, the solution to the high-
dimensional SNL problem has the same dimension as the high-dimensional
anchors. This is what we call a high-dimensional solution to an SNL problem.
Relatively speaking, the solution to the original SNL problem is low-
dimensional.

A Unit-disk SNL case $(U,r,n,a)$ is defined by the region
$U\subseteq\mathbb{R}^{d}$, the radius $r>0$, the number of sensors
$n\in\mathbb{N}$, and the positions of anchors $a={a_{1},\dots,a_{m}}\subset
U$. This case represents a distribution of the SNL problem
$(G,d,\tilde{d},a)$, generated by a random framework. The sensors are $n$
random vectors, independently drawn from a probability distribution $P$ on
$U$. The anchors remain the same as the given ones and an edge is included in
the framework if and only if the Euclidean distance between the two vertices
of the edge is less than or equal to $r$. In this paper, $U$ is bounded and
$P$ is the uniform distribution on $U$.

The loss function of an SNL problem $(G,d,\tilde{d},a)$ is defined to be

$\operatorname{loss}\left(x\right)=\sum_{\\{i,j\\}\in
N_{x}}|\|x_{i}-x_{j}\|^{b}-d_{ij}^{b}|^{c}+\sum_{(i,j)\in
N_{a}}|\|a_{i}-x_{j}\|^{b}-\tilde{d}_{ij}^{b}|^{c},$ (2)

where $x_{i}\in\mathbb{R}^{d}$ for $i=1,2,\dots,n$. We call $b$ the inside
degree and $c$ the outside degree. The domain of $\operatorname{loss}(x)$ is
$\mathbb{R}^{dn}$ and the codomain of $\operatorname{loss}(x)$ is
$\mathbb{R}$. Moreover, we define the loss function of a framework to be the
loss function of the SNL problem generated by the framework.

In this paper, we often use the loss function

$\operatorname{loss}\left(x\right)=\sum_{\\{i,j\\}\in
N_{x}}|\|x_{i}-x_{j}\|^{2}-d_{ij}^{2}|+\sum_{(i,j)\in
N_{a}}|\|a_{i}-x_{j}\|^{2}-\tilde{d}_{ij}^{2}|,$ (3)

which is the $b=2,c=1$ case of (2).

We introduce some basic definitions from graph rigidity theory.

A framework is defined to be locally rigid if it is not flexible; i.e., there
exists a neighbourhood of the framework’s sensors such that there is no other
solution to the SNL problem generated by the framework in the neighbourhood.

A framework is defined to be globally rigid if the SNL problem generated by
the framework has a unique solution.

A framework is defined to be universally rigid if the SNL problem generated by
the framework has a unique solution in any dimension.

##  3 Non-Convexity of the Low-Dimensional Optimization

In this section, we mainly discuss the low-dimensional optimization method,
i.e., minimizing the loss function.

This method of minimizing the loss function is widely used in former works
such as [5, 4, 38, 29, 41]. In this section, we will show that the loss
function is often non-convex. Specifically, in Subsection 3.2, we will prove
that in the unit-disk SNL case, if the anchors are relatively few, the loss
function (2) will be non-convex with a high probability, which is our main
depiction of the non-convexity of the loss function.

The unit-disk SNL case is important in practice since the wireless sensors can
only communicate with their neighbors within a limited radio range or
“radius”. The importance of the unit-disk SNL case was also mentioned in [5,
4, 42, 41, 7, 19]. Hence, it is common that many researchers assume the unit-
disk SNL case to carry out probabilistic and combinatorial results on sensor
networks, we refer the readers to [11, 28, 32, 2] for details of these
results.

We first show some landscapes of the SNL loss function to let the readers know
its common non-convexity intuitively in Subsection 3.1. Next, we introduce our
main theorem in Subsection 3.2. Moreover, we will show that direct dimension
augmentation is also often non-convex in Subsection 3.3.

###  3.1 Landscape Examples of the SNL Loss Function

In this subsection, in order to show the landscape more clearly, the dimension
of the SNL problem is set to $2$ and the loss function (2) is set to the
$b=2,c=1$ case (3).

The loss function (3) can be regarded as a summation of positive terms
assigned for each edge of the graph. We first consider one term of the
summation, i.e.,

$f_{ij}(x_{j})=|\|a_{i}-x_{j}\|^{2}-\tilde{d}_{ij}^{2}|.$ (4)

Figure 1: Landscape of loss function of 1 anchor 1 sensor

The minimizers of the loss function (4) form a circle of radius
$\tilde{d}_{ij}$ around the anchor, see Figure 1.

In general, the loss function (3) is non-convex. Here is a non-convex example
of the SNL loss function with 3 anchors and 1 sensor. We construct the example
by setting the positions of the anchors to $(-1,0)$, $(1,0)$ and $(0,0.4)$ and
the position of the sensor to $(0,1)$. The graph of the framework is fully
connected. By direct calculation, the loss function of this SNL problem is

$\displaystyle f(x)=$
$\displaystyle|\|x-(-1,0)\|^{2}-(\sqrt{2})^{2}|+|\|x-(1,0)\|^{2}-(\sqrt{2})^{2}|$
$\displaystyle+|\|x-(0,0.4)\|^{2}-0.6^{2}|,$

where $x\in\mathbb{R}^{2}$. It is easy to see from Figure 2, which is the
landscape of $f(x)$, that $f(x)$ is non-convex and has at least two local
minimizers. We note that the framework is globally rigid, which means that
there exists a unique solution to the SNL problem (1). However, the loss
function $f(x)$ has at least two local minimizers. As a result, global
rigidity does not imply the convexity of the SNL loss function, even if the
associated graph of the framework is fully connected. Furthermore, as a
comparison, we can see in Figure 4 that the loss function of SDR optimization
is convex.

Figure 2: Landscape of loss function of 3 anchors 1 sensor

###  3.2 Common Non-Convexity

In this subsection, we will prove that the loss function is often non-convex
in the unit-disk SNL case.

We give an outline of the proof in this paragraph. First, a sufficient
condition for the loss function (2) to be non-convex is given in Lemma 3.1.
Then we use the sufficient condition (5) to estimate the probability. We first
estimate the left-hand side of (5) by a constructive event. The event is an
intersection of events that control the lower bound on the distances on the
left-hand side of (5). The probability of the event is estimated by some
probability inequalities. Using some deterministic inequalities, we estimate
the right-hand side of (5). Then if this event occurs, the sufficient
condition (5) holds. This finishes the proof.

Then we begin the rigorous proof.

We first have this key lemma as a sufficient condition for the loss function
(2) to be non-convex.

######  Lemma 3.1.

A sufficient condition for the loss function (2) to be non-convex is

$2\sum_{\\{i,j\\}\in N_{x}}d_{ij}^{bc}>\sum_{(i,j)\in
N_{a}}|\|a_{i}+s_{j}\|^{b}-\tilde{d}_{ij}^{b}|^{c}.$ (5)

###### Proof.

Consider three points. $s\in\mathbb{R}^{dn}$ is the sensors’ point.
$z=0\in\mathbb{R}^{dn}$ is the second point. $y=-s$ is the third point. It is
obvious that $z=0.5s+0.5y$. Therefore, a sufficient condition for the loss
function (2) to be non-convex is

$2\operatorname{loss}(z)>\operatorname{loss}(s)+\operatorname{loss}(y),$

which is

$2\sum_{\\{i,j\\}\in N_{x}}d_{ij}^{bc}>\sum_{(i,j)\in
N_{a}}(|\|a_{i}+s_{j}\|^{b}-\tilde{d}_{ij}^{b}|^{c}-2|\|a_{i}\|^{b}-\tilde{d}_{ij}^{b}|^{c}).$

Therefore, the inequality (5) is the sufficient condition for the loss
function (2) to be non-convex. This finishes the proof. ∎

######  Remark.

The condition appears to be too strong in general. However, the condition is
not that strong in the specific context of SNL. As demonstrated in Theorem
3.4, the non-convexity of the loss function (2) typically arises from the
symmetry of the nodes. Additionally, we can translate and rotate the nodes
such that the axis of symmetry passes the origin. Therefore, this sufficient
condition is the key of the non-convexity of the loss function (2) to some
extent.

######  Theorem 3.2.

For a unit-disk SNL case $(U,r,n,a)$, assume that the region $U$ is connected,
open, and bounded. Then for any given set of anchors $a$, radius $r>0$, and
probability $p_{0}<1$, there exists $N\in\mathbb{N}$ such that for all number
of sensors $n>N$, the probability that the loss function (2) of the SNL
problem in the unit-disk SNL case $(U,r,n,a)$ is not convex is larger than
$p_{0}$. Specifically, a lower bound on the probability is
$1-nv\tbinom{n-1}{v-1}(1-p_{r})^{n-v}$. Here, $v=\lfloor\sqrt{n}\rfloor$ and
$p_{r}$ is a positive constant probability dependent solely on the region $U$
and the radius $r$. The definition of $p_{r}$ will be given in the proof.

###### Proof.

Without loss of generality, we assume that the origin is in the region $U$.

Then we define some events. Define event $A_{i}$ to be $\\{$There exist at
least $v$ sensors in the region between two concentric circles with radii
$\varepsilon r$ and $r$ centered at $s_{i}\\}$. Here, we set $v$ to
$\lfloor\sqrt{n}\rfloor$ and set $\varepsilon\in(0,1)$ to satisfy the
following property: no matter where the sensor $s$ is, the probability that
the distance from $s$ to another independent random sensor $s^{\prime}$
belongs to $[\varepsilon r,r]$ has a uniform lower bound $p_{r}>0$, or more
rigorously, there exists $p_{r}>0$ such that for all $x\in U$, we have

$P(\|s-s^{\prime}\|\in[\varepsilon r,r]|s=x)\geq p_{r}.$

In most cases, such as a square region, we can simply set $\varepsilon$ to
$0.5$.

If the event $A_{1}\cap A_{2}\cap\dots\cap A_{n}$ occurs, we have

$\sum_{\\{i,j\\}\in N_{x}}d^{bc}_{ij}\geq\frac{1}{2}nvr^{bc}\varepsilon^{bc}.$
(6)

Then we estimate the probability $P(A_{1}\cap A_{2}\cap\dots\cap A_{n})$. By
basic knowledge of probability theory, we have

$\displaystyle P(A_{1}\cap A_{2}\cap\dots\cap A_{n})$
$\displaystyle=1-P(\overline{A_{1}\cap A_{2}\cap\dots\cap A_{n}})$
$\displaystyle=1-P(\overline{A_{1}}\cup\overline{A_{2}}\cup\dots\cup\overline{A_{n}})$
$\displaystyle\geq 1-\sum_{i=1}^{n}P(\overline{A_{i}})$
$\displaystyle=1-nP(\overline{A_{1}}).$ (7)

Then we estimate $P(\overline{A_{1}})$. Define event $A_{1i}$ to be $\\{$There
exist exactly $i$ sensors in the region between two concentric circles with
radii $\varepsilon r$ and $r$ centered at $s_{1}\\}$. Then, we have

$\overline{A_{1}}=A_{10}\sqcup A_{11}\sqcup A_{12}\sqcup\dots\sqcup
A_{1(v-1)}.$

Therefore, we have

$P(\overline{A_{1}})=P(A_{10})+P(A_{11})+\dots+P(A_{1(v-1)}).$ (8)

Then we estimate $P(A_{1k})$ for $k=0,\dots,v-1$. Let $s^{\prime}$ be an
independent random sensor, we define

$p_{s_{1}}:=P({\|s^{\prime}-s_{1}\|\in[\varepsilon r,r]}|s_{1})$

for all fixed $s_{1}\in U$. By the definition of $p_{r}$, we have
$p_{s_{1}}\in[p_{r},1]$. Therefore,

$P(A_{1k})=\mathbb{E}(\mathbbm{1}_{A_{1k}})=\mathbb{E}(\mathbb{E}(\mathbbm{1}_{A_{1k}}|s_{1}))=\mathbb{E}(\tbinom{n-1}{k}(1-p_{s_{1}})^{n-1-k}p_{s_{1}}^{k}),$
(9)

for all $k=0,1,\dots,v-1$. Then we estimate the term
$\tbinom{n-1}{k}(1-p_{s_{1}})^{n-1-k}p_{s_{1}}^{k}$ in Lemma 3.3.

######  Lemma 3.3.

If $n$ satisfies $(n-1)p_{r}\geq\lfloor\sqrt{n}\rfloor-1$ and
$k\in\\{0,1,\dots,v-1\\}$ is given, we have

$(1-p)^{n-1-k}p^{k}\leq(1-p_{r})^{n-1-k}p_{r}^{k}$

for all $p\in[p_{r},1]$.

###### Proof.

Define

$f(p):=(1-p)^{n-1-k}p^{k}.$

Then its derivative is

$f^{\prime}(p)=(1-p)^{n-1-k-1}p^{k-1}\big{(}(n-1-k)(-1)p+(1-p)k\big{)}.$ (10)

As $(n-1)p_{r}\geq\lfloor\sqrt{n}\rfloor-1$, we have

$k\leq(n-1)p$

for all $k=0,1,2,\dots,v-1$ and $p\in[p_{r},1]$. Therefore, we have

$(k+1-n)p+(1-p)k=(1-n)p+k\leq 0$

for all $k=0,1,2,\dots,v-1$ and $p\in[p_{r},1]$. Therefore, according to (10),
we have $f^{\prime}(p)\leq 0$ for all $p\in[p_{r},1]$. As a result, $f(p)\leq
f(p_{r})$; i.e.,

$(1-p)^{n-1-k}p^{k}\leq(1-p_{r})^{n-1-k}p_{r}^{k}.$

∎

By Lemma 3.3, if $n$ is large enough, we have

$P(A_{1k})=\mathbb{E}(\tbinom{n-1}{k}(1-p_{s_{1}})^{n-1-k}p_{s_{1}}^{k})\leq\tbinom{n-1}{k}(1-p_{r})^{n-1-k}p_{r}^{k}.$

Therefore, by (8), we have

$\displaystyle P(\overline{A_{1}})$ $\displaystyle=$ $\displaystyle
P(A_{10})+P(A_{11})+\dots+P(A_{1(v-1)})$ $\displaystyle\leq$
$\displaystyle\sum_{k=0}^{v-1}\tbinom{n-1}{k}(1-p_{r})^{n-1-k}p_{r}^{k}$
$\displaystyle\leq$ $\displaystyle v\tbinom{n-1}{v-1}(1-p_{r})^{n-v}.$

As a consequence, for large enough $n$,

$nP(\overline{A_{1}})\leq nv\tbinom{n-1}{v-1}(1-p_{r})^{n-v}\leq
vn^{\sqrt{n}}(1-p_{r})^{\frac{1}{2}n}.$

As $n$ becomes larger, $vn^{\sqrt{n}}(1-p_{r})^{\frac{1}{2}n}$ is approaching
$0$. Therefore, by (7), $P(A_{1}\cap A_{2}\cap\dots\cap A_{n})$ is approaching
$1$.

Next, we consider (5). Denote the region’s diameter by $D$; i.e.,

$D:=\sup_{x,y\in U}\|x-y\|.$

Since we have assumed that the origin is in the region $U$, we have
$\|a_{i}\|,\|s_{i}\|\leq D$. Due to the definition of $D$, we also have
$|\tilde{d}_{ij}|\leq D$. Therefore, we have

$\displaystyle\sum_{(i,k)\in
N_{a}}|\|a_{i}+s_{j}\|^{b}-\tilde{d}_{ij}^{b}|^{c}$ $\displaystyle\leq$
$\displaystyle\sum_{(i,k)\in
N_{a}}\max\\{\|a_{i}+s_{j}\|^{bc},\tilde{d}_{ij}^{bc}\\}$ $\displaystyle\leq$
$\displaystyle\sum_{(i,k)\in N_{a}}(2D)^{bc}$ $\displaystyle\leq$
$\displaystyle nm(2D)^{bc}.$ (11)

Here, we denote the number of anchors by $m$. Due to (6) and (11), if $n$ is
big enough, (5) holds. Therefore, with a high probability larger than
$1-nv\tbinom{n-1}{v-1}(1-p_{r})^{n-v}$, the loss function (2) of the SNL
problem in the unit-disk SNL case is not convex. ∎

######  Corollary 3.3.1.

If we let $r>\sqrt{2}$, the graph of the random framework will always be
complete. This means that even if all edges are given, when the anchors are
relatively few, the loss function (2) is non-convex with high-probability in
the unit-disk SNL case.

Following the above corollary, we provide an example to show further that more
edges (information) don’t always imply better convexity of the loss function
(2).

Actually, we provide a stronger example here. The example satisfies that as
the radius of the sensors increases, which implies that more edges are given,
the originally convex loss function (3) becomes non-convex.

In this example, the anchors are respectively $a_{1}=(-e,h)$, $a_{2}=(-e,-h)$,
$a_{3}=(e,h)$, $a_{4}=(e,-h)$, and the sensors are respectively $s_{1}=(-e,0)$
and $s_{2}=(e,0)$. Here, $e>0$ and $2e-\varepsilon<h<2e$ for a very small
$\varepsilon>0$. The connections among the nodes are shown in Figure 3.

Figure 3: The connections among the nodes in the case of $h<r<2e$ (left) and
$2e<r<\sqrt{4e^{2}+h^{2}}$ (right).

When the radius $r$ is relatively small, the framework contains four edges,
which are $\\{a_{1},s_{1}\\}$, $\\{a_{2},s_{1}\\}$, $\\{a_{3},s_{2}\\}$ and
$\\{a_{4},s_{2}\\}$. In this case, we denote the loss function by

$F_{0}(x_{11},x_{12},x_{21},x_{22})=f_{1}(x_{11},x_{12})+f_{2}(x_{21},x_{22}),$

where $f_{1}$ denotes the two terms of edges $\\{a_{1},s_{1}\\}$ and
$\\{a_{2},s_{1}\\}$, and $f_{2}$ denotes the two terms of edges
$\\{a_{3},s_{2}\\}$ and $\\{a_{4},s_{2}\\}$. To prove that $F_{0}$ is convex,
we only need to prove that $f_{1}$ and $f_{2}$ are convex. To prove that
$f_{1}$ and $f_{2}$ are convex, we only need to prove that the function

$f(x,y)=|x^{2}+(y-h)^{2}-h^{2}|+|x^{2}+(y+h)^{2}-h^{2}|$

is convex, since $f_{1}$ and $f_{2}$ can be obtained by translation of $f$.
Additionally, by direct calculation, we have

$f(x,y)=\max\\{x^{2}+(y-h)^{2}-h^{2}+x^{2}+(y+h)^{2}-h^{2},4hy,-4hy\\}.$

Since $f$ is the maximum of three convex functions, $f$ itself is a convex
function. As a conclusion, the loss function $F_{0}$ is a convex function.

When the radius $r$ is relatively large, the frame work contains five edges,
which are $\\{a_{1},s_{1}\\}$, $\\{a_{2},s_{1}\\}$, $\\{a_{3},s_{2}\\}$,
$\\{a_{4},s_{2}\\}$ and $\\{s_{1},s_{2}\\}$. In this case, we denote the loss
function by $F(x_{11},x_{12},x_{21},x_{22})$. Then we can directly verify that

$F(-e,h,e,h)+F(e,h,-e,h)<2F(0,h,0,h).$

Therefore, $F$ is non-convex.

Moreover, we will introduce another theorem to show that in some cases, the
loss function (2) has more than one local minimizers.

######  Theorem 3.4.

Let $\rho$ be a $2$-dimensional locally rigid framework with colinear anchors.
Consider a new framework $\tau$ obtained by slightly perturbing the anchors of
$\rho$. Then, the loss function (2) of framework $\tau$ still possesses at
least 2 local minimizers.

###### Proof.

Apparently, there are at least $2$ global minimizers of $\rho$’s loss
function. One is the true solution, which is denoted by $y_{1}$. The other is
the mirror image of the true solution with respect to the line where anchors
lie, which is denoted by $y_{2}$. Because $\rho$ is locally rigid, the two
global minimizers are isolated. Therefore, there exist two small disjoint
balls centered at $y_{1}$ and $y_{2}$. The two balls’ boundary function values
have a strictly positive infimum. We denote the ball centred at $y_{2}$ by
$B_{2}$. Upon applying a slight perturbation, both the function value at
$y_{2}$ and the infimum of the function values at $\partial B_{2}$
continuously change. Therefore, if the perturbation is sufficiently small, the
function value at $y_{2}$ will remain smaller than the infimum of the function
values at $\partial B_{2}$. This implies the presence of at least one local
minimizer within $B_{2}$. Coupled with the persistent global minimizer
$y_{1}$, we can conclude that there are still at least two local minimizers of
the loss function of the new framework $\tau$. ∎

This theorem suggests that for the framework whose anchors are almost
colinear, its loss function exhibits unfavorable properties. Actually, the
almost colinearity of the sensors can contribute to more local minimizers. In
numerous cases, some of the anchors and sensors are almost colinear, which
contributes to the common bad loss function.

###  3.3 Non-Convexity of Direct Dimension Augmentation

Recall that the domain and codomain of the loss function (2) are

$\operatorname{loss}\left(x\right):\mathbb{R}^{dn}\to\mathbb{R}.$

If we directly augment its dimension to $n(n+d)$, the new loss function
$\tilde{\operatorname{loss}}:\mathbb{R}^{n(n+d)}\to\mathbb{R}$ will be

$\tilde{\operatorname{loss}}\left(x\right)=\sum_{\\{i,j\\}\in
N_{x}}|\|x_{i}-x_{j}\|^{b}-d_{ij}^{b}|^{c}+\sum_{(i,j)\in
N_{a}}|\|a_{i}-x_{j}\|^{b}-\tilde{d}_{ij}^{b}|^{c},$ (12)

where $x_{i}\in\mathbb{R}^{n+d}$ are the variables. We augment the loss
function to $(n+d)$-dimension because the SDR method finds the high-
dimensional solution in $(n+d)$-dimension. Theorem 3.2 also holds for this new
loss function. This suggests that the new loss function (12) is also often
non-convex.

######  Theorem 3.5.

For a unit-disk SNL case $(U,r,n,a)$, assume that the region $U$ is connected,
open, and bounded. Then for any given set of anchors $a$, radius $r>0$, and
probability $p_{0}<1$, there exists $N\in\mathbb{N}$ such that for all number
of sensors $n>N$, the probability that the new loss function (12) of the SNL
problem in the unit-disk SNL case $(U,r,n,a)$ is not convex is larger than
$p_{0}$. Specifically, a lower bound on the probability is
$1-nv\tbinom{n-1}{v-1}(1-p_{r})^{n-v}$. The definitions of $v$ and $p_{r}$
remain consistent with those in Theorem 3.2.

###### Proof.

Due to the definition of the new loss function (12) and Theorem 3.2, there
exists $N\in\mathbb{N}$ such that for all number of sensors $n>N$, the
probability that the new loss function (12) of the generated framework is not
convex in its $nd$-dimensional subspace is larger than
$1-nv\tbinom{n-1}{v-1}(1-p_{r})^{n-v}$, so the new loss function is not convex
in its entire $n(d+n)$-dimensional space with probability larger than
$1-nv\tbinom{n-1}{v-1}(1-p_{r})^{n-v}$. This finishes the proof. ∎

The above theorem indicates that the new loss function (12) is often non-
convex, which is similar to the original loss function (2). This suggests that
directly augmenting the dimension of the loss function may not be an effective
way to augment the dimension and extract more information, which indicates the
failure of the first-order dimension augmentation.

##  4 Convexity of the High-Dimensional Optimization

In 2004, Biswas and Ye [7] proposed a semi-definite relaxation (SDR) algorithm
based on semi-definite programming (SDP) to solve the SNL problem. The SDR
method is the high-dimensional optimization we mainly discuss in this paper.
Since then, the SDR method has emerged as a promising approach to solving the
SNL problem.

As a product-type dimension augmentation of the former loss function method,
the optimization problem of the SDR method is always a convex optimization,
which we will show in Subsection 4.1. In contrast, the direct first-order
dimension augmentation of the loss function is often non-convex, as shown in
Subsection 3.3.

###  4.1 Formulation of the SDR method

We recall that an SNL problem (1) is to find a realization
$x_{1},\dots,x_{n}\in\mathbb{R}^{d}$, such that

$\begin{cases}\|a_{i}-x_{j}\|=\tilde{d}_{ij}\quad\forall(i,j)\in N_{a},\\\
\|x_{i}-x_{j}\|=d_{ij}\quad\forall\\{i,j\\}\in N_{x}.\end{cases}$

Denote by $X=(x_{1},x_{2},\dots,x_{n})$ the $d\times n$ matrix of the
positions of all sensors. Let $Y=X^{T}X$. Denote by $Y_{ij}$ the $(i,j)$ entry
of the matrix $Y$. We have

$\|a_{i}-x_{j}\|^{2}=a_{i}^{T}a_{i}-2a_{i}^{T}x_{j}+Y_{jj},\quad\|x_{i}-x_{j}\|^{2}=Y_{ii}-2Y_{ij}+Y_{jj}.$
(13)

Equation (13) suggests that the terms in the loss function (3) can be
rewritten as $|Y_{ii}-2Y_{ij}+Y_{jj}-d_{ij}^{2}|$ or
$|a_{i}^{T}a_{i}-2a_{i}^{T}x_{j}+Y_{jj}-\tilde{d}_{ij}^{2}|$. Therefore, we
can augment the dimension of the original loss function. A specific form of
the dimension augmentation of the loss function (3) is given by

$\displaystyle\begin{split}\text{minimize}\quad&\sum_{\\{i,j\\}\in
N_{x}}|Y_{ii}-2Y_{ij}+Y_{jj}-d_{ij}^{2}|+\sum_{(i,j)\in
N_{a}}|a_{i}^{T}a_{i}-2a_{i}^{T}x_{j}+Y_{jj}-\tilde{d}_{ij}^{2}|\\\
\text{subject to}\quad&Y=X^{T}X.\end{split}$ (14)

One key step of the semi-definite relaxation (SDR) is relaxing the last
equation to $Y\succeq X^{T}X$. Here is the formulation of the relaxed
optimization problem

minimize $\displaystyle\sum_{\\{i,j\\}\in
N_{x}}|Y_{ii}-2Y_{ij}+Y_{jj}-d_{ij}^{2}|+\sum_{(i,j)\in
N_{a}}|a_{i}^{T}a_{i}-2a_{i}^{T}x_{j}+Y_{jj}-\tilde{d}_{ij}^{2}|$ (15) subject
to $\displaystyle Y\succeq X^{T}X.$

To further develop the problem structure, we introduce the notation:

$Z:=\begin{pmatrix}I_{d}&X\\\ X^{T}&Y\\\ \end{pmatrix}.$ (16)

It is shown in [8, p. 28] that $Z\succeq 0$ if and only if $Y-X^{T}X\succeq
0$. As a result, the optimization problem (15) is equivalent to the following
form:

minimize $\displaystyle\sum_{{i,j}\in
N_{x}}|Z_{(i+d)(i+d)}-2Z_{(i+d)(j+d)}+Z_{(j+d)(j+d)}-d_{ij}^{2}|$ (17)
$\displaystyle+\sum_{(i,j)\in
N_{a}}|a_{i}^{T}a_{i}-2a_{i}^{T}Z_{(1:d)j}+Z_{(j+d)(j+d)}-\tilde{d}{ij}^{2}|$
subject to $\displaystyle Z_{1:d,1:d}=I_{d},\quad Z\succeq 0.$

The objective function of (17) is convex with respect to $Z$. This convexity
is demonstrated in Figure 4, which examines the same example as Figure 2. The
true locations of the three anchors are $(-1,0)$, $(1,0)$ and $(0,0.4)$ and
the true location of the sensor is $(0,1)$. In this example, $Z$ contains
three independent variables: $X\in\mathbb{R}^{2}$ and $Y\in\mathbb{R}$. The
constraint in (17) can be expressed as $Y\geq X^{T}X$. To visualize the loss
landscape of (17) over $\mathbb{R}^{2}$, we fix $X$ and minimize the loss
function subject to the given constraint, treating $Y$ as the independent
variable. The resulting landscape is depicted in Figure 4.

Figure 4: Landscape of SDR loss function of 3 anchors 1 sensor

The following paragraphs of this subsection aim to show that the optimization
problem (17) is equivalent to the optimization problem (18). Moreover, the
optimization problem (18) is a semi-definite programming (SDP) problem. The
SDP problem (18) can be readily solved by employing a solver, enabling us to
obtain the solution directly. We denote

$\tilde{W}_{ij}:=a_{i}^{T}a_{i}-2a_{i}^{T}x_{j}+Y_{jj}-\tilde{d}_{ij}^{2},\quad
W_{ij}:=Y_{ii}-2Y_{ij}+Y_{jj}-d_{ij}^{2}.$

Denote the $j$th standard basis of $\mathbb{R}^{n}$ by $e_{j}$. By direct
calculation, we have

$\displaystyle\tilde{W}_{ij}=a_{i}^{T}a_{i}-2a_{i}^{T}x_{j}+Y_{jj}-\tilde{d}_{ij}^{2}=\begin{pmatrix}a_{i}^{T}&-e_{j}^{T}\end{pmatrix}Z\begin{pmatrix}a_{i}\\\
-e_{j}\end{pmatrix}-\tilde{d}_{ij}^{2},$ $\displaystyle
W_{ij}=Y_{ii}-2Y_{ij}+Y_{jj}-d_{ij}^{2}=\begin{pmatrix}0&e_{i}^{T}-e_{j}^{T}\end{pmatrix}Z\begin{pmatrix}0\\\
e_{i}-e_{j}\end{pmatrix}-d_{ij}^{2}.$

We denote

$\displaystyle\tilde{w}_{ij}^{+}=\max(\tilde{W}_{ij},0),\quad\tilde{w}_{ij}^{-}=-\min(\tilde{W}_{ij},0),$
$\displaystyle w_{ij}^{+}=\max(W_{ij},0),\quad w_{ij}^{-}=-\min(W_{ij},0).$

It follows that (17) is equivalent to

$\displaystyle\begin{split}\text{minimize}\quad&\sum_{\\{i,j\\}\in
N_{x}}(w_{ij}^{+}+w_{ij}^{-})+\sum_{(i,j)\in
N_{a}}(\tilde{w}_{ij}^{+}+\tilde{w}_{ij}^{-})\\\ \text{subject
to}\quad&\begin{pmatrix}a_{i}^{T}&-e_{j}^{T}\end{pmatrix}Z\begin{pmatrix}a_{i}\\\
-e_{j}\end{pmatrix}-\tilde{d}_{ij}^{2}=\tilde{w}_{ij}^{+}-\tilde{w}_{ij}^{-},\quad\forall(i,j)\in
N_{a}\\\
&\begin{pmatrix}0&e_{i}^{T}-e_{j}^{T}\end{pmatrix}Z\begin{pmatrix}0\\\
e_{i}-e_{j}\end{pmatrix}-d_{ij}^{2}=w_{ij}^{+}-w_{ij}^{-},\quad\forall\\{i,j\\}\in
N_{x}\\\ &w_{ij}^{+},w_{ij}^{-}\geq 0,\quad\forall(i,j)\in N_{a}\\\
&\tilde{w}_{ij}^{+},\tilde{w}_{ij}^{-}\geq 0,\quad\forall\\{i,j\\}\in N_{x}\\\
&Z_{1:d,1:d}=I_{d},\ Z\succeq 0.\end{split}$ (18)

We note that (18) is a convex optimization problem. Specifically, it is a
semi-definite programming (SDP) problem. We can also see similar
reformulations of (1) as convex optimization problems in [7, 5, 22, 37, 41].
In this section, the SNL problem (1) is reformulated as the optimization
problem (18) by delicately increasing the dimension of the problem, leading to
convexity, solvability, and other favorable properties of the high-dimensional
optimization problem.

Furthermore, using similar techniques, we can do a second-order dimension
augmentation to the optimization problem to minimize the loss function (2)
with $b=c=2$, which is a multivariate polynomial. This reformulation
transforms the problem into an SDP problem with a convex quadratic objective
function. Consequently, it offers an alternative approach to [20, 21] for
accomplishing a second-order dimension augmentation of the SNL problem’s
polynomial loss function.

###  4.2 Properties of the Solution Matrix

A fundamental theoretical result of the SDR method was found by So and Ye in
[37, Theorem 2], which showed that a semi-definite programming solver based on
the interior point method finds the true positions of the sensors if and only
if the framework is universally rigid. Additionally, in the unit-disk SNL
case, which is common in practice, the probability that the graph is a
trilateration and the probability that the framework is universally rigid were
estimated by [11] and [32] respectively. It was shown in [42, 36] that if the
graph of a framework is a trilateration, the framework will be universally
rigid. Furthermore, results from [11] and [32] indicated that it is usual for
the SDR method to find the true solution to the SNL problem directly.

We give the geometric meaning of the solution given by the SDP solver in this
paragraph. We decompose $Z$ to obtain $X$ and $Y$ by equation (16). If
$\text{rank}(Z)=d$, by knowledge of linear algebra, $Y=X^{T}X$. In this case,
following (14), $X$ is a solution to the SNL problem (1). If
$\text{rank}(Z)\neq d$, our solution is indeed a solution to the relaxed
problem (15) rather than (14). Since $Z\succeq 0$, we have $Y-X^{T}X\succeq 0$
by knowledge of linear algebra. It follows that there exists $0\neq
X_{2}\in\mathbb{R}^{n\times n}$ such that $X_{2}^{T}X_{2}=Y-X^{T}X$. It was
suggested by So in [36, Section 3.4.2] that

$\begin{pmatrix}X\\\ X_{2}\end{pmatrix}$ (19)

is a solution to the $(n+d)$-dimensional SNL problem.

If the framework that generates the SNL problem is not universally rigid, we
can implement some other methods to get the true solution from the high-
dimensional solution that we obtained. Matrix $Z$ in (18) and matrix (19), are
two forms of the high-dimensional solution. We may take $Z_{1:d,(d+1):(d+n)}$,
i.e., $X$ in (19), as the solution directly. In addition, we can do gradient
descent using $Z_{1:d,(d+1):(d+n)}$ as a warm-start to minimize the loss
function, which will be discussed in Section 5. We can also construct new
regularization by $Z$ to restart the SDP solver, which was reported to have a
large improvement; see [5] for details.

As a conclusion, as stated in Section 1, under certain circumstances
(universally rigid), the finite convergence (second-order convergence) of the
dimension augmentation is guaranteed; i.e., if the framework is universally
rigid, the second-order dimension augmentation, in other words the SDR method,
will find the same optimal point as the low-dimensional loss function method.

##  5 Explanation for the Success of the SDR+GD Method

If the SDR solution is considered as a warm-start of the minimizing loss
function method, the probability to find the true low-dimensional solution
will be greatly enhanced. This phenomenon was observed and stated in [4, 5],
but only an empirical explanation is provided.

The authors use the SDR solution as the initial value for minimizing the loss
function (2) with $b=c=2$. To achieve this optimization, they employ the
gradient descent algorithm, a widely-used iterative method for minimizing
differentiable functions. This process involves subtracting the gradient of
the current point at each step, with the option of incorporating a step size
factor. It is important to note that in the case of a non-convex objective
function, gradient descent may converge to local minima, underscoring the
significance of selecting an appropriate starting point. Alternatively, other
optimization algorithms, like steepest descent, can be employed as well; see,
e.g., [41].

In this section, we will show our more rigorous explanation for the success of
the regularized SDR+GD (gradient descent) method in [5, 4].

Denote the set of all solutions of an SNL problem $\xi_{d}$ by $S(\xi_{d})$.
If we increase the dimension of the SNL problem $\xi_{d}$ from $d$ to
$d^{\prime}$, we denote the new high-dimensional SNL problem by
$\xi_{d^{\prime}}$. We will prove that there exists a simple smooth path with
constant edge lengths joining every two solutions of one SNL problem in a
higher dimension due to [3]. This means that every point on the simple smooth
path is a solution to the high-dimensional SNL problem.

The construction of the simple smooth path was from a lemma which is used to
prove the Kneser–Poulsen conjecture in [3].

######  Theorem 5.1.

Suppose that ${p}=({p_{1}},{p_{2}},\dots,{p_{n}})$ and
${q}=({q_{1}},{q_{2}},\dots,{q_{n}})$ are two solutions to a $d$-dimensional
SNL problem $\xi_{d}=(G,d,\tilde{d},a)$. Then the following path
${p}(t):[0,1]\to\mathbb{R}^{2nd}$ joins ${p}$ and ${q}$,

$\displaystyle{p}_{i}(t):=\left(\frac{{p}_{i}+{q}_{i}}{2}+(\cos\pi
t)\frac{{p}_{i}-{q}_{i}}{2},(\sin\pi t)\frac{{p}_{i}-{q}_{i}}{2}\right),\quad
1\leq i\leq n,$ $\displaystyle p(t):=(p_{1}(t),p_{2}(t),\dots,p_{n}(t)).$

Additionally, every point on the path is a solution to the $2d$-dimensional
SNL problem $\xi_{2d}$; i.e., $S(\xi_{2d})$ contains the path.

###### Proof.

It is not difficult to directly verify that the path joins ${p}$ and ${q}$,
and for all $t\in[0,1]$ and $\\{i,j\\}\in N_{x}$, $\|{p}_{i}(t)-{p}_{j}(t)\|$
is constant. Similarly, it is not difficult to directly verify that for all
$t\in[0,1]$ and $(i,j)\in N_{a}$, $\|a_{i}-{p}_{j}(t)\|$ is constant.
Therefore, ${p}(t)$ always satisfies the distance condition. This means that
${p}(t)$ is always a solution to the $2d$-dimensional SNL problem $\xi_{2d}$.
∎

Then for an SNL problem, if the SDR solution ${p}$ is a
$d^{\prime}$-dimensional solution where $d^{\prime}>d$, there exists a simple
smooth path in $S(\xi_{2d^{\prime}})$ joining the high-dimensional solution
${p}$ and the true solution ${p_{0}}$.

As regularization can be included in the SDR method, the solution will
minimize the regularized objective function. In some cases, if the direction
along which the regularization decreases is similar to the projection
direction, due to the path connectedness, the solution found by SDR may be
close to the true $d$-dimensional solution. Finally, we choose the projection
of the high-dimensional solution as the warm-start for the loss function
method. Since the projection is close to the global minimizer, the gradient
descent method may avoid converging to other local minimizers of the loss
function that are far from the global minimizer.

Specifically, the regularization provided by [5, 4] demonstrates superior
performance compared to other baseline methods. The key insight lies in the
fact that the regularization is designed to maximize the sum of distances
between unconnected nodes, thereby minimizing the length in the projection
direction. The connectedness between the high-dimensional solution and the
true solution ensures the possibility of the regularization effectively
guiding the SDR method toward the true solution. Hence, the utilization of
effective regularization techniques is crucial in achieving favorable outcomes
in this context.

##  6 Comparison with the Neural Network

In the context of the SNL problem, our findings demonstrate the consistent
superiority of the high-dimensional SDR method over the low-dimensional
approach. As previously discussed, the high-dimensional method outperforms the
low-dimensional method in the SNL problem, which minimizes the loss function
in $\mathbb{R}^{d}$. Moreover, existing literature (e.g., [5, 4]) suggests
that utilizing the high-dimensional solution as a warm-start for the low-
dimensional method yields even better performance than both the low-
dimensional and high-dimensional methods in the SNL problem. This highlights
the ability of high-dimensional models to enhance low-dimensional optimization
by providing an advantageous warm-start.

Interestingly, similar phenomena can be observed in the field of neural
networks, where researchers and practitioners have increasingly focused on
developing larger and more complex architectures within the realm of deep
learning. Notable examples include AlphaFold, AlphaGo, ResNet, GPT-3,
Transformer, and VGG [18, 34, 13, 9, 39, 35]. This shift toward larger neural
networks indicates their ability to achieve high performance across various
tasks. Additionally, large neural networks can serve as effective
initializations, providing a warm-start for new networks in different tasks.
This process is commonly referred to as transfer learning.

In the following paragraphs, we will show the high performance of larger
neural networks and their capability to facilitate transfer learning.

Larger neural network models exhibit superior performance primarily due to
their capacity to generalize and their capability to extract diverse and
expressive features. This characteristic results in improved performance and
generalization on a given task, as well as on new, unseen data. The
effectiveness of larger models has been demonstrated by neural networks such
as VGG, ResNet, DenseNet, and large-scale Transformer models like BERT and
GPT-3 [35, 13, 16, 10, 9].

Furthermore, larger models hold promise for facilitating transfer learning in
various domains, as evidenced by studies such as [43]. Transfer learning
involves fine-tuning or extracting features from a pre-trained model on a
specific task or domain. Pre-trained transformers like BERT [27, 14] and large
CNNs such as ResNet [30] have achieved state-of-the-art performance on diverse
natural language processing tasks with relatively small amounts of task-
specific data.

In the following sections, we will first discuss the blessing of high-
dimensional models, emphasizing their exceptional ability to extract more
information from the problem and their generalization ability. Subsequently,
we will explore the capability of high-dimensional models to serve as warm-
starts for new models.

###  6.1 Blessing of a High-Dimensional Model

The blessing of high-dimensional models can be observed in other applications
of SDP and designs of neural networks. Augmenting the dimension of the
problems can extract more information from the problems and make the process
of optimization easier. Therefore, if the problem is difficult, increasing the
dimension of the problem with a possible relaxation may reach an acceptable
high-dimensional solution. This leaves the possibility to project it onto a
lower-dimensional space and get a solution with better accuracy, which was
suggested by [5, 4]. Therefore, in neural networks and optimization, high-
dimensional models have more generalization ability.

For instance, the semi-definite relaxation of the max-cut problem (see [12])
and the sensor network localization (SNL) problem both follow a paradigm of
second-order dimension augmentation, including increasing the dimension of the
problem, relaxing the problem, obtaining a warm-start from the high-
dimensional solution and using it for better optimization. Increasing the
dimension of the problem can lead to a better quality of the solution, which
was suggested by [5, 4]. Here is a flow chart of the SDR method in the SNL
problem, where $z$ is the padded vector of $Z=\text{mat}(z)$,
$\text{PSD}^{n+d}$ is the cone of padded positive semi-definite
$(n+d)\times(n+d)$ matrices, and $A,g$ are calculated by the SNL problem.

$\begin{cases}\|a_{i}-x_{j}\|=\tilde{d}_{ij},\\\
\|x_{i}-x_{j}\|=d_{ij}.\end{cases}$ SNL Dimension augmentation:
$\begin{aligned} &\text{minimize }\|Az-g\|_{1}\\\ &\text{subject to:}\\\
&\begin{cases}z\in\text{PSD}^{n+d}\\\ \text{rank
mat}(z)=d.\end{cases}\end{aligned}$ Relaxation: $\begin{aligned}
&\text{minimize }\|Az-g\|_{1}\\\ &\text{subject to:}\\\
&z\in\text{PSD}^{n+d}.\\\ \end{aligned}$ Getting a warm-start: Take
$Z_{1:d,(d+1):(d+n)}$. AnswerreformulateinputrelaxSDP solverGDcheck Figure 5:
A flowchart of the SDR algorithm in SNL

Similarly, a high-dimensional model of a neural network can extract more
features from the dataset. With a well-designed structure, large neural
networks are enabled to have more generalization ability than small neural
networks. For instance, Transformer [39] and GPT [9] can capture long-term
dependencies in the dataset, which improves the performance of many natural
language processing tasks. As for Computer Vision tasks, ResNet [13] and VGG
[35] are examples of high-dimensional models that can perform well on a wide
range of image classification problems.

Generally, high-dimensional models learn more complex features than low-
dimensional models and can outperform the latter under certain conditions.
However, such models may also potentially overfit the data as the number of
parameters increases. Therefore, adding a regularizer or performing transfer
learning is necessary to avoid the overfitting issue. In the scenario of
solving SNL problems, the importance of regularization in optimization was
also suggested by experiments in [5, 4].

Furthermore, a well-formed larger model may contain some specific structures
of higher order. For instance, the method of semi-definite relaxation of the
SNL problem exploits the structure of the problem by iterating the relaxation
of the vector product $Y_{ij}$ of the expected position of the sensors to
minimize the loss function

$\sum_{\\{i,j\\}\in N_{x}}|Y_{ii}-2Y_{ij}+Y_{jj}-d_{ij}^{2}|+\sum_{(i,j)\in
N_{a}}|a_{i}^{T}a_{i}-2a_{i}^{T}x_{j}\ +Y_{jj}-\tilde{d}_{ij}^{2}|.$

Moreover, in the max-cut problem, one ultimately wants to solve

$\displaystyle\begin{split}\text{maximize}\quad&\frac{1}{2}\sum_{1\leq i<j\leq
M}r_{ij}(1-b_{i}b_{j}),\\\ \text{subject to}\quad&|b_{i}|=1,\quad
i=1,\dots,M,\end{split}$ (20)

where $r_{ij}\geq 0$ are known. One may do a second-order augmentation as

$\displaystyle\begin{split}\text{maximize}\quad&\frac{1}{2}\sum_{1\leq i<j\leq
M}r_{ij}(1-B_{ij}),\\\ \text{subject to}\quad&B_{ii}=1,\quad i=1,\dots,M,\\\
&B\succeq 0.\end{split}$ (21)

This process increases the dimension of the optimization problem we solve from
$M$, the dimension of (20), to $O(M^{2})$, the dimension of (21), which
received theoretical and experimental success; see, e.g., [12, 22].

In comparison, the transformer architecture uses the scaled product to train
attention over data, as described by the equation:

$\text{Attention}(Q,K,V)=\text{softmax}\left(\frac{QK^{T}}{\sqrt{d_{k}}}\right)V.$

Here, the matrices $Q,K$ and $V$ represent the queries, keys and values [39],
and $d_{k}$ is the dimension of the keys. This matrix product is used
similarly; it helps the model to identify which queries are important and then
scales the attention to each one. The scaled product is used to ensure that
the attention is evenly distributed across all of the queries. This suggests
that the matrix product can sometimes be a good structure to increase the
dimension of the problem.

###  6.2 Blessing of a Warm-Start from a High-Dimensional Model

In addition to increasing the dimension of a problem, the way to get a warm-
start from the high-dimensional solution also plays an important role in
solving the problem.

For example, in the max-cut problem, the solution is generated by rounding the
solution obtained from the relaxed problem to a feasible solution for the
original problem, which can be done using various methods, such as the
Goemans-Williamson algorithm [12]. We recall the max-cut problem (20) and its
relaxed form (21). The key process is to let

$b_{j}=1,\quad\text{if }v_{i}^{T}v\geq 0.$

where $v$ is a vector uniformly distributed on the unit sphere $S_{n}$ and
$v_{i}$ is the $i$th column of $F$. Here, $F$ is the incomplete Cholesky
decomposition of $B$, i.e., $B=F^{T}F$. The methods used in this key step
determine how well the solution to the relaxed problem can be translated back
to the solution set to the original problem.

Similarly, in the SNL problem, the reularized SDR+GD method that uses the SDR
solution as a warm-start of the loss function method has better performance
than the pure high-dimensional method and pure low-dimensional method, which
is shown in [5, 4].

Also, in the field of transfer learning, there are two kinds of analogies to
the process of generating warm-starts from the high-dimensional models, which
are fine-tuning and feature extraction. We refer the readers to [25, 43] for
details.

Fine-tuning is the process of taking a pre-trained model and adapting its
weights to new tasks. It usually involves some amount of supervised training
and typically requires using the same type of neural network architecture as
the pre-trained model. The new model is then initialized with the weights of
the pre-trained model and then retrained on the new dataset. Fine-tuning is
useful when the dataset is relatively small, as it allows for better
generalization than training from scratch.

Feature extraction is the process of extracting useful features from a pre-
trained model for use in another task. Feature extraction usually involves
extracting the last few layers of a pre-trained model and using them as inputs
to a new model trained on the new task. Feature extraction usually requires
using a different type of neural network architecture than the pre-trained
model. It is useful for tasks with large datasets or with plenty of data to
use for feature extraction.

In both cases, the trained large neural network provides a warm-start for the
final neural network which we get from various training methods.

##  7 Conclusions and Future Work

The blessing of high-order dimensionality in scientific computing stems from
the ability to exploit the structure of a problem by increasing the dimension
of the problem and getting warm-starts from the high-dimensional optimization.
This approach can lead to more efficient algorithms and better generalization.
However, it is essential to carefully design the larger model, considering the
problem’s structure, such as the order of the dimension augmentation, and the
choice of generating a warm-start for the original problem. By doing so, one
can tackle complex problems in various fields, such as real-world optimization
problems and machine learning, by increasing the dimension of the problem.

Taking SNL as an example, we have demonstrated in Section 3 that the low-
dimensional method of minimizing the loss function does not work well, as the
loss function is often non-convex. Our main theorem 3.2 clearly illustrates
this fact in terms of probability. In contrast, the high-dimensional SDR
method introduced in Section 4 skillfully reformulate the SNL problem as a
convex problem. Additionally, we have proved in Section 3.3 that the method of
direct dimension augmentation usually minimizes a non-convex objective
function. Furthermore, we give an explanation for why the SDR+GD method that
uses the SDR solution as a warm-start of the loss function method works in
Section 5.

We emphasize in Section 6 the connection between our findings and some similar
methods in neural networks, as well as the blessing of dimensionality in the
fields of optimization and machine learning.

Future work related to this paper includes:

  * •

Generalization of the product-type dimension augmentation.

As shown above, the product-type dimension augmentation technique is used to
solve SNL and max-cut problems. We wonder if this technique can be used for
more optimization problems. More specifically, we wonder if there is a more
general type of non-convex optimization problem that can be solved by this
technique.

  * •

Completely rigorous explanation for the success of the SDR+GD method.

We hope a completely rigorous explanation can be given to explain why the
warm-start given by the SDR method works so well in the SDR+GD method.
Moreover, we wonder if there exists regularization in the SDR method that can
help the SDR method solve all SNL problems generated by globally rigid
frameworks.

Acknowledgment. We are grateful to Jiajin Li, Chunlin Sun, Bo Jiang and Qi
Deng for their valuable remarks and suggestions which helped us to improve the
paper and the code.

## References

  * [1] Amir Beck, Marc Teboulle, and Zahar Chikishev.  Iterative minimization schemes for solving the single source localization problem.  SIAM Journal on Optimization, 19(3):1397–1416, 2008.
  * [2] Christian Bettstetter.  On the minimum node degree and connectivity of a wireless multihop network.  In Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, pages 80–91, 2002.
  * [3] Károly Bezdek and Robert Connelly.  The kneser–poulsen conjecture for spherical polytopes.  Discrete & Computational Geometry, 32:101–106, 2004.
  * [4] Pratik Biswas, Tzu-Chen Lian, Ta-Chung Wang, and Yinyu Ye.  Semidefinite programming based algorithms for sensor network localization.  ACM Transactions on Sensor Networks, 2(2):188–220, 2006.
  * [5] Pratik Biswas, T-C Liang, K-C Toh, Yinyu Ye, and T-C Wang.  Semidefinite programming approaches for sensor network localization with noisy distance measurements.  IEEE transactions on automation science and engineering, 3(4):360–371, 2006.
  * [6] Pratik Biswas and Yinyu Ye.  A distributed method for solving semidefinite programs arising from ad hoc wireless sensor network localization.  Multiscale Optimization Methods and Applications, page 69–84, 2003\.
  * [7] Pratik Biswas and Yinyu Ye.  Semidefinite programming for ad hoc wireless sensor network localization.  In Proceedings of the 3rd international symposium on Information processing in sensor networks, pages 46–54, 2004.
  * [8] S. Boyd, L. El Ghaoui, E. Feron, and V. Balakrishnan.  Linear Matrix Inequalities in System and Control Theory, volume 15 of Studies in Applied Mathematics.  SIAM, Philadelphia, PA, June 1994.
  * [9] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  Advances in neural information processing systems, 33:1877–1901, 2020.
  * [10] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  arXiv preprint arXiv:1810.04805, 2018.
  * [11] T. Eren, O.K. Goldenberg, W. Whiteley, Y.R. Yang, A.S. Morse, B.D.O. Anderson, and P.N. Belhumeur.  Rigidity, computation, and randomization in network localization.  In IEEE INFOCOM 2004, volume 4, pages 2673–2684 vol.4, 2004.
  * [12] Michel X Goemans and David P Williamson.  Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming.  Journal of the ACM (JACM), 42(6):1115–1145, 1995.
  * [13] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [14] Jeremy Howard and Sebastian Ruder.  Universal language model fine-tuning for text classification.  arXiv preprint arXiv:1801.06146, 2018.
  * [15] Yaohua Hu, Chong Li, Jinhua Wang, Xiaoqi Yang, and Linglingzhi Zhu.  Linearized proximal algorithms with adaptive stepsizes for convex composite optimization with applications.  Applied Mathematics & Optimization, 87(3):52, 2023.
  * [16] Gao Huang, Zhuang Liu, Laurens Van Der Maaten, and Kilian Q Weinberger.  Densely connected convolutional networks.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 4700–4708, 2017.
  * [17] Xiang Ji and Hongyuan Zha.  Sensor positioning in wireless ad-hoc sensor networks using multidimensional scaling.  In IEEE INFOCOM 2004, volume 4, pages 2652–2661. IEEE, 2004.
  * [18] John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ronneberger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Žídek, Anna Potapenko, et al.  Highly accurate protein structure prediction with alphafold.  Nature, 596(7873):583–589, 2021.
  * [19] Fabian Kuhn, Rogert Wattenhofer, and Aaron Zollinger.  Ad-hoc networks beyond unit disk graphs.  In Proceedings of the 2003 joint workshop on Foundations of mobile computing, pages 69–78, 2003.
  * [20] Jean B Lasserre.  A sum of squares approximation of nonnegative polynomials.  SIAM review, 49(4):651–669, 2007.
  * [21] Jean B Lasserre.  Moments and sums of squares for polynomial optimization and related problems.  Journal of Global Optimization, 45(1):39–61, 2009.
  * [22] Zhi-Quan Luo, Wing-Kin Ma, Anthony Man-Cho So, Yinyu Ye, and Shuzhong Zhang.  Semidefinite relaxation of quadratic optimization problems.  IEEE Signal Processing Magazine, 27(3):20–34, 2010.
  * [23] Jiawang Nie.  Sum of squares method for sensor network localization.  Computational Optimization and Applications, 43(2):151–179, 2009\.
  * [24] Jiawang Nie.  Optimality conditions and finite convergence of lasserre’s hierarchy.  Mathematical Programming, 146, 06 2012.
  * [25] Sinno Jialin Pan and Qiang Yang.  A survey on transfer learning.  IEEE Transactions on knowledge and data engineering, 22(10):1345–1359, 2010.
  * [26] Michael Pauley and Jonathan H. Manton.  Global optimisation for time of arrival-based localisation.  In 2018 IEEE Statistical Signal Processing Workshop (SSP), pages 791–795, 2018.
  * [27] Yifan Peng, Shankai Yan, and Zhiyong Lu.  Transfer learning in biomedical natural language processing: an evaluation of bert and elmo on ten benchmarking datasets.  arXiv preprint arXiv:1906.05474, 2019.
  * [28] Mathew D. Penrose.  On k-connectivity for a geometric random graph.  Random Structures and Algorithms, 15(2):145–164, 1999.
  * [29] Ting Kei Pong and Paul Tseng.  (robust) edge-based semidefinite programming relaxation of sensor network localization.  Mathematical Programming, 130(2):321–358, 2010.
  * [30] Edmar Rezende, Guilherme Ruppert, Tiago Carvalho, Fabio Ramos, and Paulo De Geus.  Malicious software classification using transfer learning of resnet-50 deep neural network.  In 2017 16th IEEE International Conference on Machine Learning and Applications (ICMLA), pages 1011–1014. IEEE, 2017.
  * [31] Nasir Saeed, Haewoon Nam, Tareq Y. Al-Naffouri, and Mohamed-Slim Alouini.  A state-of-the-art survey on multidimensional scaling-based localization techniques.  IEEE Communications Surveys & Tutorials, 21(4):3565–3583, 2019\.
  * [32] Davood Shamsi, Nicole Taheri, Zhisu Zhu, and Yinyu Ye.  Conditions for correct sensor network localization using sdp relaxation.  Discrete Geometry and Optimization, page 279–301, 2013.
  * [33] Yi Shang, Wheeler Ruml, Ying Zhang, and Markus PJ Fromherz.  Localization from mere connectivity.  In Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, pages 201–212, 2003.
  * [34] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al.  Mastering the game of go with deep neural networks and tree search.  nature, 529(7587):484–489, 2016.
  * [35] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  arXiv preprint arXiv:1409.1556, 2014.
  * [36] Anthony Man-Cho So.  A semidefinite programming approach to the graph realization problem: Theory, applications and extensions.  PhD thesis, Citeseer, 2007.
  * [37] Anthony Man-Cho So and Yinyu Ye.  Theory of semidefinite programming for sensor network localization.  Mathematical Programming, 109(2-3):367–384, 2007.
  * [38] Paul Tseng.  Second‐order cone programming relaxation of sensor network localization.  SIAM Journal on Optimization, 18(1):156–185, 2007.
  * [39] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  Advances in neural information processing systems, 30, 2017.
  * [40] Vijayanth Vivekanandan and Vincent W. S. Wong.  Ordinal mds-based localization for wireless sensor networks.  In IEEE Vehicular Technology Conference, pages 1–5, 2006.
  * [41] Zizhuo Wang, Song Zheng, Yinyu Ye, and Stephen Boyd.  Further relaxations of the semidefinite programming approach to sensor network localization.  SIAM Journal on Optimization, 19(2):655–673, 2008.
  * [42] Zhisu Zhu, Anthony Man-Cho So, and Yinyu Ye.  Universal rigidity: Towards accurate and efficient localization of wireless networks.  In 2010 Proceedings IEEE INFOCOM, pages 1–9. IEEE, 2010.
  * [43] Fuzhen Zhuang, Zhiyuan Qi, Keyu Duan, Dongbo Xi, Yongchun Zhu, Hengshu Zhu, Hui Xiong, and Qing He.  A comprehensive survey on transfer learning.  Proceedings of the IEEE, 109(1):43–76, 2020.