# Which algorithm would you choose?

Started by April 8, 2011
```Say you have two signals, x and y, where y is the output of an unknown
FIR filter. The only thing which is "known" about the FIR filter is
that it has N filter coefficients.

The above relates to acoustic echo cancellation for speech signals
sampled at 8kHz. I guess you can call it a channel estimation problem?
Or a deconvolution problem? I don't know....

Anyways....As a pre-liminary experiment I tried the following (in
MATLAB):

clc
close all
clear all

N = 40;
x = randn(1,100);
b = fir1(N-1,0.9);
y = filter(b,1,x);

est_b = filter([y zeros(1,N-1)], x, [1 zeros(1,N-1) zeros(1,150)]);

figure
subplot(3,1,1)
plot(x)
subplot(3,1,2)
plot(y)
subplot(3,1,3)
plot(b)
hold on
plot(est_b(1:N),'r--')
drawnow

The estimate est_b of the filter coefficients b is good, but sometimes
it fails..

Can anybody explain why this happens?

I wasn't able to see a pattern for the failures.

Another question to you is: Which algorithm would you choose for an
adaptive acoustic echo canceller for an embedded platform? There are
probably lots of factors to consider, but just give me the names of a

Thank you.

```
```I think what you are running into is that there are conditions on the origi=
nal data x, and the filter b that must be met for the channel identificatio=
e must be some conditions under which the system is ill conditioned.

A naive example is when x is all zeros. Then you have no hope of recovering=
the original filter. More generally, there are a set conditions on x and b=
that must be met for b to be recoverable. Blind deconvolution literature t=
alks about "source diversity." I'm a bit rusty with the details, but it's s=
omething along the lines of requiring the source to have no nulls in its sp=
ectrum.

Chris
```
```On Apr 8, 9:20=A0pm, John McDermick <johnthedsp...@gmail.com> wrote:
> Say you have two signals, x and y, where y is the output of an unknown
> FIR filter. The only thing which is "known" about the FIR filter is
> that it has N filter coefficients.

Wrong problem statement. You will need to know (or assume)
something more, like that the process under study is an
AR process, a sum-of-sines process, or something like that.

In these cases the best you can come up with is a *limit*
on N, not the exact parameter.

...
> Can anybody explain why this happens?
>
> I wasn't able to see a pattern for the failures.

The pattern is that you use a defunct algorithm.

> Another question to you is: Which algorithm would you choose for an
> adaptive acoustic echo canceller for an embedded platform? There are
> probably lots of factors to consider, but just give me the names of a