5
$\begingroup$

I am working with adaptive filters and similar adaptive models (mainly with gradient adaptation) for a few years. I and my colleagues always struggle to find out the correct size of regression vector.

So far, as I find out by the hard way (experience):

  1. for filtration mostly works well (low MSE) with something about 10-50 last samples, this number changes according to data and used step-size / algorithm.

  2. for prediction the optimal size also depends on data and learning rate. Longer windows (regression vectors) commonly works well and it can be beneficial to skip samples, example:

Example ad 2.

For data where is one really dominant frequency (but changing over time) works for me the vector

$[u(k), u(k-15), u(k-30), u(k-45), u(k-60)]$ (size of 4 samples)

with the same MSE as

$[u(k), u(k-1), ..., u(k-60)]$ (size of 60 samples)

it seems that only what matters is to cover the size of data about 2 last waves of with the most dominant frequency, no matter how much samples was used.

My question

What is applicable theory for this problem (at least possibly)? I am pretty sure there must be some data attributes what can tell how big regression vector is important to get the most from the data. But I do not really now what should I study, or how to search for it.

Any hint or research direction recomendation is welcome. Thanks in advance.

$\endgroup$
0
$\begingroup$

Suppose that you are adapting $w$ to minimize $\text{E}(y[n]-w[n]*u[n])^2$ where $$y[n]=h[n]*u[n]+\nu[n]$$ $y[n]$ and $u[n]$ are known and $\nu[n]$ is an additive noise component. With a long enough FIR filter you can model any linear system $h$ with any accuracy. You can opt for a shorter filter length in expense of limited modelling accuracy. A key parameter is the sampling rate of the signals. If the signals are over sampled unnecessarily then the required length for $w$ increases.

Suppose that we settle for a certain modelling accuracy and we want to find $w$. If all the samples of $u[n]$ are available and $h$ remains constant you can find an estimate of $h$ namely $w$ using a least square estimation. This estimation will have a limited accuracy. But it is the best you can do. This error is referred to as the Least square error which here I (a bit wrongly) consider the same as Mean Square Error (MSE error).

Since $h$ may change, we need to continuously estimate $h$, and that is why we are using the adaptive filters. Let's say that we use the LMS adaptation to find $w$. Now on top of the MSE error we have extra error owing to the way that the LMS adaptation is performed. This error is called misadjustmentis and it is caused by the limited window where $u[n]$ is used in the adaptation. If the LMS step size $\mu$ approaches zero we are including all sample of $u[n]$ in estimation, but then there is no adaptation. It can be proved (Take a look at any adaptive filters book) that misadjustment is proportional to

  1. The filter length
  2. The step size

The other issue is the tracking behavior of the filter. Since $h$ is changing we like to adapt the filter as fast as possible. To increase the adaption speed we can increase $\mu$. To keep the filter stable we should have $\mu<\frac{1}{\lambda_{\text{max}}}$ where $\lambda_i$ are the eigenvalues of the covariance matrix of $u[n]$. The situation is worse if the sample of $u[n]$ are correlated (apparantly your scenario). In this case the covariance matrix has different eigen values and the adaptive filter converges with different modes where the time constant $\tau_i$ for each mode will be $$\tau_i=\frac{1}{2 \mu \lambda_i}>\frac{\lambda_{\text{max}}}{2 \lambda_i}$$ The ratio of largest to smallest eigenvalue $\frac{\lambda_{\text{max}}}{\lambda_{\text{min}}}$ increases as the samples of $u[n]$ become more correlated and the LMS filter becomes slower. Unfortunately the speed cannot be increased idefinitely by increasing $\mu$. Since $\mu$ is limited from above by $\frac{1}{\lambda_{\text{max}}}$.

Back to your case: It seems that your data is highly correlated that is why removing 14/15 of samples does not change the performance that much. Throwing away samples of $u[n]$ can help in your case for the following reasons:

  1. You are decreasing the length of the part that you are adapting. This can decrease the misadjustment.
  2. You are whitening your data by down sampling it. This decreases the eigen ratio and improves the tracking behavior of the filter.
  3. Another issue with highly correlated $u[n]$ is the potential divergence of filter at frequencies where $u[n]$ has almost no component. If $u(e^{j\omega_i})=0$ then $h(e^{j\omega_i})$ can go to infinity if the filter length is infinite. The shorter the filter the least likely that this occurs. This problem however can be solved by introducing leakage.

The negative impact of throwing way samples of $u[n]$ is that your are imposing a certain assumption on $w$. By using only $[u(k), u(k-15), u(k-30), u(k-45), u(k-60)]$ you are assuming that $w$ takes a form like: $$w=[w_0~...~0~w_{15}~0~...0~w_{30}~...~w_{60}]$$ This limits the ability of $w$ to model an arbitrary $h$.

$\endgroup$
  • $\begingroup$ Thanks a lot. You show me some important point. I am trying to process it and understand it. Can you please provide me with reference for more reading about "The eigen ratio increases as the samples of u[n] becomes more correlated and the LMS filter becomes slower. Unfortunately the speed cannot be improved by increasing μ" $\endgroup$ – matousc Feb 23 '17 at 20:22
  • $\begingroup$ You can have a look at the adaptive filters book by Haykin (chapter 9 Least mean square algorithm). My favorite is the book Adaptive filters by Farhang Boroujeni (eu.wiley.com/WileyCDA/WileyTitle/productCd-1119979544.html). I found that the related appendix from the Haykin book is available online freely : onlinelibrary.wiley.com/doi/10.1002/9780470231616.app1/pdf $\endgroup$ – Hooman Feb 23 '17 at 22:04
0
$\begingroup$

With the LMS adaptive algorithm, the degree of adaptation or change to the adaptive filter weights also depends on the scaling of the input vector, x(n). An alternative approach that addresses this dependency on the scaling is the Normalized LMS (NLMS) algorithm. Here the input vector, x(n), is scaled or normalized by its "power".

There is a lot fantastic reference material on adaptive filtering such as the Farhang-Boroujeny and Haykin textbooks (the Farhang-Boroujeny book is definitely the more practical textbook of the two), but an aspect of working with adaptive filters that is often over looked is that it is, in a large number of ways, an art form. I've found that most adaptive filtering problems are different enough from other filtering problems that simulation is necessary.

$\endgroup$
  • $\begingroup$ Thanks, you have got a good point. Data scale (and offset!) Influence the final MSE also. I should specificity in my question that I use (LMS, NLMS, RLS) and use zero mean data with unit variance (or similar). $\endgroup$ – matousc Feb 28 '17 at 19:02
  • $\begingroup$ Just to chime in: I don't come from EE ( more statistics-econometrics. tryhing to self-study DSP as time permits ) but some useful and possibly related material is called "time-varying coefficient regression models". I'm going to look at the books mentioned (thanks for those recommendations) because the discussion sounds eerily familar to me but the technical terms you use are almost totally different. thanks for neat discussion. $\endgroup$ – mark leeds Jan 25 '18 at 4:47
  • $\begingroup$ I think there are a lot of common numerical methods for adaptive filtering that are used in many diverse fields of practice. However, it's the unique terminology of a given field that isolates its methods from other fields of practice. If you are interested in discussing your work, please let me know. $\endgroup$ – Michael_RW Jan 25 '18 at 13:33

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.