# GpLMS: Generalized Parallel Least Mean Square Algorithm for Partial Observations

Ghattas Akkad, Viet-Dung Nguyen, Ali Mansour

► To cite this version:

Ghattas Akkad, Viet-Dung Nguyen, Ali Mansour. GpLMS: Generalized Parallel Least Mean Square Algorithm for Partial Observations. 14th International KES Conference on Intelligent Decision Technologies, KES-IDT 2022, Jun 2022, Rhodes, Greece. pp.441-448, 10.1007/978-981-19-3444-5_38 hal-03772375

HAL Id: hal-03772375

https://ensta.hal.science/hal-03772375v1

Submitted on 12 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# GpLMS: Generalized Parallel Least Mean Square
## Algorithm For Partial Observations *

Ghattas Akkad¹, Viet-Dung Nguyen², and Ali Mansour²

¹ ISEN Yncrea-Ouest, VISION-AD, Carquefou, France
ghattas.akkad@isen-ouest.yncrea.fr

² Lab-STICC, UMR 6285 CNRS ENSTA Bretagne, Brest, France
{viet.nguyen,ali.mansour}@ensta-bretagne.fr

**Abstract.** We propose a generalized parallel least mean square algorithm (GpLMS) to deal with partial observation scenarios. GpLMS takes advantage of a two stage parallel LMS architecture to enhance the convergence rate and updates weight vector based on observed entries to obtain a low computational complexity. We compare the results from our proposed algorithm with the state-of-the-arts in an adaptive beamforming context to illustrate its effectiveness.

**Keywords:** Least mean square (LMS) · Parallel LMS · adaptive beamforming · array processing.

## 1 Introduction

We consider problem of adaptive filter with partial observation scenarios. Those scenarios can be met in two different contexts such as data generated with missing entries and data sampled actively. Both contexts are often met in many practical applications such as recommender system (5), wireless sensor network (4), big and real-time data processing (6), to name a few.

The Least Mean Square (LMS) algorithm (2) is a classical, non-blind, adaptive algorithm used to iteratively adjust a filters weight vector in order to minimize the error between the filters output $y(k)$ with respect to a reference, training, signal $d(k)$.

In beamforming applications, an adaptive filter is used to perform spatial multiplexing and increase the systems signal to noise ratio (SNR). It generates and steers the antennas array main beam, with constructive energy, towards the direction of arrival (DOA) of the desired signal and to place nulls, with destructive energy, in the direction of interference (2).

To maintain an uninterrupted and reliable communication, adaptive filters are required to maintain an accelerated convergence and high precision in a low complexity structure (1). However, while simple and effective, the LMS algorithm still exhibits a trade off between its convergence speed and steady state error,

<footnote>* Supported by the AID-DGA and ANR in France to whom the authors are grateful.</footnote>
impacting its performance. Its speed and accuracy are further impacted in the presence of missed samples, i.e. the case of an antenna(s) malfunction.

Different algorithms have been proposed to eliminated the LMS speed-accuracy trade off, i.e. such as the least-least mean square (LLMS) (8) and the recursive LMS (RLMS) (7), however at the cost of a high increase in complexity. In previous work, we proposed a parallel LMS (pLMS) adaptive filter (1) to eliminate the LMS speed-accuracy trade off while maintaining a linear complexity structure. The pLMS is formed of two LMS filters operating in parallel, i.e. same inputs, and connected by an error feedback.

Thus, in this work, we would like to propose a generalized pLMS (GpLMS) algorithm for partial observation scenarios, i.e. missed samples, as well as compute its complexity and validate its behavior.

## 2 Signal model and least mean square (LMS) algorithm

*Signal model:* We consider the following signal model with the output $y(k)$:

$$y(k) = \mathbf{w}^H(k)\mathbf{x}(k) + n(k) \quad (1)$$

where $\mathbf{x}$ is a $N \times 1$ input vector, $\mathbf{w}$ is a weight vector, and $n(k)$ is noise. Here, we assume the noise is additive white Gaussian noise as $n \sim N(0, \sigma_n^2)$. This signal model is refereed to as the model with full observation.

We now describe a partial observation scenario. Let $\mathcal{P}_{\Omega_k}[\mathbf{x}] = \mathbf{x}_{\Omega_k}$ be a sampling operator that selects a part or all entries of the input vector $\mathbf{x}$ where $\Omega_k \in \{1, \dots, N\}$ being a set of entry indices that are observed at $k$th time instant. The signal model 2, in this scenario of interest, can be rewritten as

$$y(k) = \mathbf{w}_{\Omega_k}^H(k)\mathbf{x}_{\Omega_k}(k) + n(k). \quad (2)$$

We note that, in a missing data stream, $\Omega_k$ corresponds to missing entries. On the other hand, $\Omega_k$ can be, for example, a set of uniform sampling indices of the large input vector (i.e., large $\mathbf{x}$).

*Least mean square algorithm:* Let us consider the following mean square error (MSE) cost function

$$MSE = E[e^2(k)] \quad (3)$$

where E stands for expected value operator, the error signal $e$ is defined as

$$e(k) = d(k) - y(k) \quad (4)$$

with $d(k)$ being the reference signal. The classical LMS method seeks an optimal solution $\mathbf{w}(k+1)$ by using a stochastic gradient descent algorithm as follows (3)

$$\begin{aligned} \mathbf{w}(k+1) &= \mathbf{w}(k) + \mu_{\text{LMS}} \nabla_w E[e_k^2] \\ &\approx \mathbf{w}(k) + \mu_{\text{LMS}} e_k^* \mathbf{x}(k) \end{aligned} \quad (5)$$
where $\nabla_w$ is the nabla operator to the weight $\mathbf{w}$ and $\mu_{LMS}$ is a given step size. The main advantage of the LMS algorithm is its low-computational complexity, thus being suitable for processing big data or time-sensitive applications. However, there is always a trade-off between its complexity and convergence rate.

<figure><img src="image_2.png" /><figcaption>Fig. 1. GpLMS Top Level Block Diagram</figcaption></figure>

## 3 Proposed method

Inspired by the parallel LMS (pLMS) (2), we propose a generalization of this algorithm, referred to as GpLMS, to handle partial observation scenarios. By generalization we mean that pLMS for full observations is a special case of our proposed algorithm. Our main idea here is to devise a two stage parallel LMS scheme where the error from each LMS contributes to a total error, defined as $e_{GpLMS}$

$$e_{GpLMS} = e_1(k) - je_2(k-1), \qquad (6)$$

that is used to update the weight vector. Here, $j$ refers to the imaginary number. This modification allows the algorithm to speed up convergence rate as compared to the classical LMS. To deal with missing data, we will update the entries of weight vector $\mathbf{w}$ corresponding to only observed data. By this way, we can avoid redundant computations as assigning missing data to zeros (even though two implementations result in an identical performance). Fig. 1 illustrates this idea and a summary of GpLMS is presented in Algorithm 1.

*Complexity analysis.* In terms of computational complexity, GpLMS has a complexity of $O(4|\Omega_k|)$ per iteration where $|\Omega_k|$ defines the cardinality of $\Omega_k$ where the main cost comes from the computation of $y_{LMS1}$ and $y_{LMS2}$ as well as the weight updates of $\mathbf{w}$ and $\tilde{\mathbf{w}}$. This complexity is smaller than that of the original pLMS that is order of $O(4N)$ since $|\Omega_k| \le N$.
<caption>**Algorithm 1 Generalized parallel LMS (GpLMS)**</caption>

1: **Input:** $\mathbf{x}(k), d(k), n_t, \mu, \Omega_k$
2: **Output:** $\mathbf{w}(k), e_{GpLMS}$
3: **Initialize:**
$\mathbf{w}(0) = \bar{\mathbf{w}}(0) = \mathbf{0}, \mathbf{x}(-1) = \mathbf{x}(0), e_1(0) = 0, e_2(-1) = 0, d(-1) = d(0)$
4: **for** $k = 0$ to $K$ **do**
5: &nbsp;&nbsp;&nbsp;&nbsp;▷ First LMS
6: &nbsp;&nbsp;&nbsp;&nbsp;5: $y_{LMS1} = \mathbf{w}_{\Omega_k}^H \mathbf{x}_{\Omega_k}$
7: &nbsp;&nbsp;&nbsp;&nbsp;6: $e_1(k) = d(k) - y_{LMS1}$
8: &nbsp;&nbsp;&nbsp;&nbsp;7: $e_{GpLMS} = e_1(k) - je_2(k-1)$
9: &nbsp;&nbsp;&nbsp;&nbsp;8: **for** $n \in \Omega_k$ **do**
10: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ Update weight $\mathbf{w}$
11: &nbsp;&nbsp;&nbsp;&nbsp;9: $w_n(k+1) = w_n(k) + \mu e_{GpLMS}^*(k)x_n(k)$
12: &nbsp;&nbsp;&nbsp;&nbsp;10: **end for**
13: &nbsp;&nbsp;&nbsp;&nbsp;▷ Second LMS
14: &nbsp;&nbsp;&nbsp;&nbsp;11: $y_{LMS2} = \bar{\mathbf{w}}_{\Omega_k}^H \mathbf{x}_{\Omega_k}$
15: &nbsp;&nbsp;&nbsp;&nbsp;12: $e_2(k) = d(k) - y_{LMS2}$
16: &nbsp;&nbsp;&nbsp;&nbsp;13: **for** $n \in \Omega_k$ **do**
17: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;▷ Update weight $\bar{\mathbf{w}}$
18: &nbsp;&nbsp;&nbsp;&nbsp;14: $\bar{w}_n(k+1) = \bar{w}_n(k) + \mu e_2^*(k)x_n(k)$
19: &nbsp;&nbsp;&nbsp;&nbsp;15: **end for**
20: &nbsp;&nbsp;&nbsp;&nbsp;16: **end for**

# 4 Numerical results

A Monte Carlo simulation is performed on a Uniform Linear Antenna (ULA) array with $N = 16$ elements to evaluate the models and with $M = 4, 8$ and $12$ missing samples, respectively. The simulation is performed for 500 realizations with 200 samples each. The synchronization, pilot, signal and interferences are generated as a random binary data stream with respect to the below settings

1. Pilot signal modulated using Binary Phase Shift Keying (BPSK) with an angle of arrival (AOA) of 35° and an amplitude of $V_s = 1$

2. Interference signal modulated using 8 Quadrature Amplitude Modulation (QAM) with an AOA of 15° and an amplitude of $V_i = 0.2$

3. Interference signal modulated using 4-PSK with an AOA of 80° and an amplitude of $V_i = 0.2$

The input signal is mixed with a complex Additive Wight Gaussian Noise to obtain a signal to noise ratio (SNR) of 10 dB. The default filters configuration, at $k = 0$, are: $\mu_p = \mu_r = \mu = 0.01$, $d(-1) = d(0)$, $\mathbf{x}(-1) = \mathbf{x}(0)$. The MSE convergence behavior is first presented, in Fig. 2, for the LMS, pLMS and GpLMS in the case of full and partial observations, i.e. $M = 4$.

As shown in Fig. 2, in the case of partial observations and in contrast to the pLMS and GpLMS, the LMS exhibits a considerable delay in its convergence
speed. Moreover, compared to the pLMS, the GgLMS maintained an accelerated
convergence behaviour and a low steady state error. In contrast to the pLMS
and LMS in partial observations, in GgLMS the 0 samples corresponding to a
malfunctioning antenna are ignored and not considered in the next computation.

<figure><img src="image_3.png" /><figcaption>Fig. 2. LMS, pLMS and GgLMS MSE Convergence Behavior with $N = 16$ and $M = 4$</figcaption></figure>

The beam radiation pattern for the pLMS in full observations and GgLMS is
shown in Fig. 3. The pLMS was able to accurately steer its main beam and nulls
toward the direction of arrival of the desired signal at 35° and the interferences
at 15° and 80°, respectively. In contrast, the GgLMS was able to accurately steer
its main beam towards the desired signal at 35° and a null in the direction of
the second interfering signal at 80°.

To further investigate the performance of the GgLMS we evaluate its MSE
behaviour and steady state error in the case of $M = 4, 8, 12$ missing samples.
From Fig. 4, we can see that the GgLMS was able to maintain an accelerated
convergence behaviour and an acceptable steady state error for different partial
observation cases. As the number of missing samples increases from $M = 4$ to
$M = 12$ the GgLMS converged successfully and maintained a stable performance
with a steady state error, on average, less than 0.1. Thus, validating the efficiency
and validity of our proposed algorithm in partial observation scenarios.
<figure><img src="image_4.png" /><figcaption>Fig. 3. pLMS and GpLMS Beam Pattern with $N = 16$ and $M = 4$</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 4. GpLMS Beam Pattern for $SNR = 10$ dB, $N = 16$ and $M = 4, 8, 12$</figcaption></figure>
# 5 Conclusion

We have developed a low-complexity LMS algorithm to deal with partial obser-
vations that can be met in many signal processing applications. The proposed
algorithm generalizes pLMS (2) to enhance performance in the presence of miss-
ing entries. Moreover, it also inherits parallel structure of pLMS to improve
convergence rate. A performance analysis and a hardware implementation of
GpLMS is also developing and will be presented in a near future work.
Bibliography

[1] Akkad, G., Mansour, A., ElHassan, B., Inaty, E.: A multi-stage parallel lms structure and its stability analysis using transfer function approximation. In: 2020 28th European Signal Processing Conference (EUSIPCO). pp. 1851–1855 (2021). https://doi.org/10.23919/Eusipco47968.2020.9287604

[2] Akkad, G., Mansour, A., ElHassan, B.A., Inaty, E., Ayoubi, R., Srar, J.A.: A pipelined reduced complexity two-stages parallel LMS structure for adaptive beamforming. IEEE Transactions on Circuits and Systems I: Regular Papers 67(12), 5079–5091 (2020)

[3] Haykin, S.S.: Adaptive filter theory. Pearson Education India (2008)

[4] Kong, L., Xia, M., Liu, X.Y., Chen, G., Gu, Y., Wu, M.Y., Liu, X.: Data loss and reconstruction in wireless sensor networks. IEEE Transactions on Parallel and Distributed Systems 25(11), 2818–2828 (2014)

[5] Ma, H., King, I., Lyu, M.R.: Effective missing data prediction for collaborative filtering. In: Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval. pp. 39–46 (2007)

[6] Slavakis, K., Giannakis, G.B., Mateos, G.: Modeling and optimization for big data analytics: (statistical) learning tools for our era of data deluge. IEEE Signal Processing Magazine 31(5), 18–31 (2014)

[7] Srar, J.A., Chung, K.S.: Adaptive rlms algorithm for antenna array beamforming. In: TENCON 2009 - 2009 IEEE Region 10 Conference. pp. 1–6 (2009). https://doi.org/10.1109/TENCON.2009.5396256

[8] Srar, J.A., Chung, K.S., Mansour, A.: Adaptive array beamforming using a combined lms-lms algorithm. IEEE Transactions on Antennas and Propagation 58(11), 3545–3557 (2010). https://doi.org/10.1109/TAP.2010.2071361