3
$\begingroup$

I have been trying to follow the Least Mean Square(LMS) algorithm derivation given by Wikipedia here and have the following questions.

enter image description here

  1. Here I expected $y(n)$ is to be computed by convolving $x(n)$ with $h(n)$, but in the equation given by Wikipedia it is shown as a matrix multiplication $y(n) = h^H(n).x(n)$. Are these two operations(convolution and matrix multiplication) same here?.
  2. Why do we need a Hermitian transpose rather than normal transpose in the above equation?
  3. Cost function is defined as $E\{|e(n)|^2\}$. Why do we need expectation operator here? Why not normal Mean Square Error(MSE)?
  4. Does LMS filter converge to all type of input signal?
  5. I understand LMS make use of Stochastic Gradient Descent and the update equation for the same is $\hat{h}(n+1)=\hat{h}(n)+\mu x(n)e^*(n)$, what would be the update equation if we would have used a normal Gadient Descent?
$\endgroup$
  • $\begingroup$ I believe these are too many questions to be asked in a single post. $\endgroup$ – Tendero Mar 6 '18 at 20:07
  • $\begingroup$ i think it's fine. all falls under the umbrella of the title of the OP. $\endgroup$ – robert bristow-johnson Mar 7 '18 at 2:29
6
$\begingroup$
  1. Here I expected $y(n)$ is to be computed by convolving $x(n)$ with $h(n)$, but in the equation given by Wikipedia it is shown as a matrix multiplication $y(n) = h^H(n).x(n)$. Are these two operations(convolution and matrix multiplication) same here?.

The system is an FIR system, so the vector multiplication here is equivalent to convolution --- for one time instant output. Note that $x(n)$ is a vector o the current and last $N$ samples of $x(n)$.

  1. Why do we need a Hermitian transpose rather than normal transpose in the above equation?

Because the signal is assumed to be complex.

  1. Cost function is defined as $E\{|e(n)|^2\}$. Why do we need expectation operator here? Why not normal Mean Square Error(MSE)?

Because the error is assumed to be stochastic. We don't want to minimize for one realization, we want to minimize for all realizations.

  1. Does LMS filter converge to all type of input signal?

You don't believe the proof? :-)

Provided the assumptions made by the proof are met, then the LMS algorithm converges for all signals.

The convergence is only convergence in the mean: what can happen is the filter gets close to the optimal value, but bounces around a bit. It's not guaranteed to stay precisely on the optimal value.

The main constraint is on the value of the step size, $\mu$. It needs to be big enough to ensure convergence and small enough to not diverge.

The picture below shows a couple of examples. One where the convergence is slow but steady (low, but high enough $\mu$) and the other where $\mu$ is a little higher where the convergence bounces around a little.

enter image description here

  1. I understand LMS make use of Stochastic Gradient Descent and the update equation for the same is $\hat{h}(n+1)=\hat{h}(n)+\mu x(n)e^*(n)$, what would be the update equation if we would have used a normal Gradient Descent?

The main difference is that stochastic gradient descent uses sample-by-sample updates, rather than a larger data set. See this discussion on Quora for more details.

enter image description here

$\endgroup$
  • $\begingroup$ It would be really helpful if you can answer the followup questions also. (1)You mean x is taken like a sliding window of the same size of h after each step so that both can be multiplied together?. (3) Can you explain what you mean by realization here?. (4)What are the assumptions made by the proof?. Thanks in advance. $\endgroup$ – SAJIL C K Mar 7 '18 at 3:31
  • $\begingroup$ 1) Yes. 2) There is no 2? 3) Noise is stochastic. If you run a test twice, the noise won't be the same in both cases. Each case is a realization. 4) Mainly that you're only proving convergence in the mean (it won't necessarily get to and STAY at the optimal value; it'll bounce around a bit) and you need to ensure that the step size parameter (usually $\mu$) is not too big nor too small. $\endgroup$ – Peter K. Mar 7 '18 at 13:08

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.