Matriz de Toeplitz - Toeplitz matrix

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 A n  ×  n de la forma

${\ 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 i ,  j de A se denota A _{i ,  j} entonces tenemos

${\ Displaystyle A_ {i, j} = A_ {i + 1, j + 1} = a_ {ij}.}$

Una matriz de Toeplitz no es necesariamente cuadrada .

Resolver un sistema Toeplitz

Una ecuación matricial de la forma

${\ Displaystyle Ax = b}$

se llama sistema de Toeplitz si A es una matriz de Toeplitz. Si A es una matriz de Toeplitz n  ×  n , entonces el sistema tiene solo 2 n - 1 grados de libertad , en lugar de n ² . Por lo tanto, podríamos esperar que la solución de un sistema Toeplitz fuera más fácil y, de hecho, ese es el caso.

Los sistemas Toeplitz pueden resolverse mediante el algoritmo de Levinson en tiempo O ( n ² ) . Se ha demostrado que las variantes de este algoritmo son débilmente estables (es decir, exhiben estabilidad numérica para sistemas lineales bien acondicionados ). El algoritmo también se puede utilizar para encontrar el determinante de una matriz de Toeplitz en el tiempo O ( n ² ) .

Una matriz de Toeplitz también se puede descomponer (es decir, factorizar) en tiempo O ( n ² ) . El algoritmo de Bareiss para una descomposición LU es estable. Una descomposición LU proporciona un método rápido para resolver un sistema Toeplitz y también para calcular el determinante.

En la literatura se han descrito algoritmos que son asintóticamente más rápidos que los de Bareiss y Levinson, pero no se puede confiar en su precisión.

Propiedades generales

• Una matriz de Toeplitz n  ×  n puede definirse como una matriz A donde A _{i ,  j} = c _{i - j} , para constantes c _{1− n} , ..., c _{n −1} . El conjunto de n  ×  n matrices de Toeplitz es un subespacio del espacio vectorial de n  ×  n matrices (bajo suma de matrices y multiplicación escalar).
• Se pueden agregar dos matrices de Toeplitz en O ( n ) tiempo (almacenando solo un valor de cada diagonal) y multiplicarlas en O ( n ² ) tiempo.
• Las matrices de Toeplitz son persimétricas . Las matrices simétricas de Toeplitz son tanto centrosimétricas como 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 en un espacio de dimensión finita, puede representarse mediante dicha matriz. 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 . Esto significa que se diagonalizan en la misma base cuando la dimensión de la fila y la columna tiende al infinito.
• Un semi-definida positiva n  ×  n matriz de Toeplitz de rango r < n pueden ser de forma única como factores como${\ Displaystyle A}$

${\ Displaystyle A = \ sum _ {k = 1} ^ {r} d_ {k} v (f_ {k}) v (f_ {k}) ^ {\ operatorname {H}} = VDV ^ {\ operatorname { H}}}$

donde es una matriz diagonal definida positiva r  ×  r , es una matriz de Vandermonde n  ×  r tal que las columnas son . Aquí y es la frecuencia normalizada, y es la transposición de Hermitian . Si el rango r = n , entonces la descomposición de Vandermonde no es única.${\ Displaystyle D = \ mathrm {diag} (d_ {1}, \ ldots, d_ {r})}$ ${\ Displaystyle V = [v (f_ {1}), \ ldots, v (f_ {r})]}$ ${\ Displaystyle v (f) = [1, e ^ {i2 \ pi f}, \ ldots, e ^ {i2 \ pi (n-1) f}] ^ {\ operatorname {T}}}$${\ Displaystyle i ^ {2} = - 1}$${\ Displaystyle f_ {k} \ in [0,1]}$${\ Displaystyle V ^ {\ operatorname {H}}}$${\ Displaystyle V}$

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

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

donde 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.${\ 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 la autocorrelación , la correlación cruzada , la media móvil , etc.

Matriz infinita de Toeplitz

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 solo 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 prueba es fácil de establecer y se puede encontrar como Teorema 1.1 en el enlace del libro de Google: ${\ Displaystyle f}$${\ Displaystyle A}$${\ Displaystyle A}$${\ Displaystyle L ^ {\ infty}}$

Ver también

• Matriz circulante , una matriz de Toeplitz 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 filas invertidas)

Notas

Referencias

• Bojanczyk, AW; Brent, RP; de Hoog, FR; Sweet, DR (1995), "Sobre la estabilidad de Bareiss y los algoritmos de factorización de Toeplitz relacionados", SIAM Journal on Matrix Analysis and Applications , 16 : 40–57, arXiv : 1004.5510 , doi : 10.1137 / S0895479891221563
• 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 fiables rápidos para matrices con estructura , SIAM , págs. 103-116
• Chan, RH-F .; Jin, X.-Q. (2007), Introducción a los solucionadores iterativos de Toeplitz , SIAM
• Chandrasekeran, S .; Chicle.; Sol, X .; Xia, J .; Zhu, J. (2007), "Un algoritmo superrápido para sistemas Toeplitz de ecuaciones lineales", SIAM Journal on Matrix Analysis and Applications , 29 (4): 1247–1266, 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 discreta de Fourier y la solución rápida de grandes sistemas Toeplitz para series de tiempo de memoria larga", Revista de la Asociación Estadounidense de Estadística , 101 (474): 812–822, CiteSeerX  10.1.1.574.4394 , doi : 10.1198 / 016214505000001069
• Krishna, H .; Wang, Y. (1993), "El algoritmo dividido de Levinson 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
• Mukherjee, Bishwa Nath; Maiti, Sadhan Samar (1988), "Sobre algunas propiedades de las 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
• Presione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), Recetas numéricas: El arte de la informática científica (Tercera ed.), Cambridge University Press , ISBN 978-0-521-88068-8
• Stewart, M. (2003), "Un solucionador de Toeplitz superrápido con estabilidad numérica mejorada" , SIAM Journal on Matrix Analysis and Applications , 25 (3): 669–693, doi : 10.1137 / S089547980241791X
• Yang, Zai; Xie, Lihua; Stoica, Petre (2016), "Descomposición de Vandermonde de matrices de Toeplitz multinivel con aplicación a superresolución multidimensional", IEEE Transactions on Information Theory , 62 (6): 3685–3701, arXiv : 1505.02510 , doi : 10.1109 / TIT.2016.2553041

Otras lecturas

• Bareiss, EH (1969), "Solución numérica de ecuaciones lineales con Toeplitz y matrices vectoriales de Toeplitz", Numerische Mathematik , 13 (5): 404–424, doi : 10.1007 / BF02163269
• Goldreich, O .; Tal, A. (2018), "Rigidez matricial de matrices de Toeplitz aleatorias", Complejidad computacional , 27 (2): 305–350, doi : 10.1007 / s00037-016-0144-9
• Golub GH , van Loan CF (1996), Computaciones matriciales ( Johns Hopkins University Press ) §4.7 — Toeplitz y sistemas relacionados
• Gray RM, Toeplitz y matrices circulantes: una revisión ( ahora editores )
• Noor, F .; Morgera, SD (1992), "Construcción de una matriz Hermitian Toeplitz a partir de un conjunto arbitrario de valores propios", IEEE Transactions on Signal Processing , 40 (8): 2093-2094, Bibcode : 1992ITSP ... 40.2093N , doi : 10.1109 / 78.149978
• Pan, Victor Y. (2001), Matrices estructuradas y polinomios: algoritmos superrápidos unificados , Birkhäuser , ISBN 978-0817642402
• Ye, Ke; Lim, Lek-Heng (2016), "Cada matriz es un producto de las matrices de Toeplitz", Foundations of Computational Mathematics , 16 (3): 577–598, arXiv : 1307.5132 , doi : 10.1007 / s10208-015-9254-z