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.     

Recursive and iterative algorithms for computing eigenvalues ofHermitian Toeplitz matrices

The numerical solution of the complete eigenspectrum for Hermitian Toeplitz matrices is presented. Trench's algorithm (1989), which employs bisection on contiguous intervals, and the Pegasus method are used to achieve estimates of distinct eigenvalues. Several modifications of Trench's algorithm are examined; the goals are an increase in the rate of convergence, even at some reduction in estimate accuracy, and an accommodation of eigenvalue multiplicity or clustering. A promising approach that contains three key ingredients is found. They are: a modification of Trench's procedure to employ noncontiguous intervals, a procedure for multiplicity identification, and a replacement of the Pegasus method by the modified Rayleigh quotient iteration. The result is the basis for a novel eigenspectrum solver with a cubic convergence rate and good estimation accuracy. Simulation results for high-order Hermitian Toeplitz matrices are provided     

Algorithm for wavelet transform of Toeplitz matrices

An algorithm is presented for calculating the 2D wavelet transform of a Toeplitz matrix. The algorithm exploits the special form of the Toeplitz matrix in order to reduce the number of operations required. More specifically. It is shown that the number of 1D wavelet transformations that are necessary to carry out a sub-band decomposition can be reduced to eight     

Algorithm for cosine transform of Toeplitz matrices

An algorithm for calculating the 2D cosine transform of a Toeplitz matrix is presented. The algorithm is based on the application of 1D cosine transforms. More specifically, four 1D cosine transforms of size N are needed to obtain the transform of a Toeplitz matrix of size N×N. This is an improvement over previously published algorithms. The algorithm is also simple and regular     

Distribution of ordered eigenvalues of Wishart matrices

Simple, exact and computationally efficient expressions for the cumulative distribution function and the probability density function of the lth largest eigenvalue of a Wishart matrix are presented. The results are important in the performance analysis of multiple-input, multiple-output systems operating over Rayleigh fading channels     

Construction of a Hermitian Toeplitz matrix from an arbitrary setof eigenvalues

A solution to the inverse eigenvalue problem for Hermitian Toeplitz matrices is presented. The approach taken is to first construct a real symmetric negacyclic matrix of order 2n and to then relate the negacyclic matrix to a Hermitian Toeplitz matrix of order n with the desired eigenspectrum     

Bounds on the size of nonnegative definite circulant embeddings ofpositive definite Toeplitz matrices

Dembo et al. (see ibid., vol. 35, pp. 1206-1212, 1989) showed that an N×N positive definite Toeplitz matrix T could be embedded in a 2M×2M nonnegative definite circulant matrix S with M=O[κ(T)N ²]. This paper shows that the size of the embedding can be reduced to M=O[κ(T)^1/2N^5/4] and that this is best possible for the technique presented by Dembo et al     

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     

On the convergence of the inverses of Toeplitz matrices and its applications

Many issues in signal processing involve the inverses of Toeplitz matrices. One widely used technique is to replace Toeplitz matrices with their associated circulant matrices, based on the well-known fact that Toeplitz matrices asymptotically converge to their associated circulant matrices in the weak sense. This often leads to considerable simplification. However, it is well known that such a weak convergence cannot be strengthened into strong convergence. It is this fact that severely limits the usefulness of the close relation between Toeplitz matrices and circulant matrices. Observing that communication receiver design often needs to seek optimality in regard to a data sequence transmitted within finite duration, we define the finite-term strong convergence regarding two families of matrices. We present a condition under which the inverses of a Toeplitz matrix converges in the strong sense to a circulant matrix for finite-term quadratic forms. This builds a critical link in the application of the convergence theorems for the inverses of Toeplitz matrices since the weak convergence generally finds its usefulness in issues associated with minimum mean squared error and the finite-term strong convergence is useful in issues associated with the maximum-likelihood or maximum a posteriori principles.     

The eigenvalues of matrices that occur in certain interpolationproblems

The eigenvalues of the matrices that occur in certain finite-dimensional interpolation problems are directly related to their well posedness and strongly depend on the distribution of the interpolation knots, that is, on the sampling set. We study this dependency as a function of the sampling set itself and give accurate bounds for the eigenvalues of the interpolation matrices. The bounds can be evaluated in as few as four arithmetic operations, and therefore, they greatly simplify the assessment of sampling sets regarding numerical stability. The accuracy and usefulness of the bounds are illustrated with examples     

Toeplitz properties of the block matrices encountered in theprocessing of spatiotemporal signals

Various signal processing applications, such as system identification, FIR (finite impulse response) Wiener filtering, linear prediction, and spectral estimation, are known to lead to the solution of Toeplitz systems for the case of one-dimensional signals and to Toeplitz-block Toeplitz systems for the case of two-dimensional signals. The authors investigate such systems for the case of L-dimensional signals with L>2 and emphasize their block and persymmetrical nature. Such important characteristics allow the use of fast algorithms for signals of any dimension. The case of three-dimensional signals is treated in detail not only because it is of special interest for video applications, but also because the reasoning used for this case can be straightforwardly applied to higher-dimension signals     

Inferring the eigenvalues of covariance matrices from limited,noisy data

The eigenvalue spectrum of covariance matrices is of central importance to a number of data analysis techniques. Usually, the sample covariance matrix is constructed from a limited number of noisy samples. We describe a method of inferring the true eigenvalue spectrum from the sample spectrum. Results of Silverstein (1986), which characterize the eigenvalue spectrum of the noise covariance matrix, and inequalities between the eigenvalues of Hermitian matrices are used to infer probability densities for the eigenvalues of the noise-free covariance matrix, using Bayesian inference. Posterior densities for each eigenvalue are obtained, which yield error estimates. The evidence framework gives estimates of the noise variance and permits model order selection by estimating the rank of the covariance matrix. The method is illustrated with numerical examples     

Evaluation of constituent matrices of a companion matrix with repeated eigenvalues

An analytical function of a companion matrix with repeated eigenvalues is expressed in terms of constituent matrices. The constituent matrices are then found to be equal to the product of two matrices with elements partly from a certain matrix and its inversion. This matrix may be either a Vandermonde matrix or a modal matrix. Equations for computing these matrices are given as a power series of x which is very useful for both hand and machine computations.     

Simple bounds on modal propagation constant for arbitrarily shapedoptical fibres

The authors show that, when a fibre core cross-section is distorted from circular, the fundamental mode propagation constant β always decreases. To complement the upper bound on β thus obtained, a second approximation is given to β resulting in a simple lower bound and which only requires computation of a geometric shape factor and results for circular cross-sections. The results hold for arbitrary shape and grading     

A direct approach to the constituent matrices of an arbitrary matrix with multiple eigenvalues

A direct approach for computing the constituent matrices of an arbitrary square constant matrix is presented. The technique, which involves finding the partial fraction expansion coefficients, requires only straightforward matrix multiplications.     

Generalized eigenvector problem for Hermitian Toeplitz matrices and its application to beamforming

The generalized eigenvector problem (GEP) for Hermitian Toeplitz matrices is studied and some properties related to its eigenvectors and the associated eigenfilters are derived. Zero locations of the eigenfilters are also investigated and all of the results are applied to the maximum SINR (signal-to-interference-plus-noise ratio) beamforming problem based on ULAs (uniform linear arrays), since maximizing output SINR can be formulated as a generalized eigenvector problem where the matrix pair consisting of the desired signal correlation matrix and interference plus noise correlation matrix. Theoretical analysis based on a three-element ULA is provided, supported by simulations.     

Eigenvector properties of Toeplitz matrices and their application to spectral analysis of time series

This paper presents a proof for an important eigenvector property of Toeplitz matrices. The property, a variant of Caratheodory's theorem, is that the zeroes of the polynomials formed from eigenvectors with unique maximum/minimum eigenvalues of a positive definite Toeplitz matrix are distinct and lie on the unit circle. The proof is based on simple matrix-theoretical results and offers an insight that is lacking in existing proofs. A representation form for Toeplitz matrices is obtained and this form is used for justification of Pisarenko's spectral analysis based on eigenvectors/eigenvalues of the covariance matrix. The theoretical groundwork developed for the proof of the eigenvector property is then used to compare Pisarenko's null eigenvector technique with Burg's maximum entropy analysis, and arguments are presented in favor of the former technique.     

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     

NOTE ON THE JOHNSON''''S BOUNDS AND GRAHAM''''S BOUNDS FOR CONSTANT WEIGHT CODES

This paper presents four classes of codes which meet the Johnson's upper bound and twoclasses of codes which have gone beyond the Graham's lower bound.     

Simple expressions for worst and best case Cramer-Rao bounds foramplitude and phase estimation of low-frequency sinusoid

Simple expressions are presented for the worst and best case Cramer-Rao bounds for amplitude and phase estimation of a sinusoid in additive white Gaussian noise. The expressions are valid in the sub-Rayleigh region where the difference between the critical bounds becomes important