# Stochastic approximation algorithm

The goal is to find the FIR filter coefficients $\mathbf{h} = [5;3]$ with the help of the adaptive FIR filter $\mathbf{w}$ of order $p = 2$.

I have implemented the Stochastic approximation algorithm in MATLAB for this adaptive system identification problem.

$\mathbf{w}[k] = \mathbf{w}[k-1] + (1/k) \cdot \mathbf{x}[k] e[k]$

As input sequence I use white gaussian noise with zero mean and variance of 1. Measurement noise is also WGN with variance of 1.

$N = 1000$ ... number of measured datapoints

For the input sequence above my algorithm works fine and converges and I find the right $\mathbf{w}$.

However if I change my input sequence to $x[k] = 0.1 \cdot \cos(\pi k /(N/10))$ my algorithm doesn't find the right coefficients.

So my question is:

Is the Stochastic approximation algorithm restricted to special input sequences, and if so what is the optimal input sequence to use?

• uhm, this is called the LMS Adaptive Filter . you might wanna look that up. dunno why the adaptation gain should be $1/k$. – robert bristow-johnson Jun 14 '17 at 18:41
• I know that it's called LMS. The adaptation gain is a specification i have got for this project – Don Jun 14 '17 at 18:47

The issue is possibly that the input signal you have chosen is not persistently exciting. This means that the signal doesn't "excite" enough modes of the filter in order to be able to accurately estimate its parameters. Another way to think about it is that it doesn't have enough energy in enough places in the spectrum: just at the frequency of the cosine, whereas white noise has energy everywhere in the spectrum.

From the paper:

Recent work (e.g. [1–5]) has shown the convergence and robustness properties of adaptive estimation and control algorithms to be closely related to persistence of excitation of regression vectors (equivalently that they have a sufficient number of spectral lines [5])

To do system identification using a driving function, it is necessary that the driving function $x[n]$ be broadbanded, meaning that the driving function has a Fourier Transform of non-zero value over a broad range of frequencies. The reason for this is that division by zero is a problem.

Think of System Identification in terms of this most basic method:

Driving signal $x[n]$ with DTFT $X(e^{j\omega})$, which is given.

Output signal $y[n]$ with DTFT $Y(e^{j\omega})$, which is measured.

System impulse response $h[n]$ with DTFT or frequency response $H(e^{j\omega})$, which is what you are looking for.

$$y[n] = h[n] \circledast x[n]$$

$$Y(e^{j\omega}) = H(e^{j\omega}) \cdot X(e^{j\omega})$$

This means

$$H(e^{j\omega}) = \frac{Y(e^{j\omega})}{X(e^{j\omega})}$$

You cannot determine $H(e^{j\omega})$ for frequencies $\omega$ such that $X(e^{j\omega})=0$ because you cannot divide by zero. Even if your system identification method is not this simple division, the fact is that at any frequencies where $X(e^{j\omega})=0$, you fundamentally do not have the information you need to derive any information for $H(e^{j\omega})$ at those frequencies.

$$x[n] = A \cos(\omega_0 n)$$
that means $X(e^{j\omega})=0$ for all frequencies other than $\omega = \pm \omega_0$. You might be able to get away with driving function having zero energy for a few discrete frequencies, but this driving function is zero for all frequencies other than a couple. Your system identification cannot tell you anything about the system other than what it does at a single real frequency of $\omega_0$.