6
$\begingroup$

I have a question regarding Recursive Least Squares (RLS) adaptive filter.

According to Wikipedia (Recursive Least Squares in Wikipedia), to prevent infinite memory one introduces a forgetting factor $0 < \lambda \le 1$. Then the RLS recursive update equations are: enter image description here

The relevant update is:

$$ \mathbf{P}(n) = \lambda^{-1} \cdot \left( \mathbf{P}(n-1) -\mathbf{g}(n)\mathbf{x}^T(n) \mathbf{P}(n-1) \right). $$

Unless there is some "magical cancellation" then $\mathbf{P}(n) \propto \lambda^{-n}$ which tends to infinity as $n$ grows (since $\lambda^{-1} > 1$). Which means that after long time the filter will "explode" and cause overflow which will ruin the output signal.

I tested the RLS in a Python code, and found that as $\lambda$ decreases, the time-point in which the matrix $\mathbf{P}(n)$ diverges (practically, when I encounter an overflow in $\mathbf{P}(n)$) comes sooner.

Since all papers and Wikipedia define $\lambda < 1$ and the formula for $\mathbf{P}$ goes with $\lambda^{-1}$, I assume this well-tested algorithm somehow addresses the issue of divergence. Why the algorithm does not diverge in theory and practice and what should I do to prevent it diverge when processing very long streams of data?

Side note: I am actually using the RLS for complex signals, therefore transpose ($A^T$) should be replaced with hermitian conjugate ($A^H = \bar{H}^T$) and one needs to pay attention for complex conjugates.

$\endgroup$
1
  • 1
    $\begingroup$ Well, having $\lambda < 1$ alone does not guarantee divergence, does it? Divergence depends on the term in parenthesis as well. $\endgroup$
    – MBaz
    Feb 13, 2023 at 17:42

2 Answers 2

2
$\begingroup$

The convergence itself depends on the eigen values of the empirical correlation matrix (See remark below).

By setting $ \lambda \leq 1 $ we allow the filter to adapt in the non stationary cases.

We can think that also the factor basically damps the eigen values of the matrix if $ \lambda > 1 $. In the case $ \lambda < 1 $ you may thing that you increase the eigen values, yet not necessarily above the critical value for convergence.

Specifically, for you equation of interest:

$$ P = {\lambda}^{-1} \left( P - \boldsymbol{x} \boldsymbol{g}^{T} P \right) = {\lambda}^{-1} \left( I - \boldsymbol{x} \boldsymbol{g}^{T} \right) P $$

Now, in order to have convergence for the equation above what's needed is that $ {\lambda}^{-1} \left( I - \boldsymbol{x} \boldsymbol{g}^{T} \right) $ will have all eigen values within the unit circle. It can happen for $ \lambda < 1 $ as it depends not only on it.

Remark: Actually for $ \lambda \in \left( 0, 1 \right] $ it can be shown that for any bounded input the algorithm will converge regardless of the eigen values.

Remark: If you want to read more about the specific case, you may look for the term convergence of fixed point iterations. For instance Marta Čertíková - FPI for Linear Systems - Fixed Point Iterations (On Web Archive). She has a great course NUMERICAL MATHEMATICS.

$\endgroup$
4
  • $\begingroup$ Actually, I asked how RLS converges if $\mathbf{P}(n) \propto \lambda^{-n}$ when $\lambda < 1$. When I implemented it with $\lambda = 0.95$ it diverges after about 1000 iterations and when I decreased it to $\lambda = 0.5$ it diverged much faster (after less than 300 iterations). $\endgroup$ Feb 14, 2023 at 10:23
  • $\begingroup$ The reasoning is the same, It depends on the eigen values of the multiplication and not only on $\lambda$. I will update accordingly. $\endgroup$
    – Royi
    Feb 14, 2023 at 10:34
  • $\begingroup$ Thank you. If I understand correctly the term $I - \mathbf{g}\mathbf{x}^T$ is the term that ensures convergence, provided that its largest eigenvalue is smaller than $\lambda$. Am I correct? $\endgroup$ Feb 15, 2023 at 13:47
  • $\begingroup$ Yes, they are both must be a contraction operator. Your intuition is correct, just that $ \lambda $ is not the only term in play. $\endgroup$
    – Royi
    Feb 18, 2023 at 6:33
0
$\begingroup$

I also encountered the same problem as you, when I use the step like follows enter image description here

The matrix $P(n)$ diverges, which using $z^H(n)$ instead of $x^{T}(n)P(n-1)$.

Then I using the fomular $$P(n) = \lambda^{-1} \cdot (P(n-1) - g(n)x^{T}(n)P(n-1))$$

$P(N)$ become convergence,only by change the calculation order.

The algorithm is sensitivity to roundoff noise that accumulates due to the recursive computations, which may cause instabilities in the algorithm.

hope this helps.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.