AAK Theorem and a Design of Multidimensional BIBO Stable Filters

Bossoto Bossoto^*, Gabriel Bissanga

Faculty of Sciences and Technology, Marien Ngouabi University, Brazzaville, Congo.

DOI: 10.4236/ojdm.2024.142002                

Abstract

Rational approximation theory occupies a significant place in signal processing and systems theory. This research paper proposes an optimal design of BIBO stable multidimensional Infinite Impulse Response filters with a realizable (rational) transfer function thanks to the Adamjan, Arov and Krein (AAK) theorem. It is well known that the one dimensional AAK results give the best approximation of a polynomial as a rational function in the Hankel semi norm. We suppose that the Hankel matrix associated to the transfer function has a finite rank.

Keywords

Multidimensional Filter, Design, BIBO Stability, Optimal, AAK Theorem, Transfer Function, Hankel Matrix

1. Introduction

Multidimensional filters are central elements in digital signal processing and control systems.

Consider a n dimensional (nD) filter S with an analytic transfer function

$H\left(z_1,\cdots ,z_n\right)={\displaystyle \underset{\alpha \in {\mathbb{Z}}^n}{\sum }}{h}_{\alpha }{z}^{\alpha }.$ (1)

The sequence ${\left\{h_{\alpha }\right\}}_{\alpha \in {\mathbb{Z}}^n}$ is the so called impulse response of the filter.

To avoid burst in a filter, stability is a necessary condition. For instance, the filter S is BIBO stable if for any bounded input signal x, the output y is bounded. A fundamental theorem states that S is BIBO stable if and only if

${\displaystyle \underset{\alpha \in {\mathbb{Z}}^n}{\sum }}{h}_{\alpha }<\infty .$ (2)

However, only a rational filter (filter having a rational transfer function) is physically realizable. Under some assumptions, the filter S is rational and BIBO stable if and only if all poles of H lie in the unit polydik

${\mathbb{D}}^n=\left\{z\in {ℂ}^n,\left|z_i\right|<1,i=1,2,\cdots ,n\right\}$ (see [1] [2] for example).

Note that BIBO stability has also been studied in the consensus coordination of control systems [3] [4] .

Given the significance of rational approximation theory in signal processing and systems theory, during the last years several mathematicians have been researching the problem of approximating multivariate functions (see for example [5] [6] [7] ). One can also cite the works of Avilov and all [8] through the method of Padé-type extended to several variables and recently Austin and all [9] by discrete least-squares methods.

We propose in this paper to introduce a possibility to design multidimensional BIBO stable Infinite Impulse Response (IIR) filters as realizable filters thanks to the one dimensional AAK (Adamyan, Arov and Kreĭn) theorem [2] . To our knowledge such approach does not exist in the literature. We are concerned with filters S such that the multidimensional transfer function $H\in ℂ\left[z_1\mathrm{,}\cdots \mathrm{,}{z}_n\right]$ may be written as a combination (sum or product) of separable polynomials. We assume that the Hankel operator associated to H has a finite rank.

It is known that the AAK theorem gives the best approximation of a univariate polynomial as a rational function in the Hankel semi-norm. A remarkable contribution of AAK’s result is its significance to engineering. One of its important applications is the problem of system reduction which consists of finding a lower-dimensional linear system to approximate a given high-dimensional linear system in a certain optimal sense. The AAK result provides a wonderful characterization of this problem in sense that the Hankel norm of the error between the given high-order transfer function and the approximant is minimized over all transfer functions of the same (lower) order (see [2] for an overview on the topic). The origins of the AAK method can be founded in the papers by Adamyan-Arov-Kreĭn [10] [11] . One can cite also the following paper [12] .

Outline

This paper is organized as follows. Section 2 provides some explanations on the system reduction problem and preliminaries on AAK theorem for one dimensional (1D) filters. In Section 3, we propose rational optimal approximations of the transfer functions of a multidimensional (nD) filter by our approach based on AAK results.

2. Preliminaries on AAK Theorem on 1D Filters

Consider $H\left(z\right)={\displaystyle \underset{n=0}{\overset{\infty }{\sum }}}{h}_n{z}^{-n}$ , the transfer function of an 1D filter. The Hankel matrix corresponding to $H\left(z\right)$ is the infinite matrix ${\Gamma }_H={\left[h_{\mathcal{l}+m-1}\right]}_{\mathcal{l}\mathrm{,}m=\mathrm{1,2,}\cdots }$ , namely

${\Gamma }_H=\left(\begin{array}{cccc}{h}_1& h_2& h_3& \cdots \\ h_2& h_3& \cdots & \cdots \\ h_3& \cdots & \cdots & \cdots \\ \cdots & \cdots & \cdots & \cdots \end{array}\right).$ (3)

The matrix ${\Gamma }_H$ can be viewed as an operator on the space of square summable sequences ${\mathcal{l}}^2$ . The operator norm of ${\Gamma }_H$ is given by

${\Vert {\Gamma }_H\Vert }_s:=\underset{{\Vert x\Vert }_{{\mathcal{l}}^2}=1}{\sup }\Vert {\Gamma }_{H}x\Vert$ (4)

and one defines the Hankel semi-norm of $H\left(z\right)$ by

${\Vert H\left(z\right)\Vert }_{\Gamma }={\Vert {\Gamma }_H\Vert }_s\mathrm{.}$ (5)

If $h_0=0$ , then ${\Vert {\Gamma }_H\Vert }_s$ is the spectral norm of the operator ${\Gamma }_H$ .

Note that the terms

$H_a\left(z\right)=h_0\text{and}{H}_s={\displaystyle \underset{n=1}{\overset{\infty }{\sum }}}{h}_n{z}^{-n}$

are called the analytic and the singular part of $H\left(z\right)={\displaystyle \underset{n=0}{\overset{\infty }{\sum }}}{h}_n{z}^{-n}$ .

For a positive integer m, let

${\mathcal{H}}_m=\left\{\text{Hankel}\text{matrix}\Gamma ;\Vert \Gamma \Vert <\infty ,\text{rank}\Gamma \le m\right\}\mathrm{.}$ (6)

The problem stated as follows:

${\Vert {\Gamma }_H-{\hat{\Gamma }}_m\Vert }_s=\underset{{\Gamma }_m\in {\mathcal{H}}_m}{\inf }{\Vert {\Gamma }_H-{\Gamma }_m\Vert }_s$ (7)

is called system reduction for the filter [2] and is equivalent to the extremal problem

${\Vert H-{\hat{r}}_m\Vert }_{\Gamma }=\underset{r_m\in {\mathcal{R}}_m^s}{\inf }\Vert H-r_m\Vert$ (8)

with

${\mathcal{R}}_m^s\mathrm{<mo>\; :\; </mo>}=\left\{r_d\left(z\right)=\frac{p_1{z}^{d-1}+\cdots +p_d}{z^d+q_1{z}^{d-1}+\cdots +q_d}\mathrm{<mo>\; ;\; </mo>}\text{all}\text{poles}\text{of}{r}_d\left(z\right)\text{lie}\text{in}\left|z\right|<\mathrm{1,}d\le m\right\}\mathrm{.}$ (9)

The following theorem makes a connection between the system reduction problem and the approximation of a polynomial as a rational function.

Theorem 1 ( [2] , Kronecker’s theorem). The infinite Hankel matrix ${\Gamma }_H$ has finite rank m if and only if the singular part $H_s$ is a strictly proper rational function in z i.e.

$H\left(z\right)={\displaystyle \underset{n=0}{\overset{\infty }{\sum }}}{h}_n{z}^{-n}=h_0+\frac{p_1{z}^{m-1}+\cdots +p_m}{z^m-c_m{z}^{m-1}-\cdots -c_1}.$ (10)

Moreover,

Corollary 1 (Kronecker Nehari result, [2] ). The function

$H\left(z\right)={\displaystyle \underset{n=1}{\overset{\infty }{\sum }}}{h}_n{z}^{-n}$

is in ${\mathcal{R}}_m^s$ if and only if its corresponding Hankel matrix ${\Gamma }_H$ is in ${\mathcal{H}}_m$ .

Definition 1. Let $\Gamma$ be a Hankel matrix and ${\Gamma }^{\mathrm{<mo>\; *\; </mo>}}$ its adjoint.

The s-numbers (or singular values) of $\Gamma$ are the eigenvalues of $\left|\Gamma \right|={\Gamma }^{\mathrm{<mo>\; *\; </mo>}}\Gamma$ .

Any pair $\left({\xi }_m\mathrm{,}{\eta }_m\right)$ of elements in ${\mathcal{l}}^2$ that satisfies

$\Gamma {\xi }_m=s_m{\eta }_m\text{and}\Gamma {\eta }_m=s_m{\xi }_m$

is called a Schmidt pair of $\Gamma$ .

One denotes by $L^{\infty }\left(\left|z\right|=1\right)$ the espace of essentially bounded functions on the unit circle $\left|z\right|=1$ . Then

Theorem 2 ( [2] , Adamjan, Arov, and Krein theorem). Let $f\left(z\right)$ be a given function in $L^{\infty }\left(\left|z\right|=1\right)$ such that the Hankel matrix ${\Gamma }_f$ associated to f is a compact operator with s-numbers $s_1\ge s_2\ge \cdots \ge s_{\infty }=0$ and let

$\left({\xi }_m={\left\{u_i^{\left(m\right)}\right\}}_{i=1,2,\cdots },{\eta }_m={\left\{v_i^{\left(m\right)}\right\}}_{i=1,2,\cdots }\right)$ , the Schmidt pair corresponding to $s_m$ . Then a solution to the extremal problem

${\Vert f-{\hat{r}}_m\Vert }_{\Gamma }=\underset{r\in {\mathcal{R}}_m^s}{\inf }\Vert f-r\Vert$

is given by the singular part ${\left[\hat{h}\left(z\right)\right]}_s$ of

$\hat{h}\left(z\right)=f\left(z\right)-s_{m+1}\frac{{\displaystyle \underset{i=1}{\overset{\infty }{\sum }}}{v}_i^{\left(m+1\right)}{z}^i}{{\displaystyle \underset{i=1}{\overset{\infty }{\sum }}}{u}_i^{\left(m+1\right)}{z}^{i-1}}$ (11)

A detailed proof of this theorem has been made in [2] .

3. Approximation of the Transfer Function of an (nD) BIBO Stable Filter

Definition 2: We say that a polynomial $r\in ℂ\left[z_1\mathrm{,}\cdots \mathrm{,}{z}_n\right]$ is stable if

$r\left(z_1,\cdots ,z_n\right)=0\text{only}\text{for}\left|z_1\right|<1,\cdots ,\left|z_n\right|<1.$

Let ${\mathcal{R}}_m^n$ be the set of rational polynomials in $ℂ\left[z_1\mathrm{,}\cdots \mathrm{,}{z}_n\right]$ with stable denominator and such that the degrees of the numerator and denominator do not exceed m.

One has the following result.

Proposition 1: Suppose that

$H\left(z\right)={\displaystyle \underset{\alpha \in {\mathbb{N}}^n-\left\{\mathrm{0,}\cdots \mathrm{,0}\right\}}{\sum }}{h}_{\alpha }{z}^{\alpha }$ (12)

is the transfer function of a multidimensional (nD) BIBO stable filter such that

1) $H\left(z_1\mathrm{,}\cdots \mathrm{,}{z}_n\right)=H_1\left(z_1\right)\times \cdots \times H_n\left(z_n\right)$ ,

2) For each $i=\mathrm{1,2,}\cdots \mathrm{,}n$ , $H_i$ is a polynomial in $L^{\infty }\left(\left|z\right|=1\right)$ ,

3) The operators ${\Gamma }_{H_i}$ are compact operators with finite ranks $R_i\le m$ .

Then an optimal approximation of H as a rational function in ${\mathcal{R}}_m^n$ is given by

${\left[\hat{h}\left(z_1\mathrm{,}\cdots \mathrm{,}{z}_n\right)\right]}_s={\left[{\hat{h}}_1\left(z_1\right)\right]}_s\times \cdots \times {\left[{\hat{h}}_n\left(z_n\right)\right]}_s\mathrm{,}$ (13)

the elements ${\left[{\hat{h}}_i\left(z_i\right)\right]}_s$ being the singular parts of a certain polynomial function ${\hat{h}}_i$ .

Remark 1: If the hypothesis one in the proposition 1 is replaced by

$H\left(z_1\mathrm{,}\cdots \mathrm{,}{z}_n\right)=H_1\left(z_1\right)+\cdots +H_n\left(z_n\right)\mathrm{,}$

then

${\left[\hat{h}\left(z_1\mathrm{,}\cdots \mathrm{,}{z}_n\right)\right]}_s={\left[{\hat{h}}_1\left(z_1\right)\right]}_s+\cdots +{\left[{\hat{h}}_n\left(z_n\right)\right]}_s\mathrm{.}$

Proof. The existence of such approximation of the (nD) transfer function H (in ${\mathcal{R}}_m^n$ ) given in Equation (12) is certified by the Kronecker-Nehari result applied to each $H_i$ . The Formula (13) is given by the application of the AAK theorem to each polynomial $H_i$ and for each $i=\mathrm{1,2,}\cdots \mathrm{,}n$

${\hat{h}}_i\left(z_i\right)=H_i\left(z_i\right)-s_{m+1}^i\frac{{\displaystyle \underset{j=1}{\overset{\infty }{\sum }}}{v}_j^{\left(m+1\right)}{z}_i^j}{{\displaystyle \underset{j=1}{\overset{\infty }{\sum }}}{u}_j^{\left(m+1\right)}{z}_i^{j-1}}$ (14)

with $s_{m+1}^i$ the ${\left(m+1\right)}^{\text{th}}$ s-number of ${\Gamma }_{H_i}$ .

Moreover one has.

Corollary 2 (Lemma 2.1, [2] ). If for each $i=1,\cdots ,n$

${\left[{\hat{h}}_i\left(z_i\right)\right]}_s=\frac{p_1{z}_i^{m-1}+\cdots +p_m}{z_i^m-c_m{z}_i^{m-1}-\cdots -c_1}$ (15)

and

${\Gamma }_{H_i}^m=\left(\begin{array}{ccc}{h}_1^i& \cdots & h_m^i\\ ⋮& & ⋮\\ h_m^i& \cdots & h_{2m-1}^i\end{array}\right)\mathrm{.}$

the principal minor of order m in ${\Gamma }_{H_i}$ , then

$\left(\begin{array}{c}{c}_1\\ ⋮\\ c_m\end{array}\right)={\left({\Gamma }_{H_i}\right)}^{-m}\cdot \left(\begin{array}{c}{h}_{m+1}^i\\ ⋮\\ h_{2m}^i\end{array}\right)$ (16)

and

$p_1=h_1^i,p_2=h_2^i-c_1{h}_1^i,\cdots ,p_m=h_m^i-h_{m-1}^i{c}_1-\cdots -h_1^i{c}_{m-1}.$ (17)

Proposition 2: Suppose that

$H\left(z_1,\cdots ,z_n\right)=\frac{{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{P}_i\left(z_i\right)}{{\displaystyle \underset{i=1}{\overset{n}{\sum }}}{Q}_i(\; z\; i\; )}$

belongs to ${\mathcal{R}}_m^n$ . Then for each $i=\mathrm{1,2,}\cdots \mathrm{,}n$ the coefficients of $P_i$ and $Q_i$ can be computed thanks to corollary 2. More precisely if

$P_i\left(z_i\right)=p_1{z}_i^{m-1}+\cdots +p_m,Q_i\left(z_i\right)=z_i^m-c_m{z}_i^{m-1}-\cdots -c_1$

and $H_i\left(z_i\right):=H\left(1,\cdots ,1,z_i,1,\cdots ,1\right)$ then

1) The coefficients of $P_i$ and $Q_i$ except $p_m$ and $c_1$ are computed by using (16) and (17);

2) The rank of ${\Gamma }_{H_i}$ , $R_i\le m$ .

Proof. The item 1 is a consequence of the corollary 2.

The contraposition of the theorem of DeCarlo et al [13] allows to say that $H_i$ belongs to ${\mathcal{R}}_m^s$ . The item 2 is then a consequence of Corollary 1.

4. Conclusion

This paper has proposed an optimal design of a multidimensional BIBO stable filter with a rational transfer function $H\in ℂ\left[z_1\mathrm{,}\cdots \mathrm{,}{z}_n\right]$ . The approach is based on the one dimensional AAK theorem. Two propositions have been developed and require that the Hankel operators ${\Gamma }_{H_i}$ associated with the polynomial function H are compact with finite ranks. We hope that in further works, comparisons (based on numerical tests) with other methods that exist in the literature on the approximation of multivariate functions will be made.

Data Availability

No underlying data was collected or produced in this study.

Funding Statement

This study did not receive any funding in any form.

Conflicts of Interest

All authors certify that they have no affiliations with or involvement in any organization or entity with any financial interest or non-financial interest in the subject matter in this manuscript.

References

[1]	Anderson, B. and Jury, E. (1974) Stability of Multidimensional Digital Filters. IEEE Transactions on Circuits and Systems, 21, 300-304. https://doi.org/10.1109/TCS.1974.1083834
[2]	Chui, C.K. and Chen, G. (1992) Signal Processing and Systems Theory. Springer Science & Business Media, Berlin. https://doi.org/10.1007/978-3-642-97406-9
[3]	Shang, Y. (2023) Resilient Vector Consensus over Random Dynamic Networks under Mobile Malicious Attacks. Oxford University Press, Oxford. https://doi.org/10.1093/comjnl/bxad043
[4]	Shang, Y. (2023) Resilient Tracking Consensus over Dynamic Graphs: A Linear System Approach. Cambridge University Press, Cambridge. https://doi.org/10.1017/S0956792522000225
[5]	Chisholm, J.S.R. (1973) Rational Approximants Defined from Double Power Series. Mathematics of Computation, 27, 841-848. https://doi.org/10.1090/S0025-5718-1973-0382928-6
[6]	Cuyt, A.A.M. (1983) A Comparison of Some Multivariate Padé-Approximants. SIAM Journal on Mathematical Analysis, 14, 195-202. https://doi.org/10.1137/0514016
[7]	Cuyt, A., Driver, K. and Lubinsky, D. (1996) Kronecker Type Theorems, Normality and Continuity of the Multivariate Padé Operator. Numerische Mathematik, 73, 311-327. https://doi.org/10.1007/s002110050195
[8]	Vavilov, V.V., Tchobanou, M.K. and Tchobanou, P.M. (2002) Design of Multi-Di-mensional Recursive Systems through Pad’e Type Rational Approximation. Nonlinear Analysis: Modelling and Control, 7, 105-125. https://doi.org/10.15388/NA.2002.7.1.15206
[9]	Austin, A.P., Krishnamoorthy, M., Leyffer, S., Mrenna, S., Müller, J. and Schulz, H. (2021) Practical Algorithms for Multivariate Rational Approximation. Computer Physics Communications, 261, Article ID: 107663. https://doi.org/10.1016/j.cpc.2020.107663
[10]	Adamyan, V.M., Arov, D.Z. and Krein, M.G. (1968) Infinite Hankel Matrices and Generalized Carathéodory—Fejer and Riesz Problems. Functional Analysis and Its Applications, 2, 1-18. https://doi.org/10.1007/BF01075356
[11]	Adamyan, V., Arov, D. and Krein, M.G. (1971) Analytic Properties of Schmidt Pairs for a Hankel Operator and the Generalized Schur-Takagi Problem. Mathematics of the USSR-Sbornik, 86, 34-75. https://doi.org/10.1070/SM1971v015n01ABEH001531
[12]	Prokhorov, V.A. (1993) On a Theorem of Adamian, Arov, and Krein. Matematicheskii Sbornik, 184, 89-104.
[13]	Decarlo, R.A., Murray, J. and Saeks, R. (1977) Multivariable Nyquist Theory. International Journal of Control, 25, 657-675. https://doi.org/10.1080/00207177708922261