A fast algorithm for computing the smallest eigenvalue of a symmetric positive‐definite Toeplitz matrix

Recent progress in signal processing and estimation has generated considerable interest in the problem of computing the smallest eigenvalue of a symmetric positive‐definite (SPD) Toeplitz matrix. An algorithm for computing upper and lower bounds to the smallest eigenvalue of a SPD Toeplitz matrix has been recently derived (Linear Algebra Appl. 2007; DOI: 10.1016/j.laa.2007.05.008 ). The algorithm relies on the computation of the R factor of the QR factorization of the Toeplitz matrix and the inverse of R. The simultaneous computation of R and R^?1 is efficiently accomplished by the generalized Schur algorithm. In this paper, exploiting the properties of the latter algorithm, a numerical method to compute the smallest eigenvalue and the corresponding eigenvector of SPD Toeplitz matrices in an accurate way is proposed. Copyright © 2008 John Wiley & Sons, Ltd.     

关于Toeplitz矩阵的某些注记

In this paper,we study real symmetric Toeplitz matrices commutable with tridi-agonal matrices, present more detailed results than those in [1], and extend them to non-symmetric Toeplitz matrices. Also, complex Toeplitz matrices, especially the corresponding matrices of lower order, are discussed.     

An eigenvalue problem for a symmetric Toeplitz matrix

An algorithm is developed which determines eigenvalues for a symmetric Toeplitz matrix. To this end, we substantiate the generality of eigenvalues problems for a symmetric Toeplitz matrix and for a persymmetric Hankel one. The latter is reduced to an eigenvalue problem for a persymmetric Jacobi matrix. In the even order case, the problem reduces to a Jacobi matrix with halved order.     

实对称五对角矩阵逆特征值问题

1 引 言 对于n阶实对称矩阵A=(aij),r是一个正整数,且1≤r≤n-1,当|i-j|>r时,aij=0(i,j=1,2,…,n),至少有一个i使得ai,i+r≠0,则称矩阵A是带宽为2r+1的实对称带状矩阵.特别地,当r=1时,称A为实对称三对角矩阵;当r=2时,称A为实对称五对角矩阵. 实对称带状矩阵逆特征值问题应用十分广泛,这类问题不仅来自微分方程逆特征值问     

A Proposal for Toeplitz Matrix Calculations

In contrast to the usual (and successful) direct methods for Toeplitz systems Ax = b, we propose an algorithm based on the conjugate gradient method. The preconditioner is a circulant, so that all matrices have constant diagonals and all matrix-vector multiplications use the Fast Fourier Transform. We also suggest a technique for the eigenvalue problem, where current methods are less satisfactory. If the first indications are supported by further experiment, this new approach may have useful applications—including nearly Toeplitz systems, and parallel computations.     

关于周期对称三对角矩阵的广义特征值反问题

在给定部分特征值、部分特征向量及附加条件下提出了一类反问题,并给出了此问题解存在性的证明及求解的算法.     

Equilibrium problem for the eigenvalues of banded block Toeplitz matrices

We consider banded block Toeplitz matrices T_n with n block rows and columns. We show that under certain technical assumptions, the normalized eigenvalue counting measure of T_n for n → ∞ weakly converges to one component of the unique vector of measures that minimizes a certain energy functional. In this way we generalize a recent result of Duits and Kuijlaars for the scalar case. Along the way we also obtain an equilibrium problem associated to an arbitrary algebraic curve, not necessarily related to a block Toeplitz matrix. For banded block Toeplitz matrices, there are several new phenomena that do not occur in the scalar case: (i) The total masses of the equilibrium measures do not necessarily form a simple arithmetic series but in general are obtained through a combinatorial rule; (ii) The limiting eigenvalue distribution may contain point masses, and there may be attracting point sources in the equilibrium problem; (iii) More seriously, there are examples where the connection between the limiting eigenvalue distribution of T_n and the solution to the equilibrium problem breaks down. We provide sufficient conditions guaranteeing that no such breakdown occurs; in particular we show this if T_n is a Hessenberg matrix.     

Extreme eigenvalues of real symmetric Toeplitz matrices

We exploit the even and odd spectrum of real symmetric Toeplitz matrices for the computation of their extreme eigenvalues, which are obtained as the solutions of spectral, or secular, equations. We also present a concise convergence analysis for a method to solve these spectral equations, along with an efficient stopping rule, an error analysis, and extensive numerical results.

     

Distribution of Eigenvalues of Real Symmetric Palindromic Toeplitz Matrices and Circulant Matrices

Consider the ensemble of real symmetric Toeplitz matrices, each independent entry an i.i.d. random variable chosen from a fixed probability distribution p of mean 0, variance 1, and finite higher moments. Previous investigations showed that the limiting spectral measure (the density of normalized eigenvalues) converges weakly and almost surely, independent of p, to a distribution which is almost the standard Gaussian. The deviations from Gaussian behavior can be interpreted as arising from obstructions to solutions of Diophantine equations. We show that these obstructions vanish if instead one considers real symmetric palindromic Toeplitz matrices, matrices where the first row is a palindrome. A similar result was previously proved for a related circulant ensemble through an analysis of the explicit formulas for eigenvalues. By Cauchy’s interlacing property and the rank inequality, this ensemble has the same limiting spectral distribution as the palindromic Toeplitz matrices; a consequence of combining the two approaches is a version of the almost sure Central Limit Theorem. Thus our analysis of these Diophantine equations provides an alternate technique for proving limiting spectral measures for certain ensembles of circulant matrices. A. Massey’s current address: Department of Mathematics, UCLA, Los Angeles, CA 90095, USA. e-mail: amassey3102@math.ucla.edu.     

A mean value algorithm for Toeplitz matrix completion

In this paper, we propose a new mean value algorithm for the Toeplitz matrix completion based on the singular value thresholding (SVT) algorithm. The completion matrices generated by the new algorithm keep a feasible Toeplitz structure. Meanwhile, we prove the convergence of the new algorithm under some reasonal conditions. Finally, we show the new algorithm is much more effective than the ALM (augmented Lagrange multiplier) algorithm through numerical experiments and image inpainting.     

A note on inversion of Toeplitz matrices

It is shown that the invertibility of a Toeplitz matrix can be determined through the solvability of two standard equations. The inverse matrix can be denoted as a sum of products of circulant matrices and upper triangular Toeplitz matrices. The stability of the inversion formula for a Toeplitz matrix is also considered.     

Computing a Nearest P-Symmetric Nonnegative Definite Matrix Under Linear Restriction

Let $P$ be an $n\times n$ symmetric orthogonal matrix. A real $n\times n$ matrix $A$ is called P-symmetric nonnegative definite if $A$ is symmetric nonnegative definite and $(PA)^T=PA$. This paper is concerned with a kind of inverse problem for P-symmetric nonnegative definite matrices: Given a real $n\times n$ matrix $\widetilde{A}$, real $n\times m$ matrices $X$ and $B$, find an $n\times n$ P-symmetric nonnegative definite matrix $A$ minimizing $||A-\widetilde{A}||_F$ subject to $AX =B$. Necessary and sufficient conditions are presented for the solvability of the problem. The expression of the solution to the problem is given. These results are applied to solve an inverse eigenvalue problem for P-symmetric nonnegative definite matrices.     

On algebras of Toeplitz fuzzy matrices

In this paper, necessary and sufficient conditions are given for a product of Toeplitz fuzzy matrices to be Toeplitz. As an application, a criterion for normality of Toeplitz fuzzy matrices is derived and conditions are deduced for symmetric idempotency of Toeplitz fuzzy matrices. We discuss similar results for Hankel fuzzy matrices. Keywords: Fuzzy matrix, Toeplitz and Hankel matrices.     

Structure preserving eigenvalue embedding for undamped gyroscopic systems

This paper concerns the eigenvalue embedding problem of undamped gyroscopic systems. Based on a low-rank correction form, the approach moves the unwanted eigenvalues to desired values and the remaining large number eigenvalues and eigenvectors of the original system do not change. In addition, the symmetric structure of mass and stiffness matrices and the skew-symmetric structure of gyroscopic matrix are all preserved. By utilizing the freedom of the eigenvectors, an expression of parameterized solutions to the eigenvalue embedding problem is derived. Finally, a minimum modification algorithm is proposed to solve the eigenvalue embedding problem. Numerical examples are given to show the application of the proposed method.     

Analytical inversion of general periodic tridiagonal matrices

In this paper we present an analytical forms for the inversion of general periodic tridiagonal matrices, and provide some very simple analytical forms which immediately lead to closed formulae for some special cases such as symmetric or perturbed Toeplitz for both periodic and non-periodic tridiagonal matrices. An efficient computational algorithm for finding the inverse of any general periodic tridiagonal matrices from the analytical form is given, it is suited for implementation using Computer Algebra systems such as MAPLE, MATLAB, MACSYMA, and MATHEMATICA. An example is also given to illustrate the algorithm.     

Generating equations approach for quadratic matrix equations

We show how Van Loan's method for annulling the (2,1) block of skew‐Hamiltonian matrices by symplectic‐orthogonal similarity transformation generalizes to general matrices and provides a numerical algorithm for solving the general quadratic matrix equation: For skew‐Hamiltonian matrices we find their canonical form under a similarity transformation and find the class of all symplectic‐orthogonal similarity transformations for annulling the (2,1) block and simultaneously bringing the (1,1) block to Hessenberg form. We present a structure‐preserving algorithm for the solution of continuous‐time algebraic Riccati equation. Unlike other methods in the literature, the final transformed Hamiltonian matrix is not in Hamiltonian–Schur form. Three applications are presented: (a) for a special system of partial differential equations of second order for a single unknown function, we obtain the matrix of partial derivatives of second order of the unknown function by only algebraic operations and differentiation of functions; (b) for a similar transformation of a complex matrix into a symmetric (and three‐diagonal) one by applying only finite algebraic transformations; and (c) for finite‐step reduction of the eigenvalues–eigenvectors problem of a Hermitian matrix to the eigenvalues– eigenvectors problem of a real symmetric matrix of the same dimension. Copyright © 1999 John Wiley & Sons, Ltd.     

Eigenvalues and eigenvectors of banded Toeplitz matrices and the related symbols

It is known that for a tridiagonal Toeplitz matrix, having on the main diagonal the constant a₀ and on the two first off‐diagonals the constants a₁(lower) and a₋₁(upper), which are all complex values, there exist closed form formulas, giving the eigenvalues of the matrix and a set of associated eigenvectors. For example, for the 1D discrete Laplacian, this triple is (a₀,a₁,a₋₁)=(2,−1,−1). In the first part of this article, we consider a tridiagonal Toeplitz matrix of the same form (a₀,a_ω,a_−ω), but where the two off‐diagonals are positioned ω steps from the main diagonal instead of only one. We show that its eigenvalues and eigenvectors can also be identified in closed form and that interesting connections with the standard Toeplitz symbol are identified. Furthermore, as numerical evidences clearly suggest, it turns out that the eigenvalue behavior of a general banded symmetric Toeplitz matrix with real entries can be described qualitatively in terms of the symmetrically sparse tridiagonal case with real a₀, a_ω=a_−ω, ω=2,3,…, and also quantitatively in terms of those having monotone symbols. A discussion on the use of such results and on possible extensions complements the paper.     

Eigenvectors of Hessenberg Toeplitz matrices and a problem by Dai,Geary, and Kadanoff

The paper is devoted to the eigenvectors of Hessenberg Toeplitz matrices whose symbol has a power singularity. We describe the structure of the eigenvectors and prove an asymptotic formula which can be used to compute individual eigenvectors effectively. The symbols of our matrices are special Fisher–Hartwig symbols, and the theorem of this paper confirms and makes more precise a conjecture by Dai, Geary, and Kadanoff of 2009 in a particular case.     

广义块Toeplitz特征值问题的基于sine变换的预处理子

在求块Toeplitz矩阵束（Amn，Bmn）特征值的Lanczos过程中，通过对移位块Toepltz矩阵Amn-ρBmn进行基于sine变换的块预处理，从而改进了位移块Toeplitz矩阵的谱分布，加速了Lanczos过程的收敛速度．该块预处理方法能通过快速算法有效快速执行．本文证明了预处理后Lanczos过程收敛迅速，并通过实验证明该算法求解大规模矩阵问题尤其有效．