Toeplitz matrix

Summary

In linear algebra, a Toeplitz matrix or diagonal-constant matrix, named after Otto Toeplitz, is a matrix in which each descending diagonal from left to right is constant. For instance, the following matrix is a Toeplitz matrix:

Any matrix of the form

is a Toeplitz matrix. If the element of is denoted then we have

A Toeplitz matrix is not necessarily square.

Solving a Toeplitz system

edit

A matrix equation of the form

 

is called a Toeplitz system if   is a Toeplitz matrix. If   is an   Toeplitz matrix, then the system has at most only   unique values, rather than  . We might therefore expect that the solution of a Toeplitz system would be easier, and indeed that is the case.

Toeplitz systems can be solved by algorithms such as the Schur algorithm or the Levinson algorithm in   time.[1][2] Variants of the latter have been shown to be weakly stable (i.e. they exhibit numerical stability for well-conditioned linear systems).[3] The algorithms can also be used to find the determinant of a Toeplitz matrix in   time.[4]

A Toeplitz matrix can also be decomposed (i.e. factored) in   time.[5] The Bareiss algorithm for an LU decomposition is stable.[6] An LU decomposition gives a quick method for solving a Toeplitz system, and also for computing the determinant.

Properties

edit
  • An   Toeplitz matrix may be defined as a matrix   where  , for constants  . The set of   Toeplitz matrices is a subspace of the vector space of   matrices (under matrix addition and scalar multiplication).
  • Two Toeplitz matrices may be added in   time (by storing only one value of each diagonal) and multiplied in   time.
  • Toeplitz matrices are persymmetric. Symmetric Toeplitz matrices are both centrosymmetric and bisymmetric.
  • Toeplitz matrices are also closely connected with Fourier series, because the multiplication operator by a trigonometric polynomial, compressed to a finite-dimensional space, can be represented by such a matrix. Similarly, one can represent linear convolution as multiplication by a Toeplitz matrix.
  • Toeplitz matrices commute asymptotically. This means they diagonalize in the same basis when the row and column dimension tends to infinity.
  • For symmetric Toeplitz matrices, there is the decomposition
 
where   is the lower triangular part of  .
 
where   and   are lower triangular Toeplitz matrices and   is a strictly lower triangular matrix.[7]

Discrete convolution

edit

The convolution operation can be constructed as a matrix multiplication, where one of the inputs is converted into a Toeplitz matrix. For example, the convolution of   and   can be formulated as:

 
 

This approach can be extended to compute autocorrelation, cross-correlation, moving average etc.

Infinite Toeplitz matrix

edit

A bi-infinite Toeplitz matrix (i.e. entries indexed by  )   induces a linear operator on  .

 

The induced operator is bounded if and only if the coefficients of the Toeplitz matrix   are the Fourier coefficients of some essentially bounded function  .

In such cases,   is called the symbol of the Toeplitz matrix  , and the spectral norm of the Toeplitz matrix   coincides with the   norm of its symbol. The proof is easy to establish and can be found as Theorem 1.1 of.[8]

See also

edit
  • Circulant matrix, a square Toeplitz matrix with the additional property that  
  • Hankel matrix, an "upside down" (i.e., row-reversed) Toeplitz matrix
  • Szegő limit theorems – Determinant of large Toeplitz matrices
  • Toeplitz operator – compression of a multiplication operator on the circle to the Hardy space

Notes

edit

References

edit
  • Bojanczyk, A. W.; Brent, R. P.; de Hoog, F. R.; Sweet, D. R. (1995), "On the stability of the Bareiss and related Toeplitz factorization algorithms", SIAM Journal on Matrix Analysis and Applications, 16: 40–57, arXiv:1004.5510, doi:10.1137/S0895479891221563, S2CID 367586
  • Böttcher, Albrecht; Grudsky, Sergei M. (2012), Toeplitz Matrices, Asymptotic Linear Algebra, and Functional Analysis, Birkhäuser, ISBN 978-3-0348-8395-5
  • Brent, R. P. (1999), "Stability of fast algorithms for structured linear systems", in Kailath, T.; Sayed, A. H. (eds.), Fast Reliable Algorithms for Matrices with Structure, SIAM, pp. 103–116, doi:10.1137/1.9781611971354.ch4, hdl:1885/40746, S2CID 13905858
  • Chan, R. H.-F.; Jin, X.-Q. (2007), An Introduction to Iterative Toeplitz Solvers, SIAM, doi:10.1137/1.9780898718850, ISBN 978-0-89871-636-8
  • Chandrasekeran, S.; Gu, M.; Sun, X.; Xia, J.; Zhu, J. (2007), "A superfast algorithm for Toeplitz systems of linear equations", SIAM Journal on Matrix Analysis and Applications, 29 (4): 1247–66, CiteSeerX 10.1.1.116.3297, doi:10.1137/040617200
  • Chen, W. W.; Hurvich, C. M.; Lu, Y. (2006), "On the correlation matrix of the discrete Fourier transform and the fast solution of large Toeplitz systems for long-memory time series", Journal of the American Statistical Association, 101 (474): 812–822, CiteSeerX 10.1.1.574.4394, doi:10.1198/016214505000001069, S2CID 55893963
  • Hayes, Monson H. (1996), Statistical digital signal processing and modeling, Wiley, ISBN 0-471-59431-8
  • Krishna, H.; Wang, Y. (1993), "The Split Levinson Algorithm is weakly stable", SIAM Journal on Numerical Analysis, 30 (5): 1498–1508, doi:10.1137/0730078
  • Monahan, J. F. (2011), Numerical Methods of Statistics, Cambridge University Press, doi:10.1017/CBO9780511977176, ISBN 978-1-139-08211-2
  • Mukherjee, Bishwa Nath; Maiti, Sadhan Samar (1988), "On some properties of positive definite Toeplitz matrices and their possible applications" (PDF), Linear Algebra and Its Applications, 102: 211–240, doi:10.1016/0024-3795(88)90326-6
  • Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007), Numerical Recipes: The Art of Scientific Computing (3rd ed.), Cambridge University Press, ISBN 978-0-521-88068-8
  • Stewart, M. (2003), "A superfast Toeplitz solver with improved numerical stability", SIAM Journal on Matrix Analysis and Applications, 25 (3): 669–693, doi:10.1137/S089547980241791X, S2CID 15717371
  • Yang, Zai; Xie, Lihua; Stoica, Petre (2016), "Vandermonde decomposition of multilevel Toeplitz matrices with application to multidimensional super-resolution", IEEE Transactions on Information Theory, 62 (6): 3685–3701, arXiv:1505.02510, doi:10.1109/TIT.2016.2553041, S2CID 6291005

Further reading

edit