# PRNet: Self-Supervised Learning for Partial-to-Partial Registration

Yue Wang
Massachusetts Institute of Technology
<EMAIL_ADDRESS>
&Justin Solomon
Massachusetts Institute of Technology
<EMAIL_ADDRESS>

###### Abstract

We present a simple, flexible, and general framework titled Partial
Registration Network (PRNet), for partial-to-partial point cloud registration.
Inspired by recently-proposed learning-based methods for registration, we use
deep networks to tackle non-convexity of the alignment and partial
correspondence problems. While previous learning-based methods assume the
entire shape is visible, PRNet is suitable for partial-to-partial
registration, outperforming PointNetLK, DCP, and non-learning methods on
synthetic data. PRNet is self-supervised, jointly learning an appropriate
geometric representation, a keypoint detector that finds points in common
between partial views, and keypoint-to-keypoint correspondences. We show PRNet
predicts keypoints and correspondences consistently across views and objects.
Furthermore, the learned representation is transferable to classification.

##  1 Introduction

_Registration_ is the problem of predicting a rigid motion aligning one point
cloud to another. Algorithms for this task have steadily improved, using
machinery from vision, graphics, and optimization. These methods, however, are
usually orders of magnitude slower than “vanilla” Iterative Closest Point
(ICP), and some have hyperparameters that must be tuned case-by-case. The
trade-off between efficiency and effectiveness is steep, reducing
generalizability and/or practicality.

Recently, PointNetLK [1] and Deep Closest Point (DCP) [2] show that learning-
based registration can be faster and more robust than classical methods, even
when trained on different datasets. These methods, however, cannot handle
partial-to-partial registration, and their one-shot constructions preclude
refinement of the predicted alignment.

We introduce the Partial Registration Network (PRNet), a sequential decision-
making framework designed to solve a broad class of registration problems.
Like ICP, our method is designed to be applied _iteratively_ , enabling
coarse-to-fine refinement of an initial registration estimate. A critical new
component of our framework is a keypoint detection sub-module, which
identifies points that match in the input point clouds based on co-contextual
information. Partial-to-partial point cloud registration then boils down to
detecting keypoints the two point clouds have in common, matching these
keypoints to one another, and solving the Procrustes problem.

Since PRNet is designed to be applied iteratively, we use Gumbel–Softmax [3]
with a straight-through gradient estimator to sample keypoint correspondences.
This new architecture and learning procedure modulates the sharpness of the
matching; distant point clouds given to PRNet can be coarsely matched using a
diffuse (fuzzy) matching, while the final refinement iterations prefer sharper
maps. Rather than introducing another hyperparameter, PRNet uses a sub-network
to predict the temperature [4] of the Gumbel–Softmax correspondence, which can
be cast as a simplified version of the actor-critic method. That is, PRNet
_learns_ to modulate the level of map sharpness each time it is applied.

We train and test PRNet on ModelNet40 and on real data. We visualize the
keypoints and correspondences for shapes from the same or different
categories. We transfer the learned representations to shape classification
using a linear SVM, achieving comparable performance to state-of-the-art
supervised methods on ModelNet40.

#### Contributions.

We summarize our key contributions as follows:

  * •

We present the _Partial Registration Network_ (PRNet), which enables partial-
to-partial point cloud registration using deep networks with state-of-the-art
performance.

  * •

We use Gumbel–Softmax with straight-through gradient estimation to obtain a
sharp and near-differentiable mapping function.

  * •

We design an _actor-critic closest point_ module to modulate the sharpness of
the correspondence using an action network and a value network. This module
predicts more accurate rigid transformations than differentiable soft
correspondence methods with fixed parameters.

  * •

We show registration is a useful proxy task to learn representations for 3D
shapes. Our representations can be transferred to other tasks, including
keypoint detection, correspondence prediction, and shape classification.

  * •

We release our code to facilitate reproducibility and future research.
111https://github.com/WangYueFt/prnet

##  2 Related Work

Rigid Registration. ICP [5] and variants [6, 7, 8, 9] have been widely used
for registration. Recently, probabilistic models [10, 11, 12] have been
proposed to handle uncertainty and partiality. Another trend is to improve the
optimization: [13] applies Levenberg–-Marquardt to the ICP objective, while
global methods seek a solution using branch-and-bound [14], Riemannian
optimization [15], convex relaxation [16], mixed-integer programming [17], and
semidefinite programming [18].

Learning on Point Clouds and 3D Shapes. Deep Sets [19] and PointNet [20]
pioneered deep learning on point sets, a challenge problem in learning and
vision. These methods take coordinates as input, embed them to high-
dimensional space using shared multilayer perceptrons (MLPs), and use a
symmetric function (e.g., $\max$ or $\sum$) to aggregate features. Follow-up
works incorporate local information, including PointNet++ [21], DGCNN [22],
PointCNN [23], and PCNN [24]. Another branch of 3D learning designs
convolution-like operations for shapes or applies graph convolutional networks
(GCNs) [25, 26] to triangle meshes [27, 28], exemplifying architectures on
non-Euclidean data termed geometric deep learning [29]. Other works, including
SPLATNet [30], SplineCNN [31], KPConv [32], and GWCNN [33], transform 3D
shapes to regular grids for feature learning.

Keypoints and Correspondence. Correspondence and registration are dual tasks.
Correspondence is the approach while registration is the output, or vice
versa. Countless efforts tackle the correspondence problem, either at the
point-to-point or part-to-part level. Due to the $O(n^{2})$ complexity of
point-to-point correspondence matrices and $O(n!)$ possible permutations, most
methods (e.g., [34, 35, 36, 37, 38, 39, 40, 41]) compute a sparse set of
correspondences and extend them to dense maps, often with bijectivity as an
assumption or regularizer. Other efforts use more exotic representations of
correspondences. For example, functional maps [42] generalize to mappings
between functions on shapes rather than points on shapes, expressing a map as
a linear operator in the Laplace–Beltrami eigenbasis. Mathematical methods
like functional maps can be made ‘deep’ using priors learned from data: Deep
functional maps [43, 44] learn descriptors rather than designing them by hand.

For partial-to-partial registration, we cannot compute bijective
correspondences, invalidating many past representations. Instead, keypoint
detection is more secure. To extract a sparser representation, KeyPointNet
[45] uses registration and multiview consistency as supervision to learn a
keypoint detector on 2D images; our method performs keypoint detection on
point clouds. In contrast to our model, which learns correspondences from
registration, [46] uses correspondence prediction as the training objective to
learn how to segment parts. In particular, it utilizes PointNet++ [21] to
product point-wise features, generates matching using a correspondence
proposal module, and finally trains the pipeline with ground-truth
correspondences.

Self-supervised Learning. Humans learn knowledge not only from teachers but
also by predicting and reasoning about unlabeled information. Inspired by this
observation, self-supervised learning usually involves predicting part of an
input from another part [47, 48], solving one task using features learned from
another task [45] and/or enforcing consistency from different views/modalities
[49, 50]. Self-supervised pretraining is an effective way to transfer
knowledge learned from massive unlabeled data to tasks where labeled data is
limited. For example, BERT [51] surpasses state-of-the-art in natural language
processing by learning from contextual information. ImageNet Pretrain [52]
commonly provides initialization for vision tasks. Video-audio joint analysis
[53, 54, 55] utilizes modality consistency to learn representations. Our
method is also self-supervised, in the sense that no labeled data is needed.

Actor–Critic Methods. Many recent works can be counted as actor–critic
methods, including deep reinforcement learning [56], generative modeling [57],
and sequence generation [58]. These methods generally involve two functions:
taking actions and estimating values. The predicted values can be used to
improve the actions while the values are collected when the models interact
with environment. PRNet uses a sub-module (value head) to predict the level of
granularity at which we should map two shapes. The value adjusts the
temperature of Gumbel–Softmax in the action head.

##  3 Method

|
---|---
(a) Network architecture for PRNet | (b) ACP
Figure 1: Network architecture for PRNet and ACP.

We establish preliminaries about the rigid alignment problem and related
algorithms in §3.1; then, we present PRNet in §3.2. For ease of comparison to
previous work, we use the same notation as [2].

###  3.1 Preliminaries: Registration, ICP, and DCP

Consider two point clouds
$\mathcal{X}=\\{\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{i},\ldots,\boldsymbol{x}_{N}\\}\subset\mathbb{R}^{3}$
and
$\mathcal{Y}=\\{\boldsymbol{y}_{1},\ldots,\boldsymbol{y}_{j},\ldots,\boldsymbol{y}_{M}\\}\subset\mathbb{R}^{3}$.
The basic task in rigid registration is to find a rotation
$\boldsymbol{R}_{\mathcal{XY}}$ and translation
$\boldsymbol{t}_{\mathcal{XY}}$ that rigidly align $\mathcal{X}$ to
$\mathcal{Y}$. When $M=N$, ICP and its peers approach this task by minimizing
the objective function

$\begin{split}E(\boldsymbol{R}_{\mathcal{XY}},\boldsymbol{t}_{\mathcal{XY}},m)\\!=\\!\frac{1}{N}\\!\sum_{i=1}^{N}\|\boldsymbol{R}_{\mathcal{XY}}\boldsymbol{x}_{i}+\boldsymbol{t}_{\mathcal{XY}}-\boldsymbol{y}_{m(x_{i})}\|^{2}.\end{split}$
(1)

Here, the rigid transformation is defined by a pair
$[\boldsymbol{R}_{\mathcal{XY}},\boldsymbol{t}_{\mathcal{XY}}]$, where
$\boldsymbol{R}_{\mathcal{XY}}\in\mathrm{SO}(3)$ and
$\boldsymbol{t}_{\mathcal{XY}}\in\mathbb{R}^{3}$; $m$ maps from points in
$\mathcal{X}$ to points in $\mathcal{Y}$. Assuming $m$ is fixed, the alignment
in (1) is given in closed-form by

$\boldsymbol{R}_{\mathcal{XY}}=\boldsymbol{V}\boldsymbol{U}^{\top}\qquad\textrm{and}\qquad\boldsymbol{t}_{\mathcal{XY}}=-\boldsymbol{R}_{\mathcal{XY}}\overline{\boldsymbol{x}}+\overline{\boldsymbol{y}},$
(2)

where $\boldsymbol{U}$ and $\boldsymbol{V}$ are obtained using the singular
value decomposition (SVD)
$\boldsymbol{H}=\boldsymbol{U}\boldsymbol{S}\boldsymbol{V}^{\top}$, with
$\boldsymbol{H}=\sum_{i=1}^{N}(\boldsymbol{x}_{i}-\overline{\boldsymbol{x}})(\boldsymbol{y}_{m(x_{i})}-\overline{\boldsymbol{y}})^{\top}$.
In this expression, centroids of $\mathcal{X}$ and $\mathcal{Y}$ are defined
as $\overline{\boldsymbol{x}}=\frac{1}{N}\sum_{i=1}^{N}\boldsymbol{x}_{i}$ and
$\overline{\boldsymbol{y}}=\frac{1}{N}\sum_{i=1}^{N}\boldsymbol{y}_{m(x_{i})},$
respectively.

We can understand ICP and the more recent learning-based DCP method [2] as
providing different choices of $m$:

Iterative Closest Point. ICP chooses $m$ to minimize (1) with
$[\boldsymbol{R}_{\mathcal{XY}},\boldsymbol{t}_{\mathcal{XY}}]$ fixed,
yielding:

$\begin{split}m(\boldsymbol{x}_{i},\mathcal{Y})=\operatorname*{arg\,min}_{j}\
\|\boldsymbol{R}_{\mathcal{XY}}\boldsymbol{x}_{i}+\boldsymbol{t}_{\mathcal{XY}}-\boldsymbol{y}_{j}\|_{2}\end{split}$
(3)

ICP approaches a fixed point by alternating between (2) and (3); each step
decreases the objective (1). Since (1) is non-convex, however, there is no
guarantee that ICP reaches a global optimum.

Deep Closest Point. DCP uses deep networks to learn $m$. In this method,
$\mathcal{X}$ and $\mathcal{Y}$ are embedded using learned functions
$\mathcal{F}_{\mathcal{X}}$ and $\mathcal{F}_{\mathcal{Y}}$ defined by a
Siamese DGCNN [22]; these lifted point clouds are optionally contextualized by
a Transformer module [59], yielding embeddings $\Phi_{\mathcal{X}}$ and
$\Phi_{\mathcal{Y}}$. The mapping $m$ is then

$\begin{split}m(\boldsymbol{x}_{i},\mathcal{Y})=\mathrm{softmax}(\Phi_{\mathcal{Y}}\Phi_{\boldsymbol{x}_{i}}^{\top}).\end{split}$
(4)

This formula is applied in one shot followed by (2) to obtain the rigid
alignment. The loss used to train this pipeline is mean-squared error (MSE)
between ground-truth rigid motion from synthetically-rotated point clouds and
prediction; the network is trained end-to-end.

###  3.2 Partial Registration Network

DCP is a one-shot algorithm, in that a single pass through the network
determines the output for each prediction task. Analogously to ICP, PRNet is
designed to be _iterative_ ; multiple passes of a point cloud through PRNet
refine the alignment. The steps of PRNet, illustrated in Figure 1, are as
follows:

  1. 1.

take as input point clouds $\mathcal{X}$ and $\mathcal{Y}$;

  2. 2.

detect keypoints of $\mathcal{X}$ and $\mathcal{Y}$;

  3. 3.

predict a mapping from keypoints of $\mathcal{X}$ to keypoints of
$\mathcal{Y}$;

  4. 4.

predict a rigid transformation
$[\boldsymbol{R}_{\mathcal{XY}},\boldsymbol{t}_{\mathcal{XY}}]$ aligning
$\mathcal{X}$ to $\mathcal{Y}$ based on the keypoints and map;

  5. 5.

transform $\mathcal{X}$ using the obtained transformation;

  6. 6.

return to 1 using the pair
$(\boldsymbol{R}_{\mathcal{XY}}\mathcal{X}+\boldsymbol{t}_{\mathcal{XY}},\mathcal{Y})$
as input.

When predicting a mapping from keypoints in $\mathcal{X}$ to keypoints in
$\mathcal{Y}$, PRNet uses Gumbel–Softmax [3] to sample a matching matrix,
which is sharper than (4) and approximately differentiable. It has a value
network to predict a temperature for Gumbel–Softmax, so that the whole
framework can be seen as an actor-critic method. We present details of and
justifications behind the design below.

Notation. Denote by
$\mathcal{X}^{p}=\\{\boldsymbol{x}_{1}^{p},\ldots,\boldsymbol{x}_{i}^{p},\ldots,\boldsymbol{x}_{N}^{p}\\}$
the rigid motion of $\mathcal{X}$ to align to $\mathcal{Y}$ after $p$
applications of PRNet; $\mathcal{X}^{1}$ and $\mathcal{Y}^{1}$ are initial
input shapes. We will use
$[\boldsymbol{R}_{\mathcal{XY}}^{p},\boldsymbol{t}_{\mathcal{XY}}^{p}]$ to
denote the $p$-th rigid motion predicted by PRNet for the input pair
$(\mathcal{X},\mathcal{Y})$.

Since our training pairs are synthetically generated, before applying PRNet we
know the ground-truth
$[\boldsymbol{R}_{\mathcal{XY}}^{*},\boldsymbol{t}_{\mathcal{XY}}^{*}]$
aligning $\mathcal{X}$ to $\mathcal{Y}$. From these values, during training we
can compute “local” ground-truth
$[\boldsymbol{R}_{\mathcal{XY}}^{p*},\boldsymbol{t}_{\mathcal{XY}}^{p*}]$ on-
the-fly, which maps the current $(\mathcal{X}^{p},\mathcal{Y})$ to the best
alignment:

$\boldsymbol{R}^{p*}_{\mathcal{XY}}=\boldsymbol{R}^{*}_{\mathcal{XY}}\boldsymbol{R}^{1\dots
p\top}_{\mathcal{XY}}\qquad\mathrm{and}\qquad\boldsymbol{t}^{p*}_{\mathcal{XY}}=\boldsymbol{t}^{*}_{\mathcal{XY}}-\boldsymbol{R}^{p*}_{\mathcal{XY}}\boldsymbol{t}^{1\dots
p}_{\mathcal{XY}},$ (5)

where

$\boldsymbol{R}^{1\dots
p}_{\mathcal{XY}}=\boldsymbol{R}^{p-1}_{\mathcal{XY}}\ldots\boldsymbol{R}^{1}_{\mathcal{XY}}\qquad\mathrm{and}\qquad\boldsymbol{t}^{1\dots
p}_{\mathcal{XY}}=\boldsymbol{R}^{p-1}_{\mathcal{XY}}\boldsymbol{t}^{1\dots
p-1}_{\mathcal{XY}}+\boldsymbol{t}^{p-1}_{\mathcal{XY}}.$ (6)

We use $m^{p}$ to denote the mapping function in $p$-th step.

Synthesizing the notation above, $\mathcal{X}^{p}$ is given by

$\boldsymbol{x}^{p}_{i}=\boldsymbol{R}_{\mathcal{XY}}^{p-1}\boldsymbol{x}_{i}^{p-1}+\boldsymbol{t}_{\mathcal{XY}}^{p-1}$
(7)

where

$\boldsymbol{R}_{\mathcal{XY}}^{p}=\boldsymbol{V}^{p}\boldsymbol{U}^{p\top}\qquad\textrm{and}\qquad\boldsymbol{t}_{\mathcal{XY}}^{p}=-\boldsymbol{R}_{\mathcal{XY}}^{p}\overline{\boldsymbol{x}}^{p}+\overline{\boldsymbol{y}}.$
(8)

In this equation, $\boldsymbol{U}^{p}$ and $\boldsymbol{V}^{p}$ are computed
using (2) from $\mathcal{X}^{p}$, $\mathcal{Y}^{p}$, and $m^{p}$.

Keypoint Detection. For partial-to-partial registration, usually $N\neq M$ and
only subsets of $\mathcal{X}$ and $\mathcal{Y}$ match to one another. To
detect these mutually-shared patches, we design a simple yet efficient
keypoint detection module based on the observation that the $L^{2}$ norms of
features tend to indicate whether a point is important.

Using $\mathcal{X}^{p}_{k}$ and $\mathcal{Y}^{p}_{k}$ to denote the $k$
keypoints for $\mathcal{X}^{p}$ and $\mathcal{Y}^{p}$, we take

$\begin{array}[]{r@{\
}l}\mathcal{X}^{p}_{k}&=\mathcal{X}^{p}(\mathrm{topk}(\|\Phi_{\boldsymbol{x}_{1}}^{p}\|_{2},\ldots,\|\Phi_{\boldsymbol{x}_{i}}^{p}\|_{2},\ldots,\|\Phi_{\boldsymbol{x}_{N}}^{p}\|_{2}))\\\
\mathcal{Y}^{p}_{k}&=\mathcal{Y}^{p}(\mathrm{topk}(\|\Phi_{\boldsymbol{y}_{1}}^{p}\|_{2},\ldots,\|\Phi_{\boldsymbol{y}_{i}}^{p}\|_{2},\ldots,\|\Phi_{\boldsymbol{y}_{M}}^{p}\|_{2}))\end{array}$
(9)

where $\mathrm{topk}(\cdot)$ extracts the indices of the $k$ largest elements
of the given input. Here, $\Phi$ denotes embeddings learned by DGCNN and
Transformer.

By aligning only the keypoints, we remove irrelevant points from the two input
clouds that are not shared in the partial correspondence. In particular, we
can now solve the Procrustes problem that matches keypoints of $\mathcal{X}$
and $\mathcal{Y}$. We show in §4.3 that although we do not provide explicit
supervision, PRNet still learns how to detect keypoints reasonably.

Gumbel–Softmax Sampler. One key observation in ICP and DCP is that (3) usually
is not differentiable with respect to the map $m$ but by definition yields a
sharp correspondence between the points in $\mathcal{X}$ and the points in
$\mathcal{Y}$. In contrast, the smooth function (4) in DCP is differentiable,
but in exchange for this differentiability the mapping is blurred. We desire
the best of both worlds: A potentially sharp mapping function that admits
backpropagation.

To that end, we use Gumbel–Softmax [3] to sample a matching matrix. Using a
straight-through gradient estimator, this module is approximately
differentiable. In particular, the Gumbel–Softmax mapping function is given by

$\begin{split}m^{p}(\boldsymbol{x}_{i},\mathcal{Y})=\mathrm{one\,hot}\left[\operatorname*{arg\,max}_{j}\mathrm{softmax}(\Phi_{\mathcal{Y}}^{p}\Phi_{\boldsymbol{x}_{i}}^{p\top}+g_{ij})\right],\end{split}$
(10)

where $(g_{i1},\ldots,g_{ij},\ldots,g_{iN})$ are i.i.d. samples drawn from
Gumbel(0, 1). The map in (10) is not differentiable due to the discontinuity
of $\operatorname*{arg\,max}$, but the straight-through gradient estimator
[60] yields (biased) subgradient estimates with low variance. Following their
methodology, on backward evaluation of the computational graph, we use (4) to
compute $\frac{\partial L}{\partial\Phi_{*}^{p}}$, ignoring the
$\mathrm{one\,hot}$ operator and the $\operatorname*{arg\,max}$ term.

Actor-Critic Closest Point (ACP). The mapping functions (4) and (10) have
fixed “temperatures,” that is, there is no control over the sharpness of the
mapping matrix $m^{p}$. In PRNet, we wish to adapt the sharpness of the map
based on the alignment of the two shapes. In particular, for low values of $p$
(the initial iterations of alignment) we may satisfied with high-entropy
approximate matchings that obtain a coarse alignment; later during iterative
evaluations, we can sharpen the map to align individual pairs of points.

To make this intuition compatible with PRNet’s learning-based architecture, we
add a parameter $\lambda$ to (10) to yield a generalized Gumbel–Softmax
matching matrix:

$\begin{split}m^{p}(\boldsymbol{x}_{i},\mathcal{Y})=\mathrm{one\,hot}\left[\operatorname*{arg\,max}_{j}\mathrm{softmax}\left(\frac{\Phi_{\mathcal{Y}}^{p}\Phi_{\boldsymbol{x}_{i}}^{p\top}+g_{ij}}{\lambda}\right)\right]\end{split}$
(11)

When $\lambda$ is large, the map matrix $m^{p}$ is smoothed out; as
$\lambda\to 0$ the map approaches a binary matrix.

It is difficult to choose a single $\lambda$ that suffices for all
$(\mathcal{X},\mathcal{Y})$ pairs; rather, we wish $\lambda$ to be chosen
adaptively and automatically to extract the best alignment for each pair of
point clouds. Hence, we use a small network $\Theta$ to predict $\lambda$
based on global features $\Psi_{\mathcal{X}}^{p}$ and $\Psi_{\mathcal{Y}}^{p}$
aggregated from $\Phi_{\mathcal{X}}^{p}$ and $\Phi_{\mathcal{Y}}^{p}$ channel-
wise by global pooling (averaging). In particular, we take
$\lambda=\Theta(\Psi_{\mathcal{X}}^{p},\Psi_{\mathcal{Y}}^{p}),$ where
$\Psi_{\mathcal{X}}^{p}=\mathrm{avg}_{i}\Phi_{\boldsymbol{x}_{i}}^{p}$ and
$\Psi_{\mathcal{Y}}^{p}=\mathrm{avg}_{i}\Phi_{\boldsymbol{y}_{i}}^{p}.$ In the
parlance of reinforcement learning, this choice can be seen as a simplified
version of actor-critic method. $\Phi_{\mathcal{X}}^{p}$ and
$\Phi_{\mathcal{Y}}^{p}$ are learned jointly with DGCNN [22] and Transformer
[59]; then an actor head outputs a rigid motion, where (11) uses the $\lambda$
predicted from a critic head.

Loss Function. The final loss $L$ is the summation of several terms $L_{p}$,
indexed by the number $p$ of passes through PRNet for the input pair. $L_{p}$
consists of three terms: a rigid motion loss $L_{p}^{m}$, a cycle consistency
loss $L_{p}^{c}$, and a global feature alignment loss $L_{g}$. We also
introduce a discount factor $\gamma<1$ to promote alignment within the first
few passes through PRNet; during training we pass each input pair through
PRNet $P$ times.

Combining the terms above, we have

$L=\sum_{p=1}^{P}\gamma^{p-1}L_{p},\qquad\textrm{where}\qquad
L_{p}=L_{p}^{m}+\alpha L_{p}^{c}+\beta L_{g}^{p}.$ (12)

The rigid motion loss $L_{p}^{m}$ is,

$\begin{split}L_{p}^{m}=\|\boldsymbol{R}^{p\top}_{\mathcal{XY}}\boldsymbol{R}^{p*}_{\mathcal{XY}}-I\|^{2}+\|\boldsymbol{t}_{\mathcal{XY}}^{p}-\boldsymbol{t}^{p*}_{\mathcal{XY}}\|^{2}\end{split}$
(13)

Equation (5) gives the “localized” ground truth values for
$\boldsymbol{R}^{p*}_{\mathcal{XY}},\boldsymbol{t}^{p*}_{\mathcal{XY}}$.
Denoting the rigid motion from $\mathcal{Y}$ to $\mathcal{X}$ in step $p$ as
$[\boldsymbol{R}_{\mathcal{YX}}^{p},\boldsymbol{t}_{\mathcal{YX}}^{p}],$ the
cycle consistency loss is

$\begin{split}L_{p}^{c}=\|\boldsymbol{R}^{p}_{\mathcal{XY}}\boldsymbol{R}^{p}_{\mathcal{YX}}-I\|^{2}+\|\boldsymbol{t}_{\mathcal{XY}}^{p}-\boldsymbol{t}^{p}_{\mathcal{YX}}\|^{2}.\end{split}$
(14)

Our last loss term is a global feature alignment loss, which enforces
alignment of global features $\Psi_{\mathcal{X}}^{p}$ and
$\Psi_{\mathcal{Y}}^{p}$. Mathematically, the global feature alignment loss is

$L_{g}^{p}=\|\Psi_{\mathcal{X}}^{p}-\Psi_{\mathcal{Y}}^{p}\|.$ (15)

This global feature alignment loss also provides signal for determining
$\lambda$. When two shapes are close in global feature space, $\lambda$ should
be small, yielding a sharp matching matrix; when two shapes are far from each
other, $\lambda$ increases and the map is blurry.

##  4 Experiments

Model | MSE($\boldsymbol{R}$) $\downarrow$ | RMSE($\boldsymbol{R}$) $\downarrow$ | MAE($\boldsymbol{R}$) $\downarrow$ | R2($\boldsymbol{R}$) $\uparrow$ | MSE($\boldsymbol{t}$) $\downarrow$ | RMSE($\boldsymbol{t}$) $\downarrow$ | MAE($\boldsymbol{t}$) $\downarrow$ | R2($\boldsymbol{t}$) $\uparrow$
---|---|---|---|---|---|---|---|---
ICP | 1134.552 | 33.683 | 25.045 | -5.696 | 0.0856 | 0.293 | 0.250 | -0.037
Go-ICP [14] | 195.985 | 13.999 | 3.165 | -0.157 | 0.0011 | 0.033 | 0.012 | 0.987
FGR [61] | 126.288 | 11.238 | 2.832 | 0.256 | 0.0009 | 0.030 | 0.008 | 0.989
PointNetLK [1] | 280.044 | 16.735 | 7.550 | -0.654 | 0.0020 | 0.045 | 0.025 | 0.975
DCP-v2 [2] | 45.005 | 6.709 | 4.448 | 0.732 | 0.0007 | 0.027 | 0.020 | 0.991
PRNet (Ours) | 10.235 | 3.199257 | 1.454 | 0.939 | 0.0003 | 0.016 | 0.010 | 0.997

Table 1: Test on unseen point clouds

Model | MSE($\boldsymbol{R}$) $\downarrow$ | RMSE($\boldsymbol{R}$) $\downarrow$ | MAE($\boldsymbol{R}$) $\downarrow$ | R2($\boldsymbol{R}$) $\uparrow$ | MSE($\boldsymbol{t}$) $\downarrow$ | RMSE($\boldsymbol{t}$) $\downarrow$ | MAE($\boldsymbol{t}$) $\downarrow$ | R2($\boldsymbol{t}$) $\uparrow$
---|---|---|---|---|---|---|---|---
ICP | 1217.618 | 34.894 | 25.455 | -6.253 | 0.086 | 0.293 | 0.251 | -0.038
Go-ICP [14] | 157.072 | 12.533 | 2.940 | 0.063 | 0.0009 | 0.031 | 0.010 | 0.989
FGR [61] | 98.635 | 9.932 | 1.952 | 0.414 | 0.0014 | 0.038 | 0.007 | 0.983
PointNetLK [1] | 526.401 | 22.943 | 9.655 | -2.137 | 0.0037 | 0.061 | 0.033 | 0.955
DCP-v2 [2] | 95.431 | 9.769 | 6.954 | 0.427 | 0.0010 | 0.034 | 0.025 | 0.986
PRNet (Ours) | 24.857 | 4.986 | 2.329 | 0.850 | 0.0004 | 0.021 | 0.015 | 0.995
PRNet (Ours*) | 15.624 | 3.953 | 1.712 | 0.907 | 0.0003 | 0.017 | 0.011 | 0.996

Table 2: Test on unseen categories. PRNet (Ours*) denotes the model trained on
ShapeNetCore and tested on ModelNet40 held-out categories. Others are trained
on first 20 ModelNet40 categories and tested on ModelNet40 held-out
categories.

Model | MSE($\boldsymbol{R}$) $\downarrow$ | RMSE($\boldsymbol{R}$) $\downarrow$ | MAE($\boldsymbol{R}$) $\downarrow$ | R2($\boldsymbol{R}$) $\uparrow$ | MSE($\boldsymbol{t}$) $\downarrow$ | RMSE($\boldsymbol{t}$) $\downarrow$ | MAE($\boldsymbol{t}$) $\downarrow$ | R2($\boldsymbol{t}$) $\uparrow$
---|---|---|---|---|---|---|---|---
ICP | 1229.670 | 35.067 | 25.564 | -6.252 | 0.0860 | 0.294 | 0.250 | -0.045
Go-ICP [14] | 150.320 | 12.261 | 2.845 | 0.112 | 0.0008 | 0.028 | 0.029 | 0.991
FGR [61] | 764.671 | 27.653 | 13.794 | -3.491 | 0.0048 | 0.070 | 0.039 | 0.941
PointNetLK [1] | 397.575 | 19.939 | 9.076 | -1.343 | 0.0032 | 0.0572 | 0.032 | 0.960
DCP-v2 [2] | 47.378 | 6.883 | 4.534 | 0.718 | 0.0008 | 0.028 | 0.021 | 0.991
PRNet (Ours) | 18.691 | 4.323 | 2.051 | 0.889 | 0.0003 | 0.017 | 0.012 | 0.995

Table 3: Test on unseen point clouds with Gaussian noise

Our experiments are divided into four parts. First, we show performance of
PRNet on a partial-to-partial registration task on synthetic data in §4.1.
Then, we show PRNet can generalize to real data in §4.2. Third, we visualize
the keypoints and correspondences predicted by PRNet in §4.3. Finally, we show
a linear SVM trained on representations learned by PRNet can achieve
comparable results to supervised learning methods in §4.4.

###  4.1 Partial-to-Partial Registration on ModelNet40

We evaluate partial-to-partial registration on ModelNet40 [62]. There are
12,311 CAD models spanning 40 object categories, split to 9,843 for training
and 2,468 for testing. Point clouds are sampled from the CAD models by
farthest-point sampling on the surface. During training, a point cloud with
1024 points $\mathcal{X}$ is sampled. Along each axis, we randomly draw a
rigid transformation; the rotation along each axis is sampled in
$[0,45^{\circ}]$ and translation is in $[-0.5,0.5]$. We apply the rigid
transformation to $\mathcal{X}$, leading to $\mathcal{Y}$. We simulate partial
scans of $\mathcal{X}$ and $\mathcal{Y}$ by randomly placing a point in space
and computing its 768 nearest neighbors in $\mathcal{X}$ and $\mathcal{Y}$
respectively.

We measure mean squared error (MSE), root mean squared error (RMSE), mean
absolute error (MAE), and coefficient of determination (R2). Angular
measurements are in units of degrees. MSE, RMSE and MAE should be zero while
R2 should be one if the rigid alignment is perfect. We compare our model to
ICP, Go-ICP [14], Fast Global Registration (FGR) [61], and DCP [2].

Figure 1 shows the architecture of ACP. We use DGCNN with 5 dynamic EdgeConv
layers and a Transformer to learn co-contextual representations of
$\mathcal{X}$ and $\mathcal{Y}$. The number of filters in each layer of DGCNN
are $(64,64,128,256,512)$. In the Transformer, only one encoder and one
decoder with 4-head attention are used. The embedding dimension is 1024. We
train the network for 100 epochs using Adam [63]. The initial learning rate is
0.001 and is divided by 10 at epochs 30, 60, and 80.

Model | z/z $\uparrow$ |  $\mathrm{SO}(3)$/$\mathrm{SO}(3)$ $\uparrow$ | input size
---|---|---|---
PointNet [20] | 89.2 | 83.6 | $2048\times 3$
PointNet++ [21] | 89.3 | 85.0 | $1024\times 3$
DGCNN [22] | 92.2 | 87.2 | $1024\times 3$
VoxNet [64] | 83.0 | 73.0 | 303
SubVolSup [65] | 88.5 | 82.7 | 303
SubVolSup MO [65] | 89.5 | 85.0 | $20\times 30^{3}$
MVCNN 12x [66] | 89.5 | 77.6 | $12\times 224^{2}$
MVCNN 80x [66] | 90.2 | 86.0 | $80\times 224^{2}$
RotationNet 20x [67] | 92.4 | 80.0 | $20\times 224^{2}$
Spherical CNNs [68] | 88.9 | 86.9 | $2\times 64^{2}$
PRNet (Ours) | 85.2 | 80.5 | $1024\times 3$

Table 4: ModelNet40: transfer learning

Partial-to-Partial Registration on Unseen Objects. We first evaluate on the
ModelNet40 train/test split. We train on 9,843 training objects and test on
2,468 testing objects. Table 1 shows performance. Our method outperforms its
counterparts in all metrics.

Partial-to-Partial Registration on Unseen Categories. We follow the same
testing protocol as [2] to compare the generalizability of different models.
ModelNet40 is split evenly by category into training and testing sets. PRNet
and DCP are trained on the first 20 categories, and then all methods are
tested on the held-out categories. Table 2 shows PRNet behaves more strongly
than others. To further test generalizability, we train it on ShapeNetCore
dataset [69] and test on ModelNet40 held-out categories. ShapeNetCore has
57,448 objects, and we do the same preprocessing as on ModelNet40. The last
row in Table 2, denoted as PRNet (Ours*), surprisingly shows PRNet performs
much better than when trained on ModelNet40. This supports the intuition that
data-driven approaches work better with more data.

Partial-to-Partial Registration on Unseen Objects with Gaussian Noise. We
further test robustness to noise. The same preprocessing is done as in the
first experiment, except that noise independently sampled from
$\mathcal{N}(0,0.01)$ and clipped to $[-0.05,0.05]$ is added to each point. As
in Table 3, learning-based methods, including DCP and PRNet, are more robust.
In particular, PRNet exhibits stronger performance and is even comparable to
the noise-free version in Table 1.

###  4.2 Partial-to-Partial on Real Data

Figure 2: Left: Input partial point clouds. Right: Transformed partial point
clouds.

We test our model on the Stanford Bunny dataset [70]. Since the dataset only
has 10 real scans, we fine tune the model used in Table 1 for 10 epochs with
learning rate 0.0001. For each scan, we generate 100 training examples by
randomly transforming the scan in the same way as we do in §4.1. This training
procedure can be viewed as inference time fine-tuning, in contrast to
optimization-based methods that perform one-time inference for each test case.
Figure 2 shows the results. We further test our model on more scans from
Stanford 3D Scanning Repository [71] using a similar methodology; Figure 3
shows the registration results.

###  4.3 Keypoints and Correspondences

Figure 3: More examples on The Stanford 3D Scanning Repository [71].

We visualize keypoints on several objects in Figure 4 and correspondences in
Figure 6. The model detects keypoints and correspondences on partially
observable objects. We overlay the keypoints on top of the fully observable
objects. Also, as shown in Figure 5, the keypoints are consistent across
different views.

(a) Partial Point Clouds (b) Full Point Clouds

Figure 4: Keypoint detection of a pair of beds. Point clouds in red are
$\mathcal{X}$ and point clouds in green are $\mathcal{Y}$. Points in black are
keypoints detected by PRNet. Point clouds in the first row are in the original
pose while point clouds in the second row are transformed using the rigid
transformation predicted by PRNet. (a) PRNet takes as input partial point
clouds. (b) The obtained rigid transformation is applied to full point clouds
for better visualization.  Figure 5: Keypoint detection with different partial
scans. We show the same pair of $\mathcal{X}$ and $\mathcal{Y}$ with different
views. The keypoints are data-dependent and consistent across different views.
Figure 6: Correspondences for pairs of objects.

###  4.4 Transfer to Classification

Representations learned by PRNet can be transferred to object recognition. We
use the model trained on ShapeNetCore in §4.1 and train a linear SVM on top of
the embeddings predicted by DGCNN. In Table 4, we show classification accuracy
on ModelNet40. $z/z$ means the model is trained when only azimuthal rotations
are present on both during and testing. $\mathrm{SO}(3)$/$\mathrm{SO}(3)$
means the object is moved with a random motion in $\mathrm{SO}(3)$ during both
training and testing. Although other methods are supervised, ours achieves
comparable performance.

##  5 Conclusion

PRNet tackles a general partial-to-partial registration problem, leveraging
self-supervised learning to learn geometric priors directly from data. The
success of PRNet verifies the sensibility of applying learning to partial
matching as well as the specific choice of Gumbel–Softmax, which we hope can
inspire additional work linking discrete optimization to deep learning. PRNet
is also a reinforcement learning-like framework; this connection between
registration and reinforcement learning may provide inspiration for additional
interdisciplinary research related to rigid/non-rigid registration.

Our experiments suggest several avenues for future work. For example, as shown
in Figure 6, the matchings computed by PRNet are not bijective, evident e.g.
in the point clouds of cars and chairs. One possible extension of our work to
address this issue is to use Gumbel–Sinkhorn [72] to encourage bijectivity.
Improving the efficiency of PRNet when applied to real scans also will be
extremely valuable. As described in §4.2, PRNet currently requires inference-
time fine-tuning on real scans to learn useful data-dependent representations;
this makes PRNet slow during inference. Seeking universal representations that
generalize over broader sets of registration tasks will improve the speed and
generalizability of learning-based registration. Another possibility for
future work is to improve the scalability of PRNet to deal with large-scale
real scans captured by LiDAR.

Finally, we hope to find more applications of PRNet beyond the use cases we
have shown in the paper. A key direction bridging PRNet to applications will
involve incorporating our method into SLAM or structure-from-motion can
demonstrate its value for robotics applications and robustness to realistic
species of noise. Additionally, we can test the effectiveness of PRNet for
registration problems in medical imaging and/or high-energy particle physics.

##  6 Acknowledgements

The authors acknowledge the generous support of Army Research Office grant
W911NF1710068, Air Force Office of Scientific Research award FA9550-19-1-031,
of National Science Foundation grant IIS-1838071, from an Amazon Research
Award, from the MIT-IBM Watson AI Laboratory, from the Toyota-CSAIL Joint
Research Center, from a gift from Adobe Systems, and from the Skoltech-MIT
Next Generation Program. Any opinions, findings, and conclusions or
recommendations expressed in this material are those of the authors and do not
necessarily reflect the views of these organizations. The authors also thank
members of MIT Geometric Data Processing group for helpful discussion and
feedback on the paper.

## References

  * [1] Hunter Goforth, Yasuhiro Aoki, R. Arun Srivatsan, and Simon Lucey.  PointNetLK: Robust & efficient point cloud registration using PointNet.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
  * [2] Yue Wang and Justin Solomon.  Deep closest point: Learning representations for point cloud registration.  In IEEE International Conference on Computer Vision (ICCV), 2019\.
  * [3] Eric Jang, Shixiang Gu, and Ben Poole.  Categorical reparameterization with Gumbel-Softmax.  In International Conference on Learning Representations (ICLR), 2017\.
  * [4] Chengzhou Tang and Ping Tan.  BA-net: Dense bundle adjustment networks.  In International Conference on Learning Representations (ICLR), 2019\.
  * [5] Paul J. Besl and Neil D. McKay.  A method for registration of 3-d shapes.  IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 14(2):239–256, February 1992.
  * [6] Szymon Rusinkiewicz and Marc Levoy.  Efficient variants of the ICP algorithm.  In Third International Conference on 3D Digital Imaging and Modeling (3DIM), 2001.
  * [7] Aleksandr Segal, Dirk Hähnel, and Sebastian Thrun.  Generalized-ICP.  In Robotics: Science and Systems, 2009.
  * [8] Sofien Bouaziz, Andrea Tagliasacchi, and Mark Pauly.  Sparse iterative closest point.  In Proceedings of the Symposium on Geometry Processing, 2013.
  * [9] François Pomerleau, Francis Colas, and Roland Siegwart.  A review of point cloud registration algorithms for mobile robotics.  Now Foundations and Trends, 4(1):1–104, May 2015.
  * [10] Gabriel Agamennoni, Simone Fontana, Roland Y. Siegwart, and Domenico G. Sorrenti.  Point clouds registration with probabilistic data association.  In International Conference on Intelligent Robots and Systems (IROS), 2016.
  * [11] Timo Hinzmann, Thomas Stastny, Gianpaolo Conte, Patrick Doherty, Piotr Rudol, Marius Wzorek, Enric Galceran, Roland Siegwart, and Igor Gilitschenski.  Collaborative 3d reconstruction using heterogeneous UAVs: System and experiments.  In International Symposium on Robotic Research, 2016.
  * [12] Dirk Hähnel and Wolfram Burgard.  Probabilistic matching for 3d scan registration.  In Proceedings of the VDI - Conference Robotik (Robotik), 2002.
  * [13] Andrew W. Fitzgibbon.  Robust registration of 2D and 3D point sets.  In British Machine Vision Conference (BMVC), 2001.
  * [14] Jiaolong Yang, Hongdong Li, Dylan Campbell, and Yunde Jia.  Go-ICP: A globally optimal solution to 3d ICP point-set registration.  IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 38(11):2241–2254, November 2016.
  * [15] David M. Rosen, Luca Carlone, Afonso S. Bandeira, and John J. Leonard.  SE-Sync: A certifiably correct algorithm for synchronization over the Special Euclidean group.  In The Workshop on the Algorithmic Foundations of Robotics (WAFR), 2016.
  * [16] Haggai Maron, Nadav Dym, Itay Kezurer, Shahar Kovalsky, and Yaron Lipman.  Point registration via efficient convex relaxation.  ACM Transactions on Graphics (TOG), 35(4):73:1–73:12, July 2016\.
  * [17] Gregory Izatt, Hongkai Dai, and Russ Tedrake.  Globally optimal object pose estimation in point clouds with mixed-integer programming.  In International Symposium on Robotic Research, 2017.
  * [18] Heng Yang and Luca Carlone.  A polynomial-time solution for robust registration with extreme outlier rates.  In Robotics: Science and Systems, 2019.
  * [19] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander Smola.  Deep sets.  In Advances in Neural Information Processing Systems, 2017.
  * [20] Charles Ruizhongtai Qi, Hao Su, Kaichun Mo, and Leonidas J. Guibas.  PointNet: Deep learning on point sets for 3d classification and segmentation.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
  * [21] Charles Ruizhongtai Qi, Li Yi, Hao Su, and Leonidas J Guibas.  PointNet++: Deep hierarchical feature learning on point sets in a metric space.  In Advances in Neural Information Processing Systems, 2017.
  * [22] Yue Wang, Yongbin Sun, Sanjay E. Sarma Ziwei Liu, Michael M. Bronstein, and Justin M. Solomon.  Dynamic graph CNN for learning on point clouds.  ACM Transactions on Graphics (TOG), 38:146, 2019.
  * [23] Yangyan Li, Rui Bu, Mingchao Sun, Wei Wu, Xinhan Di, and Baoquan Chen.  PointCNN: Convolution on X-transformed points.  In Advances in Neural Information Processing Systems, 2018.
  * [24] Matan Atzmon, Haggai Maron, and Yaron Lipman.  Point convolutional neural networks by extension operators.  ACM Transactions on Graphics (TOG), 37(4):71:1–71:12, July 2018\.
  * [25] David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aspuru-Guzik, and Ryan P Adams.  Convolutional networks on graphs for learning molecular fingerprints.  In Advances in Neural Information Processing Systems, 2015.
  * [26] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In International Conference on Learning Representations (ICLR), 2017\.
  * [27] Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodolà, Jan Svoboda, and Michael M. Bronstein.  Geometric deep learning on graphs and manifolds using mixture model cnns.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
  * [28] Yu Wang, Vladimir Kim, Michael Bronstein, and Justin Solomon.  Learning geometric operators on meshes.  Representation Learning on Graphs and Manifolds (ICLR workshop), 2019.
  * [29] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst.  Geometric deep learning: going beyond Euclidean data.  IEEE Signal Processing Magazine, 34(4):18–42, 2017.
  * [30] Hang Su, Varun Jampani, Deqing Sun, Subhransu Maji, Evangelos Kalogerakis, Ming-Hsuan Yang, and Jan Kautz.  SPLATNet: Sparse lattice networks for point cloud processing.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
  * [31] Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller.  SplineCNN: Fast geometric deep learning with continuous B-spline kernels.  In Computer Vision and Pattern Recognition (CVPR), 2018.
  * [32] Hugues Thomas, Charles Ruizhongtai Qi, Jean-Emmanuel Deschaud, Beatriz Marcotegui, Franccois Goulette, and Leonidas J. Guibas.  KPConv: Flexible and deformable convolution for point clouds.  In International Conference on Computer Vision (ICCV), 2019.
  * [33] Danielle Ezuz, Justin Solomon, Vladimir G. Kim, and Mirela Ben-Chen.  GWCNN: A metric alignment layer for deep shape analysis.  Computer Graphics Forum, 2017.
  * [34] Alexander M Bronstein, Michael Bronstein, and Ron Kimmel.  Generalized multidimensional scaling: A framework for isometry-invariant partial surface matching.  In Proceedings of the National Academy of Sciences of the United States of America, 2006.
  * [35] Qi-Xing Huang, Bart Adams, Martin Wicke, and Leonidas J. Guibas.  Non-rigid registration under isometric deformations.  In Proceedings of the Symposium on Geometry Processing, 2008.
  * [36] Yaron Lipman and Thomas Funkhouser.  Möbius voting for surface correspondence.  In ACM SIGGRAPH, 2009.
  * [37] Vladimir G. Kim, Yaron Lipman, and Thomas Funkhouser.  Blended intrinsic maps.  In ACM SIGGRAPH, 2011.
  * [38] Justin Solomon, Andy Nguyen, Adrian Butscher, Mirela Ben-Chen, and Leonidas Guibas.  Soft maps between surfaces.  Computer Graphics Forum, 31(5):1617–1626, August 2012.
  * [39] Justin Solomon, Leonidas Guibas, and Adrian Butscher.  Dirichlet energy for analysis and synthesis of soft maps.  In Proceedings of the Symposium on Geometry Processing, 2013.
  * [40] Justin Solomon, Gabriel Peyré, Vladimir G. Kim, and Suvrit Sra.  Entropic metric alignment for correspondence problems.  ACM Transactions on Graphics (TOG), 35(4):72:1–72:13, July 2016\.
  * [41] Danielle Ezuz, Justin Solomon, and Mirela Ben-Chen.  Reversible harmonic maps between discrete surfaces.  ACM Transactions on Graphics (TOG), 38(2):15:1–15:12, March 2019\.
  * [42] Maks Ovsjanikov, Mirela Ben-Chen, Justin Solomon, Adrian Butscher, and Leonidas Guibas.  Functional maps: A flexible representation of maps between shapes.  ACM Transactions on Graphics (TOG), 31(4):30:1–30:11, July 2012\.
  * [43] Or Litany, Tal Remez, Emanuele Rodolà, Alex Bronstein, and Michael Bronstein.  Deep functional maps: Structured prediction for dense shape correspondence.  In International Conference on Computer Vision (ICCV), 2017.
  * [44] Oshri Halimi, Or Litany, Emanuele Rodolà, Alex Bronstein, and Ron Kimmel.  Self-supervised learning of dense shape correspondence.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
  * [45] Supasorn Suwajanakorn, Noah Snavely, Jonathan J Tompson, and Mohammad Norouzi.  Discovery of latent 3d keypoints via end-to-end geometric reasoning.  In Advances in Neural Information Processing Systems (NeurIPS), 2018\.
  * [46] Li Yi, Haibin Huang, Difan Liu, Evangelos Kalogerakis, Hao Su, and Leonidas Guibas.  Deep part induction from articulated object pairs.  ACM Transactions on Graphics (TOG), 37(6):209:1–209:15, December 2018.
  * [47] Richard Zhang, Phillip Isola, and Alexei A Efros.  Colorful image colorization.  In European Conference on Computer Vision (ECCV), 2016.
  * [48] Richard Zhang, Phillip Isola, and Alexei A Efros.  Split-brain autoencoders: Unsupervised learning by cross-channel prediction.  In Computer Vision and Pattern Recognition (CVPR), 2017.
  * [49] Lluis Castrejon, Yusuf Aytar, Carl Vondrick, Hamed Pirsiavash, and Antonio Torralba.  Learning aligned cross-modal representations from weakly aligned data.  In Computer Vision and Pattern Recognition (CVPR), 2016.
  * [50] Yusuf Aytar, Lluis Castrejon, Carl Vondrick, Hamed Pirsiavash, and Antonio Torralba.  Cross-modal scene networks.  CoRR, abs/1610.09003, 2016.
  * [51] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: pre-training of deep bidirectional transformers for language understanding.  In The Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL), 2018.
  * [52] Kaiming He, Ross B. Girshick, and Piotr Dollár.  Rethinking imagenet pre-training.  In Computer Vision and Pattern Recognition (CVPR), 2019.
  * [53] Hang Zhao, Chuang Gan, Andrew Rouditchenko, Carl Vondrick, Josh McDermott, and Antonio Torralba.  The sound of pixels.  In European Conference on Computer Vision (ECCV), 2018.
  * [54] Andrew Oweppns and Alexei A Efros.  Audio-visual scene analysis with self-supervised multisensory features.  In European Conference on Computer Vision (ECCV), 2018.
  * [55] Ariel Ephrat, Inbar Mosseri, Oran Lang, Tali Dekel, Kevin Wilson, Avinatan Hassidim, William T. Freeman, and Michael Rubinstein.  Looking to listen at the cocktail party: A speaker-independent audio-visual model for speech separation.  ACM Transactions on Graphics, 37(4):112:1–112:11, July 2018.
  * [56] Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu.  Asynchronous methods for deep reinforcement learning.  In International Conference on Machine Learning (ICML), 2016.
  * [57] David Pfau and Oriol Vinyals.  Connecting generative adversarial networks and actor-critic methods.  In NeurIPS Workshop on Adversarial Training, 2016.
  * [58] Dzmitry Bahdanau, Philemon Brakel, Kelvin Xu, Anirudh Goyal, Ryan Lowe, Joelle Pineau, Aaron C. Courville, and Yoshua Bengio.  An actor-critic algorithm for sequence prediction.  In International Conference on Learning Representations, ICLR, 2017.
  * [59] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In Advances in Neural Information Processing Systems (NeurIPS), 2017\.
  * [60] Yoshua Bengio.  Estimating or propagating gradients through stochastic neurons.  CoRR, abs/1305.2982, 2013.
  * [61] Qian-Yi Zhou, Jaesik Park, and Vladlen Koltun.  Fast global registration.  In European Conference on Computer Vision (ECCV), 2016.
  * [62] Zhirong Wu, Shuran Song, Aditya Khosla, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao.  3d ShapeNets: A deep representation for volumetric shape modeling.  In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015.
  * [63] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In International Conference for Learning Representations (ICLR), 2015.
  * [64] Daniel Maturana and Sebastian Scherer.  Voxnet: A 3d convolutional neural network for real-time object recognition.  In International Conference on Intelligent Robots and Systems, 2015\.
  * [65] Charles Ruizhongtai Qi, Hao Su, Matthias Nießner, Angela Dai, Mengyuan Yan, and Leonidas Guibas.  Volumetric and multi-view CNNs for object classification on 3d data.  In Computer Vision and Pattern Recognition (CVPR), 2016.
  * [66] Hang Su, Subhransu Maji, Evangelos Kalogerakis, and Erik G. Learned-Miller.  Multi-view convolutional neural networks for 3d shape recognition.  In International Conference on Computer Vision (ICCV), 2015.
  * [67] Asako Kanezaki, Yasuyuki Matsushita, and Yoshifumi Nishida.  RotationNet: Joint object categorization and pose estimation using multiviews from unsupervised viewpoints.  In Computer Vision and Pattern Recognition (CVPR), 2018.
  * [68] Carlos Esteves, Christine Allen-Blanchette, Ameesh Makadia, and Kostas Daniilidis.  Learning SO(3) equivariant representations with spherical CNNs.  In European Conference on Computer Vision (ECCV), 2017.
  * [69] Angel Xuan Chang, Thomas A. Funkhouser, Leonidas J. Guibas, Pat Hanrahan, Qi-Xing Huang, Zimo Li, Silvio Savarese, Manolis Savva, Shuran Song, Hao Su, Jianxiong Xiao, Li Yi, and Fisher Yu.  ShapeNet: An information-rich 3d model repository.  CoRR, abs/1512.03012, 2015.
  * [70] Greg Turk and Marc Levoy.  Zippered polygon meshes from range images.  In Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques, 1994.
  * [71] The Stanford 3d scanning repository.
  * [72] Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek.  Learning latent permutations with Gumbel–Sinkhorn networks.  In International Conference on Learning Representations (ICLR), 2018\.

## Supplementary

We provide more details of PRNet in this section.

#### Actor-Critic Closest Point.

A shared DGCNN [22] is to use extract embeddings for $\mathcal{X}$ and
$\mathcal{Y}$ separately. The number of filters per layer are
$(64,64,128,256,512)$. We use BatchNorm and LeakyReLU after each MLP in the
EdgeConv layer. The local aggregation function of $k$-nn graph is $\max$, and
there is no global aggregation function used in DGCNN.
$\mathcal{F}_{\mathcal{X}}$ and $\mathcal{F}_{\mathcal{Y}}$ denote the
representations learned by DGCNN.

After DGCNN, $\mathcal{F}_{\mathcal{X}}$ and $\mathcal{F}_{\mathcal{Y}}$ are
fed into the Transformer. The Transformer is an asymmetric function that
learns co-contextual representations $\Phi_{\mathcal{X}}$ and
$\Phi_{\mathcal{Y}}$. Transformer has only one encoder and one decoder. 4-head
self-attention is used in encoder and decoder. LayerNorm, instead of
BatchNorm, is used in the Transformer. Unlike the original implementation of
Transformer, we do not use Dropout. For detailed presentation of Transformer,
we refer readers to the
tutorial.222http://nlp.seas.harvard.edu/2018/04/03/attention.html

There are two heads on top of the representations $\Phi_{\mathcal{X}}$ and
$\Phi_{\mathcal{Y}}$: a action head consisting of Gumbel-Softmax and SVD; a
value head to predict a $\lambda$ for Gumbel-Softmax in the action head. The
value head is parameterized by a 4-layer MLPs. The number of filters are
$(128,128,128,1)$. BatchNorm and ReLU are used after each linear layer in the
MLPs.

#### Training Protocol.

We train the model for 100 epochs. At epochs 30, 60, and 80, we divide the
learning rate by 10; it is initially 0.001. Each training pair $\mathcal{X}$
and $\mathcal{Y}$ is passed through PRNet three times iteratively (the rigid
alignment of $\mathcal{X}$ is updated three times). The final rigid
transformation is the combination of these three local rigid transformations.
$\alpha$ for cycle consistency loss and $\beta$ for feature alignment loss are
both 0.1. The weight decay used is $10^{-4}$. The number of keypoints is 512
on training. For visualization purposes, however, we show 64 keypoints in
Figure 4, Figure 5, and Figure 6.

Our model is trained on a Google Cloud GPU instance with 4 Tesla V100 GPUs and
takes 10 hours to complete.

As for DCP-v2, we take the implementation from the authors’ released code
333https://github.com/WangYueFt/dcp and train it as they suggest.

#### Choices of $\lambda$.

We compare to alternative choices of ways to determine $\lambda$: (1) fixing
$\lambda$ manually; (2) annealing $\lambda$ to near 0 as the training going;
(3) including $\lambda$ as a variable during training. We train the PRNet in
the same way for each option, except the choice of $\lambda$ is different.
Table 5 verifies our choice of strategies for computing $\lambda$.

Model | MSE($\boldsymbol{R}$) $\downarrow$ | RMSE($\boldsymbol{R}$) $\downarrow$ | MAE($\boldsymbol{R}$) $\downarrow$ | R2($\boldsymbol{R}$) $\uparrow$ | MSE($\boldsymbol{t}$) $\downarrow$ | RMSE($\boldsymbol{t}$) $\downarrow$ | MAE($\boldsymbol{t}$) $\downarrow$ | R2($\boldsymbol{t}$) $\uparrow$
---|---|---|---|---|---|---|---|---
Fixed $\lambda$ | 13.661 | 3.696 | 1.659 | 0.919 | 0.0003 | 0.018 | 0.012 | 0.996
Annealed $\lambda$ | 12.732 | 3.568 | 1.630 | 0.924 | 0.0003 | 0.017 | 0.011 | 0.996
Learned $\lambda$ | 13.506 | 3.675 | 1.675 | 0.920 | 0.0003 | 0.018 | 0.012 | 0.996
Predicted $\lambda$ | 10.235 | 3.199257 | 1.454 | 0.939 | 0.0003 | 0.016 | 0.010 | 0.997

Table 5: Choices of $\lambda$

Method | MAE($\boldsymbol{R}$) $\downarrow$ | R2($\boldsymbol{R}$) $\uparrow$ | MAE($\boldsymbol{t}$) $\downarrow$ | R2($\boldsymbol{t}$) $\uparrow$
---|---|---|---|---
Random sampling | 1.689 | 0.927 | 0.011 | 0.997
Closeness to other points | 2.109 | 0.861 | 0.013 | 0.995
$L^{2}$ Norm | 1.454 | 0.939 | 0.010 | 0.997

(a) Different keypoint detection methods.

Different $k$ | MAE($\boldsymbol{R}$) $\downarrow$ | R2($\boldsymbol{R}$) $\uparrow$ | MAE($\boldsymbol{t}$) $\downarrow$ | R2($\boldsymbol{t}$) $\uparrow$
---|---|---|---|---
16 | 27.843 | -14.176 | 0.136 | 0.326
32 | 8.293 | -1.848 | 0.048 | 0.892
64 | 3.129 | 0.563 | 0.024 | 0.979
128 | 2.007 | 0.879 | 0.016 | 0.991
256 | 1.601 | 0.932 | 0.012 | 0.996
384 | 1.508 | 0.934 | 0.011 | 0.997
512 | 1.454 | 0.939 | 0.010 | 0.997

(d) Different number of keypoints ($k$).

Model | MAE($\boldsymbol{R}$) $\downarrow$ | R2($\boldsymbol{R}$) $\uparrow$ | MAE($\boldsymbol{t}$) $\downarrow$ | R2($\boldsymbol{t}$) $\uparrow$
---|---|---|---|---
ICP | 25.165 | -5.860 | 0.250 | -0.045
Go-ICP | 2.336 | 0.308 | 0.007 | 0.994
FGR | 2.088 | 0.393 | 0.003 | 0.999
PointNetLK | 3.478 | 0.051 | 0.005 | 0.994
DCP | 2.777 | 0.887 | 0.009 | 0.998
PRNet (Ours) | 0.960 | 0.979 | 0.006 | 1.000

(b) Experiments on full point clouds.

Data Missing Ratio | MAE($\boldsymbol{R}$) $\downarrow$ | R2($\boldsymbol{R}$) $\uparrow$ | MAE($\boldsymbol{t}$) $\downarrow$ | R2($\boldsymbol{t}$) $\uparrow$
---|---|---|---|---
75% | 6.447 | 0.028 | 0.042 | 0.921
50% | 3.939 | 0.623 | 0.0288 | 0.969
25% | 1.454 | 0.939 | 0.010 | 0.997

(e) Data missing ratio.

Discount Factor $\lambda$ | MAE($\boldsymbol{R}$) $\downarrow$ | R2($\boldsymbol{R}$) $\uparrow$ | MAE($\boldsymbol{t}$) $\downarrow$ | R2($\boldsymbol{t}$) $\uparrow$
---|---|---|---|---
0.5 | 1.921 | 0.917 | 0.014 | 0.995
0.7 | 1.998 | 0.884 | 0.014 | 0.995
0.9 | 1.454 | 0.939 | 0.010 | 0.997
0.99 | 1.732 | 0.915 | 0.012 | 0.996

(c) Different discount factors ($\lambda$).

Data Noise | MAE($\boldsymbol{R}$) $\downarrow$ | R2($\boldsymbol{R}$) $\uparrow$ | MAE($\boldsymbol{t}$) $\downarrow$ | R2($\boldsymbol{t}$) $\uparrow$
---|---|---|---|---
$\mathcal{N}(0,0.01^{2})$ | 2.051 | 0.889 | 0.012 | 0.995
$\mathcal{N}(0,0.1^{2})$ | 5.013 | 0.617 | 0.020 | 0.991
$\mathcal{N}(0,0.5^{2})$ | 21.129 | -2.830 | 0.064 | 0.917

(f) Data noise.

Table 6: Ablation studies.

#### Keypoint detection alternatives, experiments on full point clouds,
effects of discount factor, choice of $k$, robustness to data missing ratio,
robustness to data noise.

To understand the effectiveness of each part, we conduct additional
experiments in Table 6; to save space, we only show MAE and R2. (a) First, we
consider alternatives to keypoint selection: in the first alternative, the two
sets of keypoints are chosen independently and randomly on the two surfaces
($\mathcal{X}$ and $\mathcal{Y}$); in the second alternative, we use
_centrality_ to choose keypoints, keeping the $k$ points whose average
distance (in feature space) to the rest in the point cloud is minimal.
Empirically, the $L^{2}$ norm used in our pipeline to select keypoints
outperforms others. (b) Second, we compare our method to others on full point
clouds. In this experiment, 768 points are sampled from each point cloud to
cover the full shape using farthest-point sampling. In the full point cloud
setting, PRNet still outperforms others. (c) Third, we verify our choice of
discount factor $\lambda$; small large discount factors encourage alignment
within the first few passes through PRNet while large discount factors promote
longer-term return. (d) Fourth, we test the choice of number of keypoints: the
model achieves surprisingly good performance even with 64 keypoints, but
performance drops significantly when $k<32$. (e) Fifth, we test its robustness
to missing data. The missing data ratio in original partial-to-partial
experiment is 25%; we further test with 50% and 75%. This test shows that with
75% points missing, the method still achieves reasonable performance, even
compared to other methods tested with only 25% points missing. (f) Finally, we
test the model robustness to noise level. Noise is sampled from
$\mathcal{N}(0,\sigma^{2})$. The model is trained with $\sigma=0.01$ and
tested with $\sigma\in[0.01,0.1,0.5]$. Even with $\sigma=0.1$, the model still
performs reasonably well.

# points | ICP | Go-ICP | FGR | PointNetLK | DCP | PRNet
---|---|---|---|---|---|---
512 | 0.134 | 14.763 | 0.230 | 0.049 | 0.014 | 0.042
1024 | 0.170 | 14.853 | 0.250 | 0.061 | 0.024 | 0.073
2048 | 0.242 | 14.929 | 0.248 | 0.069 | 0.058 | 0.152

Table 7: Inference time (in seconds).

#### Efficiency.

We benchmark the inference time of different methods on a desktop computer
with an Intel 16-core CPU, an Nvidia GTX 1080 Ti GPU, and 128G memory. Table 7
shows learning based methods (on GPUs) are faster than non-learning based
counterparts (on CPUs). PRNet is on a par with PointNetLK while being slower
than DCP.

#### More figures of keypoints and correspondences.

In Figure 7 and Figure 8, we show more visualizations of keypoints and
correspondences for different pairs of objects.

Figure 7: Keypoint detection for different pairs of objects.  Figure 8:
Correspondence prediction for different pairs of objects.


# A HIGHLY ROBUST SPARSE FRACTAL ARRAY

Kretika Goel
Research Scholar
SENSE
IIT Delhi
<EMAIL_ADDRESS>
&Monika Aggarwal
Professor
CARE
IIT DELHI
<EMAIL_ADDRESS>
&Subrat Kar
Professor
Dept of Electrical Engg
IIT Delhi
<EMAIL_ADDRESS>

###### Abstract

The term fractal refers to the fractional dimensions that have recursive
nature and exhibit better array factor properties. In this article, we present
a new class of sparse array where the recursive nature of a fractal can be
used in designing an antenna array called a sparse fractal array by combining
sparsity properties of the various sparse array and the recursive nature of
fractal array. The most important property of the proposed array is the hole-
free difference coarray which makes it a good choice for DOA estimation as
various algorithms like coarray MUSIC etc demand hole-free difference coarray.
But the performance of any array depends on the presence of essential and
nonessential sensors in it which governs whether the difference coarray will
get affected upon sensor failure or not. Hence, in this paper, a rigorous
analysis is done for various combinations of sparse fractal arrays to test
their robustness in presence of a faulty sensor environment.

_K_ eywords Sparse array $\cdot$ fractal array $\cdot$ essential sensors
$\cdot$ fragility $\cdot$ robustness

##  1 Introduction

Sparse arrays have attracted considerable attention in various fields such as
radar, array signal processing [1], beamforming, the direction of arrival
estimation [2], ultrasound imaging, 5G communications [3], etc. The important
property of sparse arrays i.e. these are the sensor arrays with nonuniform
element spacing enables them to resolve more sources than the available
physical sensors. This property of sparse arrays arises from the virtual
counterpart of the physical array i.e. called a difference coarray which is
the pair-wise difference of each sensor location in the physical array. The
higher the size of the contiguous region of the difference coarray, the more
can be the degree of freedom [4].

Various types of 1D sparse arrays coined so far include minimum redundancy
arrays (MRA) [5], minimum holes arrays (MHA) [6], nested arrays (NA) [7] and
coprime arrays (CP) [8],[9], CADIS [10], CACIS [11], Augmented nested array
[12], super nested array [13], etc leading to numerous studies proposing
diverse sparse configuration. The importance of all these arrays is the
increased size of their virtual coarray which makes the DOF of all of them of
the order of O(N2) which is high enough as compared to ULA which has DOF O(N)
where N is the number of sources present in a physical array. Hence, it can be
inferred that the larger the size of the virtual coarray, the more the number
of resolvable sources and the better the resolution of the array. Hence, array
designing is of prime importance in signal processing because the size of
uniform difference coarray is an important metric in achieving better array
performance.

In some implementations, arrays with symmetric geometry are highly preferred
because they not only ease the computational complexity but also improve the
DOA estimation performance [14]. Moreover such symmetric and recursive
geometries also facilitate the array calibration in presence of mutual
coupling [15]. Hence, In this paper, we consider one such symmetric array as a
Fractal array. The introduction of various sparse arrays has sparked great
interest in non-uniform arrays, leading to numerous studies. The performance
of an antenna array can further be improved by another class of array
designing i.e by using fractal geometric techniques. The term fractal, which
means irregular fragments, was originally coined by Mandelbrot [16] which has
contributed a lot to the new and rapidly growing field of research as fractal
antenna engineering which includes the study of fractal-shaped antenna
elements, as well as the use of fractals in antenna arrays.

A wide variety of applications of fractal arrays has been found in fractal
electrodynamics [17], in which fractal geometry is combined with
electromagnetic theory for the analysis and design of antenna systems. Fractal
arrays are recursive arrays that can be formed through the repetitive
application of a generating subarray. A generating subarray is a small array
at scale one ( P = 1 ) which is used to build larger arrays at higher scales
(i.e., P > 1 ). Generating subarray has elements that are turned on and off in
a certain pattern. Followed by copying, scaling, and translation to produce
the fractal array which can otherwise be considered as a sequence of self-
similar subarrays.

Fractal arrays are of two types: deterministic and natural fractal structures
[18] where Deterministic fractal structures are the geometric structures that
have exact dimensions for the expansion. Another type is Random Fractals which
are distinguished by the crudest measure of size, which is dimension. All the
fractals found in nature are random fractals like mountains, coastal lines,
and fractal-shaped flowers. The advantage of using fractal antenna array (FA)
is that it improves multi-beam, and multi-band characteristics and also
improves array factor behavior. One such example of a Fractal Array is A
Cantor array is used for DOA estimation [19]. A Cantor array is a recursively
generated Array whose difference coarray is hole-free, has a large aperture
length, is symmetric, and has a maximal economy. Since resolving more
uncorrelated sources using fewer elements is mitigated by Sparse Array by
providing a much larger aperture virtual array that resolves more sources.
Hence to combine the properties of sparse arrays and fractal arrays [20],[21]
a novel sparse fractal array is proposed in this paper which combines these
arrays to attain all the properties like extended aperture, high DOF,
symmetry, recursiveness, and hole-free virtual coarray, robustness, and array
economy.

Sparse arrays are very valuable in terms of cost reduction and effective
performance with limited sensors and reduced cost. The array geometry plays
important role in the direction of arrival estimation of the sources falling
on the array. Hence it should be robust enough to the faulty sensor
environment. Faulty sensors change the pattern of difference coarray which
leads to failure of coarray MUSIC which is applied to estimate the DOA of the
sources falling on the antenna array. In general, sensors could fail randomly
and may cause the breakdown of the overall system. It is sometimes observed
that, for some sparse arrays, such as MRA, sensor failure could shrink the ULA
segment in the different coarray which leads to degradation in the performance
of the system. According to the literature, the issue of sensor failure can be
addressed in two ways [22]. Firstly by developing new algorithms which make
the system self-calibrate at times of sensor failure. Secondly by analyzing
array geometries in the presence of a faulty sensor environment and then
designing the system in such a way that the cost of system designing is
governed by the presence of essential and inessential sensors in it [23]. In
the literature, the validation of the first method is found in [24] where DOA
estimation is carried out based on a minimal resource allocation network, and
in [25] array is diagnosed based on Bayesian compressive sensing. However,
these papers do not fully exploit the interplay between the array
configuration and the exact condition under which these algorithms are
applicable. To study the second method various measures are proposed in [26]
to quantify the robustness of arrays. In [27] beampattern is studied based on
the given sensor failure probability. But the impact of faulty sensors on the
difference coarray especially for the sparse arrays still needs to be
investigated. This paper tries to do so by examining the proposed sparse
fractal arrays in a faulty sensor environment and then compares the results
with the already existing most common sparse arrays.

##  2 ARRAY DATA MODEL

Figure 1:  Array with m Elements

Let M narrowband, uncorrelated, and far-field real sources with wavelength
$\lambda$ impinge on the 1D antenna array whose elements are located at
n$\lambda$/d where n $\in$ L and d is the inter element spacing between the
elements as shown in fig.1

The $i^{th}$ source with azimuth angle $\theta$ impinge on the array from the
direction {($\theta_{1}$) ,($\theta_{2}$),($\theta_{3}$ ) $\cdots$
($\theta_{M}$ )} where $\theta_{i}$ $\in$ $[-\pi/2,\pi/2]$

The array output at the time ’t’ can be expressed as:

$Y(t)=\sum_{i=1}^{M}A(\theta_{i}^{{}^{\prime}}).S_{i}(t)+N(t)$ (1)

where $\theta_{i}^{{}^{\prime}}$ are normalized DOA such that
$\theta_{i}^{{}^{\prime}}$ = (d/ $\lambda$)sin( $\theta_{i}$) and
d=$\lambda/2$ is the inter sensor spacing. Each element of the steering vector
$A(\theta_{i}^{{}^{\prime}})=[a(\theta_{1}),\cdots,a(\theta_{M}]$
corresponding to the sensors at the location $n\lambda/d$ where $n\in L$. And
is defined as $e^{2\pi j\cdot sin(\theta_{i}^{{}^{\prime}}}$ . Signal
$S_{i}(t)=[s_{1}(t),\cdots,s_{M}(t)]^{T}]$ is the source signal vector and
N(t) is the white Gaussian noise vector with zero mean and variance
$\sigma^{2}$. t = 1, 2, • • •, T refers to the sampling time, where T is the
total number of snapshots.

The covariance matrix of Y(t) can be written as:

$R=E[Y(t)\cdot Y(t)^{H}]=\sum_{i=1}^{M}\sigma_{i}^{2}\cdot
A(\theta_{i}^{{}^{\prime}})\cdot A^{H}(\theta_{i}^{{}^{\prime}})+\sigma^{2}I$
(2)

where $\sigma_{i}^{2}$ is the $i^{th}$ source power and $\sigma^{2}$ is the
noise power.

Note that the entity $A(\theta_{i}^{{}^{\prime}})\cdot
A^{H}(\theta_{i}^{{}^{\prime}})$ in the covariance matrix defined in eq.2 is
of the form $e^{2\pi(\theta^{{}^{\prime}})(s_{i}-s_{j})}$ where
$(s_{i}-s_{j})$ $\in$ D i.e the difference coarray having $(s_{i}-s_{j})$ as
the difference between $i^{th}$ and $j^{th}$ sensor location.

Applying vectorization operation on eq.2 and reshaping it to get the
autocorrelation vector defined on the difference coarray we get,

$Y_{d}(t)=\sum_{i=1}^{M}\sigma_{i}^{2}\cdot
A_{D}(\theta_{i}^{{}^{\prime}})+\sigma^{2}I^{{}^{\prime}}$ (3)

where $I^{{}^{\prime}}=[E^{T}_{1}E^{T}_{2}\cdot E^{T}_{N}]^{T}$ with $E_{i}$
being a column vector of all zeros except value 1 at the $i^{th}$ position.
The auto-correlation vector $Y_{d}$, can be considered as sensor output on the
difference coarray D. If D contains a contiguous ULA segment $D_{U}$, then DOA
can be estimated via coarray MUSIC on the autocorrelation evaluated at $D_{U}$
which ensures that coarray MUSIC can resolve $O(|L^{2}|)$ uncorrelated sources
using $|L|$ physical sensors thereby enhancing the degree of freedom.

Sparse arrays are designed so that the difference-coarray D contains a ULA
part around the origin, which is denoted by $D_{U}$. Based on the relationship
between D and $D_{U}$, the signal over $D_{U}$ is then constructed as follows:

$Y_{d_{U}}(t)=\sum_{i=1}^{M}\sigma_{i}^{2}\cdot
A_{D_{U}}(\theta_{i}^{{}^{\prime}})+\sigma^{2}I^{{}^{\prime}}$ (4)

Doa estimation using finite snapshots can be carried out by calculating the
finite snapshot version of Y(t),$Y_{d}(t)$, $Y_{d_{U}}(t)$ and R as
$Y^{\prime}(k)$ ,$Y^{\prime}_{d}(k)$, $Y^{\prime}_{d_{U}}(k)$ and $R^{\prime}$
respectively where $k=1,2,3.....K$ be K realizations of eq.1. K is the total
number of snapshots. The covariance matrix for which can be estimated as
$R^{\prime}=\sum_{k=1}^{K}Y^{\prime}(k).Y^{\prime}(k)^{H}/K$ . From R’ finite
snapshot autocorrelation vector on $D_{U}$ can be formulated as
$Y^{\prime}_{d_{U}}(k)$. Moreover, for sparse array, the covariance matrix R
is not hermitian Toeplitz in general but for coarray, we can construct a
hermitian Toeplitz matrix by the method explained in [28].

Now partitioning the signal subspace and noise subspace of this matrix and
then applying coarray MUSIC to it will give the desired spectrum of the signal
which helps in DOA estimation.

##  3 PROPOSED SPARSE FRACTAL ANTENNA ARRAY

First explaining the basic Cantor arrays [6] which are the fractal arrays that
can be defined recursively as :

$C_{r+1}=C_{r}U(C_{r}+3^{r})where,r\in N$ (5)

Note that the cantor array definition is followed from [2] which states that
the basic Cantor arrays are symmetric and Cr has N = 2r physical elements. Let
C =[0,1] then Cr will have hole-free difference coarray Dr with an aperture as
3r. Its difference coarray is of the order $O(Nlog_{2}3)\equiv O(N1.585)$
which results in degraded performance when compared to sparse arrays whose
difference coarray satisfies O(N2) property. To overcome this limitation of a
fractal array we propose a new architecture in which the Cantor array is mixed
with the sparse array that will generate an array with increased DOF and
reduced RMSE thus showing better performance over other arrays.

######  Definition 3.1 (Proposed 1D SFA).

The proposed SFA(sparse fractal array ) consists of two sub-arrays, i.e. sub-
array 1 and sub-array 2. Let Sub-array 1 is an M elements sparse array and
lets sub-array 2 be an N elements Fractal array, which is created from Cantor
set. The element position of in subarray 1 and subarray2 is defined by the
$\widetilde{S_{1}}$ and $\widetilde{S_{2}}$ where

$\widetilde{S_{1}}=[m1,m2,.....M]d1,m1=1$ (6)
$\widetilde{S_{2}}=[n1,n2,......N]d2,n1=0$ (7)

Where m and n are integers and d1 and d2 are inter-element spacing such that
d2 = (2M +1)d1. And the proposed array will be denoted as:

$\widetilde{S}=\widetilde{S_{1}}\oplus\widetilde{S_{2}}$ (8)

Where element position of proposed SFA is expressed by the cross summation
$\oplus$ defined over $\widetilde{S_{1}}$ and $\widetilde{S_{2}}$ and the SFA
will have MN elements.

Example 1: Let subarray 1 be nested array whose sensor location for M=6 is
defined in the set $\widetilde{S_{1}}$. Let d1=1 so the normalized sensor
positions in the first subarray are given as : $\widetilde{S_{1}}$ = [1 2 3 4
8 12]. For constructing $\widetilde{S_{2}}$ we will use the basic Fractal
array (FA) =0,1 in the paper. Now $\widetilde{S_{2}}$ = [0 1]d2 where d2 =
(2mM +1)d1 =(2*6 +1)d1=13d1 $\widetilde{S_{2}}$ =[0 13]d1 Using the above
relation $\widetilde{S_{1DSFA}}$ = $\widetilde{S_{1}}$ $\oplus$
$\widetilde{S_{2}}$ we get, $\widetilde{S}$=[1 2 3 4 8 12 14 15 16 17 21 25]

######  Definition 3.2 (Difference coarray of the proposed SFA).

The difference coarray $\widetilde{D}$ for an array $\widetilde{S}$ is defined
as the set of differences between the sensor locations given in set
$\widetilde{S}$. $\widetilde{D}$ = {n1-n2 : n1,n2 $\in$ $\widetilde{S}$ } Let
$\widetilde{D_{u}}$ represent the contiguous range of the sensors in the
difference coarray $\widetilde{D}$ which is hole free and the most useful when
comes to the application of estimation algorithms. The virtual sensor
positions in the difference coarray are also called lags and for case1 the
virtual aperture of the proposed SFA extends from -24 to 24. In the given
example $\widetilde{D_{u}}$ also lies in the range -24 to 24 as there are no
holes present in the difference coarray of the proposed SFA. Therefore all
information on the difference coarray can be exploited. Fig.2 shows the
physical array of the proposed SFA and its different coarray .

######  Definition 3.3 (Weights Function of the proposed SFA).

The weight function w ( k ) can be understood as the number of sensor pairs
with separation $k\in Z$ where Z is an integer. This can also be written as w
(k ) = $|(n1,n2)\in L^{2}:n1-n2=k|$. By definition, w ( k ) is an integer-
valued even function, i.e. w (-k ) = w (k ) . Designing any sparse array
requires the optimal utilization of the difference between coarray D and the
weight function w ( k). For example, both the MRA and the MHA have different
coarrays of size $O(N^{2})$ but the problem in MRA is that it has no close
form expression hence the work in [29] and [30] lacks the closed form
expression to deal with sparse and fractal array as the sparse arrays which
have closed-form expressions for the sensor locations are simple to compute
like nested array, coprime array, generalized coprime array, and super nested
array, etc. Hence, we make use of all such sparse arrays whose closed-form
expression exists which can be used for designing sparse fractal arrays.
Hence, we make use of all such sparse arrays whose closed-form expression
exists which can be used for designing sparse fractal arrays.

##  4 NUMERICAL EXAMPLES

While designing any array configurations we need to select the basic arrays
which fulfill some laid down criteria according to literature first among them
is that the sensor locations should be expressed in closed-form. Secondly, the
difference coarray of the basic array should be hole free because the
estimation performance of various DOA estimation methods, e.g., MUSIC and
ESPRIT depends on the cardinality of the central ULA segment of the difference
coarray. Hence, for the proper estimation of the number of sources hole free
difference coarray is required. Thirdly, the difference coarray should be
large enough to achieve increased DOF concerning the number of sensors. So
keeping all such criteria in mind various configurations of sparse fractal
arrays have been tried and tested using the basic arrays as a nested array,
coprime array, Augmented nested arrays, and super nested arrays which are
expressed one by one.

### 1.

[Nested Fractal array ( NFA)]

A two level nested array consists of two uniform linear arrays called inner
and outer uniform linear arrays where the inner ULA has N1 elements with
spacing d1 and the outer ULA has N2 elements with spacing d2 such that d2=(N1
+ 1)d1. Sensors locations of the physical array is given by
$\\{md1,(m=1,2,3\cdots N1)\cup nd2,(n=1,2,3\cdots N2)\\}$ where if N is even
then N1=N2=N/2 and if N is odd then N1=(N-1)/2; N2=(N+1)/2. Using the basic
sparse array as a nested array for N=6 and taking the cross sum with the basic
fractal array i.e. [0 1] as defined in example 1 we obtain the NFA as shown in
Fig along with its difference coarray which has no holes present in it. The
central ULA segment of the difference coarray of the proposed NFA is
$\widetilde{D_{u}}$ hence it can resolve up to $|(\widetilde{D_{u}}-1)/2|$
number of sources . Hence, with 6 physical sensor and $|\widetilde{D_{u}}|$ =
49 , it can estimate maximum of 24 sources. Therefore to check the
effectiveness let us assume 24 uncorrelated sources falling on the RCPA whose
normalized DOA are picked up randomly from $\theta$ = [- 0.5, 0.5] . Let SNR
=0 dB and snapshots be 500. Applying MUSIC on the finite snapshot version of
the above model, we get the following results as shown in Fig.2 with 0.0014
RMSE achieved.

Figure 2: (a) Physical and Virtual array of NFA,(b) normalized MUSIC Spectrum
of 24 signals applied on it for doa estimation along with RMSE.

### 2.

[Coprime Fractal Array(CFA)] According to the proposed method let subarray 1
be conventional coprime array whose sensor location for coprime pair M=2 and
N=3 and total number of elements as $2M+N-1=6$ is defined in the set
$\widetilde{S_{1}}$ . Let d1=1 so the normalized sensor positions in the first
subarray is given as : $\widetilde{S_{1}}$ = [0 2 3 4 6 9]. For constructing
$\widetilde{S_{2}}$ we will use the basic Fractal array (FA) = [0,1] in the
paper. Now $\widetilde{S_{2}}$ = [0 1]d2, Where d2 = (2mM +1)d1 =(2*6
+1)d1=13d1 $\widetilde{S_{2}}$ =[0 13]d1. Using the above relation
$\widetilde{S_{1DSFA}}$ = $\widetilde{S_{1}}$ $\oplus$ $\widetilde{S_{2}}$ we
get, $\widetilde{S}$=[ 0 2 3 4 6 9 13 15 16 17 19 22] and the virtual aperture
of the proposed CFA extends from -24 to 24 . In the given example
$\widetilde{D_{u}}$ also lies in the range -22 to 22 also there are no holes
present in the difference coarray of the proposed CFA. Let 22 uncorrelated
sources fall on the CFA whose normalized DOA are picked up randomly from
$\theta$ = [-0.5, 0.5]. Let SNR =0 dB and snapshots be 500. Applying MUSIC on
the finite snapshot version of the above model, we get the following results
as shown in Fig.3 with 0.0027 RMSE achieved.

Figure 3: (a) Physical and Virtual array of CFA,(b) normalized MUSIC Spectrum
of 22 signals applied on it for doa estimation along with RMSE.

### 3.

[Augmented GenI Fractal Array(AUGGENIFA)]

An augmented nested array or ACA was formed by first splitting the dense
subarray of the nested array into various parts, which is further rearranged
in a particular manner at the sides of the sparse subarray. Using this
concept, an augmented nested array (ANA) was designed by splitting the dense
ULA of the nested array into a few left/right sub-arrays which are then
arranged on either side of the low element density subarray of the nested
array. According to the proposed method let subarray 1 be AUGGENI for N=6 a
whose sensor location is defined in the set $\widetilde{S_{1}}$ . Let d1=1 so
the normalized sensor positions in the first subarray is given as :
$\widetilde{S_{1}}$ = [1 4 8 12 13 14]. For constructing $\widetilde{S_{2}}$
we will use the basic Fractal array (FA) = [0,1] we get, $\widetilde{S}$=[ 1 4
8 12 13 14 17 21 25 26 27], and the difference coarray of the proposed
AUGGENIFA extends from -26 to 26 which means that it can estimate a maximum of
26 sources. For checking the array we take the maximum possible sources i.e.
26 uncorrelated sources falling on the AUGGENIFA whose normalized DOA are
picked up randomly from $\theta$ = [-0.5, 0.5]. Let SNR =0 dB and snapshots be
500. Applying MUSIC on the finite snapshot version of the above model, we get
the following results as shown in Fig.4 with 0.00156 RMSE achieved.

Figure 4: (a) Physical and Virtual array of AUGGENIFA,(b) normalized MUSIC
Spectrum of 26 signals applied on it for doa estimation along with RMSE.

### 4.

[Augmented GenII Fractal Array(AUGGENIIFA)]

Another type of augmented nested array is ANAGENII which is formed by
splitting the dense sub-array of the actual nested array into odd and even
parts, respectively, and then arranging it on either side of the less dense
subarray of the nested array. For N=6, AUGGENII will have the sensor locations
at $\widetilde{S_{1}}$ = [1 2 4 8 12 13] and by using basic Fractal array (FA)
= [0,1] we get we get, $\widetilde{S}$=[ 1 2 4 8 12 13 14 15 17 21 25 26] .
For checking the array we take the maximum possible sources i.e. 26
uncorrelated sources falling on the AUGGENIFA whose normalized DOA are picked
up randomly from $\theta$ = [- 0.5, 0.5]. Let SNR =0 dB and snapshots be 500.
Applying MUSIC on the finite snapshot version of the above model, we get the
following results as shown in Fig.5 with 0.00127 RMSE achieved.

Figure 5: (a) Physical and Virtual array of AUGGENIIFA,(b) normalized MUSIC
Spectrum of 26 signals applied on it for doa estimation along with RMSE.

### 5.

[Super Nested Fractal Array (SNFA)]

Super nested arrays have the same number of sensors, and the same difference
coarray as nested arrays but the arrangement of sensors in a unique manner
leads to reduced mutual coupling than nested arrays. For N=6, Super nested
arrays will have the sensor locations at $\widetilde{S_{1}}$ = [1 1 3 6 8 11
12] and by using basic Fractal array (FA) = [0,1] we get we get SNFA as
$\widetilde{S}$=[ 1 3 6 8 11 12 14 16 19 21 24 25] . For checking the
validation of the proposed array we take the maximum possible sources i.e. 25
uncorrelated sources falling on the SNFA whose normalized DOA are picked up
randomly from $\theta$ = [- 0.5, 0.5]. Let SNR =0 dB and snapshots be 500.
Applying MUSIC on the finite snapshot version of the above model, we get the
following results as shown in Fig. 6 with 0.00174 RMSE achieved.

Figure 6: (a) Physical and Virtual array of Supernested Fractal Array,(b)
normalized MUSIC Spectrum of 25 signals applied on it for doa estimation along
with RMSE.

##  5 ROBUSTNESS OF SPARSE FRACTAL ARRAY TO SENSOR FAILURE

There is a well known theory according to literature that the larger the
difference in coarray, the less robust the array is. This can otherwise be
stated as given two arrays with the same physical number of elements and the
same difference coarray, one could be much more robust as compared to another.
Hence, it is necessary to design the sparse array in such a way that it
maintains a balance between the size and the robustness of the difference
coarray because when such an array is used for doa estimation then the
performance is affected both by the size of the different arrays and the
robustness properties.

######  Definition 5.1 (Essential Sensors).

A sensor in an array is said to be essential if its presence and absence makes
an effect on the structure of the different coarray. In other words, an
essential sensor as its name signifies is essential because its failure can
alter the difference coarray which means that it will no longer be hole free.
And the presence of holes in the difference coarray means it degrades the
performance of estimation algorithms and the array is said to be less robust.
The necessity to study the essentialness property of the sensors is that it
helps in system designing because the cost of sensors assignment truly depends
on their essential and inessential behavior. For example, let there be two
sensors with different costs and qualities. Let the first sensor is costly but
has a low failure probability and another sensor is less expensive but easily
fails. Therefore, to maintain a balance between the budget and the robustness
of an array, the first sensor can be used as an essential sensor, and another
sensor can be used as an inessential sensor while designing the array.

######  Definition 5.2 ( The fragility of a sensor array ).

The term fragility is the characteristic term that is used to define whether
the array is robust to sensor failure or not. It can be better stated in terms
of fragility i.e. an array is said to be more robust if it is less fragile and
vice versa. Hence, the fragility(F) varies from 0 to 1, where 0 means less
fragile and more robust and 1 means more fragile and less robust array. The
formula for calculating fragility is the number of essential sensors divided
by the total number of sensors in an array.

######  Definition 5.3 (The R-essentialness property of a sensor array).

The R-essentialness means that it is not always necessary that only one sensor
will fail at a time and only its failure will govern the robustness of an
array. There can be the possibility that R sensors can fail at a time hence
all possibilities need to be considered which define the robustness of an
array. All such R possibilities are called R-essentialness. A subarray
$\widetilde{Z}$ of $\widetilde{S}$ is said to be k -essential with respect to
an array $\widetilde{S}$ if it has the following properties. Firstly,
$\widetilde{Z}$ has size exactly R . Secondly, The difference coarray changes
when $\widetilde{Z}$ is removed from $\widetilde{S}$ . Note that the R
-essentialness is an attribute of a subarray $\widetilde{Z}$ of
$\widetilde{S}$ and the fragility for all such subarrays will be called
R-Fragility i.e. if two sensors fail at a time then it is 2-essentialness with
2-Fragility defining the robustness of an array.

Fig.7 explains the concept of essential and inessential sensors i.e the
sensors at $\\{0,2,4,9,17,22\\}$ are essential sensors because the removal of
them alters the difference coarray while the sensors at
$\\{3,6,13,15,16,19\\}$ are inessential sensors as there removal does not
alter the original difference coarray of proposed CFA. Hence the total number
of essential sensors in CFA are 6 which calculates fragility $F_{1}=0.5$ which
satisfy $0\leq F\leq 1$.Hence, the proposed fractal design is robust to sensor
failure.

Figure 7:  (a) The original array and its difference coarray of Proposed
Coprime Fractal Array. The array configurations and the difference coarrays
after the deletion of (b) the sensor at 0, (c) the sensor at 2, (d) the sensor
at 3, or (e) the sensor at 4,(f) the sensor at 6, (g) the sensor at 9, or (h)
the sensor at 13,(i) the sensor at 15, (j) the sensor at 16, or (k) the sensor
at 17,(l) the sensor at 19, (m) the sensor at 22 from the original array in
(a). Here the sensors are denoted by red dots and empty space resembles holes.

##  6  SIMULATION RESULTS

To study the robustness of proposed sparse fractal arrays we consider 1 sensor
failure called 1-essentialness, 2 sensor failures called 2-essentialness, and
3 sensor failures at a time as 3-essentialness respectively whose fragility is
also calculated as F1, F2, and F3 respectively. The cumulative results are
shown in the table but due to space limitation we will only show
1-essentialness results in the table but all F are shown in the Table.1 which
will be used for further comparisons.

Table 1: Robustness Analysis of Proposed Sparse Fractal Array S.No. |  Proposed Sparse Fractal Arrays with 12 physical sensors. |  1-Essentialness |  Fragility
---|---|---|---
1 |  Nested fractal Array |  {1,2,3,4,17,21,25} |  F1=0.5833 F2=0.8788 F3=0.9909
2 |  Coprime Fractal array |  {0,2,4,9,17,22} |  F1=0.5000 F2=0.8182 F3=0.9727
3 |  AUGGENI Fractal Array |  {1,4,8,12,17,21,25,26,27} |  F1=0.8182 F2=1
4 |  AUGGENII Fractal Array |  {1,2 ,3,4,17,21,25} |  F1=0.5833 F2=0.8788 F3=0.9909
5 |  Super Nested Fractal Array |  {1,3,6,8,11,12,21,24,25} |  F1=0.7500 F2=1

After plotting these results of fragility F1 with respect to normalized
difference coarray which is obtained by the relation and comparing it with
some already existing sparse arrays we get Fig. which shows that out of all
proposed fractal arrays coprime fractal array is found to be more robust and
very less fragile whereas already existing MRA, MHA, and nested array has F=1
which means they are least robust to sensor failure.

Figure 8:  Robustness analysis for all proposed arrays for F=1 with 12
physical sensors in each sparse fractal array

Fig shows the R fragility of several array configurations with 12 physical
sensors and taking 1-essentialness, 2-essentialness, and 3-essentialness with
respect to F1, F2, and F3 we found that It can be observed that the ULA is the
most robust array since it has the smallest F for all R. The nested array and
the super nested array are least robust as $(F_{R}=1forall1\leq R\leq|S|)$ The
prototype coprime array, Proposed NFA, CFA, AUGGENII, AUGGENI are less robust
than the ULA but more robust than the nested array and the SNFA.

Figure 9:  The R-fragility of several array configurations with 12 physical
sensors

##  7 CONCLUDING REMARKS

In this paper, we have proposed various sparse fractal array configurations
and have generated the hole-free difference coarray which is crucial for the
functionality of coarray MUSIC and other estimation algorithms. Further, we
have studied the robustness of proposed arrays to sensor failure by taking
various combinations of sensor failure on the proposed arrays. It helps to
study the behavior of the probability that the difference coarray changes when
the particular sensor fails. Hence, the essentialness property of the sensors
in an array forms the basis for analyzing the robustness of sparse arrays. In
the future, it is of considerable interest to design 2D sparse fractal arrays
and study the robustness of arrays.

## ACKNOWLEDGMENT

The authors would like to thank the Center for Sensors, Instrumentation and
Cyber-physical Systems Engg (SENSE), Center for Applied Research in
Electronics (CARE) and the Department of Electrical Engineering, Indian
Institute of Technology Delhi (IIT Delhi) for the facilities used in this
research.

## References

  * [1] Jim Partan, Jim Kurose, and Brian Neil Levine.  A survey of practical issues in underwater networks.  ACM SIGMOBILE Mobile Computing and Communications Review, 11(4):23–33, 2007.
  * [2] John Heidemann, Wei Ye, Jack Wills, Affan Syed, and Yuan Li.  Research challenges and applications for underwater sensor networking.  In IEEE Wireless Communications and Networking Conference, 2006. WCNC 2006., volume 1, pages 228–235. IEEE, 2006.
  * [3] Guoqiang Mao, Barış Fidan, and Brian DO Anderson.  Wireless sensor network localization techniques.  Computer networks, 51(10):2529–2553, 2007.
  * [4] Minglei Yangg, Alexander M Haimovich, Baixiao Chen, and Xin Yuan.  A new array geometry for doa estimation with enhanced degrees of freedom.  In 2016 IEEE international conference on acoustics, speech and signal processing (ICASSP), pages 3041–3045. IEEE, 2016.
  * [5] Geng Wang, Minghao He, Chunlai Yu, Jun Han, and Changxiao Chen.  Fast underdetermined doa estimation based on generalized mra via original covariance vector sparse reconstruction.  IEEE Access, 9:66805–66815, 2021.
  * [6] Guodong Qin, Moeness G Amin, and Yimin D Zhang.  Doa estimation exploiting sparse array motions.  IEEE Transactions on Signal Processing, 67(11):3013–3027, 2019\.
  * [7] Piya Pal and Palghat P Vaidyanathan.  Nested arrays: A novel approach to array processing with enhanced degrees of freedom.  IEEE Transactions on Signal Processing, 58(8):4167–4181, 2010.
  * [8] Chun-Lin Liu, PP Vaidyanathan, and Piya Pal.  Coprime coarray interpolation for doa estimation via nuclear norm minimization.  In 2016 IEEE International Symposium on Circuits and Systems (ISCAS), pages 2639–2642. IEEE, 2016.
  * [9] PP Vaidyanathan and Piya Pal.  Sparse sensing with coprime arrays.  In 2010 Conference record of the forty fourth Asilomar conference on signals, systems and computers, pages 1405–1409. IEEE, 2010.
  * [10] Saeed M Alamoudi, Mohammed A Aldhaheri, Saleh A Alawsh, and Ali H Muqaibel.  Sparse doa estimation based on a shifted coprime array configuration.  In 2016 16th Mediterranean Microwave Symposium (MMS), pages 1–4. IEEE, 2016.
  * [11] Bo-lin Cheng, Ming-wei Li, Ming-yue Feng, and Xiao-jie Tang.  Doa estimation on cacis-type array based on fast-rvm algorithm.  In 2019 6th International Conference on Systems and Informatics (ICSAI), pages 1577–1582. IEEE, 2019.
  * [12] Penghui Ma, Jianfeng Li, Fan Xu, and Xiaofei Zhang.  Hole-free coprime array for doa estimation: Augmented uniform co-array.  IEEE Signal Processing Letters, 28:36–40, 2020.
  * [13] Chun-Lin Liu and PP Vaidyanathan.  Super nested arrays: Sparse arrays with less mutual coupling than nested arrays.  In 2016 IEEE International Conference on Acoustics, Speech and signal processing (ICASSP), pages 2976–2980. IEEE, 2016.
  * [14] Fu Li, Hui Liu, and Richard J Vaccaro.  Performance analysis for doa estimation algorithms: unification, simplification, and observations.  IEEE Transactions on Aerospace and Electronic Systems, 29(4):1170–1184, 1993.
  * [15] Zhongfu Ye, Jisheng Dai, Xu Xu, and Xiaopei Wu.  Doa estimation for uniform linear array with mutual coupling.  IEEE Transactions on Aerospace and Electronic Systems, 45(1):280–288, 2009.
  * [16] Douglas H Werner, Randy L Haupt, and Pingjuan L Werner.  Fractal antenna engineering: The theory and design of fractal antenna arrays.  IEEE Antennas and propagation Magazine, 41(5):37–58, 1999.
  * [17] Dwight L Jaggard.  Fractal electrodynamics and modeling.  In Directions in electromagnetic wave modeling, pages 435–446. Springer, 1991.
  * [18] Chun-Lin Liu and PP Vaidyanathan.  Maximally economic sparse arrays and cantor arrays.  In 2017 IEEE 7th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP), pages 1–5. IEEE, 2017\.
  * [19] Zixiang Yang, Qing Shen, Wei Liu, Yonina C Eldar, and Wei Cui.  Extended cantor arrays with hole-free fourth-order difference co-arrays.  In 2021 IEEE International Symposium on Circuits and Systems (ISCAS), pages 1–5. IEEE, 2021.
  * [20] Regev Cohen and Yonina C Eldar.  Sparse array design via fractal geometries.  IEEE transactions on signal processing, 68:4797–4812, 2020.
  * [21] P Raiguru and RK Mishra.  Doa estimation on fractal-based array.  In Advances in Electrical Control and Signal Systems, pages 777–784. Springer, 2020.
  * [22] Chun-Lin Liu and Palghat P Vaidyanathan.  Robustness of difference coarrays of sparse arrays to sensor failures—part i: A theory motivated by coarray music.  IEEE Transactions on Signal Processing, 67(12):3213–3226, 2019\.
  * [23] Chun-Lin Liu and PP Vaidyanathan.  Robustness of coarrays of sparse arrays to sensor failures.  In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 3231–3235. IEEE, 2018.
  * [24] S Vigneshwaran, Narasimhan Sundararajan, and P Saratchandran.  Direction of arrival (doa) estimation under array sensor failures using a minimal resource allocation neural network.  IEEE Transactions on Antennas and Propagation, 55(2):334–343, 2007\.
  * [25] Chenglong Zhu, Wen-Qin Wang, Hui Chen, and Hing Cheung So.  Impaired sensor diagnosis, beamforming, and doa estimation with difference co-array processing.  IEEE Sensors Journal, 15(7):3773–3780, 2015.
  * [26] Angeliki Alexiou and Athanassios Manikas.  Investigation of array robustness to sensor failure.  Journal of the Franklin Institute, 342(3):255–272, 2005.
  * [27] Matteo Carlin, Giacomo Oliveri, and Andrea Massa.  On the robustness to element failures of linear ads-thinned arrays.  IEEE Transactions on Antennas and Propagation, 59(12):4849–4853, 2011.
  * [28] Chun-Lin Liu and PP Vaidyanathan.  Remarks on the spatial smoothing step in coarray music.  IEEE Signal Processing Letters, 22(9):1438–1442, 2015.
  * [29] Priyadarshini Raiguru and RK Mishra.  A new recursively generated array geometry for doa estimation.  In 2019 TEQIP III Sponsored International Conference on Microwave Integrated Circuits, Photonics and Wireless Networks (IMICPW), pages 167–169. IEEE, 2019.
  * [30] Regev Cohen and Yonina C Eldar.  Sparse fractal array design with increased degrees of freedom.  In ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 4195–4199. IEEE, 2019.