# Exploring Self-Attention for Visual Odometry

Hamed Damirchi  Rooholla Khorrambakht  Hamid D. Taghirad  Senior Member  IEEE
Faculty of Electrical and Computer Engineering
K. N. Toosi University of Technology
P.O. Box 16315-1355  Tehran  lran
hdamirchi<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Visual odometry networks commonly use pretrained optical flow networks in
order to derive the ego-motion between consecutive frames. The features
extracted by these networks represent the motion of all the pixels between
frames. However, due to the existence of dynamic objects and texture-less
surfaces in the scene, the motion information for every image region might not
be reliable for inferring odometry due to the ineffectiveness of dynamic
objects in derivation of the incremental changes in position. Recent works in
this area lack attention mechanisms in their structures to facilitate dynamic
reweighing of the feature maps for extracting more refined egomotion
information. In this paper, we explore the effectiveness of self-attention in
visual odometry. We report qualitative and quantitative results against the
SOTA methods. Furthermore, saliency-based studies alongside specially designed
experiments are utilized to investigate the effect of self-attention on VO.
Our experiments show that using self-attention allows for the extraction of
better features while achieving a better odometry performance compared to
networks that lack such structures.

##  1 Introduction

Figure 1: Saliency maps of the 7th sequence of the KITTI [4] dataset. The
difference between the two maps show that our method is able to reject the
features corresponding to moving objects while DeepVO [16] shows no reactions
to the presense of such artifacts.

Visual odometry (VO) refers to the task of deriving the incremental poses
between consecutive frames captured by a camera. Over the past decade, VO
algorithms have received attention from the robotics [3], and especially
autonomous driving [2, 10] research communities, where vision-based subsystems
have played a crucial role as localization pipelines. Classical approaches to
visual odometry rely on hand-crafted methods to extract features from
consecutive images. However, This process is not robust to real-world
artifacts such as intense illumination changes and near texture-less surfaces.
Moreover, the extracted features do not encode any semantic meanings that may
provide clues about motion patterns of objects and their reliability for VO.
Therefore, such classical methods fail when dynamic objects are present in the
scene or when the feature extraction methods fail to extract enough
distinctive descriptors for an adequate ego-motion estimation.

Deep learning has been proposed as a means to provide robust feature
extractors [12]. Convolutional neural networks (CNN) are pervasively used to
extract rich features from a single image or a stream of images in various
fields such as optical flow estimation [7], and next-frame prediction networks
[14]. Traditionally, CNNs utilize local convolutions in order to extract
features from different regions of the input. This locality means that they
are not able to globally manipulate the extracted features from one region at
every stage, based on the information derived from other areas of the same
image. In other words, CNNs lack structures that provide information about the
content of the image on a global scale rather than a local one. Hence, in the
case of VO networks, the local content at each stage may not reject the
unreliable features corresponding to dynamic objects that are present in the
image.

Self-attention [18] has been proposed as a non-local method that allows the
network to pool information from various regions of the input in order to
provide a means for the manipulation of the data at a local level. Hence,
self-attention layers allow each pixel to attend to all pixels regardless of
their position on the feature map. Such methods have been applied to
relocalization [15], yet, no rigorous exploration has been carried out to
investigate their efficacy and structural benefits for visual odometry. In
this paper, we explore the benefits of utilizing self-attention mechanisms in
VO networks by focusing on issues such as feature importance and moving
objects. We provide extensive visualizations to illustrate the ability of
attention based VO algorithms to consistently focus on salient features from
the images and reject dynamic objects as can be seen in Fig. 1. Self-attention
based VO, while requiring minimal architectural modifications and added
parameters, allows us to achieve higher accuracies in egomotion estimation
compared to attention-less SOTA networks. Moreover, Our comparisons point out
the lack of structure in the process of feature extraction capabilities of
attention-less networks. This paper is structured as follows. We provide a
brief overview of the current SOTA in VO and commonly used attention modules
in Section 2. We present our method in Section 3 and provide details of the
proposed architecture. Section 4 discusses the setting of our experiments
alongside implementation details, and in Section 5, we present the
quantitative and qualitative results alongside providing custom evaluations
that further elucidate the benefit of attention in VO. Our contributions are
as follows:

  * •

Provide quantitative analysis to show the boost in performance when using
self-attention in VO and compare our method against SOTA, VO methods that lack
attention mechanisms

  * •

Visualize the temporal frame-to-frame losses, directly, for attention-enabled
and attention-less methods when dynamic objects are present in the scene

  * •

Provide gradient-based analyses to qualitatively analyze the effect of self-
attention on the feature extraction capabilities of the network

  * •

Provide temporal analyses based on the semantic segmentation maps from the
input images to show the consistency of our method in attending to salient
features from various object categories

##  2 Related Work

In this section, we provide an overview of VO and localization methods
available in the literature and the various attention mechanisms used to
improve the performance of these pipelines. Algorithmically, localization may
be categorized into two broad approaches, odometry and relocalization.
Odometry focuses on deriving the incremental changes in position, while
relocalization is concerned with treating the global pose of inputs as a
regression problem. Unlike learning-based methods that capture the motion
model directly from data, classical methods utilize scene geometry and
iterative non-linear optimizers to perform odometry.

In classic visual odometry methods, a common assumption is that the world
around is static [22]. Furthermore, the simplifications considered in deriving
the camera models in classical methods and the lack of learning to compensate
for them limit the deployability of a large portion of classical methods. Such
pipelines deal with moving objects in the scene through outlier detection
methods and robust optimizers. As a different approach, multi-object tracking
may also be utilized to remove these objects from the images [19]. In this
paper, we propose an end-to-end method that is able to extract adequate
features while disregarding the information from moving objects without any
preprocessing or deliberate augmentations of data during training.

DeepVO [16] was the first learning-based visual odometry method that used a
CNN-LSTM approach and achieved competitive results against classical VO
methods. This work was later extended [17] to include uncertainty alongside
the pose outputs from the network. Neither of the mentioned methods modified
the CNN architecture and used a network pretrained on optical flow to extract
features from consecutive frames. In later sections, we show that compared to
this method, better performance is achieved by modifying the visual feature
extractor using attention layers. Moreover, due to the similarity of the base
structure of our network to [16], we are able to compare our attention-based
VO network directly against this SOTA attention-less network.

[15] proposes AtLoc, a relocalization system that uses attention mechanisms in
order to increase the performance of the relocalization pipelines. This work
shows that a trained attention-less network uses regions of the input that are
not suitable for performing relocalization. Instead, they focus on impermanent
foreground features rather than the background objects which should be the
main factor when inferring the global location of the input.

[20] proposes the adoption of external memory modules with VO pipelines and
introduces a pose refinement approach based on temporal attention layers in
order to rectify the pose features at different iterations of the algorithm.
In our approach, we propose the utilization of self-attention mechanisms to
refine the extracted motion features from the visual encoder of the network.

[9] proposes two attention-based VO methods. the first method utilizes a
segmentation network to provide semantic masks that weigh the different
regions of the image with the aid of an optical flow network. The second
proposed network in [9] uses squeeze-and-excite [6] attention blocks. In this
paper, we utilize spatial self-attention rather than channel-wise attention
while no auxiliary networks are used to provide attention over the feature
maps. Furthermore, we analyze the effectiveness of such attention mechanisms
in different scenarios and provide visualizations and in-depth analyses to
explain the necessity of spatial self-attention in the task of VO.

Figure 2: The overview of the proposed architecture.

##  3 Methodology

###  3.1 Overview

A general overview of the proposed architecture can be seen in Fig. 2. This
architecture follows a CNN-LSTM approach where the visual features
corresponding to the motion between two frames are captured by a CNN and
passed to a multi-layered LSTM for temporal modeling. To facilitate faster
convergence, we use the pretrained weights from an optical flow estimation
network [7] to initialize our visual encoder. This way, the network can extend
the input-output relationship formed to estimate the motion of pixels to
derive the poses between the input frames. Fig. 2 depicts the architecture of
this encoder where the input RGB images are stacked together to form a tensor
of size $6\times H\times W$ and passed through 10 stages of convolutional
layers to extract the necessary visual features.

Figure 3: Detailed structure of the self-attention block.

###  3.2 Self-Attention Block

The extracted features are then passed through the self-attention block, which
outputs feature maps with the same size as the inputs. Our implementation of
this block is based on [21] and is visualized in Fig. 3. The input to the
SABlock is first linearly projected to form three feature maps, named query,
key, and value, through independent weight matrices as follows:

$\mathbf{Q}=\mathbf{W}_{q}\mathbf{X},\mathbf{K}=\mathbf{W}_{k}\mathbf{X},\mathbf{V}=\mathbf{W}_{v}\mathbf{X}$
(1)

Where $\mathbf{X}\in\mathbb{R}^{d_{in}\times n}$,
$\mathbf{W}_{q},\mathbf{W}_{k}\in\mathbb{R}^{d_{k}\times d_{in}}$, and
$\mathbf{W}_{v}\in\,\mathbb{R}^{d_{v}\times d_{in}}$. Then, to calculate the
unnormalized attention map, the query and key matrices are multiplied and
passed through a softmax function.

$\boldsymbol{\lambda}=softmax(\frac{\mathbf{Q}^{T}\mathbf{K}}{\sqrt{\mathbf{d_{k}}}}),\boldsymbol{\lambda}\in\mathbb{R}^{n\times
n}$ (2)

The multiplication step weighs the encoded content of the input features from
every region against the encoded contents of the other regions, yielding the
said attention map. The purpose of the subsequent softmax function is to
normalize the attentiveness of every region to each query vector. In other
words, the softmax function normalizes $\boldsymbol{\lambda}$ such that the
rows of the $n$ by $n$ attention map sum to one. This formulation resembles a
weighted averaging process where the weights are derived based on the
similarity of the content between input features. Thereafter, the resulting
attention map is used alongside the value matrix to derive the weighted
features.

$\mathbf{O}_{h_{i}}=\boldsymbol{\lambda}\mathbf{V}^{T},$ (3)

Where $\mathbf{O}_{h_{i}}$ corresponds to the output of a single head of this
attention mechanism. Since every feature vector derived from the visual
encoder before the SABlock has a limited receptive field of the input images,
an attention-less network would have no way of discriminating against features
that contain erroneous information. However, by passing the said features
through the self-attention block, the model can manipulate the faulty features
and rectify the derived motion representation based on the global content of
the input. The outputs from each of the heads are then concatenated and
multiplied by a weight matrix $\mathbf{W}_{o}$ to yield the output of the
SABlock. Thereafter, this output is weighted by a learnable parameter and the
results are treated as residual values by being added to the original feature
maps. This process is formulated as below

$\mathbf{O}=\overset{h}{\underset{i=1}{\mathrm{concat}}}[\mathbf{O}_{h_{i}}]\\\
$ (4)
$\mathbf{X}^{\prime}=\mathbf{X}+\boldsymbol{\gamma}\times(\mathbf{W}_{o}\mathbf{O})$
(5)

Where h is the number of heads and $\boldsymbol{\gamma}$ is a learnable
parameter that is initialized to zero. In practice we set h to 1 throughout
this work.

###  3.3 Pose Estimation

The output from the self-attention block is then passed through a global
average pooling (GAP) layer to derive the vector containing the motion
information,

$\mathbf{M}=\frac{1}{H\times
W}\sum_{i=1,j=1}^{H,W}\mathbf{X}\textprime_{ij}^{c}$ (6)

Where $c$ represents the depth index of the feature map. The utilization of
the SABlock before the GAP layer allows for a more refined dimensionality
reduction process. This compares to a setting where SABlocks are not used
before the GAP layer and both the accurate and inaccurate information are
naively averaged, leading to reduced feature maps that encode warped
representations of the transformation between the input images. This is a
crucial point in the case of visual odometry where feature reliability is
essential for accurate odometry estimation. The lack of mechanisms which
provide a global sense of motion that is present in the input, leads to the
inability of the network in estimating the true motion when artifacts are
present in the input.

Thereafter, as can be seen in Fig. 2, the resulting vector from the GAP layer,
$\mathbf{M}$, is used as input to a two-layer LSTM network to model the motion
vectors in a temporal sense. A two-layer fully connected network, which is not
shown in Fig. 3, is used to derive the 6-DoF pose that represents the
incremental movement between the image pairs.

###  3.4 Loss Function

In our approach, we parameterize the desired output of the network as
$\boldsymbol{\xi}^{*}=ln(\mathbf{T}^{*})$ where $\mathbf{T}^{*}$ represents
the true $4\times 4$ transformation matrix between the global poses of the two
input images. Therefore, the network is trained to estimate
$\boldsymbol{\xi}^{*}\in\mathbb{R}^{6}$, the lie algebra coordinates, which is
the logarithm mapping of $\mathbf{T}^{*}$. Similar to [11], the loss function
itself is formulated as follows

$\mathcal{L}=\frac{1}{2}\mathbf{g}(\boldsymbol{\xi})^{T}(\boldsymbol{\Sigma}^{-1})\mathbf{g}(\boldsymbol{\xi})$
(7)

Where

$\mathbf{g}(\boldsymbol{\xi})=\text{ln}(\text{exp}(\boldsymbol{\xi})\mathbf{T}^{*{{}^{-1}}})$
(8)

Where $\boldsymbol{\xi}$ is the output of the network, and $\mathbf{T}^{*}$ is
the true transformation matrix. To weigh the motion loss in each of the axes
and balance their mutual impact, we use the empirical covariance matrix which
is calculated using the training set through the following formulation

$\mathbf{\mathbf{\Sigma}}=\frac{1}{N-1}\sum_{i=1}^{N}\left(\boldsymbol{\xi}_{i}^{*}-\overline{\boldsymbol{\xi}^{*}}\right)\left(\boldsymbol{\xi}_{i}^{*}-\overline{\boldsymbol{\xi}^{*}}\right)^{\mathbf{T}}$
(9)

where
$\overline{\boldsymbol{\xi}^{*}}=\frac{1}{N}\sum_{i=1}^{N}\boldsymbol{\xi}_{i}^{*}$
and $\boldsymbol{\xi}^{*}=ln(\mathbf{T}^{*})$.

###  3.5 Architectural Details

As can be seen in Fig. 2, the CNN section of our architecture is composed of
10 layers. The three initial layers of our CNN use kernels with sizes of
$7\times 7$, $5\times 5$ and $5\times 5$, respectively, while each uses a
stride of 2. All the preceding layers have strides 1 and 2 intermittently. The
number of output channels for each layer is depicted in Fig. 2. For the
SABlock, we set $d_{k}$, $d_{q}$ and $d_{v}$ to 128. Both of the LSTM layers
are made up of 1024 hidden units while a single layer fully connected layer is
used to estimate the output.

##  4 Implementation and Evaluation

We used PyTorch and PyTorch lightning to implement our method. An NVIDIA Tesla
T4 GPU was used to train all the networks. The networks were trained for 300
epochs, while early stopping techniques were employed to reduce overfitting.
Furthermore, a learning rate of 1e-4 and Adam optimizer [8] with the proposed
hyperparameters in [8] were used for training.

###  4.1 Datasets

For all experiments, we used the KITTI odometry dataset. This dataset consists
of 22 sequences of driving a car in urban areas in the presence of a large
number of moving objects and artifacts in the images. The ground truth for the
first 11 of the sequences is available and we use sequences 0, 1, 2, 8, and 9
for training and leave 3, 4, 5, 6, 7, and 10 for testing. Random short
sequences with random lengths are chosen from the training sequences while 5%
of them are separated for validation purposes. The images are resized to (218,
720) and the training sequences are shuffled at the end of each epoch. It
should be noted that no augmentations were done on the input images.

###  4.2 Evaluation Metrics

In order to provide quantitative measures and compare the performance of our
approach against the classical and data-driven methods, we use the KITTI
odometry benchmarking methods proposed in [4]. This evaluation method reports
the relative translation and rotation accuracy of the estimates over sequences
of length 100m-800m. The translation accuracy is reported as the percentage of
deviation from the ground truth, while rotation error is reported in units of
degrees per-meter. Averaging the error over different distances provides an
adequate measure of drift as well as incremental accuracy.

##  5 Experiments

###  5.1 Quantitative Results

The quantitative results of our approach are reported in Table 1. The
competing SOTA approach in deep learning based visual odometry is DeepVO [16]
while VISO2-M [5], a SOTA feature-based algorithm, is chosen as the classical
approach that we will compare our results against. Since the codes for DeepVO
were not open-sourced, we implemented this method as close as possible based
on [16]. It should be noted that the structure of DeepVO closely resembles our
network with the exception of the attention layers. As can be seen in Table 1,
our average and sequence-based results consistently surpass DeepVO. In
particular, the averaged accuracy of our method surpass that of DeepVO by
32.4% on translation and 37.7% on rotation, proving the advantage of attention
on VO in terms of performance. Additionally, the performance of our method is
consistently better than the monocular vision based VISO2 in terms of
translation accuracy with the exception of sequence 6. In terms of rotation,
our method outperforms VISO2-M in sequences 5, 7 and 10. Overall, the average
results on all test sequences show that our method is able to surpass the
performance of both classical and SOTA deep learning based odometry baselines.

Table 1: Quantitiative results against competing approaches

Test Seq. | VISO2-M [5] | DeepVO [16] | AVO (ours)
---|---|---|---
trel(%)/rrel(∘) | trel(%)/rrel(∘) | trel(%)/rrel(∘)
Seq 03 | $27.63/\mathbf{0.055}$ | $12.88/0.056$ | $\mathbf{12.29}/0.073$
Seq 04 | $15.82/\mathbf{0.018}$ | $13.26/0.048$ | $\mathbf{11.31}/\mathbf{0.018}$
Seq 05 | $16.54/0.055$ | $11.49/0.037$ | $\mathbf{7.662/0.028}$
Seq 06 | $\mathbf{10.14}/\mathbf{0.027}$ | $17.73/0.060$ | $12.17/0.037$
Seq 07 | $33.23/0.154$ | $13.47/0.090$ | $\mathbf{7.582/0.034}$
Seq 10 | $29.18/0.115$ | $18.18/0.073$ | $\mathbf{14.66}/\mathbf{0.040}$
Avg. | $22.09/0.071$ | $14.50/0.061$ | $\mathbf{10.95}/\mathbf{0.038}$

###  5.2 Qualitative Results

The visualizations regarding the trajectory estimates are provided in Fig. 4.
It can be seen that our network is able to track the ground truth trajectory
significantly better in case of sequence 5. This sequence alongside sequence 7
contain numerous moving objects present in the scene while sequence 5 also
exhibits tortuous paths. Furthermore, based on the results from sequence 10
and 3, the issue of drift in DeepVO [16] is apparent from the initial segment
of the trajectories while our approach drifts slower. Compared to VISO2-M [5]
and based on results from Fig. 4(a) and Fig. 4(d), our network is able to
maintain a slower drift while providing a better accuracy in terms of tracking
the true trajectory. Based on Fig. 4(a) and Fig. 4(d), VISO2-M, is not able to
estimate the scale properly while our method shows an adequate implicit scale
estimation capability that is formed during training. Additionally, VISO2-M
shows an unstable behavior, during a short stopping of the car, based on the
estimated path at location (-175,-10) of Fig. 4(c) while none of the deep
learning based methods exhibit such behavior.

(a) Sequence 3

(b) Sequence 5

(c) Sequence 7

(d) Sequence 10

Figure 4: Qualitative results for the test sequences of the KITTI dataset.

###  5.3 Attribution Analysis

To provide an insight into how self-attention allows the network to focus on
certain regions of the image and to show the ability of the attention
mechanism in manipulating the way features are utilized, we use integrated
gradients [13] to provide a saliency analysis of our approach. Through this
method, we visualize the gradient of the output pose with respect to each of
the pixels of the input images. In other words, we will be able to
qualitatively analyze the effect of each region of the input on the output
pose. Therefore, by comparing the generated saliency maps from our approach
against DeepVO [16], we will be able to get an intuition into the effects of
attention modules on the feature extraction capabilities of VO networks.

The results of the attribution analyses are presented in Fig. 5. As can be
seen in this figure, 6 scenarios are presented where three contain moving
objects in the scene, and the others correspond to straight movement, turning,
and saturated images. The intensity of the red pixels in the overlaid figures
on the bottom rows of Fig. 5 show the gradient magnitudes of those pixels with
respect to the output pose. Based on Fig. 5(d), Fig. 5(e), and Fig. 5(f) it
can be seen that our approach is able to consistently disregard the
information from moving objects and use the salient features from the
background to make estimations regarding the changes in the pose of the
vehicle. This is while DeepVO seems to have no structure in terms of
dynamically changing the effect of different pixels on the output. The same
patterns present themselves when analyzing Fig. 5(c) and Fig. 5(b) where our
network focuses on foreground objects consistently across different scenarios
while disregarding artifacts in the input. In particular, our network puts a
strong emphasis on the usage of pixels that belong to the road and buildings
to provide pose estimates even in the presence of saturation, as can be seen
in Fig. 5(a).

(a) Saturation

(b) Turning

(c) Straight Movement

(d) Moving Object 1

(e) Moving Object 2

(f) Moving Object 3

Figure 5: Attribution analyses using integrated gradients [13] in different
scenarios (best viewed in color)

###  5.4 Loss Analysis

To analyze the effect of moving cars on the accuracy of the estimates from
each of the networks, we visualized the frame-to-frame loss values in the
presence of moving cars in the scene. Fig. 6(a) shows a moving object that was
present in the scene in test sequence 3 of the KITTI dataset. We visualize the
loss from each of the networks during the presence of this object in the input
frames. As can be seen in Fig. 6(c), our network is able to maintain its
accuracy throughout this scene while exhibiting minimal amounts of changes in
the value of error. This is while the loss from DeepVO [16] fluctuates
significantly for the duration of this sequence. Combined with the results
from Section 5.3, it is evident that the ability of our method in rejecting
moving instances allows for a smaller error as well as fewer fluctuations.
Fig. 6(b) presents a case where a moving vehicle enters the frame. Based on
the plots in Fig. 6(d), upon the entrance of the vehicle, the loss values for
both networks experience a sudden increase at index 10 of the x-axis. However,
our method shows a lower value of error at the peak of this change, which
eventually leads to a better performance on this test sequence.

(a) Sequence 3

(b) Sequence 7

(c) Loss plot for Seq. 3

(d) Loss plot for Seq. 7

Figure 6: Input pairs alongside frame-to-frame loss plots for test sequences
(best viewed in color)

###  5.5 Consistency Analysis

In this analysis, we show the consistency of our method in extracting salient
features from the inputs. To provide meaningful visualizations regarding the
reliance of each model on various objects that are present in the scene,
through time, we used a semantic segmentation network to label each of the
pixels of the input images. Specifically, we used SSeg [23], which currently
is the SOTA approach in the task of semantic segmentation on the KITTI
segmentation benchmark [1]. For each frame, the category of objects that
affect the output pose the most is chosen and visualized as the top salient
category. By running this pipe on 50 consecutive frames on sequence 5 of the
KITTI dataset, the visualization in Fig. 7 was derived. Based on this figure,
our method is able to consistently focus on the road and building regions of
the inputs in order to estimate the output poses while DeepVO [16] shows an
unstable behavior by switching between different categories of objects. These
results are aligned with visualizations in Fig. 5 where our network is able to
dynamically shift focus onto background objects while DeepVO showed randomness
in selection of object categories to infer the incremental pose.

(a) Top Salient categories for AVO (ours) (b) Top salient categories for
DeepVO [16]

Figure 7: Top salient categories for both our method and DeepVO through 5.

###  5.6 Conclusion

In this paper, we showed the efficacy of self-attention modules on VO networks
by comparing attention-based VO networks against SOTA attention-less
counterparts. The quantitative analyses on the KITTI odometry dataset show
that the addition of self-attention module to the visual feature extractor
boosts the performance of the odometry network and allows us to surpass the
performance of the SOTA attention-less network. Our saliency analyses showed
that with the addition of the attention module the visual feature extractor as
a whole is able to dynamically reject the moving objects that are present in
the scene while showing an adequate feature extraction capability even in the
presence of saturation in the input images. Additionally, frame to frame loss
plots showed that in the presence of moving objects, our approach is able to
maintain its accuracy while SOTA methods showed unstable behaviours. Finally,
semantic segmentation based analyses allowed us to further analyze the
consistency of the networks and show the ability of an attention-based VO
model in consistent extraction of salient features.

## References

  * [1] Hassan Alhaija, Siva Mustikovela, Lars Mescheder, Andreas Geiger, and Carsten Rother.  Augmented reality meets computer vision: Efficient data generation for urban driving scenes.  International Journal of Computer Vision (IJCV), 2018.
  * [2] Changhao Chen, Bing Wang, Chris Xiaoxuan Lu, Niki Trigoni, and Andrew Markham.  A survey on deep learning for localization and mapping: Towards the age of spatial machine intelligence, 2020.
  * [3] Christian Forster, Zichao Zhang, Michael Gassner, Manuel Werlberger, and Davide Scaramuzza.  SVO : Semidirect Visual Odometry for Monocular and Multicamera Systems.  2016\.
  * [4] Andreas Geiger, Philip Lenz, and Raquel Urtasun.  Are we ready for autonomous driving? the kitti vision benchmark suite.  In Conference on Computer Vision and Pattern Recognition (CVPR), 2012.
  * [5] Andreas Geiger, Julius Ziegler, and Christoph Stiller.  Stereoscan: Dense 3d reconstruction in real-time.  In Intelligent Vehicles Symposium (IV), 2011.
  * [6] J. Hu, L. Shen, and G. Sun.  Squeeze-and-excitation networks.  In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7132–7141, 2018.
  * [7] Eddy Ilg, Nikolaus Mayer, Tonmoy Saikia, Margret Keuper, Alexey Dosovitskiy, and Thomas Brox.  Flownet 2.0: Evolution of optical flow estimation with deep networks.  CoRR, abs/1612.01925, 2016.
  * [8] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  CoRR, abs/1412.6980, 2015.
  * [9] X. Kuo, C. Liu, K. Lin, and C. Lee.  Dynamic attention-based visual odometry.  In 2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pages 160–169, 2020.
  * [10] S. Milz, G. Arbeiter, C. Witt, B. Abdallah, and S. Yogamani.  Visual slam for automated driving: Exploring the applications of deep learning.  In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), pages 360–36010, 2018.
  * [11] V. Peretroukhin and J. Kelly.  Dpc-net: Deep pose correction for visual localization.  IEEE Robotics and Automation Letters, 3(3):2424–2431, 2018.
  * [12] R. Sagawa, Y. Shiba, T. Hirukawa, S. Ono, H. Kawasaki, and R. Furukawa.  Automatic feature extraction using cnn for robust active one-shot scanning.  In 2016 23rd International Conference on Pattern Recognition (ICPR), pages 234–239, 2016.
  * [13] Mukund Sundararajan, Ankur Taly, and Qiqi Yan.  Axiomatic attribution for deep networks.  CoRR, abs/1703.01365, 2017.
  * [14] R. Villegas, Jimei Yang, Seunghoon Hong, Xunyu Lin, and H. Lee.  Decomposing motion and content for natural video sequence prediction.  ArXiv, abs/1706.08033, 2017.
  * [15] Bing Wang, Changhao Chen, Chris Lu, Peijun Zhao, Niki Trigoni, and Andrew Markham.  Atloc: Attention guided camera localization.  Proceedings of the AAAI Conference on Artificial Intelligence, 34:10393–10401, 04 2020.
  * [16] S. Wang, R. Clark, H. Wen, and N. Trigoni.  Deepvo: Towards end-to-end visual odometry with deep recurrent convolutional neural networks.  In 2017 IEEE International Conference on Robotics and Automation (ICRA), pages 2043–2050, 2017.
  * [17] Sen Wang, Ronald Clark, Hongkai Wen, and Niki Trigoni.  End-to-end, sequence-to-sequence probabilistic visual odometry through deep neural networks.  The International Journal of Robotics Research, 37(4-5):513–542, 2018.
  * [18] Xiaolong Wang, Ross B. Girshick, Abhinav Gupta, and Kaiming He.  Non-local neural networks.  CoRR, abs/1711.07971, 2017.
  * [19] S. Wangsiripitak and D. W. Murray.  Avoiding moving outliers in visual slam by tracking moving objects.  In 2009 IEEE International Conference on Robotics and Automation, pages 375–380, 2009.
  * [20] Fei Xue, Xin Wang, Shunkai Li, Qiuyuan Wang, Junqiu Wang, and Hongbin Zha.  Beyond tracking: Selecting memory and refining poses for deep visual odometry.  In IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019, pages 8575–8583. Computer Vision Foundation / IEEE, 2019.
  * [21] Han Zhang, Ian Goodfellow, Dimitris Metaxas, and Augustus Odena.  Self-attention generative adversarial networks.  05 2018.
  * [22] Jun Zhang, Mina Henein, Robert Mahony, and Viorela Ila.  Vdo-slam: A visual dynamic object-aware slam system, 2020.
  * [23] Yi Zhu, K. Sapra, F. Reda, K. Shih, S. Newsam, A. Tao, and Bryan Catanzaro.  Improving semantic segmentation via video propagation and label relaxation.  2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 8848–8857, 2019.


# A Low Complexity Block-oriented Functional Link Adaptive Filtering Algorithm

Pavankumar Ganjimala1, Subrahmanyam Mula2
Electrical engineering department, Indian Institute of Technology Palakkad,
Palakkad, India
E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The high computation complexity of nonlinear adaptive filtering algorithms
poses significant challenges at the hardware implementation level. In order to
tackle the computational complexity problem, this paper proposes a novel
block-oriented functional link adaptive filter (BO-FLAF) to model memoryless
nonlinear systems. Through theoretical complexity analysis, we show that the
proposed Hammerstein BO trigonometric FLAF (HBO-TFLAF) has $47\%$ lesser
multiplications than the original TFLAF for a filter order of $1024$.
Moreover, the HBO-TFLAF exhibits a faster convergence rate and achieved $3-5$
dB lesser steady-state mean square error (MSE) compared to the original TFLAF
for a memoryless nonlinear system identification task.

###### Index Terms:

Nonlinear adaptive filters, system identification, functional link adaptive
filters, spline adaptive filters

##  I Introduction

Conventionally, signal processing applications such as active noise control
(ANC), echo cancellation, channel equalization etc. have relied on linear
adaptive filters to model unknown systems due to their ease of design,
implementation and lesser computational complexity [1]. However, in reality, a
lot of practical problems involve nonlinear elements [2, 3, 4] which cannot be
modelled by the conventional methods. One way to address this issue is to use
nonlinear adaptive filters which incorporate nonlinearity in their model and
thus improve the modelling accuracy.

Different structures and algorithms for nonlinear adaptive filters have been
proposed in literature. Some of the important classes of algorithms are kernel
adaptive filters (KAF) [5], functional link adaptive filters (FLAF) [6] and
spline adaptive filters (SAF) [7]. Out of these the FLAF belongs to a class of
filters known as linear-in-the-parameters (LIP) filters and has been widely
used in online learning applications [8, 9]. Most of the recent works
improving FLAF [10, 11, 12, 13] focus on improving the performance of the
basic FLAF. There are only a few efforts which tackle the high computational
complexity issue of nonlinear adaptive filters [14, 15, 16]. Compared to the
FLAF, the SAF belongs to the block-oriented class of filters. Block-oriented
filters are composed of a cascade of purely linear (L) or nonlinear (NL)
modelling blocks and can be of Hammerstein type (NL-L) or Wiener type (L-NL).
SAF has been proposed as a low-complexity solution for various applications
[17, 18, 19]. The low complexity of SAF can be attributed to its block-
oriented structure [20]. With that motivation, we propose a novel low
complexity block-oriented FLAF structure in this paper. In the next section,
we give a brief overview of the FLAF.

##  II Functional link adaptive filter

The block diagram of an $M$-tap FLAF is shown in Fig. 1. As depicted in the
figure, input samples $x(n)$ are fed to a tapped delay line and each of the
$M$ outputs is expanded into $Q$ samples through a functional expansion block
(FEB), where $Q$ is the number of functional links. The FEB generates the
nonlinear terms which help model the nonlinear system. The functional links
are a set of $Q$ functions
$\Phi=[\varphi_{0}(\cdot),\varphi_{1}(\cdot),\dots\varphi_{Q-1}(\cdot)]$. The
output expansion of an input sample $x(n-i)$ is given as
$\bar{\mathbf{g}}_{i}(n)\in\mathbb{R}^{Q}$, where

$\displaystyle\bar{\mathbf{g}}_{i}(n)$
$\displaystyle=\begin{bmatrix}\varphi_{0}(x(n-i))\\\ \varphi_{1}(x(n-i))\\\
\vdots\\\ \varphi_{Q-1}(x(n-i))\end{bmatrix}$ (1)

$i=0,\dots M-1$ and $n$ is the time index. The entire input buffer after
expansion results in the expansion buffer $\mathbf{g}(n)$, given as

$\mathbf{g}(n)=[\bar{\mathbf{g}}_{0}(n)^{T},\bar{\mathbf{g}}_{1}(n)^{T},\dots\bar{\mathbf{g}}_{M-1}(n)^{T}]^{T}$
(2)

There are various choices for FEB basis functions such as Chebyshev, Legendre
and trigonometric polynomials. Among these, the trigonometric polynomial
function is widely used in literature as it provides the best compact
representation and is computationally inexpensive [6]. We consider the
trigonometric polynomial in this paper, for which the function expansion of
the $i^{\text{th}}$ sample in the tapped delay line is given by

$\varphi_{j}(x(n-i))=\begin{cases}x(n-i),&j=0\\\ sin(p\pi x(n-i)),&j=2p-1\\\
cos(p\pi x(n-i)),&j=2p\end{cases}$ (3)

where $p=1\dots P$, and $j=0\dots Q-1$. $P$ is the expansion order which
denotes the amount of nonlinearity required and $Q=2P+1$.

Figure 1: Original FLAF

If we consider the weight vector $\mathbf{w}(n)=[w_{0}(n),w_{1}(n),\dots
w_{MQ-1}(n)]$, then the output of the adaptive filter is given as
$y(n)=\mathbf{w}(n)^{T}\mathbf{g}(n)$ and the error $e(n)=d(n)-y(n)$, where
$d(n)$ is the desired response. The weight update equation using the
stochastic gradient rule is given as

$\mathbf{w}(n+1)=\mathbf{w}(n)+\mu e(n)\mathbf{g}(n)$ (4)

where $\mu$ is the step size parameter.

In this section, we described a memoryless FLAF, which models instantaneous
nonlinearity. An FLAF with memory can be realized using additional functional
expansions [6] which can model dynamic nonlinearity, i.e nonlinear functions
which depend on the time instant.

##  III Block-Oriented Functional Link Adaptive Filter

In this section, we propose two modifications to the FLAF to make it
computationally more efficient. First, we describe an improvisation coined as
the single $\Phi$ FLAF. Then, we describe the novel block-oriented FLAF
algorithm.

###  III-A Single $\Phi$ FLAF

Instead of delaying the input sample $x(n)$ in a tapped delay line and
performing the $M$ $\Phi$ operations in parallel as shown in the original FLAF
in Fig. 1, we can perform a single $\Phi$ operation first on the input sample
$x(n)$ and then delay the expanded samples in $\mathbf{g}_{0}(n)$ as shown in
Fig. 2(a). This idea is already present in nonlinear ANC literature [14, 21]
and we extend this to the FLAF and coin this as the single $\Phi$
architecture. The $M$ $\Phi$ blocks are identical and time-invariant.
Moreover, they just perform a point-wise mapping of the input sample. Hence,
this rearrangement does not affect the generation of $\mathbf{g}(n)$. In this
topology,
$\mathbf{g}(n)=[\bar{\mathbf{g}}_{0}(n)^{T},\bar{\mathbf{g}}_{0}(n-1)^{T},\dots\bar{\mathbf{g}}_{0}(n-M+1)^{T}]^{T}$,
where $\bar{\mathbf{g}}_{0}(n-i)$ is the expanded vector
$\bar{\mathbf{g}}_{0}(n)$ delayed by $i$ samples. In this topology, the number
of $\Phi$ modules reduces from $M$ to just $1$ and is independent of filter
order $M$, but the number of delay elements increases from $M$ to $MQ$.
Generally, delay elements (or memory) are relatively less expensive compared
to $\Phi$ block which involves polynomial function evaluations.

###  III-B Block-Oriented Functional Link Adaptive Filter

(a) FLAF with single $\Phi$ module

(b) Hammerstein block-oriented FLAF (HBO-FLAF) structure

Figure 2: Proposed FLAF modifications

Here we further reduce the computational complexity of the single $\Phi$ FLAF
by designing a block-oriented Hammerstein structure inspired from the SAF
structure [22]. We split the parallel $MQ$ tap filter in FLAF into two
separate serial filters of order $M$ and $Q$ respectively and create a novel
Hammerstein type filter called the Hammerstein block-oriented FLAF (HBO-FLAF)
which is shown in Fig. 2(b). In the first stage the $Q$ samples from the FEB
are adaptively combined by the adaptive weights
$\mathbf{a}(n)=[a_{0}(n),a_{1}(n),\dots a_{Q-1}(n)]^{T}$ to identify the
nonlinear component of the system. The output of the first stage $s(n)$ is
given to a tapped delay line of length $M$ and the outputs are then adaptively
combined by the second filter with weights
$\mathbf{w}(n)=[w_{bias}(n),w_{0}(n),w_{1}(n),\dots w_{M-1}(n)]^{T}$ to
identify the linear component. Here $w_{bias}$ is an optional adaptive bias
quantity added to obtain improved filter performance.

The output of the nonlinear filter $s(n)$ is given by

$s(n)=\mathbf{a}(n)^{T}\mathbf{g}(n)$ (5)

and
$\mathbf{g}(n)=\bar{\mathbf{g}}_{0}(n)=[\varphi_{0}(x(n)),\varphi_{1}(x(n)),\dots\varphi_{Q-1}(x(n))]^{T}$

The final output $y(n)$ is given by

$y(n)=\mathbf{w}(n)^{T}\mathbf{s}(n)$ (6)

where, $\mathbf{s}(n)=[1,s(n),s(n-1),\dots s(n-M+1)]^{T}$ is a buffer
consisting of the first stage outputs. The estimation error is defined as
$e(n)=d(n)-y(n)$, and $d(n)$ is the desired signal.

The HBO-FLAF has two weight updates to be performed. The weight update
equation is derived here using the standard stochastic gradient descent method
[23]. The weight update for the linear filter weights $\mathbf{w}(n+1)$ using
the MSE cost function can be derived as follows

$\begin{split}\mathbf{w}(n+1)&=\mathbf{w}(n)+\frac{\partial(e(n)^{2})}{\partial\mathbf{w}(n)}\\\
&=\mathbf{w}(n)+2e(n)\frac{\partial(d(n)-\mathbf{w}(n)^{T}\mathbf{s}(n))}{\partial\mathbf{w}(n)}\\\
\end{split}$

Simplifying the derivative and replacing the constant terms with a learning
rate parameter $\mu_{w}$ [7], we get the final weight update equation for the
linear weights $\mathbf{w}(n)$ as

$\mathbf{w}(n+1)=\mathbf{w}(n)+\mu_{w}e(n)\mathbf{s}(n)$ (7)

Similarly, the weight update for the nonlinear filter weights
$\mathbf{a}(n+1)$ can be derived using stochastic gradient descent as

$\mathbf{a}(n+1)=\mathbf{a}(n)+2e(n)\frac{\partial(d(n)-\mathbf{w}(n)^{T}\mathbf{s}(n))}{\partial\mathbf{a}(n)}$
(8)

Rewriting $\mathbf{s}(n)$ in terms of $\mathbf{a}(n)$

$\mathbf{s}(n)^{T}=[\mathbf{a}(n)^{T}\mathbf{g}(n),\mathbf{a}(n-1)^{T}\mathbf{g}(n-1),\dots\mathbf{a}(n-M+1)^{T}\mathbf{g}(n-M+1)]$

For a small step size, we can assume that the weights $\mathbf{a}(n)$ change
very little over each iteration [23], i.e
$\mathbf{a}(n)\approx\mathbf{a}(n-1)\approx\dots\mathbf{a}(n-M+1)$. Then
$\mathbf{s}(n)$ can be written as

$\displaystyle\mathbf{s}(n)^{T}$
$\displaystyle=[\mathbf{a}(n)^{T}\mathbf{g}(n),\dots\mathbf{a}(n)^{T}\mathbf{g}(n-M+1)]$
(9)
$\displaystyle=\mathbf{a}(n)^{T}[\mathbf{g}(n),\mathbf{g}(n-1),\dots\mathbf{g}(n-M+1)]$
$\displaystyle=\mathbf{a}(n)^{T}\mathbf{G}^{T}$

where $\mathbf{G}^{T}$ is a $Q\times M$ matrix defined as

$\mathbf{G}^{T}=[\mathbf{g}(n),\mathbf{g}(n-1),\dots\mathbf{g}(n-M+1)]$ (10)

Substituting (9) in (8) we get

$\mathbf{a}(n+1)=\mathbf{a}(n)+2e(n)\frac{\partial(d(n)-\mathbf{w}(n)^{T}\mathbf{G}\cdot\mathbf{a}(n))}{\partial\mathbf{a}(n)}$

Similar to (7), we simplify the equation for the nonlinear weights
$\mathbf{a}(n)$ using learning rate parameter $\mu_{a}$ as

$\mathbf{a}(n+1)=\mathbf{a}(n)+\mu_{a}e(n)\mathbf{w}(n)^{T}\mathbf{G}$ (11)

In this section, we presented a memoryless version of the HBO-TFLAF. Similar
to FLAF with memory, HBO-FLAF is capable of modelling nonlinear systems with
memory by adding a delay line to $\mathbf{g}(n)$. Additional adaptive weights
are added to the delay line samples and their cross terms.

###  III-C Theoretical computational complexity

The computational complexity of an algorithm can be measured in terms of the
number of arithmetic operations performed in an iteration. The computational
complexity of the least mean squares (LMS), trigonometric FLAF (TFLAF), single
$\Phi$ TFLAF, HBO-TFLAF and Hammerstein SAF (HSAF) algorithms are shown in
Table I. In this study, we only consider the memoryless version of the TFLAF
algorithm. Here we define $M$ as the length of the linear filter, $Q_{t}$ and
$P_{t}$ as the $Q$ and $P$ parameters in TFLAF, HBO-TFLAF and $Q_{h}=P_{h}+1$,
where $P_{h}$ is the order of nonlinear function in HSAF.

The TFLAF algorithm has $Q_{t}$ times more multiplications and additions
compared to the LMS algorithm. In addition, TFLAF also has $M(Q_{t}-1)$
trigonometric function evaluations and $MP_{t}$ multiplications in the FEB.
The single $\Phi$ structure reduces the number of trigonometric function
evaluations to $Q_{t}-1$ and correspondingly the $MP_{t}$ multiplications in
the FEB to $P_{t}$ multiplications. The HBO-TFLAF further reduces the
computation by splitting the $MQ_{t}$ tap filter into two filters of order $M$
and $Q_{t}$ respectively ($M+Q_{t}$ feed-forward taps). Although the HBO-TFLAF
has only $M+Q_{t}$ forward taps, the additional vector-matrix multiplication
between $\mathbf{w}(n)$ and $\mathbf{G}$ in (11) contributes to $MQ_{t}$
multiplications and $(M-1)Q_{t}$ additions. The computational complexity of
HSAF is similar to the HBO-TFLAF and has $Q_{h}$ instead of $Q_{t}$ taps.

TABLE I: Theoretical computational complexity Algorithm | Number of | Number of | Trig.
---|---|---|---
| multipliers | adders | functions
LMS | $2M+1$ | $2M$ | 0
TFLAF | $2MQ_{t}+MP_{t}+1$ | $2MQ_{t}$ | $M(Q_{t}-1)$
Single $\Phi$ TFLAF | $2MQ_{t}+P_{t}+1$ | $2MQ_{t}$ | $Q_{t}-1$
HBO-TFLAF | $2(M+Q_{t})+P_{t}$ | $2M+Q_{t}+$ | $Q_{t}-1$
$+MQ_{t}+1$ | $MQ_{t}-1$
HSAF | $2(M+Q_{h})+P_{h}$ | $2M+Q_{h}+$ | $0$
$+MQ_{h}$ | $MP_{h}+Q_{h}+$
$+(P_{h}+1)^{2}$ | $3+P_{h}(P_{h}+1)$

(a) Memoryless system 1

(b) Memoryless system 2

(c) System with memory

Figure 3: MSE learning curves

To obtain a rough estimate of the computational complexity, we consider an
acoustic echo cancellation application and assume $M=1024$ and $Q_{t}=7$,
$Q_{h}=4$. Substituting the values, the number of multiplications for TFLAF,
single $\Phi$ TFLAF, HBO-TFLAF and HSAF are $17409,14340,9235$ and $6171$
respectively and the number of additions are $14336,14336,9222$ and $5143$
respectively. The number of multiplications and additions is in the order:
TFLAF $>$ Single $\Phi$ TFLAF $>$ HBO-TFLAF $>$ HSAF. Although the HBO-TFLAF
is similar in structure to HSAF, since $Q_{t}>Q_{h}$, the HBO-TFLAF has higher
computation. HBO-TFLAF will have lower computation than the HSAF when
$Q_{t}<Q_{h}$.

##  IV MSE Performance Analysis

In order to assess the performance of the TFLAF, single $\Phi$ TFLAF and HBO-
TFLAF, we perform nonlinear system identification on three different systems
in MATLAB. We also compare performance with the HSAF and the LMS algorithm
which is a linear model. The performance metric chosen here is the mean square
error (MSE) metric given by $10\cdot\text{log}_{10}(E[e(n)^{2}])$. The MSE
learning curves are generated from averaging $500$ independent Monte Carlo
experiments followed by a $20$ tap moving average filter to improve the
visibility of the curves.

Input to the systems is white Gaussian with a variance of $0.25$ and noise
variance is taken to be $0.01$. The filter weights in LMS, RFF-KLMS, TFLAF and
linear filter weights in HSAF and HBO-TFLAF are initialized to zeros. The
nonlinear adaptive weight vector $\mathbf{a}(n)$ in HBO-TFLAF is initialized
as $\delta(n)$, where the first weight, which corresponds to the $x(n)$ output
is one and the rest are zeros. This ensures that the HBO-TFLAF structure
behaves as a linear filter initially. The bias weight ($w_{bias}$) is also
used for the TFLAF and HBO-TFLAF. The HSAF nonlinear weight vector denoted by
$\mathbf{q}(n)$ is set as $[-3.0,-2.75,\dots 2.75,3]$ (for $\Delta x=0.25$)
resembling a linear mapping. In HSAF, for all the experiments $Q_{h}=4$ and
the matrix $C$ is chosen as the CR-spline basis matrix (HSAF parameter
definitions in [22]). The parameters chosen for the various filters in the
three systems are shown in Table II. The inputs and the weight initialization
are kept the same for all the experiments.

TABLE II: Experiment parameters Parameter | Memoryless | Memoryless | System
---|---|---|---
system $1$ | system $2$ | with memory
$M$ | $512$ | $512$ | $8$
$\mu_{LMS}$ | $0.002$ | $0.004$ | $0.003$
$\mu_{TFLAF}$ | $0.0005$ | $0.0004$ | $0.0002$
$\mu_{w-BOTFLAF}$ | $0.0006$ | $0.0006$ | $0.0004$
$\mu_{a-BOTFLAF}$ | $0.0006$ | $0.0011$ | $0.0005$
$Q_{t}$ | $9$ | $9$ | $7$
$\mu_{w-HSAF}$ | $0.0015$ | $0.0018$ | $0.002$
$\mu_{q-HSAF}$ | $0.0015$ | $0.0075$ | $0.005$
$\Delta x$ | $0.25$ | $0.21$ | $0.25$

####  IV-1 Memoryless systems

First, we consider the system identification of Hammerstein-type memoryless
nonlinear systems. In system $1$, an asymmetric loudspeaker distortion system
[6] is considered. The nonlinear system is cascaded with a linear system which
is a reverberation effect generated using the image source method (ISM) with a
reverberation time of $T_{60}=60$ ms and a sampling rate of $8$ kHz and is
truncated after $512$ samples.

The MSE learning curves for system $1$ are shown in Fig. 3(a). The nonlinear
adaptive filters perform better compared to the LMS algorithm. The HBO-TFLAF,
in spite of having lesser complexity than the TFLAF, performs better than
TFLAF/Single $\Phi$ TFLAF and obtains around $3$ dB lower MSE. The performance
of HBO-TFLAF and HSAF is almost similar, with HSAF obtaining around $1$ dB
lower MSE here. We can also see that the learning curves of single $\Phi$
TFLAF and the TFLAF overlap and this proves that the single $\Phi$ TFLAF
structure is functionally identical to the TFLAF. In the subsequent plots, we
omit single $\Phi$ TFLAF learning curves.

Next, we perform the system identification of another memoryless system,
system $2$ which is a soft-clipping distortion system as described in [8],
where we consider $\zeta=0.35$. The linear system is kept the same as before.
The MSE learning curves for system $2$ are shown in Fig. 3(b). The performance
is similar to system $1$, and the HBO-TFLAF outperforms all the algorithms and
obtains $5$ dB lower MSE compared to the HSAF in this case.

From the results of the two memoryless systems, we conclude that the block-
oriented algorithms HBO-TFLAF/HSAF are the best choice to model memoryless
systems. Since TFLAF has more degrees of freedom, it tends to over-fit and
thus has lesser performance than HBO-TFLAF/HSAF. The lesser number of taps in
HBO-TFLAF/HSAF also allows it to converge to the solution faster. Although
HSAF and HBO-TFLAF are similar in structure, we observe that HBO-TFLAF has a
global weight adaptation behaviour as opposed to the local adaptation of HSAF.
The HSAF would therefore need samples spread across the input range to learn
the entire nonlinearity, whereas the HBO-TFLAF would not need such a broad
range of training samples to learn the entire nonlinearity. From the
experiments, we observe that the HBO-TFLAF models symmetric and regularly
shaped nonlinearities better, whereas HSAF is better at modelling irregular
nonlinearities. A detailed study comparing the HSAF and HBO-TFLAF is beyond
the scope of this paper and is necessary to reach more solid conclusions.
Additionally, we note that the HBO-TFLAF is slightly easier to set up and
function as it has only $4$ hyperparameters as opposed to $5$ in HSAF.

####  IV-2 System with memory

Next, to understand the limitation of block-oriented systems, we test their
MSE performance in identifying a nonlinear system with memory. We consider the
following system whose output $y(n)$, given an input $x(n)$ is

$y(n)=0.6sin(\pi x(n))^{3}+0.2cos(2\pi x(n-2))^{2}\\\ -0.1cos(4\pi
x(n-4))+1.125$ (12)

This type of system depends nonlinearly on an input sample and its past
samples (or has memory) but does not contain cross terms between the current
and past samples. We point out here that the definition of a system with
memory is slightly different in [6], which defines it as systems which have
cross terms between samples in memory.

The MSE learning curves for this system are shown in Fig. 3(c). The TFLAF has
the lowest MSE for this system. TFLAF can adapt the weights corresponding to
the functional expansion of each input sample in the memory buffer separately.
Whereas, the block-oriented models combine the functional expansion before the
memory buffer and therefore will not be able to model systems with memory. As
mentioned earlier, it is possible to add a delay line and additional filter
weights to improve HBO-TFLAF performance for memory systems. With added filter
weights, the computational advantage of HBO-TFLAF comes down. The single
$\Phi$ TFLAF becomes more computationally efficient for larger order of
memory.

##  V Conclusion and Future work

In this paper, a novel nonlinear adaptive filter structure coined HBO-FLAF is
proposed. HBO-FLAF breaks down the original FLAF into two stages and performs
the nonlinear and linear modelling separately. Through theoretical analysis
and MATLAB simulations, we demonstrated that HBO-TFLAF not only has a lower
computational complexity compared to TFLAF but it also achieves faster
convergence and lesser steady-state MSE compared to TFLAF for a memoryless
nonlinear system identification task. Therefore, HBO-FLAF can be a potential
candidate for real-time VLSI applications involving nonlinear system
identification. We also introduced the single $\Phi$ FLAF structure which has
lower computational complexity than TFLAF and maintains identical performance
as TFLAF. In the future, we plan to implement the proposed algorithms in
hardware and study the power, performance and area trade-offs.

## Acknowledgement

Pavankumar Ganjimala’s work was supported by the Prime Minister’s Research
Fellowship (PMRF), Ministry of Education (MoE), Government of India.

## References

  * [1] D. Comminiello and J. C. Principe, _Adaptive Learning Methods for Nonlinear System Modeling_. Butterworth-Heinemann, 2018.
  * [2] W. Klippel, “tutorial: loudspeaker nonlinearities—causes, parameters, symptoms,” _journal of the audio engineering society_ , vol. 54, no. 10, pp. 907–939, october 2006.
  * [3] G. L. Sicuranza and A. Carini, “A Generalized FLANN Filter for Nonlinear Active Noise Control,” _IEEE Trans. on Audio, Speech, and Language Process._ , vol. 19, no. 8, pp. 2412–2417, 2011.
  * [4] A. Amari, O. A. Dobre, R. Venkatesan _et al._ , “A survey on fiber nonlinearity compensation for 400 gb/s and beyond optical communication syst.” _IEEE Communications Surveys & Tutorials_, vol. 19, no. 4, pp. 3097–3113, 2017.
  * [5] W. Liu, J. C. Principe, and S. Haykin, _Kernel adaptive filtering: a comprehensive introduction_. John Wiley & Sons, 2011, vol. 57.
  * [6] D. Comminiello, M. Scarpiniti, L. A. Azpicueta-Ruiz _et al._ , “Functional link adaptive filters for nonlinear acoustic echo cancellation,” _IEEE Trans. on Audio, Speech, and Language Process._ , vol. 21, no. 7, pp. 1502–1512, 2013.
  * [7] M. Scarpiniti, D. Comminiello, R. Parisi _et al._ , “Nonlinear spline adaptive filtering,” _Signal Process._ , vol. 93, no. 4, pp. 772–783, 2013.
  * [8] D. Comminiello, M. Scarpiniti, L. A. Azpicueta-Ruiz _et al._ , “Nonlinear acoustic echo cancellation based on sparse functional link representations,” _IEEE/ACM Trans. on audio, speech, and language Process._ , vol. 22, no. 7, pp. 1172–1183, 2014.
  * [9] Vasundhara, N. B. Puhan, and G. Panda, “De-correlated improved adaptive exponential flaf-based nonlinear adaptive feedback cancellation for hearing aids,” _IEEE Trans. Circuits Syst. I: Reg. Papers_ , vol. 65, no. 2, pp. 650–662, 2018.
  * [10] D. Comminiello, M. Scarpiniti, S. Scardapane _et al._ , “Improving nonlinear modeling capabilities of functional link adaptive filters,” _Neural Networks_ , vol. 69, pp. 51–59, 2015.
  * [11] V. Patel, V. Gandhi, S. Heda _et al._ , “Design of adaptive exponential functional link network-based nonlinear filters,” _IEEE Trans. Circuits Syst. I: Reg. Papers_ , vol. 63, no. 9, pp. 1434–1442, 2016.
  * [12] S. Burra and A. Kar, “Performance analysis of an improved split functional link adaptive filtering algorithm for nonlinear aec,” _Applied Acoustics_ , vol. 176, p. 107863, 2021.
  * [13] T. Yu, W. Li, Y. Yu _et al._ , “Robust adaptive filtering based on exponential functional link network: Analysis and application,” _IEEE Trans. Circuits Syst. II: Express Briefs_ , vol. 68, no. 7, pp. 2720–2724, 2021.
  * [14] D. Zhou and V. DeBrunner, “Efficient adaptive nonlinear filters for nonlinear active noise control,” _IEEE Trans. Circuits Syst. I: Reg. Papers_ , vol. 54, no. 3, pp. 669–681, 2007.
  * [15] G. L. Sicuranza and A. Carini, “On the bibo stability condition of adaptive recursive flann filters with application to nonlinear active noise control,” _IEEE Trans. on Audio, Speech, and Language Process._ , vol. 20, no. 1, pp. 234–245, 2011.
  * [16] D. Comminiello, A. Nezamdoust, S. Scardapane _et al._ , “A new class of efficient adaptive filters for online nonlinear modeling,” _IEEE Trans. on Syst., Man, and Cybernetics: Syst._ , 2022.
  * [17] V. Patel and N. V. George, “Nonlinear active noise control using spline adaptive filters,” _Applied Acoustics_ , vol. 93, pp. 38–43, 2015.
  * [18] P. P. Campo, A. Brihuega, L. Anttila _et al._ , “Gradient-adaptive spline-interpolated lut methods for low-complexity digital predistortion,” _IEEE Trans. Circuits Syst. I: Reg. Papers_ , vol. 68, no. 1, pp. 336–349, 2020.
  * [19] C. Liu and H. Zhao, “A 2d-lut scheme design for complex-valued spline adaptive filter,” _IEEE Trans. Circuits Syst. II: Express Briefs_ , pp. 1–1, 2023.
  * [20] C. Jiang, H. Li, W. Qiao _et al._ , “Block-oriented time-delay neural network behavioral model for digital predistortion of rf power amplifiers,” _IEEE Trans. Microw. Theory Tech._ , vol. 70, no. 3, pp. 1461–1473, 2022.
  * [21] B. K. Mohanty, G. Singh, and G. Panda, “Hardware design for vlsi implementation of fxlms-and fslms-based active noise controllers,” _Circuits, Syst., and Signal Process._ , vol. 36, no. 2, pp. 447–473, 2017.
  * [22] M. Scarpiniti, D. Comminiello, R. Parisi _et al._ , “Hammerstein uniform cubic spline adaptive filters: Learning and convergence properties,” _Signal Process._ , vol. 100, pp. 112–123, 2014.
  * [23] A. H. Sayed, _Fundamentals of adaptive filtering_. John Wiley & Sons, 2003.