Research Showcase   

 

Unequal Order Inverse of a Matrix Polynomial

Why Inverse:   In signal processing, exact inverse of a filter or filterbank is desirable, such that the filtering operation may be exactly undone. Typical (FIR) filtering is represented by multiplication with a polynomial (in the z-transform domain, a signal X(z) is multiplied by a filter transfer function H(z), a polynomial in z). For example, let the filter be a constant 2. Since

 

its inverse is 0.5. We know that, if we have access to infinite precision, then inverse exists for any non-zero scalar constant. But constants can’t give useful filters. Extending to polynomials, let the filter be . Its inverse is

since rational functions of polynomials are also (IIR) filters. However, IIR filters have stability issues and non-linear phase, so they are not so popular. For example, image processing uses linear phase filters.

FIR Inverse:   Can we find inverse of a polynomial which is a polynomial? Unfortunately, it is only possible in the trivial case of non-zero monomial, such as

since Laurent polynomials, used in signal processing, may have both positive and negative powers. But monomials are no better than constants as a filter. While non-trivial FIR inverse is not possible for filters, fortunately, it is possible for filterbanks. Filterbanks are multi-dimensional extensions of filters. The input signal is not one-dimensional but M-dimensional (obtained from a one-dimensional signal using a serial to parallel conversion, known in multirate parlance as delay chain followed by decimators). The filter becomes a M x M matrix polynomial (known as polyphase matrix). For the constant matrix case, it is obvious that any non-singular matrix has an (FIR) inverse. How about a true matrix polynomial? It turns out that it is indeed possible for a matrix polynomial to have an FIR inverse (inverse which is also a matrix polynomial), as the following example will convince you.

Filterbanks are typically designed using a cascade of such matrix polynomials, known as lattices or building blocks, to achieve longer length filters with desirable shapes.

Existing Methods:   How does one come up with such a matrix polynomial? Since mid-nineties, many methods have been proposed. These mostly fall under 2 categories. In the unimodular category, choose H(z)=I+B(z) such that . Its inverse is

since . For example, since , let , and you have the following matrix polynomial with FIR inverse:

In the matrix polynomial diagonalization category, choose H(z)=A.D(z).C where D(z) is a diagonal matrix with FIR inverse, and A and C are constant non-singular matrices. An example is given below.

Order of the Inverse :   These existing methods produce equal order inverse. In all 3 examples above, note that the order of H(z) is 1, and the order of its inverse is also 1. As a result, in existing filterbanks, the synthesis filter lengths are equal to the analysis filter lengths. Some applications prefer unequal length filterbanks. Can we find a matrix polynomial whose inverse has unequal order? The answer is an emphatic YES! As early as in 2001 we showed such filterbanks in Reference. But here we take a simple example.

In the unimodular category of methods above,  was used to curtail the infinite inverse expression to a few terms, so that FIR inverse exists. By choosing  (n is called the nilpotency of B(z)), the same effect will be achieved, but with more terms (hence higher order) in the inverse. Using n=3 such as , we find

where the inverse order is 2, different from the forward order of 1.

Our Approach – UND:   Rather than using higher value of nilpotency, we use appropriate sequencing of maximally sparse building blocks to obtain unequal order inverse. Our building block, the unit non-diagonal (UND) matrix polynomial, has all 1’s in its diagonal, 0 everywhere else, except a lone α(z) somewhere (except at the diagonal). UND has FIR inverse of equal order:

where the blank locations are 0. The order of an UND is equal to the order of α(z). How may equal inverse order UNDs provide unequal inverse order? Let us multiply 2 UNDs.

If both α(z) and β(z) has order 1, then the forward order is now 2. Its inverse is

which is, surprise surprise, just order 1. So we indeed have an unequal order inverse.

What More Do UNDs Offer:   The following schematic shows the possible forward and inverse orders that exist (assuming α(z) has order 1, and without repeating UNDs) in red/green. Green shows those order combinations for which we have proposed specific design methods. Notice some random green locations that may be achieved by UND based design without a systematic procedure.

For the sake of completeness, we also propose unit diagonal matrix polynomials. Using these building blocks, we show how filterbanks with desired forward and inverse order may be designed. We also show that any triangular unimodular matrix may be factorized into UNDs, and hence show that this design method is complete. Further, any desired filterbank delay among all possible delays is also achievable in this design. Application of such filterbanks to audio has also been demonstrated.

Reference 1, Reference 2 ,  Reference 3