4
$\begingroup$

Why is the least squares cost function used in adaptive noise cancellation with the recursive least squares (RLS) algorithm, but the mean squared error used in signal estimation?

For an ergodic source (where time and ensemble averages should be the same) I would have thought the choice was arbitrary.

From my notes: LMS minimises $\|e[n]\|^{2}$ and RLS minimises $\sum_{i=0}^{N} e^{2}[i], $ where $e[n]$ is the difference between the desired signal and the output of the filter.

$\endgroup$
0
3
$\begingroup$

You are actually asking 2 separate questions. If I have interpreted your post correctly, they are:

  1. Why is the RLS used in Noise Cancellation, whereas the LMS is used in signal estimation?
  2. (If we assume that the signal is ergodic) Isn't minimising the Ensemble average, $E\{e_n^2 \}$, equivalent to minimising the time average, $ \sum_{i = 1}^{N}e_i^2$; i.e. Shouldn't the LMS perform as good as the RLS?

Answers:

Q1:

You are free to choose ANY adaptive filtering algorithm for ANY application (e.g. Adaptive Noise Cancellation -ANC). It need not be the RLS. The same goes with signal estimation, or any other application you can think of.

However, if you have a specific application in mind, and you know something about the system or how the algorithm performs in that setting, you may want to choose one adaptive algorithm over another. (E.g. If your application is to do with converging faster as opposed to having a low error at steady state, you might choose Algorithm X over Y)

Once again, this choice is not made based on whether you minimize the mean squared error or the sum of the squared error.


Q2:

This questions still keeps me up on some nights. Fundamentally, Minimum Mean Squared Error based algorithms are based on, finding the system parameters which minimise the $ E\{ e_n^2 \}$. Now, the expected value of the error

Both the LMS and the RLS are based on minimising this quantity. How they do it, however, is quite different. Remember, that the Expected value is statistical operator - it's the average over all realisations of the random signal. In real life applications, we only have access to one realisation of this signal.

Example: Let's say you have the price of a stock, all you get is one value at each time (e.g. £10) The stock price never says, "oh well I have a 5% chance of being £10, on the other hand I could be £12, or £14.....etc". But I digress.

SO, How are we going to minimize the mean squared error, when we can't compute the true mean? The Least Mean Square (Widrow-Hoff) says, "You know what, I am going to drop the $E\{.\}$ and minimise $e_n^2$. Yes it is a hack, but my god what a hack!

The RLS uses the fact you mentioned: Since the process is ergodic, you can get the time average instead of the ensemble. The sum squared error is equivalent to the average of the squared error. The only thing that's missing is the $1/N$ term in the sum squared error. It is discarded because, it cancels out with another $1/N$ term in the derivation of the RLS. So don't worry.

The interesting thing is how this difference affects the performance of the 2 filters. (This is a whole different question and I suggest that you ask it here - it might get a lot of people interested) The RLS is known to converge faster than the LMS. But when tracking time-varying parameters the LMS can perform better than the RLS in certain conditions.


LMS: $$ E\{e_n^2 \} \approx e_n^2$$ RLS: $$ E\{e_n^2 \} \approx \frac{1}{N} \sum_{i =1}^N e_i^2$$

To sum up: Both the RLS and LMS try to approximate $E\{e^2\}$. They way they do it is different - so the way they behave is different. And you are free to choose any filter for any application.

$\endgroup$
3
  • $\begingroup$ Thanks for taking the time to answer so thoroughly!. This cleared up a few things. I asked my lecturer, and he said if we don't choose the sum of squared errors we won't get a recursive algorithm. Which has confused me all over again. $\endgroup$ – Tom Kealy Mar 13 '13 at 10:44
  • 1
    $\begingroup$ Ha! I understand. I confused myself by looking at the handout on Wiener filters. RLS should converge to the Wiener weights (because time and ensemble averages are the same for ergodic processes), but the LMS is just an approximation so you have to do less work. $\endgroup$ – Tom Kealy Mar 13 '13 at 11:02
  • $\begingroup$ @TomKealy: Exactly, the RLS better approximates the E{e^2} because it takes the average, but the LMS only takes each value. That's mainly why the RLS converges to the Wiener weights faster. One more thing: the names Recursive Least SQUARES and Least Mean SQUARE indicate their cost functions. -> The RLS minimizes the SUM of the SQUARES while the LMS minimises the error SQUARE. $\endgroup$ – ssk08 Mar 13 '13 at 11:36
0
$\begingroup$

As far as I know, you are always taking the MSE, however maybe my peers can confirm/deny this.

Think about the simple case, where you just have two co-efficients. Those two co-efficients are on the x-y plane, and your error, is on the z-axis. This means your error has to be a scalar. Which then means you are taking the error in the expectation. (Average). Otherwise, how can you start to take derivatives, and minimize anything? So as far as I know, you are always taking expectations of errors, or as you have said, $\frac{1}{N}\sum_{n=0}^{N-1} e^{2}[n]$

Another way to think about it. You are essentially computing an error vector, for every iteration. The error vector is the error between what you have, and what you are computing, at each time sample. But you want to minimize the total error. This is where the expectation comes in.

Yet another way to think about it - think about the cost space - you are travelling in a gradient, that it going to continuously minimize an error. What error? The total error. Try hard as you might, you need, at the end of the day, a scalar error number that measures your total error in some way. The usual case is L-2 norm error, (LSE), but L-1 is also possible. The point is that you travel in a direction that minimizes a scalar number, that scalar number being some way you have decided to measure your total error.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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