Jump to content
Search

Toeplitz matrix

From Wikipedia, the free encyclopedia

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:

{\displaystyle \qquad {\begin{bmatrix}a&b&c&d&e\\f&a&b&c&d\\g&f&a&b&c\\h&g&f&a&b\\i&h&g&f&a\end{bmatrix}}.}

Any {\displaystyle n\times n} matrix {\displaystyle A} of the form

{\displaystyle A={\begin{bmatrix}a_{0}&a_{-1}&a_{-2}&\cdots &\cdots &a_{-(n-1)}\\a_{1}&a_{0}&a_{-1}&\ddots &&\vdots \\a_{2}&a_{1}&\ddots &\ddots &\ddots &\vdots \\\vdots &\ddots &\ddots &\ddots &a_{-1}&a_{-2}\\\vdots &&\ddots &a_{1}&a_{0}&a_{-1}\\a_{n-1}&\cdots &\cdots &a_{2}&a_{1}&a_{0}\end{bmatrix}}}

is a Toeplitz matrix. If the {\displaystyle i,j} element of {\displaystyle A} is denoted {\displaystyle A_{i,j}} then we have

{\displaystyle A_{i,j}=A_{i+1,j+1}=a_{i-j}.}

A Toeplitz matrix is not necessarily square.

Solving a Toeplitz system

[edit]

A matrix equation of the form

{\displaystyle Ax=b}

is called a Toeplitz system if {\displaystyle A} is a Toeplitz matrix. If {\displaystyle A} is an {\displaystyle n\times n} Toeplitz matrix, then the system has at most only {\displaystyle 2n-1} unique values, rather than {\displaystyle n^{2}}. 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 {\displaystyle O(n^{2})} 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 {\displaystyle O(n^{2})} time.[4]

A Toeplitz matrix can also be decomposed (i.e. factored) in {\displaystyle O(n^{2})} 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. Using displacement rank we obtain method requiring {\displaystyle {\tilde {O}}({\alpha ^{\omega -1}}n)} ops with the use of fast matrix multiplication algorithms, where {\displaystyle \alpha } is the rank and {\displaystyle ^{\sim }2.37\leq \omega <3}[7].

Properties

[edit]
{\displaystyle {\frac {1}{a_{0}}}A=GG^{\operatorname {T} }-(G-I)(G-I)^{\operatorname {T} }}
where {\displaystyle G} is the lower triangular part of {\displaystyle {\frac {1}{a_{0}}}A}.
{\displaystyle A^{-1}={\frac {1}{\alpha _{0}}}(BB^{\operatorname {T} }-CC^{\operatorname {T} })}
where {\displaystyle B} and {\displaystyle C} are lower triangular Toeplitz matrices and {\displaystyle C} is a strictly lower triangular matrix.[9]

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 {\displaystyle h} and {\displaystyle x} can be formulated as:

{\displaystyle y=h\ast x={\begin{bmatrix}h_{1}&0&\cdots &0&0\\h_{2}&h_{1}&&\vdots &\vdots \\h_{3}&h_{2}&\cdots &0&0\\\vdots &h_{3}&\cdots &h_{1}&0\\h_{m-1}&\vdots &\ddots &h_{2}&h_{1}\\h_{m}&h_{m-1}&&\vdots &h_{2}\\0&h_{m}&\ddots &h_{m-2}&\vdots \\0&0&\cdots &h_{m-1}&h_{m-2}\\\vdots &\vdots &&h_{m}&h_{m-1}\\0&0&0&\cdots &h_{m}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\\x_{3}\\\vdots \\x_{n}\end{bmatrix}}}
{\displaystyle y^{T}={\begin{bmatrix}h_{1}&h_{2}&h_{3}&\cdots &h_{m-1}&h_{m}\end{bmatrix}}{\begin{bmatrix}x_{1}&x_{2}&x_{3}&\cdots &x_{n}&0&0&0&\cdots &0\\0&x_{1}&x_{2}&x_{3}&\cdots &x_{n}&0&0&\cdots &0\\0&0&x_{1}&x_{2}&x_{3}&\ldots &x_{n}&0&\cdots &0\\\vdots &&\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\cdots &0&0&x_{1}&\cdots &x_{n-2}&x_{n-1}&x_{n}&0\\0&\cdots &0&0&0&x_{1}&\cdots &x_{n-2}&x_{n-1}&x_{n}\end{bmatrix}}.}

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 {\displaystyle \mathbb {Z} \times \mathbb {Z} }) {\displaystyle A} induces a linear operator on {\displaystyle \ell ^{2}}.

{\displaystyle A={\begin{bmatrix}&\vdots &\vdots &\vdots &\vdots \\\cdots &a_{0}&a_{-1}&a_{-2}&a_{-3}&\cdots \\\cdots &a_{1}&a_{0}&a_{-1}&a_{-2}&\cdots \\\cdots &a_{2}&a_{1}&a_{0}&a_{-1}&\cdots \\\cdots &a_{3}&a_{2}&a_{1}&a_{0}&\cdots \\&\vdots &\vdots &\vdots &\vdots \end{bmatrix}}.}

The induced operator is bounded if and only if the coefficients of the Toeplitz matrix {\displaystyle A} are the Fourier coefficients of some essentially bounded function {\displaystyle f}.

In such cases, {\displaystyle f} is called the symbol of the Toeplitz matrix {\displaystyle A}, and the spectral norm of the Toeplitz matrix {\displaystyle A} coincides with the {\displaystyle L^{\infty }} norm of its symbol. The proof can be found as Theorem 1.1 of Böttcher and Grudsky.[10]

See also

[edit]

Notes

[edit]
  1. ↑ Press et al. 2007, §2.8.2—Toeplitz matrices
  2. ↑ Hayes 1996, Chapter 5.2.6
  3. ↑ Krishna & Wang 1993
  4. ↑ Monahan 2011, §4.5—Toeplitz systems
  5. ↑ Brent 1999
  6. ↑ Bojanczyk et al. 1995
  7. ↑ Bostan, A.; Jeannerod, C.-P.; Schost, É. (2008). "Solving structured linear systems with large displacement rank". Theoretical Computer Science. 407 (1–3): 155–181. doi:10.1016/j.tcs.2008.05.014.
  8. ↑ Grenander, Ulf; Szegő, Gábor (1958). Toeplitz Forms and Their Applications. Berkeley, CA: University of California Press.
  9. ↑ Mukherjee & Maiti 1988
  10. ↑ Böttcher & Grudsky 2012

References

[edit]

Further reading

[edit]
Retrieved from "https://en.wikipedia.org/w/index.php?title=Toeplitz_matrix&oldid=1360186056"
Toeplitz matrix
Add topic
Morty Proxy This is a proxified and sanitized view of the page, visit original site.