Matriz de Toeplitz

Matriz con filas desplazadas

En álgebra lineal , una matriz de Toeplitz o matriz diagonal constante , llamada así por Otto Toeplitz , es una matriz en la que cada diagonal descendente de izquierda a derecha es constante. Por ejemplo, la siguiente matriz es una matriz de Toeplitz:

${\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}}.}$

Cualquier matriz de la forma ${\displaystyle n\times n}$ ${\displaystyle A}$

${\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}}}$

es una matriz de Toeplitz . Si el elemento de se denota entonces tenemos ${\displaystyle i,j}$ ${\displaystyle A}$ ${\displaystyle A_{i,j}}$

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

Una matriz de Toeplitz no es necesariamente cuadrada .

Solución de un sistema de Toeplitz

Una ecuación matricial de la forma

${\displaystyle Ax=b}$

se denomina sistema de Toeplitz si es una matriz de Toeplitz. Si es una matriz de Toeplitz, entonces el sistema tiene como máximo valores únicos, en lugar de . Por lo tanto, podríamos esperar que la solución de un sistema de Toeplitz fuera más fácil, y de hecho ese es el caso. ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle n\times n}$ ${\displaystyle 2n-1}$ ${\displaystyle n^{2}}$

Los sistemas de Toeplitz se pueden resolver mediante algoritmos como el algoritmo de Schur o el algoritmo de Levinson en el tiempo. ^{[1] [2]} Se ha demostrado que las variantes de este último son débilmente estables (es decir, exhiben estabilidad numérica para sistemas lineales bien acondicionados ). ^[3] Los algoritmos también se pueden utilizar para encontrar el determinante de una matriz de Toeplitz en el tiempo. ^[4] ${\displaystyle O(n^{2})}$ ${\displaystyle O(n^{2})}$

Una matriz de Toeplitz también se puede descomponer (es decir, factorizar) en el tiempo . ^[5] El algoritmo de Bareiss para una descomposición LU es estable. ^[6] Una descomposición LU proporciona un método rápido para resolver un sistema de Toeplitz y también para calcular el determinante. ${\displaystyle O(n^{2})}$

Propiedades

• Una matriz de Toeplitz puede definirse como una matriz donde , para constantes . El conjunto de matrices de Toeplitz es un subespacio del espacio vectorial de matrices (bajo la suma de matrices y la multiplicación escalar). ${\displaystyle n\times n}$ ${\displaystyle A}$ ${\displaystyle A_{i,j}=c_{i-j}}$ ${\displaystyle c_{1-n},\ldots ,c_{n-1}}$ ${\displaystyle n\times n}$ ${\displaystyle n\times n}$
• Se pueden sumar dos matrices de Toeplitz en el tiempo (almacenando solo un valor de cada diagonal) y multiplicarlas en el tiempo. ${\displaystyle O(n)}$ ${\displaystyle O(n^{2})}$
• Las matrices de Toeplitz son persimétricas . Las matrices de Toeplitz simétricas son centrosimétricas y bisimétricas .
• Las matrices de Toeplitz también están estrechamente relacionadas con las series de Fourier , porque el operador de multiplicación por un polinomio trigonométrico , comprimido a un espacio de dimensión finita, puede representarse mediante una matriz de este tipo. De manera similar, se puede representar la convolución lineal como una multiplicación por una matriz de Toeplitz.
• Las matrices de Toeplitz conmutan asintóticamente , es decir, se diagonalizan en la misma base cuando la dimensión de las filas y columnas tiende a infinito.

• Para matrices de Toeplitz simétricas, existe la descomposición

${\displaystyle {\frac {1}{a_{0}}}A=GG^{\operatorname {T} }-(G-I)(G-I)^{\operatorname {T} }}$

¿Dónde está la parte triangular inferior de ? ${\displaystyle G}$ ${\displaystyle {\frac {1}{a_{0}}}A}$

• La inversa de una matriz de Toeplitz simétrica no singular tiene la representación

${\displaystyle A^{-1}={\frac {1}{\alpha _{0}}}(BB^{\operatorname {T} }-CC^{\operatorname {T} })}$

donde y son matrices de Toeplitz triangulares inferiores y es una matriz triangular estrictamente inferior. ^[7] ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle C}$

Convolución discreta

La operación de convolución se puede construir como una multiplicación de matrices, donde una de las entradas se convierte en una matriz de Toeplitz. Por ejemplo, la convolución de y se puede formular como: ${\displaystyle h}$ ${\displaystyle x}$

${\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}}.}$

Este enfoque se puede ampliar para calcular autocorrelación , correlación cruzada , promedio móvil , etc.

Matriz de Toeplitz infinita

Una matriz de Toeplitz bi-infinita (es decir, entradas indexadas por ) induce un operador lineal en . ${\displaystyle \mathbb {Z} \times \mathbb {Z} }$ ${\displaystyle A}$ ${\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}}.}$

El operador inducido está acotado si y sólo si los coeficientes de la matriz de Toeplitz son los coeficientes de Fourier de alguna función esencialmente acotada . ${\displaystyle A}$ ${\displaystyle f}$

En tales casos, se denomina símbolo de la matriz de Toeplitz y la norma espectral de la matriz de Toeplitz coincide con la norma de su símbolo. La demostración es fácil de establecer y se puede encontrar como Teorema 1.1 de. ^[8] ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle L^{\infty }}$

Véase también

• Matriz circulante , una matriz de Toeplitz cuadrada con la propiedad adicional de que ${\displaystyle a_{i}=a_{i+n}}$
• Matriz de Hankel , una matriz de Toeplitz "al revés" (es decir, con las filas invertidas)
• Teoremas del límite de Szegő  : determinante de matrices de Toeplitz grandes
• Operador de Toeplitz  : compresión de un operador de multiplicación en el círculo al espacio de HardyPages displaying wikidata descriptions as a fallback

Notas

1. Press et al. 2007, §2.8.2—Matrices de Toeplitz
2. Hayes 1996, Capítulo 5.2.6
3. Krishna y Wang 1993
4. Monahan 2011, §4.5—Sistemas Toeplitz
5. Brent 1999
6. Bojanczyk y otros 1995
7. Mukherjee y Maiti 1988
8. Böttcher y Grudsky 2012

Referencias

• Bojanczyk, AW; Brent, RP; de Hoog, FR; Sweet, DR (1995), "Sobre la estabilidad de los algoritmos de factorización de Bareiss y Toeplitz relacionados", 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), Matrices de Toeplitz, álgebra lineal asintótica y análisis funcional, Birkhäuser, ISBN 978-3-0348-8395-5
• Brent, RP (1999), "Estabilidad de algoritmos rápidos para sistemas lineales estructurados", en Kailath, T.; Sayed, AH (eds.), Algoritmos rápidos y confiables para matrices con estructura , SIAM , págs. 103-116, doi :10.1137/1.9781611971354.ch4, hdl : 1885/40746 , S2CID  13905858
• Chan, RH-F.; Jin, X.-Q. (2007), Introducción a los solucionadores iterativos de Toeplitz , SIAM , doi :10.1137/1.9780898718850, ISBN 978-0-89871-636-8
• Chandrasekeran, S.; Gu, M.; Sun, X.; Xia, J.; Zhu, J. (2007), "Un algoritmo superrápido para sistemas de ecuaciones lineales de Toeplitz", SIAM Journal on Matrix Analysis and Applications , 29 (4): 1247–66, CiteSeerX  10.1.1.116.3297 , doi :10.1137/040617200
• Chen, WW; Hurvich, CM; Lu, Y. (2006), "Sobre la matriz de correlación de la transformada de Fourier discreta y la solución rápida de grandes sistemas de Toeplitz para series temporales de memoria larga", 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), Procesamiento y modelado estadístico de señales digitales , Wiley, ISBN 0-471-59431-8
• Krishna, H.; Wang, Y. (1993), "El algoritmo de Levinson dividido es débilmente estable" , SIAM Journal on Numerical Analysis , 30 (5): 1498–1508, doi :10.1137/0730078
• Monahan, JF (2011), Métodos numéricos de estadística , Cambridge University Press , doi :10.1017/CBO9780511977176, ISBN 978-1-139-08211-2
• Mukherjee, Bishwa Nath; Maiti, Sadhan Samar (1988), "Sobre algunas propiedades de matrices de Toeplitz definidas positivas y sus posibles aplicaciones" (PDF) , Álgebra lineal y sus aplicaciones , 102 : 211–240, doi : 10.1016/0024-3795(88)90326-6
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), Recetas numéricas: el arte de la computación científica (3.ª ed.), Cambridge University Press , ISBN 978-0-521-88068-8
• Stewart, M. (2003), "Un solucionador Toeplitz superrápido con estabilidad numérica mejorada", SIAM Journal on Matrix Analysis and Applications , 25 (3): 669–693, doi :10.1137/S089547980241791X, S2CID  15717371
• Yang, Zai; Xie, Lihua; Stoica, Petre (2016), "Descomposición de Vandermonde de matrices de Toeplitz multinivel con aplicación a la superresolución multidimensional", IEEE Transactions on Information Theory , 62 (6): 3685–3701, arXiv : 1505.02510 , doi :10.1109/TIT.2016.2553041, S2CID  6291005

Lectura adicional

• Bareiss, EH (1969), "Solución numérica de ecuaciones lineales con matrices de Toeplitz y Toeplitz vectoriales", Numerische Mathematik , 13 (5): 404–424, doi :10.1007/BF02163269, S2CID  121761517
• Goldreich, O. ; Tal, A. (2018), "Rigidez matricial de matrices aleatorias de Toeplitz", Computational Complexity , 27 (2): 305–350, doi :10.1007/s00037-016-0144-9, S2CID  253641700
• Golub, GH ; van Loan, CF (1996), Cálculos matriciales , Johns Hopkins University Press , §4.7—Toeplitz y sistemas relacionados, ISBN 0-8018-5413-X, OCLC  34515797
• Gray, RM, Toeplitz y las matrices circulantes: una revisión (PDF) , Now Publishers, doi : 10.1561/0100000006
• Noor, F.; Morgera, SD (1992), "Construcción de una matriz de Toeplitz hermítica a partir de un conjunto arbitrario de valores propios", IEEE Transactions on Signal Processing , 40 (8): 2093–4, Bibcode :1992ITSP...40.2093N, doi :10.1109/78.149978
• Pan, Victor Y. (2001), Matrices estructuradas y polinomios: algoritmos unificados superrápidos , Birkhäuser , ISBN 978-0817642402
• Ye, Ke; Lim, Lek-Heng (2016), "Cada matriz es un producto de matrices de Toeplitz", Fundamentos de las matemáticas computacionales , 16 (3): 577–598, arXiv : 1307.5132 , doi :10.1007/s10208-015-9254-z, S2CID  254166943