Notes on n-D Polynomial Matrix Factorizations

This paper discusses a relationship between the prime factorizability of a normal full rank n-D ( n>2) polynomial matrix and its reduced minors. Two conjectures regarding the n-D polynomial matrix prime factorization problem are posed, and a partial solution to one of the conjectures is provided. Another related open problem of factorizing an n-D polynomial matrix that is not of normal full rank as a product of two n-D polynomial matrices of smaller size is also considered, and a partial solution to this problem is presented. An illustrative example is worked out in details.     

Further Results on n-D Polynomial Matrix Factorizations

In this paper, some new results on zero prime factorization for a normal full rank n-D (n>2) polynomial matrix are presented. Assume that d is the greatest common divisor (g.c.d.) of the maximal order minors of a given n-D polynomial matrix F ₁. It is shown that if there exists a submatrix F of F ₁, such that the reduced minors of F have no common zeros, and the g.c.d. of the maximal order minors of F equals d, then F ₁ admits a zero right prime (ZRP) factorization if and only if F admits a ZRP factorization. A simple ZRP factorizability of a class of n-D polynomial matrices based on reduced minors is given. An advantage is that the ZRP factorizability can be tested before carrying out the actual matrix factorization. An example is illustrated.     

A Tutorial on GrÖbner Bases With Applications in Signals and Systems

This paper is a tutorial on GrÖbner bases and a survey on the applications of GrÖbner bases in the broad field of signals and systems. A reasonably detailed review is given of several fundamental theoretical issues that occur in the use of GrÖbner bases in multidimensional signals and systems applications. These topics include the primeness of multivariate polynomial matrices, multivariate unimodular polynomial matrix completion, and prime factorization of multivariate polynomial matrices. A brief review is also presented on the wide-ranging applications of GrÖbner bases in multidimensional as well as one-dimensional circuits, networks, control, coding, signals, and systems and other related areas like robotics and applied mechanics. The impact and scope of GrÖbner bases in signals and systems are highlighted with respect to what has already been accomplished as a stepping stone to expanding future research.      

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.     

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.

     

Spectral factorization of two-variable para-Hermitian polynomial matrices

This paper presents an algorithm for the so-called spectral factorization of two-variable para-Hermitian polynomial matrices which are nonnegative definite on thej axis, arising in the synthesis of two-dimensional (2-D)passive multiports, Wiener filtering of 2-D vector signals, and 2-D control systems design. First, this problem is considered in the scalar case, that is, the spectral factorization of polynomials is treated, where the decomposition of a two-variable nonnegative definite real polynomial in a sum of squares of polynomials in one of the two variables having rational coefficients in the other variable plays an important role (cf. Section 4). Second, by using these results, the matrix case can be accomplished, where in a first step the problem is reduced to the factorization of anunimodular para-Hermitian polynomial matrix which is nonnegative definite forp=j , and in a second step this simplified problem is solved by using so-called elementary row and column operations which are based on the Euclidian division algorithm. The matrices considered may be regular or singular and no restrictions are made concerning the coefficients of their polynomial entries; they may be either real or complex.     

Computation of simple and group factors of multivariate polynomials

This paper generalizes a recent result onsimple factorization of 2-variable (2-v) polynomials to simple andgroup factorization ofn-variate (n-v), (n3) polynomials. The emphasis is on developing a reliablenumerical technique for factorization. It is shown that simple as well as group factorization can be achieved by performing singular value decomposition (SVD) on certain matrices obtained from the coefficients of the givenn-v polynomial expressed in a Kronecker product form. For the polynomials that do not have exact simple and/or group factors, the concepts of approximate simple and group factorization are developed. The use of SVD leads to an elegant solution of an approximaten factorization problem. Several nontrivial examples are included to illustrate the results presented in this paper.Research supported by WRDC grant F33615-88-C-3605, NSF grant ECS-9110636, and NSERC of Canada grant A1345.     

On Factor Prime Factorizations for n-D Polynomial Matrices

This paper investigates the problem of factor prime factorizations for n-D polynomial matrices and presents a criterion for the existence of factor prime factorizations for an important class of n-D polynomial matrices. As a by-product, we also obtain an algebraic algorithm to check n-D factor primeness in some important cases which partially solves the long-standing open problem of recognizing n-D factor prime matrices. Some problems related to the factorization methods are also studied. Several examples are given to illustrate the results. The results presented in this paper are true over any coefficient field.     

Remarks on n -D Polynomial Matrix Factorization Problems

Multidimensional (n-D) polynomial matrix factorizations are intimately linked to many problems of multidimensional systems and signal processing. This paper gives a new result for a n-D polynomial matrix to have an minor prime factorization using methods from computer algebra. This result may be regarded as a generalization of a previous criterion under a special restriction [IEEE Trans. Circuits Syst. II: Exp Briefs, vol. 52, no. 9 (2005)]. Examples are given to illustrate results using computer algebra software system Singular.     

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.     

Reversible Resampling of Integer Signals

Except some extremely special cases, signal resampling was generally considered to be irreversible because of strong attenuation of high frequencies after interpolation. In this paper, we prove that signal resampling based on polynomial interpolation can be reversible even for integer signals, i.e., the original signal can be reconstructed losslessly from the resampled data. By using matrix factorization, we also propose a reversible method for uniform shifted resampling and uniform scaled and shifted resampling. The new factorization yields three elementary integer-reversible matrices. The method is actually a new way to compute linear transforms and a lossless integer implementation of linear transforms with the factor matrices. It can be applied to integer signals by in-place integer-reversible computation, which needs no auxiliary memory to keep the original sample data for the transformation during the process or for “undo” recovery after the process. Some examples of low-order resampling solutions are also presented in this paper and our experiments show that the resampling error relative to the original signal is comparable to that of the traditional irreversible resampling.      

Projection Operator-Based Factorization Procedure for FIR Paraunitary Matrices

A constructive procedure for factoring a polynomial paraunitary matrix as a product of atomic paraunitary matrices is considered. The generic form of the paraunitary factors results from the use of projection matrices. In the univariate case, the factorization carried out in the $z$ -transform domain collapses to other univariate paraunitary matrix factorization methods. In the multivariate case, the generic factor is constructed based on the assumption of its existence. Nontrivial examples for multiband univariate, bivariate, and trivariate cases are given to illustrate the simple and straightforward algorithmic implementation.      

A Generalized Parameter-Dependent Approach to Robust H ∞ Filtering of Stochastic Systems

This paper is concerned with the problem of robust H _∞ filtering for discrete-time stochastic systems with state-dependent stochastic noises and deterministic polytopic parameter uncertainties. We utilize the polynomial parameter-dependent approach to solve the robust H _∞ filtering problem, and the proposed approach includes results in the quadratic framework that entail fixed matrices for the entire uncertain domain and results in the linearly parameter-dependent framework that use linear convex combinations of matrices as special cases. New linear matrix inequality (LMI) conditions obtained for the existence of admissible filters are developed based on homogeneous polynomial parameter-dependent matrices of arbitrary degree. As the degree grows, a test of increasing precision is obtained, providing less conservative filter designs. A numerical example is provided to illustrate the effectiveness and advantages of the filter design methods proposed in this paper. This work was supported by HKU CRCG 200611159157, the National Nature Science Foundation of China (60504008), The Research Fund for the Doctoral Programme of Higher Education of China (20070213084), the Fok Ying Tung Education Foundation (111064), and the Key Laboratory of Integrated Automation for the Process Industry (Northeastern University), Ministry of Education of China.     

On the extreme eigenvalues of Toeplitz and real Hankel interval matrices

The purpose of this paper is to evaluate the extreme eigenvalues of a Hermitian Toeplitz interval matrix and a real Hankel interval matrix. A (n×n)-dimensional Hermitian Toeplitz (HT) matrix is determined by the elements of its first row, sayr. If the elements ofr lie in complex intervals (i.e., rectangles of the complex plane), we call the resulting set of matrices an HT interval (HTI) matrix. An HTI matrix can model real world HT matrices where the elements of the vectorr have finite precision (e.g., because of quantization, or imprecise measurement devices). In this paper we prove that the extreme eigenvalues of a given HTI matrix can be easily obtained from the 2^2(n–1) vertex HT matrices where the first element ofr is set to zero. Similarly, as a special case we obtain that the extreme eigenvalues of a real symmetric Toeplitz interval (RSTI) matrix can be obtained from 2 ^n–1 vertex matrices. Based on the above results we provide boxlike bounds for the eigenvalues on non-Hermitian complex and real Toeplitz interval matrices. Finally, we consider a real Hankel interval matrix. We prove that the maximal eigenvalue of a (n×n)-dimensional real Hankel interval matrix can be obtained from a subset of the vertex Hankel matrices containing 2^2n–3 vertex matrices, whereas the minimal eigenvalue can be obtained from another such subset also containing 2^2n–3 vertex matrices.     

A systolic architecture for optimal filter design support

A prototype filter design is reviewed to underscore the computational problems arising in such designs. A purely systolic-array architecture is presented. This array provides the computational support necessary for filter design. Due to a simple and novel data steering technique the array is capable of carrying out a number of important matrix operations such as factorization, inversion of factors, and matrix-matrix multiplication. Another interesting attribute is the array's ability to maximally overlap computations of multiphase algorithms. In this study we demonstrate the execution of a dense matrix factorization phase and a factor inversion phase on the array with no need for intraphase or interphase I/O. We show that these phases (which are the backbone of an optimal filtering algorithm) are completed in the optimal count of aboutn time units. The array employs 2n ⁿ–n simple processing elements (PEs) that are active every other time unit. It is shown that the functions of two adjacent PEs can be merged and assigned to a single PE thus maximizing PE utilization. A possible design of a merged PE is given.     

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.     

Infinite elementary divisors of polynomial matrices and impulsive solutions of linear homogeneous matrix differential equations

Impulsive solutions of linear homogeneous matrix differential equations are re-examined in the light of the theory of Jordan chains that correspond to infinite elementary divisors of the associated polynomial matrix. Infinite elementary divisors of general polynomial matrices are defined and their relation to the pole-zero structure of polynomial matrices at infinity is examined. It is shown that impulsive solutions are due to Jordan chains of a “dual” polynomial matrix that correspond to infinite elementary divisors that are associated with the orders of “zeros at infinity” of the original matrix.     

On 2D finite support convolutional codes: An algebraic approach

Two-dimensional (2D) finite codes are defined as families of compact support sequences indexed in Z × Z and taking values in F ⁿ , F a Galois field. Several properties of encoders, decoders and syndrome decoders are discussed under different hypotheses on the code structure, and related to the injectivity and primeness of the corresponding polynomial matrices in two variables. Dual codes are finally introduced as families of parity checks on a given modular code, and related to the standard theory of 2D behaviors.     

High-gain decentralised control of interconnected dynamical systems

It is shown that the class of controllable and observable interconnected dynamical systems that are amenable to high-gain decentralised control can be characterised in terms of the relatively prime polynomial matrix factors of the transfer-function matrices of the disconnected subsystems. Moreover, this characterisation greatly facilitates the synthesis of high-gain decentralised controllers for such amenable systems.     

On simplified order-one factorizations of paraunitary filterbanks

This paper revisits the order-one factorization of causal finite impulse response (FIR) paraunitary filterbanks (PU FBs). The basic form of the factorization was proposed by Vaidyanathan et al. in 1987, which is a cascade of general unitary matrices separated by diagonal delay matrices with arbitrary number of delay elements. Recently, Gao et al. have proved the completeness of this factorization and developed a more efficient structure that only uses approximately half number of free parameters. In this paper, by briefly analyzing Gao et al.'s derivation, we first point out that Gao et al.'s factorization contains redundant free parameters. Two simplified structures of Vaidyanathan's factorization are then developed, i.e., a post-filtering-based structure and a prefiltering-based structure. Our simplification relies on consecutive removal of extra degrees of freedom in adjacent stages, which is accomplished through the C-S decomposition of a general unitary matrix. Since the conventional C-S decomposition leads to a redundant representation, a new C-S decomposition is developed to minimize the number of free parameters by further incorporating the Givens rotation factorization. The proposed structures can maintain the completeness and the minimality of the original lattice. Compared with Gao et al.'s factorization, our derivations are much simpler, while the resulting structures contain fewer free parameters and less implementation cost. Besides, these new factorizations indicate that for a PU FB with a given filter length, the symmetric-delay factorization offers the largest degrees of design freedom. Several design examples are presented to confirm the validity of the theory.