Fast solution of unsymmetric banded Toeplitz systems by means of spectral factorizations and Woodbury's formula

A fast algorithm for solving systems of linear equations with banded Toeplitz matrices is studied. An important step in the algorithm is a novel method for the spectral factorization of the generating function associated with the Toeplitz matrix. The spectral factorization is extracted from the right deflating subspaces corresponding to the eigenvalues inside and outside the open unit disk of a companion matrix pencil constructed from the coefficients of the generating function. The factorization is followed by the Woodbury inversion formula and solution of several banded triangular systems. Stability of the algorithm is discussed and its performance is demonstrated by numerical experiments. Copyright © 2012 John Wiley & Sons, Ltd.     

Fast algorithm for solving the Hankel/Toeplitz Structured Total Least Squares problem

The Structured Total Least Squares (STLS) problem is a natural extension of the Total Least Squares (TLS) problem when constraints on the matrix structure need to be imposed. Similar to the ordinary TLS approach, the STLS approach can be used to determine the parameter vector of a linear model, given some noisy measurements. In many signal processing applications, the imposition of this matrix structure constraint is necessary for obtaining Maximum Likelihood (ML) estimates of the parameter vector. In this paper we consider the Toeplitz (Hankel) STLS problem (i.e., an STLS problem in which the Toeplitz (Hankel) structure needs to be preserved). A fast implementation of an algorithm for solving this frequently occurring STLS problem is proposed. The increased efficiency is obtained by exploiting the low displacement rank of the involved matrices and the sparsity of the associated generators. The fast implementation is compared to two other implementations of algorithms for solving the Toeplitz (Hankel) STLS problem. The comparison is carried out on a recently proposed speech compression scheme. The numerical results confirm the high efficiency of the newly proposed fast implementation: the straightforward implementations have a complexity of O((m+n)³) and O(m³) whereas the proposed implementation has a complexity of O(mn+n²). This revised version was published online in June 2006 with corrections to the Cover Date.     

Fast algorithms for Toeplitz and Hankel matrices

The paper gives a self-contained survey of fast algorithms for solving linear systems of equations with Toeplitz or Hankel coefficient matrices. It is written in the style of a textbook. Algorithms of Levinson-type and Schur-type are discussed. Their connections with triangular factorizations, Padè recursions and Lanczos methods are demonstrated. In the case in which the matrices possess additional symmetry properties, split algorithms are designed and their relations to butterfly factorizations are developed.     

基于神经网络的FIR多阻带数字滤波器的设计及应用

针对电子测量系统中的工频50Hz及其二次三次谐波干扰，本文运用BP神经网络设计一个三阻带数字滤波器，利用神经网络权值与FIR数字滤波器脉冲响应之间的关系，得出所设计滤波器的脉冲响应。实验表明，与窗函数法设计的三阻带滤波器相比，基于神经网络的FIR三阻带滤波器具有明显的优越性。     

Averaging operators for exponential splittings

Averaging operations are considered in connection with exponential splitting methods. Toeplitz plus Hankel related matrices are resplit by applying appropriate averaging operators leading to a hierarchy of structured matrices. With the resulting parts, the option of using exponential splitting methods becomes available. A related, seemingly important group of unitary unipotents is looked at. Based on a formula due to Lenard, a very fast iterative method to find the nearest Toeplitz plus Hankel matrix in the Frobenius norm is devised.     

Stability analysis of a general toeplitz systems solver

We show that a fast algorithm for theQR factorization of a Toeplitz or Hankel matrixA is weakly stable in the sense thatR ^T R is close toA ^T A. Thus, when the algorithm is used to solve the semi-normal equationsR ^TRx=A^T b, we obtain a weakly stable method for the solution of a nonsingular Toeplitz or Hankel linear systemAx=b. The algorithm also applies to the solution of the full-rank Toeplitz or Hankel least squares problem min ||Ax-b||₂.     

Fast matrix factorizations via discrete transmission lines

Fast algorithms, associated with the names of Schur and Levinson, are known for the triangular factorization of symmetric, positive definite Toeplitz matrices and their inverses. In this paper we show that these algorithms can be derived from simple arguments involving causality, symmetry, and energy conservation in discrete lossless transmission lines. The results not only provide a nice interpretation of the classical Schur and Levinson algorithms and a certain Toeplitz inversion formula of Gohberg and Semencul, but they also show immediately that the same fast algorithms apply not only to Toeplitz matrices but to all matrices with so-called displacement inertia (1,1). The results have been helpful in suggesting new digital filter structures and in the study of nonstationary second-order processes.     

应用多重交换法设计具有k个陷波频点的等波纹FIR陷波滤波器

本文提出了一种设计等波纹线性相位 FIR陷波滤波器的优化算法。首先介绍了线性相位 FIR滤波器的四种情况 ,然后在此基础上设计了一种应用多重交换算法来处理心电信号的陷波滤波器。此算法相对于均方误差最小准则和最大误差最小化准则具有占用存储空间小和计算时间短的优点。     

A fast method to block-diagonalize a Hankel matrix

In this paper, we consider an approximate block diagonalization algorithm of an n×n real Hankel matrix in which the successive transformation matrices are upper triangular Toeplitz matrices, and propose a new fast approach to compute the factorization in O(n ²) operations. This method consists on using the revised Bini method (Lin et al., Theor Comp Sci 315: 511–523, 2004). To motivate our approach, we also propose an approximate factorization variant of the customary fast method based on Schur complementation adapted to the n×n real Hankel matrix. All algorithms have been implemented in Matlab and numerical results are included to illustrate the effectiveness of our approach.     

Generalized inversion of finite rank Hankel and Toeplitz operators with rational matrix symbols

The goal of the paper is a generalized inversion of finite rank Hankel operators and Hankel or Toeplitz operators with block matrices having finitely many rows. To attain it a left coprime fractional factorization of a strictly proper rational matrix function and the Bezout equation are used. Generalized inverses of these operators and generating functions for the inverses are explicitly constructed in terms of the fractional factorization.     

Application of Rouche’s theorem for MP filter design

The method for the minimum-phase (MP) finite impulse response (FIR) filter design, based on Rouche’s theorem from complex analysis is presented here. The filter is designed directly from a given specification. The method uses the cosine filters and the sharpening technique resulting in a multiplierless filter.     

Using the Sherman-Morrison-Woodbury inversion formula for a fast solution of tridiagonal block Toeplitz systems

A fast numerical algorithm for solving systems of linear equations with tridiagonal block Toeplitz matrices is presented. The algorithm is based on a preliminary factorization of the generating quadratic matrix polynomial associated with the Toeplitz matrix, followed by the Sherman-Morrison-Woodbury inversion formula and solution of two bidiagonal and one diagonal block Toeplitz systems. Tight estimates of the condition numbers are provided for the matrix system and the main matrix systems generated during the preliminary factorization. The emphasis is put on rigorous stability analysis to rounding errors of the Sherman-Morrison-Woodbury inversion. Numerical experiments are provided to illustrate the theory.     

Riordan arrays and the LDU decomposition of symmetric Toeplitz plus Hankel matrices

We examine a result of Basor and Ehrhardt concerning Hankel and Toeplitz plus Hankel matrices, within the context of the Riordan group of lower-triangular matrices. This allows us to determine the LDU decomposition of certain symmetric Toeplitz plus Hankel matrices. We also determine the generating functions and Hankel transforms of associated sequences.     

Some Results in the Theory Modulated Filter Banks and Modulated Wavelet Tight Frames

Perfect reconstruction (PR) FIR filter banks, obtained by modulation of a linear-phase, lowpass, prototype filter and of length 2Mm are well known. Recently, PR modulated filter banks (MFBs) with the analysis and synthesis banks obtained from different prototypes have been reported. This paper describes a general form of modulation that includes modulations used in the literature. This modulation depends on an integer parameter, the modulation phase. The PR property is characterized for MFBs with finite and infinite impulse response filters. The MFB PR problem reduces to roughly M/2 two-channel PR problems. A natural dichotomy in the PR conditions leads us to the concepts of Type 1 and Type 2 MFBs. Unitary MFBs are characterized by the M/2 two-channel PR filter banks also being unitary (for FIR filters of length N = 2Mm, these results are given in (Malvar, Electr Lett. 26, June 1990, 906–907; Koilpillai and Vaidyanathan, IEEE Trans. SP40, No. 4, Apr. 1992, 770–783)). We also give a necessary and sufficient condition for a large class (including FIR) unitary MFB prototypes to have symmetric (even or odd) prototype filters, and exhibit unitary MFBs without symmetric prototypes. A parameterization of all FIR unitary MFBs is also given. An efficient design procedure for FIR unitary MFBs is developed. It turns out that MFBs can be implemented efficiently using Type III and Type IV DCTs. Compactly supported modulated wavelet tight frames are shown to exist and completely parameterized. K-regular modulated WTFs are designed numerically and analytically by solving a set of non-linear equations over the parameters. Design of optimal modulated WTFs for the representation of any given signal is described with examples, and this is used to design smooth modulated WTFs.     

Using FFT-based techniques in polynomial and matrix computations: recent advances and applicatons

Computations with univariate polynomials, like the evaluation of product, quotient, remainder, greatest common divisor, etc, are closely related to linear algebra computations performed with structured matrices having the Toeplitz-like or the Hankel-like structures.

The discrete Fourier transform, and the FFT algorithms for its computation, constitute a powerful tool for the design and analysis of fast algorithms for solving problems involving polynomials and structured matrices.

We recall the main correlations between polynomial and matrix computations and present two recent results in this field: in particular, we show how Fourier methods can speed up the solution of a wide class of problems arising in queueing theory where certain Markov chains, defined by infinite block Toeplitz matrices in generalized Hessenberg form, must be solved. Moreover, we present a new method for the numerical factorization of polynomials based on a matrix generalization of Koenig's theorem. This method, that relies on the evaluation/interpolation technique at the Fourier points, reduces the problem of polynomial factorization to the computation of the LU decomposition of a banded Toeplitz matrix with its rows and columns suitably permuted. Numerical experiments that show the effectiveness of our algorithms are presented     

Structured FISTA for image restoration

In this paper, we propose an efficient numerical scheme for solving some large‐scale ill‐posed linear inverse problems arising from image restoration. In order to accelerate the computation, two different hidden structures are exploited. First, the coefficient matrix is approximated as the sum of a small number of Kronecker products. This procedure not only introduces one more level of parallelism into the computation but also enables the usage of computationally intensive matrix–matrix multiplications in the subsequent optimization procedure. We then derive the corresponding Tikhonov regularized minimization model and extend the fast iterative shrinkage‐thresholding algorithm (FISTA) to solve the resulting optimization problem. Because the matrices appearing in the Kronecker product approximation are all structured matrices (Toeplitz, Hankel, etc.), we can further exploit their fast matrix–vector multiplication algorithms at each iteration. The proposed algorithm is thus called structured FISTA (sFISTA). In particular, we show that the approximation error introduced by sFISTA is well under control and sFISTA can reach the same image restoration accuracy level as FISTA. Finally, both the theoretical complexity analysis and some numerical results are provided to demonstrate the efficiency of sFISTA.     

Fast inversion algorithms of Toeplitz-plus-Hankel matrices

Summary The paper deals with the problems of fast inversion of matricesA=T+H, whereT is Toeplitz andH is Hankel. Several algorithms are presented and compared, among them algorithms working for arbitrary strongly nonsingular matricesA=T+H.     

A method of explicit factorization of matrix functions and applications

A method of explicit factorization of matrix functions of second order is proposed. The method consists of reduction of this problem to two scalar barrier problems and a finite system of linear equations. Applications to various classes of singular integral equations and equations with Toeplitz and Hankel matrices are given.     

Design of Interpolating Biorthogonal Multiwavelet Systems with Compact Support

In this paper we characterize all totally interpolating biorthogonal finite impulse response (FIR) multifilter banks of multiplicity two, and provide a design framework for corresponding compactly supported multiwavelet systems with high approximation order. In these systems, each component of the analysis and synthesis portions possesses the interpolating property. The design framework is based on scalar filter banks, and examples with approximation order two and three are provided. We show that our multiwavelet systems preserve almost all of the desirable properties of the generalized interpolating scalar wavelet systems, including the dyadic-rational nature of the filter coefficients, equality of the flatness degree of the low-pass filters and the approximation order of the corresponding functions, and equality between the uniform samples of a signal and its projection coefficients for a given scale. This last property allows us to avoid the cumbersome prefiltering associated with standard multiwavelet systems. We also show that there are no symmetric totally interpolating biorthogonal multifilter banks of multiplicity two. Finally, we point out that our design framework incorporates a simple relationship between the multiscaling functions and multiwavelets that substantially simplifies the implementation of the system.     

Diagonal and Toeplitz splitting iteration methods for diagonal‐plus‐Toeplitz linear systems from spatial fractional diffusion equations

The finite difference discretization of the spatial fractional diffusion equations gives discretized linear systems whose coefficient matrices have a diagonal‐plus‐Toeplitz structure. For solving these diagonal‐plus‐Toeplitz linear systems, we construct a class of diagonal and Toeplitz splitting iteration methods and establish its unconditional convergence theory. In particular, we derive a sharp upper bound about its asymptotic convergence rate and deduct the optimal value of its iteration parameter. The diagonal and Toeplitz splitting iteration method naturally leads to a diagonal and circulant splitting preconditioner. Analysis shows that the eigenvalues of the corresponding preconditioned matrix are clustered around 1, especially when the discretization step‐size h is small. Numerical results exhibit that the diagonal and circulant splitting preconditioner can significantly improve the convergence properties of GMRES and BiCGSTAB, and these preconditioned Krylov subspace iteration methods outperform the conjugate gradient method preconditioned by the approximate inverse circulant‐plus‐diagonal preconditioner proposed recently by Ng and Pan (M.K. Ng and J.‐Y. Pan, SIAM J. Sci. Comput. 2010;32:1442‐1464). Moreover, unlike this preconditioned conjugate gradient method, the preconditioned GMRES and BiCGSTAB methods show h‐independent convergence behavior even for the spatial fractional diffusion equations of discontinuous or big‐jump coefficients.