On the Elementwise Convergence of Continuous Functions of Hermitian Banded Toeplitz Matrices

Toeplitz matrices and functions of Toeplitz matrices (such as the inverse of a Toeplitz matrix, powers of a Toeplitz matrix or the exponential of a Toeplitz matrix) arise in many different theoretical and applied fields. They can be found in the mathematical modeling of problems where some kind of shift invariance occurs in terms of space or time. R. M. Gray's excellent tutorial monograph on Toeplitz and circulant matrices has been, and remains, the best elementary introduction to the Szegouml distribution theory on the asymptotic behavior of continuous functions of Toeplitz matrices. His asymptotic results, widely used in engineering due to the simplicity of its mathematical proofs, do not concern individual entries of these matrices but rather, they describe an "average" behavior. However, there are important applications where the asymptotic expressions of interest are directly related to the convergence of a single entry of a continuous function of a Toeplitz matrix. Using similar mathematical tools and to gain insight into the solutions of this sort of problems, the present correspondence derives new theoretical results regarding the convergence of these entries     

Adaptive Equalization Via Fast Quantized-State Methods

In adaptive equalization, there is a tradeoff between convergence rate of the equalizer tap coefficients, the computational speed for each adjustment, the implementation complexity, and algorithm robustness. Parameter update schemes called quantized state (QS) schemes, and fast versions of these schemes termed fast quantized state (FQS) schemes developed within a related context, are here applied to achieve attractive tradeoff options not previously available for adaptive equalization. Three novel simplifications to the QS schemes are introduced and justified by their performance characteristics in adaptive equalization. One simplification is to abandon the likeness to the method of instrumental variables (IV), where the "instrumental variable" is the quantized state vector, and introduce more quantization. Another simplification is to replace asymptotically Toeplitz matrices, or their inverses, by Toeplitz matrices to take advantage of fast schemes for updating QS schemes or taking their inverses.     

On the approximation of the discrete Karhunen-Loeve transform for stationary processes

Suboptimal fast transforms are useful substitutes to the optimal Karhunen-Loève transform (KLT). The selection of an efficient approximation for the KLT must be done with respect to some performance criterion that might differ from one application to another. A general class of criterion functions including most of the commonly used performance measures is introduced. They are shown to be optimized by the KLT. Various properties of the eigenvectors of the symmetric Toeplitz covariance matrix of a wide sense stationary process are reviewed. Several transforms such as the complex or real, odd and even Fourier transforms (DFT, DOFT, DREFT, DROFT), the cosine and even sine transforms (DCT, DEST) are obtained from the decomposition of a symmetric Toeplitz matrix in the sum of a circulant and a skew circulant matrix. These transforms are compared on the basis of a general performance criterion and appear to be good substitutes for the optimal KLT. Finally, it is shown that these transforms are asymptotically equivalent in performances to the KLT of an arbitrary wide sense stationary process.     

Fast computation of Toeplitz forms under narrowband conditions with applications to statistical signal processing

This paper describes methods for a fast and consistent computation of quadratic Toeplitz forms in a finite observation sequence of a stationary narrowband process. Exploiting the special structure of Toeplitz matrices, namely, their similarity to circulant matrices, the methods profit from known algorithms developed by Böhme [4] for the fast computation of circulant forms. Since many classical estimates of the correlation function and the spectral density can be interpreted as Toeplitz forms, the methods allow the development of new estimates. They compare favourably with the classical estimates and are more rapidly computable than many frequently used estimates when the process is sufficiently narrowband. Furthermore, the applicability of the methods to other signal processing tasks is indicated as the detection, classification, or parameter estimation of stochastic signals.     

Diagonalizing properties of the discrete cosine transforms

Since its introduction in 1974 by Ahmed et al., the discrete cosine transform (DCT) has become a significant tool in many areas of digital signal processing, especially in signal compression. There exist eight types of discrete cosine transforms (DCTs). We obtain the eight types of DCTs as the complete orthonormal set of eigenvectors generated by a general form of matrices in the same way as the discrete Fourier transform (DFT) can be obtained as the eigenvectors of an arbitrary circulant matrix. These matrices can be decomposed as the sum of a symmetric Toeplitz matrix plus a Hankel or close to Hankel matrix scaled by some constant factors. We also show that all the previously proposed generating matrices for the DCTs are simply particular cases of these general matrix forms. Using these matrices, we obtain, for each DCT, a class of stationary processes verifying certain conditions with respect to which the corresponding DCT has a good asymptotic behavior in the sense that it approaches Karhunen-Loeve transform performance as the block size N tends to infinity. As a particular result, we prove that the eight types of DCTs are asymptotically optimal for all finite-order Markov processes. We finally study the decorrelating power of the DCTs, obtaining expressions that show the decorrelating behavior of each DCT with respect to any stationary processes     

Conjugate-gradient preconditioning methods for shift-variant PETimage reconstruction

Gradient-based iterative methods often converge slowly for tomographic image reconstruction and image restoration problems, but can be accelerated by suitable preconditioners. Diagonal preconditioners offer some improvement in convergence rate, but do not incorporate the structure of the Hessian matrices in imaging problems. Circulant preconditioners can provide remarkable acceleration for inverse problems that are approximately shift-invariant, i.e., for those with approximately block-Toeplitz or block-circulant Hessians. However, in applications with nonuniform noise variance, such as arises from Poisson statistics in emission tomography and in quantum-limited optical imaging, the Hessian of the weighted least-squares objective function is quite shift-variant, and circulant preconditioners perform poorly. Additional shift-variance is caused by edge-preserving regularization methods based on nonquadratic penalty functions. This paper describes new preconditioners that approximate more accurately the Hessian matrices of shift-variant imaging problems. Compared to diagonal or circulant preconditioning, the new preconditioners lead to significantly faster convergence rates for the unconstrained conjugate-gradient (CG) iteration. We also propose a new efficient method for the line-search step required by CG methods. Applications to positron emission tomography (PET) illustrate the method.     

Lattice Sphere Decoding for Data Transmission Systems with Special Channel Matrices

This paper presents the effects of condition number ( \(\tau \) ) in communication system performance. It has been shown that a small condition number ( \(\tau \) ) results a better performance. The proposed scheme is using special kind of matrices with Lattice Sphere Decoding (LSD) technique for Block Data Transmission Systems (BDTS). Hankel and Toeplitz matrices are used separately as a channel matrix (H) while circulant matrix is used in the previous works. The proposed scheme reduced the condition number ( \(\tau \) ) and, therefore, improve the system performance. As a result; LSD-based BDTS with Toeplitz/Hankel matrix outperforms the LSD-based BDTS with circulant matrix. Complexity analysis is also done which based on lattice dimension and initial radius selection.     

Algorithm for the Characterization of the Cross-Correlation Structure in Multivariate Time Series

In this paper, it is shown that the block circulant matrix decomposition technique makes the multivariate singular spectrum analysis (M-SSA) a well suited tool for detecting of changes of the correlation structure in non-stationary multivariate time series in the presence of high observational noise levels. The major drawback of M-SSA, that it operates on a large covariance matrix and becomes computationally expensive, can be avoided by reordering the Toeplitz-block covariance matrix into a block Toeplitz matrix, embedding this into a block circulant matrix and efficiently block-diagonalizing this by the means of the Fast Fourier Transform (FFT) using the well known algorithm. The overall degree of synchronization among multiple-channel signals is defined by the synchronization index (the S-estimator) of the rearranged and truncated eigenvalue spectrum. Throughout the experiment, the high capability of the proposed algorithm to detect the lag-synchronized state under the influence of strong noise is validated with simulated data—a network of time series generated by autoregressive models (AR) and a network of coupled chaotic Roessler oscillators.     

Schur algorithms for Hermitian Toeplitz, and Hankel matrices withsingular leading principal submatrices

It is shown how a simple matrix algebra procedure can be used to induce Schur-type algorithms for the solution of certain Toeplitz and Hankel linear systems of equations when given Levinson-Durbin algorithms for such problems. The algorithm of P. Delsarte et al. (1985) for Hermitian Toeplitz matrices in the singular case is used to induce a Schur algorithm for such matrices. An algorithm due to G. Heinig and K. Rost (1984) for Hankel matrices in the singular case is used to induce a Schur algorithm for such matrices. The Berlekamp-Massey algorithm is viewed as a kind of Levinson-Durbin algorithm and so is used to induce a Schur algorithm for the minimal partial realization problem. The Schur algorithm for Hermitian Toeplitz matrices in the singular case is shown to be amenable to implementation on a linearly connected parallel processor array of the sort considered by Kung and Hu (1983), and in fact generalizes their result to the singular case     

Quasi-cyclic LDPC codes for fast encoding

In this correspondence we present a special class of quasi-cyclic low-density parity-check (QC-LDPC) codes, called block-type LDPC (B-LDPC) codes, which have an efficient encoding algorithm due to the simple structure of their parity-check matrices. Since the parity-check matrix of a QC-LDPC code consists of circulant permutation matrices or the zero matrix, the required memory for storing it can be significantly reduced, as compared with randomly constructed LDPC codes. We show that the girth of a QC-LDPC code is upper-bounded by a certain number which is determined by the positions of circulant permutation matrices. The B-LDPC codes are constructed as irregular QC-LDPC codes with parity-check matrices of an almost lower triangular form so that they have an efficient encoding algorithm, good noise threshold, and low error floor. Their encoding complexity is linearly scaled regardless of the size of circulant permutation matrices.     

低秩循环矩阵的构造方法及其关联的多元LDPC码

在图像处理中,低秩矩阵的冗余信息可用于图像恢复和图像特征提取,而在迭代译码中,校验矩阵的冗余行可以加快译码收敛速度。该文研究一类易于硬件实现的低秩循环矩阵。首先将循环矩阵转换为位置集合,并基于同构理论简化了位置集合的搜索空间,从而基于比特移位方法提出了循环矩阵的构造方法。考虑非零域元素的列赋值与矩阵秩之间的关系,选取Tanner图中没有长度为4的环的循环矩阵,基于非零域元素的列赋值思想提出了不同阶数、不同码率的多元LDPC码构造方法。数值仿真结果表明,与基于PEG算法构造的二元LDPC码比较,所构造的多元LDPC码在BPSK调制方式下在误码字率10–5附近有0.9 dB的增益;在与高阶调制相结合时,有更大的性能提升。此外,所构造的多元LDPC码在迭代5次与50次下的性能几乎一致,这为低时延高可靠通信提供了一种有效的候选编码方案。     

用MoM—PCG—FFT分析金属栅有限阵列的散射问题

本文用矩量法、预条件共轭梯度法和快速傅里叶变换（MoM-PCG-FFT)的混合技术来分析金属栅有限阵列的电磁散射问题。首先以等效电流作为未知函数建立积分方程组或积分－微分方程组,再用矩量法（脉冲／点匹配）获得一个线性代数方程组,其系数矩阵是一个对称二重复Toeplitz矩阵,基于这一特点,应用预条件共轭梯度法和快速傅里叶变换的结合算法（PCGFFT）来求解这个线性代数方程组,其中预条件器选用T.Chan循环预条件共轭梯度法和快速傅里叶变换的结合算法（PCGFFT）来求解这个线性代数方程组,其中预条件器选用T．Chan循环预条件器的二重分块形式。文中给出的数值算例表明该混合技术是有效的,适用于较大的金属栅有限阵列的分析。     

Estimation of structured covariance matrices

Covariance matrices from stationary time series are Toeplitz. Multichannel and multidimensional processes have covariance matrices of block Toeplitz form. In these cases and many other situations, one knows that the actual covariance matrix belongs to a particular subclass of covariance matrices. This paper discusses a method for estimating a covariance matrix of specified structure from vector samples of the random process. The theoretical foundation of the method is to assume that the random process is zero-mean multivariate Gaussian, and to find the maximum-likelihood covariance matrix that has the specified structure. An existence proof is given and the solution is interpreted in terms of a minimum-entropy principle. The necessary gradient conditions that must be satisfied by the maximum-likelihood solution are derived and unique and nonunique analytic solutions for some simple problems are presented. A major contribution of this paper is an iterative algorithm that solves the necessary gradient equations for moderate-sized problems with reasonable computational ease. Theoretical convergence properties of the basic algorithm are investigated and robust modifications discussed. In doing maximum-entropy spectral analysis of a sine wave in white noise from a single vector sample, this new estimation procedure causes no splitting of the spectral line in contrast to the Burg technique.     

Simple bounds on the extreme eigenvalues of Toeplitz matrices

Simple bounds are presented on the extreme eigenvalues of n ×n-dimensional Hermitian Toeplitz matrices. Such a matrix, say T_n, is determined by its first row. The proposed bounds have low complexity O(n); furthermore, examples are presented for which the proposed bounds are tighter than the Slepian-Landau bounds at their best, i.e. when the extreme eigenvalues of the submatrix obtained by deleting the first row and first column of T_n are known exactly. The bounds are first presented on the extreme eigenvalues of Hermitian Toeplitz matrices: the corresponding bounds for real symmetric Toeplitz matrices follow as a special case. Then, these bounds are extended to Hermitian Toeplitz interval matrices     

Symmetric convolution of asymmetric multidimensional sequencesusing discrete trigonometric transforms

This paper uses the fact that the discrete Fourier transform diagonalizes a circulant matrix to provide an alternate derivation of the symmetric convolution-multiplication property for discrete trigonometric transforms. Derived in this manner, the symmetric convolution-multiplication property extends easily to multiple dimensions using the notion of block circulant matrices and generalizes to multidimensional asymmetric sequences. The symmetric convolution of multidimensional asymmetric sequences can then be accomplished by taking the product of the trigonometric transforms of the sequences and then applying an inverse trigonometric transform to the result. An example is given of how this theory can be used for applying a two-dimensional (2-D) finite impulse response (FIR) filter with nonlinear phase which models atmospheric turbulence.     

Quasi-cyclic LDPC codes using overlapping matrices and their layered decoders

Quasi-cyclic (QC) low-density parity-check (LDPC) codes have the parity-check matrices consisting of circulant matrices. Since QC LDPC codes whose parity-check matrices consist of only circulant permutation matrices are difficult to support layered decoding and, at the same time, have a good degree distribution with respect to error correcting performance, adopting multi-weight circulant matrices to parity-check matrices is useful but it has not been much researched. In this paper, we propose a new code structure for QC LDPC codes with multi-weight circulant matrices by introducing overlapping matrices. This structure enables a system to operate on dual mode in an efficient manner, that is, a standard QC LDPC code is used when the channel is relatively good and an enhanced QC LDPC code adopting an overlapping matrix is used otherwise. We also propose a new dual mode parallel decoder which supports the layered decoding both for the standard QC LDPC codes and the enhanced QC LDPC codes. Simulation results show that QC LDPC codes with the proposed structure have considerably improved error correcting performance and decoding throughput.     

Fast cosine transform of Toeplitz matrices, algorithm andapplications

A fast algorithm for the discrete cosine transform (DCT) of a Toeplitz matrix of order N is derived. Only O(N log N)+O(M) time is needed for the computation of M elements. The storage requirement is O(N). The method carries over to other transforms (DFT, DST) and to Hankel or circulant matrices. Some applications of the algorithm are discussed     

Two methods for Toeplitz-plus-Hankel approximation to a datacovariance matrix

Recently, fast algorithms have been developed for computing the optimal linear least squares prediction filters for nonstationary random processes (fields) whose covariances have (block) Toeplitz-Hankel form. If the covariance of the random process (field) must be estimated from the data, the following problem is presented: given a data covariance matrix, computer from the available data, find the Toeplitz-plus-Hankel matrix closest to this matrix in some sense. The authors give two procedures for computing the Toeplitz-plus-Hankel matrix that minimizes the Hilbert-Schmidt norm of the difference between the two matrices. The first approach projects the data covariance matrix onto the subspace of Toeplitz-plus-Hankel matrices, for which basis functions can be computed using a Gram-Schmidt orthonormalization. The second approach projects onto the subspace of symmetric Toeplitz plus skew-persymmetric Hankel matrices, resulting in a much simpler algorithm. The extension to block Toeplitz-plus-Hankel data covariance matrix approximation is also addressed     

An algorithm for solving discrete-time Wiener-Hopf equations based upon Euclid's algorithm

An algorithm for solving a discrete-time Wiener-Hopf equation is presented based upon Euclid's algorithm. The discrete-time Wiener-Hopf equation is a system of linear inhomogeneous equations with a given Toeplitz matrix M, a given vector b, and an unknown vectorlambdasuch thatMlambda = b. The algorithm is able to find a solution of the discrete-time Wiener-Hopf equation for any type of Toeplitz matrices except for the all-zero matrix, while the Levinson algorithm and the Trench algorithm are not available when at least one of the principal submatrices of the Toeplitz matrixMis singular. The algorithm gives a solution, if one exists, even when the Toeplitz matrixMis singular, while the Brent-Gustavson-Yun algorithm only states that the Toeplitz matrixMis singular. The algorithm requiresO(t^{2})arithmetic operations fortunknowns, in the sense that the number of multiplications or divisions is directly proportional tot^{2}, like the Levinson and Trench algorithms. Furthermore, a faster algorithm is also presented based upon the half greatest common divisor algorithm, and hence it requiresO(t log^{2} t)arithmetic operations, like the Brent-Gustavson-Yun algorithm.