2
$\begingroup$

I'm looking construct a stable pole-only filter where the feedback coefficients start with a block of zeroes, i.e.

\begin{align} a_0 &= 1\\ a_i &= 0, \textrm{ for}\ 1 \le i \lt k\\ a_i &\in\mathbb{R}, \textrm{ for}\ k \le i \le n \end{align}

For $k = n$, this is a single-tap feedback delay, e.g.

$$ y_i = x_i + a_k y_{i - k} $$

which is stable as long as $|a_k| < 1$.

However, I'm looking for a way to construct such filters with arbitrary $k$ and $n$. Are there conditions or constraints that would let me construct this?

$\endgroup$
  • 2
    $\begingroup$ A notational note: the feedback coefficients are usually denoted as $a_k$, while the feedforward coefficients (the numerator of the transfer function) are $b_k$. Just pointing it out to avoid confusion. $\endgroup$ – Jason R Nov 14 '17 at 14:44
  • 1
    $\begingroup$ An easy solution would be to take any stable polynomial with roots within the unit circle and replace $z$ with $z^k$. Your single step would also be an example of this. However this will mean that between every none zero coefficient you get $k-1$ zeroes. $\endgroup$ – fibonatic Nov 15 '17 at 6:04
  • $\begingroup$ @JasonR - thanks, I got turned around there. $\endgroup$ – cloudfeet Nov 15 '17 at 14:32
  • $\begingroup$ @fibonatic - yeah, I was hoping it would be "dense" (for some hand-wavy definition of that). That's a neat trick, though. $\endgroup$ – cloudfeet Nov 15 '17 at 14:32
  • $\begingroup$ @JasonR I couldn't say the same, as I found out that some use a/b, others b/a. Personally, I learned a/b, both in mathematics and filters, so this may be a case of preference, or previous learning. $\endgroup$ – a concerned citizen Nov 16 '17 at 7:55
0
$\begingroup$

OK, so this is a bit of an intuitive argument so I'm not 100% sure about it, and it's totally sideways to the way I normally think about filters, but:

Let's consider the "feedback kernel" ($a_k ... a_n$ - so, not including $a_0$) as an FIR filter. If the magnitude of that kernel in the frequency domain is $< 1$ including inter-bin peaks, the original filter should be stable.

If so: to construct a filter: one could generate a random set of $a_k ... a_n$, find the maximum freq response of that feedback kernel, and scale such that the peak is less than 1, to get a stable feedback kernel.


To reason about this: let's construct an infinite sequence of sequences, $Y^k$:

$$ Y^0_i = a_0x_i\\ Y^j_i = -\sum_{l=k}^na_lY^{j - 1}_{i - l} $$

That is, each $Y^j$ is the previous $Y^{j - 1}$ convolved with our feedback kernel (the negation doesn't affect the argument). I also think it's true that:

$$y_i = \sum_j Y^j_i$$

Let's say $x_i$ is "time-bounded" (zero outside a finite range) - it follows inductively that every $Y^j$ is also time-bounded, because it's a convolution of the previous.

Let's also say that the feedback kernel's transfer function has magnitude $< G$ for all frequencies. This guarantees that whatever the input, the total energy in each $Y^k$ is strictly less than $G$ times the previous one. This implies a geometrically-decreasing upper bound on the magnitude of the sample values of $Y^j$ as well.

This geometric progression of bounds means that when we sum up $y_i$ it converges if $G < 1$, and to a value bounded by $K/(1 - G)$ for some $K$. The time-boundedness means that it decays over time (hand-waving over the formalism here).


Does this hold up?

$\endgroup$
  • $\begingroup$ Why do you think that the peak frequency domain magnitude of the $z$- transform of the denominator polynomial is related to stability? What's important is the root locations of the denominator polynomial. They must all be within the unit circle. $\endgroup$ – Jason R Nov 15 '17 at 14:32
  • $\begingroup$ Not the whole polynomial (including $a_0$) - I'm looking at the kernel produced by removing $a_0$. It's a bit of a weird argument which focuses largely on the time-domain, which is why I'm unsure about it. $\endgroup$ – cloudfeet Nov 15 '17 at 14:34
  • $\begingroup$ Hi: assuming my notation interp is correct ( my backgound is not EE so I didn't understand the other answers which doesn't mean they're wrong ), what you wrote is actually a delayed exponential smoothing model: $y_{t} = \sum_{i=0}^{\infty} a_{k}^{i} x_{t-k-i}$. Someone named juancho gave a beautiful EE explanation of this model. I wouldn't do it justice so I'll find the link. it's below. dsp.stackexchange.com/questions/33858/…. But it sounds like you may want something more complex with more than one parameter. $\endgroup$ – mark leeds Jul 14 '18 at 9:59
  • $\begingroup$ Last thing and still only matters if you're interested: Note that my notation changed your $i$ to $t$ and my $i$ took on a different meaning. $\endgroup$ – mark leeds Jul 14 '18 at 10:12
  • $\begingroup$ Notice that models are not quite equivalent because the link I referred to considers the case where the coefficients sum to 1. but the concept is the same and equivalence can be obtained by introducing a second parameter to your model. if interested, google for "koyck distributed lag". $\endgroup$ – mark leeds Jul 14 '18 at 10:18
0
$\begingroup$

You are looking for a polynomial of the form

$$ p(x) = x^n + \sum_{m = 0}^{n-k-1} a_m\,x^m \tag{1} $$

whose roots lie inside the unit circle. For a sufficiently large value for $|x|$ the $x^n$ term will always dominate over all the other terms. Since $|x^n| \neq 0$ for $|x|$ larger then this sufficiently large value, therefore $|p(x)| \neq 0$ for these values of $x$ as well. This implies that all the roots of $p(x)$ need to be contained inside this region of $|x|$ smaller then this sufficiently large value.

So in this case we want this region to be the unit circle, so at $|x| = 1$ the term $x^n$ should dominate. An upper bound at $|x| = 1$ for absolute value of the sum of the remaining terms would be $|\vec{a}|_1$; the 1-norm of the vector containing the coefficients of $a_m$ from $(1)$. So as long as $|\vec{a}|_1 \ll 1$ one can be sure that $(1)$ does not have any roots outside the unit circle. For this you can start with any vector $\vec{v}$ and scale it using

$$ \vec{a} = \alpha\frac{\vec{v}}{|\vec{v}|_1} \tag{2} $$

with $0<|\alpha| \ll 1$.

This does not really use the fact that there are $k-1$ zero coefficients. I suspect that as $k$ becomes larger the constraint $|\vec{a}|_1 \ll 1$ (and thus $|\alpha| \ll 1$) can become less and less strict, since $x^n$ starts to dominate faster. At least for $\vec{v}$ generated from a Gaussian distribution $\alpha = 0.9$ seems to work for a very large majority, at least for the combinations $n$ and $k$ that I tested.

$\endgroup$

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.