# Can LMS filter converge to sparse solution?

Consider received signal $r=h*s$, where $h$ is the channel and $s$ is transmitted signal. Now from $r$ ( $s$ is known) can we predict $h$ using LMS algorithm under all conditions? I was under impression that both $s$ and $h$ needs to be stationary to estimate $h$ properly. In case, $h$ is sparse (few non zero only) LMS cannot converge to sparse $h$. Is it true or false? Can someone explain my doubt pleas?

• Can I please ask how do you define "stationary"? It doesn't look like $h(t,n)$ (for example) to denote that the channel changes with time (?). – A_A Feb 26 '17 at 22:07
• en.wikipedia.org/wiki/Stationary_process I was expecting each sample of h need to be i.i.d. But if only few are non-zero how can it be iid? – Creator Feb 26 '17 at 22:12

...can we predict $h$ using LMS algorithm under all conditions?

LMS converges under most "reasonable" conditions.

The weights of the filter are adapted by a "signal" that is derived by the mean square error of the difference between two signals, which is convex. That is, it has a single minimum (when it does) and it will trickle towards it. If you notice the formula by which each weight is adapted, it does not include a cumulative term. It is just adapting the weights by the magnitude of the error. Therefore, it is supposed to "track" the situation smoothly until it eliminates the difference that is driving it. But if you now crank the $\mu$ up, it will be overshooting that single "minimum" in either side and it will go into "oscillations". Not in the "system is unstable and it is now whistling" sense but in the way that the logistic map goes into "oscillations"

I was under impression that both s and h needs to be stationary to estimate h properly.

They would have to be stationary for the weight adjustment process to "converge". Otherwise, it will keep "hunting".

In case, h is sparse (few non zero only) LMS cannot converge to sparse h. Is it true or false?

It is false...most of the times.

Given a reasonable choice for the learning parameter $\mu$ and enough time, LMS will converge to something. But, there are two "problems" that will affect your $h$ estimate: The fact that there is noise and the weights will be trying to minimise even that and the fact that you estimate $h$ from a small window in time. Therefore, the signal(s) better have exhausted the full repertoir of their variance within that window, otherwise, LMS will be "hunting" (smoothly, or wildely) around the minimum again.

Here is an example: $h_{channel}$ is innocent, maybe $h_{channel} = [1,0,0,0,0,0,0,0,0]$. You start with some random $h_{predicted}$ and feed through a sinusoid. The filter will now start adapting. Through the first few iterations, you get totally random "guesses". But there will be one guess, purely because of chance, that a coefficient will land higher than the rest. LMS will pick this up immediately and start improving on it. In the end, it will converge to something that looks like $h_{channel}$, if only the noise perturbations were not there. So, your $h_{predicted}$ is not going to look exactly like $h_{channel}$ with a few strong returns to show reflections and zeros in between, it will still have some values interdispersed with the strong reflections.

Try to think "vertically" into the coefficients of $h_{predicted}$. Because the LMS is like an Automatic Gain Control "Bank". LMS doesn't optimise the "filter" as a whole (i.e. looking at it "horizontally", as one $h$). It uses the error signal to tune each filter coefficient separately and through convolution it applies the effect of each one on the signal. Try to work out LMS, by hand, with a two coefficient $h$ to see what I am trying to say with this.

Hope this helps.

EDIT:

I am adding this small "post script" here, given the additional information that was provided in the comments.

It seems that what is sought after is the impulse response of a "corridor" over the medium of Radio Frequencies.

Depending on the room size, its construction and frequency of operation, the system will not even have the chance to "resolve" between returns.

A nanosecond of propagation at the speed of light is about 30cm of "distance". The distinct pulses that are expected here, with large intervals of "silence" between them, will pile up into "averages", creating a "complex" $h$. That $h$, by the way, is not going to be stationary, depending on the building construction, because you cannot control what the RF is bouncing off of OUTSIDE the limits of the corridor.

You might be better off with a slow chirp to obtain the frequency response of the channel (assuming that this is what you are after).

Hope this helps

• Thank you, you are confirming that signals has to be stationary for the weight to converge. In other words if the transmit signals is chirp it won't converse? I do understand the claim of convergence but it is very much function of h, is not it? – Creator Feb 27 '17 at 17:02
• @Creator you are welcome. If you are sending chirps, why use LMS for the identification? Also, you seem to be in control of the channel and experimental conditions, so why not excite it with a spike and observe the $h$ directly? – A_A Feb 27 '17 at 18:14
• My purpose of this question is to understand the issues. Sorry, I do not understand what do you mean by 'control of the channel' . I do not know the channel, I want to estimate, only assumption is it may be sparse. – Creator Feb 27 '17 at 18:38
• @Creator, I mean that you have the ability to take measurements. Can I ask what your channel is? – A_A Feb 27 '17 at 23:18
• My channel is indoor hall, room place. – Creator Feb 28 '17 at 7:36

As you know LMS is an adaptive filter which tries to find, during its recursions, a best filter that approaches the theoretically computed optimal Wiener solution of an associated normal equation under a given probabilistic framework. Its adaptivity means that it has the ability to track a nonstatinory environment (in addition to stabilize in stationary one).

However its tracking is limited just like, but more than, every other adaptive filter's is so. The tracking nature of the basic LMS filter is affected by the step-size parameter which offers a trade-off between the steady state estimation error vs tracking performance. The better (faster) it tracks the more error there will be in the estimation until it becomes useless.

In addition, due to the simplicity of its update mechanism, the LMS filter's tracking is quite slow and therefore requires a quite slowly changing statistics for any successful tracking. For much better tracking abilities there exists RLS and Kalman filters, that you can consider, which use more computation but provide much faster convergence.

Finally, the performance under sparse signals would follow the above simple guidelines: if the sparsity causes faster than allowable nonstationarities, then the LMS filter will not be successful; divergent.

Increasing the signal sampling rate may help to overcome the divergence problem at the expense of increased computational cost. Furthermore, there exists modified LMS algorithms that may take advantage of refinements and adaptivities to implement track and settle strategies based on the output feedback models that may potentially improve your results.

• I am interested know if 'h' is like number of multi-path and assume there are only few, how LMS can predict those sparse solution? – Creator Feb 26 '17 at 23:27
• in what configuration are you using the LMS filter? – Fat32 Feb 26 '17 at 23:31
• channel estimation – Creator Feb 26 '17 at 23:45
• you mean system identification configuration applied for channel estimation. in your multipath channel model the impulse response $h$ may become sparse, but it doesn't mean nonstationary alone. So Just select order of LMS high enough. – Fat32 Feb 26 '17 at 23:56
• Thank you for your support. May I ask why it does not mean non-stationary? Please – Creator Feb 27 '17 at 0:04