Gröbner Bases and Systems Theory

We present the basic concepts and results of Gröbner bases theory for readers working or interested in systems theory. The concepts and methods of Gröbner bases theory are presented by examples. No prerequisites, except some notions of elementary mathematics, are necessary for reading this paper. The two main properties of Gröbner bases, the elimination property and the linear independence property, are explained. Most of the many applications of Gröbner bases theory, in particular applications in systems theory, hinge on these two properties. Also, an algorithm based on Gröbner bases for computing complete systems of solutions (syzygies) for linear diophantine equations with multivariate polynomial coefficients is described. Many fundamental problems of systems theory can be reduced to the problem of syzygies computation.     

Gröbner Bases and Multidimensional FIR Multirate Systems

The polyphase representation with respect to sampling lattices in multidimensional (M-D) multirate signal processing allows us to identify perfect reconstruction (PR) filter banks with unimodular Laurent polynomial matrices, and various problems in the design and analysis of invertible MD multirate systems can be algebraically formulated with the aid of this representation. While the resulting algebraic problems can be solved in one dimension (1-D) by the Euclidean Division Algorithm, we show that Gröbner bases offers an effective solution to them in the M-D case.     

Algebraic Approach to Ambiguity-Group Determination in Nonlinear Analog Circuits

In this paper, a symbolic procedure for ambiguity-group determination, based on the a priori identifiability concept, is proposed. The method starts from the analysis of the occurrence of circuit parameters in the coefficients of the input/output relationship in order to select the potential canonical ambiguity groups. This first step allows one to strongly reduce the problem complexity. In a second step, the obtained nonlinear system that imposes the ambiguity conditions is solved, resorting to Gröbner bases theory. Both of these steps are completely symbolic, thus avoiding round-off errors. Furthermore, the method can be applied to both linear and nonlinear circuits. An alternative approach is also proposed, which extends to nonlinear circuits a method presented in the literature, which can be directly applied only to linear circuits. The methods are illustrated by means of benchmarks regarding well-known linear and nonlinear circuits.      

Gröbner Bases for Problem Solving in Multidimensional Systems

The objective here is to underscore recent usage of the algorithmic theory of Gröbner bases in multidimensional systems since that possibility was highlighted about fifteen years back. The main contribution here focuses on the constructive aspects of the solution, known to exist, of the two-band multidimensional IIR perfect reconstruction problem using Gröbner bases. Other recent research results on the subject with future prospects are also briefly cited.     

Parametrized Family of 2-D Non-factorable FIR Lossless Systems and Gröbner Bases

The factorability of one-dimensional (1-D) FIR lossless transfer matrices [1] in terms of Givens rotations produces the parameters that can be used for an optimal design of filter banks with prespecified filtering characteristics. Two dimensional (2-D) FIR lossless systems behave quite differently, however. Venkataraman-Levy [2] and Basu-Choi-Chiang [3] have constructed 2-D FIR paraunitary matrices of McMillan degrees (2,2) that are not factorable. Because of the state-space realization used in the construction, they are floating-point approximations, and they do not produce explicit parametrizations that can be used for optimal design process. In this paper, we formulate the lossless condition and nonfactorability condition of a 2-D FIR paraunitary matrix using multivariate polynomials in the coefficients. The resulting polynomial system can be explicitly solved with Gröbner bases. By studying the polynomial system, we obtain a continuous one parameter family of 2-D 2×2 non-factorable paraunitary matrices. As an example, we get a closed-form expression for a 2-D 2×2 paraunitary matrix that is not factorable into rotations and delays.     

On the equivalence of multivariate polynomial matrices

The equivalence of system is an important concept in multidimensional (\(n\)D) system, which is closely related to equivalence of multivariate polynomial matrices. This paper mainly investigates the equivalence of some \(n\)D polynomial matrices, several new results and conditions on the reduction by equivalence of a given \(n\)D polynomial matrix to its Smith form are obtained.     

Multidimensional Multichannel FIR Deconvolution Using GrÖbner Bases

We present a new method for general multidimensional multichannel deconvolution with finite impulse response (FIR) convolution and deconvolution filters using GrÖbner bases. Previous work formulates the problem of multichannel FIR deconvolution as the construction of a left inverse of the convolution matrix, which is solved by numerical linear algebra. However, this approach requires the prior information of the support of deconvolution filters. Using algebraic geometry and GrÖbner bases, we find necessary and sufficient conditions for the existence of exact deconvolution FIR filters and propose simple algorithms to find these deconvolution filters. The main contribution of our work is to extend the previous GrÖbner basis results on multidimensional multichannel deconvolution for polynomial or causal filters to general FIR filters. The proposed algorithms obtain a set of FIR deconvolution filters with a small number of nonzero coefficients (a desirable feature in the impulsive noise environment) and do not require the prior information of the support. Moreover, we provide a complete characterization of all exact deconvolution FIR filters, from which good FIR deconvolution filters under the additive white noise environment are found. Simulation results show that our approaches achieve good results under different noise settings.     

A Constructive Approach to Stabilizability and Stabilization of a Class of nD Systems

This paper presents a constructive approach to the problem of output feedback stabilizability and stabilization of a class of linear multidimensional (nD, n>2) systems, whose varieties of the ideals generated by the reduced minors are infinite with respect to not more than two variables. The main idea of the proposed approach is to decompose the variety of an nD system in this class into a union of several varieties, each of which is defined by polynomials in just two variables. The new method can be considered as a combination of Gröbner bases and existing results on two-dimensional (2D) digital filter stability tests and on stabilizability and stabilization of 2D systems. An example is illustrated.     

Multidimensional multichannel FIR deconvolution using Gr?bner bases.

We present a new method for general multidimensional multichannel deconvolution with finite impulse response (FIR) convolution and deconvolution filters using Gr?bner bases. Previous work formulates the problem of multichannel FIR deconvolution as the construction of a left inverse of the convolution matrix, which is solved by numerical linear algebra. However, this approach requires the prior information of the support of deconvolution filters. Using algebraic geometry and Gr?bner bases, we find necessary and sufficient conditions for the existence of exact deconvolution FIR filters and propose simple algorithms to find these deconvolution filters. The main contribution of our work is to extend the previous Gr?bner basis results on multidimensional multichannel deconvolution for polynomial or causal filters to general FIR filters. The proposed algorithms obtain a set of FIR deconvolution filters with a small number of nonzero coefficients (a desirable feature in the impulsive noise environment) and do not require the prior information of the support. Moreover, we provide a complete characterization of all exact deconvolution FIR filters, from which good FIR deconvolution filters under the additive white noise environment are found. Simulation results show that our approaches achieve good results under different noise settings.     

On Kernel Selection of Multivariate Local Polynomial Modelling and its Application to Image Smoothing and Reconstruction

This paper studies the problem of adaptive kernel selection for multivariate local polynomial regression (LPR) and its application to smoothing and reconstruction of noisy images. In multivariate LPR, the multidimensional signals are modeled locally by a polynomial using least-squares (LS) criterion with a kernel controlled by a certain bandwidth matrix. Based on the traditional intersection confidence intervals (ICI) method, a new refined ICI (RICI) adaptive scale selector for symmetric kernel is developed to achieve a better bias-variance tradeoff. The method is further extended to steering kernel with local orientation to adapt better to local characteristics of multidimensional signals. The resulting multivariate LPR method called the steering-kernel-based LPR with refined ICI method (SK-LPR-RICI) is applied to the smoothing and reconstruction problems in noisy images. Simulation results show that the proposed SK-LPR-RICI method has a better PSNR and visual performance than conventional LPR-based methods in image processing.     

Algebraic decoder of multidimensional convolutional code: constructive algorithms for determining syndrome decoder and decoder matrix based on Gr?bner basis

A representation of an multidimensional (m-D) convolutional encoder is analogous to the representation of a transfer function for a MIMO m-D FIR system. The encoder matrix is usually not square and thus finding its inverse (decoder matrix) typically employs the Moore-Penrose generalized inverse. However, the result may not be FIR (polynomial matrix) even if the generator matrix is a polynomial matrix. In this paper a constructive algorithm for computing the FIR pseudo inverse, based on the usage of Gröbner basis is presented along with detailed examples. The result obtained can be parameterized to cover the class of all possible FIR inverses. In addition, by using the computation method of syzygy with the Gröbner basis module, the syndrome matrix for a given m-D convolutional encoder is shown. Furthermore, the theory of Gröbner basis is applied to solve the algebraic syndrome decoder problems using the maximum likelihood (nearest neighborhood) criteria and the procedure for 2-D convolutional code error correction is proposed. Despite the complication of the decoding process, the proposed method is the only error correcting decoder for multidimensional convolutional code available to date.     

Algebraic multidimensional phase unwrapping and zero distributionof complex polynomials-characterization of multivariate stablepolynomials

We define the multidimensional unwrapped phase for any finite extent multidimensional signal that may have its zero on the distinguished boundary of the unit polydisc. By using this definition, we deduce that multivariate stable polynomials can be simply characterized in terms of the proposed unwrapped phase. A rigorous symbolic algebraic solution to the exact phase unwrapping problem for multidimensional finite extent signals is also proposed. This solution is based on a newly developed general Sturm sequence and does not need any numerical root finding or numerical integration technique. Furthermore, it is shown that the proposed algebraic phase unwrapping algorithm can be used to determine the exact zero distribution of any univariate complex polynomial without suffering the so-called singular case problem     

Generic Invertibility of Multidimensional FIR Filter Banks and MIMO Systems

In this paper, we study the invertibility of M-variate Laurent polynomial N times P matrices. Such matrices represent multidimensional systems in various settings such as filter banks, multiple-input multiple-output systems, and multirate systems. Given an N times P Laurent polynomial matrix H(z₁, ..., z_M) of degree at most k, we want to find a P times N Laurent polynomial left inverse matrix G(z) of H(z) such that G(z)H(z) = J. We provide computable conditions to test the invertibility and propose algorithms to find a particular inverse. The main result of this paper is to prove that H(z) is generically invertible when N - P ges M; whereas when N - P < M, then H(z) is generically noninvertible. As a result, we propose an algorithm to find a particular inverse of a Laurent polynomial matrix that is faster than current algorithms known to us.     

Multi-Channel Multi-Variate Equalizer Design

The polarimetric calibration of synthetic aperture radar (SAR) imagery requires the equalization of a multiple-input, multiple-output (MIMO) distortion system. For wide-band, wide-angle SAR systems, the distortion is frequency and angle dependent and can be accurately modelled as a two-dimensional finite impulse response (FIR) filter bank. This paper presents a design algorithm, using a Gröbner basis, to compute a FIR filter bank that exactly inverts the multi-channel distortion. The results presented for polynomial inversion of MIMO FIR systems hold for sampled data signals of arbitrary dimension.     

On factor left prime factorization problems for multivariate polynomial matrices

This paper is concerned with factor left prime factorization problems for multivariate polynomial matrices without full row rank. We propose a necessary and sufficient condition for the existence of factor left prime factorizations of a class of multivariate polynomial matrices, and then design an algorithm to compute all factor left prime factorizations if they exist. We implement the algorithm on the computer algebra system Maple, and two examples are given to illustrate the effectiveness of the algorithm. The results presented in this paper are also true for the existence of factor right prime factorizations of multivariate polynomial matrices without full column rank.

     

Results on the factorization of multidimensional matrices for paraunitary filterbanks over the complex field

This paper undertakes the study of multidimensional finite impulse response (FIR) filterbanks. One way to design a filterbank is to factorize its polyphase matrices in terms of elementary building blocks that are fully parameterized. Factorization of one-dimensional (1-D) paraunitary (PU) filterbanks has been successfully accomplished, but its generalization to the multidimensional case has been an open problem. In this paper, a complete factorization for multichannel, two-dimensional (2-D), FIR PU filterbanks is presented. This factorization is based on considering a two-variable FIR PU matrix as a polynomial in one variable whose coefficients are matrices with entries from the ring of polynomials in the other variable. This representation allows the polyphase matrix to be treated as a one-variable matrix polynomial. To perform the factorization, the definition of paraunitariness is generalized to the ring of polynomials. In addition, a new degree-one building block in the ring setting is defined. This results in a building block that generates all two-variable FIR PU matrices. A similar approach is taken for PU matrices with higher dimensions. However, only a first-level factorization is always possible in such cases. Further factorization depends on the structure of the factors obtained in the first level.     

On General Factorizations for n-D Polynomial Matrices

Multivariate (n-D) polynomial matrix factorizations are basic research subjects in multidimensional (n-D) systems and signal processing. In this paper, several results on general matrix factorizations are provided for extracting a matrix factor from a given n-D polynomial matrix whose lower order minors satisfy certain conditions. These results are further generalizations of previous results in (Lin et al. in Circuits Syst. Signal Process. 20(6):601–618, 2001). As a consequence, the application range of the constructive algorithm in (Lin et al. in Circuits Syst. Signal Process. 20(6):601–618, 2001) has been greatly extended. Three examples are worked out in detail to show the practical value of the proposed method for obtaining general factorizations for a class of n-D polynomial matrices.     

Variable digital filter design using the outer product expansion

Digital filters with adjustable frequency domain characteristics are referred to as variable digital filters. Variable filters are useful in the applications where the filter characteristics are required to be changeable during the course of signal processing. Especially in real time applications, variable filters are needed to change their coefficients instantaneously such that the real time signal processing can be performed. The present paper proposes a very efficient technique for variable 1D digital filter design. Generally speaking, the variable coefficients of variable digital filters are multidimensional functions of a set of spectral parameters which define the desired frequency domain characteristics. The authors first sample the given variable 1D magnitude specification and use the samples to construct a multidimensional array, then propose an outer product expansion method for expanding the multidimensional array as the sum of outer products of 1D arrays (vectors). Based on the outer product expansion, one can reduce the difficult problem of designing a variable 1D digital filter to the easy one that only needs constant 1D filter designs and 1D polynomial approximations. The technique can obtain variable 1D filters having arbitrary desired magnitude characteristics with a high design accuracy     

Multidimensional Blind Separation Using Higher-Order Statistics: Application to Non-Cooperative STBC Systems

Blindly separating the intercepted signals is a challenging problem in non-cooperative multiple input multiple output systems in association with space–time block code (STBC) where channel state information and coding matrix are unavailable. To our knowledge, there is no report on dealing with this problem in literature. In this paper, the STBC systems are represented with an independent component analysis (ICA) model by merging the channel and coding matrices as virtual channel matrix. Analysis shows that the source signals are of group-wise independence and the condition of mutual independence can not be satisfied for ordinary ICA algorithms when specific modulations are employed. A new multidimensional ICA algorithm is proposed to separate the intercepted signals in this case by jointly block-diagonalizing (JBD) the cumulant matrices. In this paper, JBD is achieved by a 2-step optimization algorithm and a contrast function is derived from the JBD criterion to remove the additional permutation ambiguity with explicit mathematical explanations. The convergence of the new method is guaranteed. Compared with the ICA-based channel estimation methods, simulations show that the new algorithm, which does not introduce additional ambiguities, achieves better performance with faster convergence in a non-cooperative scenario.