Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a digital signal which may be represented as noise filtered with an FIR (finite impulse response) filter. Let us suppose that the noise consists of pulses (nonzero samples on a zero background), and there is an equal probability of a pulse at any sample (so for example the number of pulses in an interval follows the poisson distribution). Further suppose the strength of each pulse is equal.

The question: Can the coefficients of the FIR filter be recovered from the filtered signal, and how?

Now assume the noise is impulsive, but may be somewhat correlated with itself (it doesn't have perfect Poisson statistics). Also assume that the strength of each pulse may vary. Can the coefficients be recovered approximately if the exact distribution of noise is not known?

Formal notation.

Noise N[i] where i=0..n, N[i] = 1 with some probability p, 0 otherwise; each N[i] is independent of other N[i]

Filter F[k] where k=0..m, m << n, unknown

Signal S[i] where i=0..n

S = N * F, where * is convolution

Given S, estimate F. N and p are also unknown.

To give this some practical background, the average period between noise pulses can be 20-40 samples, the FIR filter can have a few hundred nonzero coefficients (so the filtered signals resulting from each pulse overlap significantly), and the total signal is a few thousand samples.

share|improve this question
    
There's a signal processing StackExchange (still in beta) you could ask at if you don't get good answers here. –  Rahul Jan 22 '13 at 21:15
    
A theoretical answer to your first question is that if you are very unlucky and there does not arrive any pulses during you period of observation you will not be able to tell anything about the filter. So you cannot be certain that you will be able to recover the filter coefficients. –  Johan Jan 28 '13 at 10:00

3 Answers 3

Given the problem as stated, there is not enough information to determine $f$ exactly. If we use capital letters for the frequency domain and lower case for the time, then you have $S = F \cdot N$, which is one equation and two unknowns. There are of course uncountably many combinations of $F$ and $N$ which will give $S$.

However, since you know the expected form of $N$ from your model, you can at least draw some conclusions about $f$ by looking at $\vert S \vert / \vert N \vert $. Furthermore, if you restrict $f$ to be real and even, then $F$ will also be real and even. This means that you can ignore the phase of the frequency samples and recover the filter using $f = \mathcal{F}^{-1}\left( \vert S \vert / \vert N \vert \right)$ as long as $N(\omega)\neq0$ for all $\omega$.. Of course, you need $N$ to do this. If possible, one usually tries to find the Fourier transform of the autocorreation sequence of $n$, which will yield $\vert N \vert$. However, if that is not possible, you may be able to model $\vert N \vert$ by generating several instantiations of noise sequences and then curve-fitting (or whatever you find to be most appropriate) to their spectral magnitudes.

share|improve this answer

The term for this is "deconvolution". I'm not sure that helps much (but see Wiener deconvolution ).

Consider the formulation as an inverse problem:

$\qquad$ min $|Ax - b|^2 + \lambda |x - x_0|^2$ where
$\qquad A = N $ noise, how long ?
$\qquad x = F $ filter coefficients ~ 100
$\qquad b = S $ signal ~ 3000
$\qquad x_0 = $ coefs you want $x$ to be near to.

(Most solvers take $A(x)$ as a linear function, in your case convolution -- an $A$ matrix need not be instantiated.)

Now it looks as though $x$ is waaaay underconstrained -- $\mathbb{R}^{100}$ is big. So you'll have to constrain a.k.a. regularize $x$, get down to a say 10-parameter subspace that people can understand. I'm no expert, but a couple of ways of regularizing:

  • obviously, if you have a reasonable $x_0$, high-weight the term $|x - x_0|$
  • choose a suitable basis, Fourier ... with rapidly-decaying coefficients
  • add a smoothness constraint $|L (x - x_0|$ (but some solvers do only $L = I$)
  • L1 regularization, which nudges many $x_i$ to 0; see Lasso.

It seems to me (non-expert) that different problem areas use different regularization methods -- one size cannot fit all. Can anyone suggest an overview, or a testbench for different methods ?

share|improve this answer

As I already noted it is possible (though unlikely) that there is no noise at all and thus you do not learn anything about the signal.

A more practical problem is that unless $N[0]=1$ you will not be able to determine if $F[0] =0$. For if you take a $N$ with $N[0]=0$ and translate that vector to the left, setting $N[n]=0$, and translate $F$ to the right, setting $F[0]=0$, you will leave the output unchanged.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.