recursividad de Levinson

La recursión de Levinson o recursión de Levinson-Durbin es un procedimiento en álgebra lineal para calcular de forma recursiva la solución de una ecuación que involucra una matriz de Toeplitz . El algoritmo se ejecuta en tiempo Θ ( n ² ) , lo que supone una gran mejora con respecto a la eliminación de Gauss-Jordan , que se ejecuta en Θ( n ³ ).

El algoritmo Levinson-Durbin fue propuesto por primera vez por Norman Levinson en 1947, mejorado por James Durbin en 1960 y posteriormente mejorado a 4 n ² y luego 3 n ² multiplicaciones por WF Trench y S. Zohar, respectivamente.

Otros métodos para procesar datos incluyen la descomposición de Schur y la descomposición de Cholesky . En comparación con estos, la recursión de Levinson (particularmente la recursión de Levinson dividida) tiende a ser computacionalmente más rápida, pero más sensible a imprecisiones computacionales como errores de redondeo .

El algoritmo de Bareiss para matrices de Toeplitz (que no debe confundirse con el algoritmo general de Bareiss ) se ejecuta tan rápido como la recursión de Levinson, pero usa el espacio O ( n ² ) , mientras que la recursión de Levinson usa solo el espacio O ( n ). El algoritmo de Bareiss, sin embargo, es numéricamente estable , ^{[1] [2]} mientras que la recursividad de Levinson es, en el mejor de los casos, sólo débilmente estable (es decir, exhibe estabilidad numérica para sistemas lineales bien condicionados ). ^[3]

Los algoritmos más nuevos, llamados algoritmos de Toeplitz asintóticamente rápidos o, a veces, superrápidos , pueden resolver en Θ( n log ^p n ) varios p (por ejemplo, p = 2, ^{[4] [5]} p = 3 ^[6] ). La recursividad de Levinson sigue siendo popular por varias razones; por un lado, es relativamente fácil de entender en comparación; por otro, puede ser más rápido que un algoritmo superrápido para n pequeño (normalmente n  < 256). ^[7]

Derivación

Fondo

Las ecuaciones matriciales siguen la forma

${\displaystyle \mathbf {M} \,{\vec {x}}={\vec {y}}.}$

El algoritmo de Levinson-Durbin se puede utilizar para cualquier ecuación de este tipo, siempre que M sea una matriz de Toeplitz conocida con una diagonal principal distinta de cero. Aquí hay un vector conocido , y es un vector desconocido de números x _i aún por determinar. ${\displaystyle {\vec {y}}}$ ${\displaystyle {\vec {x}}}$

Por el bien de este artículo, ê _i es un vector formado enteramente por ceros, excepto por su i- ésimo lugar, que tiene el valor uno. Su duración estará implícitamente determinada por el contexto circundante. El término N se refiere al ancho de la matriz anterior: M es una matriz N × N. Finalmente, en este artículo, los superíndices se refieren a un índice inductivo , mientras que los subíndices denotan índices. Por ejemplo (y definición), en este artículo, la matriz T ⁿ es una matriz n × n que copia el bloque n × n superior izquierdo de M  , es decir, T ⁿ _ij = M _ij .

T ⁿ también es una matriz de Toeplitz, lo que significa que puede escribirse como

${\displaystyle \mathbf {T} ^{n}={\begin{bmatrix}t_{0}&t_{-1}&t_{-2}&\dots &t_{-n+1}\\t_{1}&t_{0}&t_{-1}&\dots &t_{-n+2}\\t_{2}&t_{1}&t_{0}&\dots &t_{-n+3}\\\vdots &\vdots &\vdots &\ddots &\vdots \\t_{n-1}&t_{n-2}&t_{n-3}&\dots &t_{0}\end{bmatrix}}.}$

Pasos introductorios

El algoritmo se desarrolla en dos pasos. En el primer paso, se establecen dos conjuntos de vectores, llamados vectores hacia adelante y hacia atrás . Los vectores hacia adelante se utilizan para ayudar a obtener el conjunto de vectores hacia atrás; entonces pueden ser descartados inmediatamente. Los vectores hacia atrás son necesarios para el segundo paso, donde se utilizan para construir la solución deseada.

La recursividad de Levinson-Durbin define el enésimo "vector directo", denominado ^, como el vector de longitud n que satisface: ${\displaystyle {\vec {f}}^{n}}$

${\displaystyle \mathbf {T} ^{n}{\vec {f}}^{n}={\hat {e}}_{1}.}$

El n ^-ésimo "vector hacia atrás" se define de manera similar; es el vector de longitud n el que satisface: ${\displaystyle {\vec {b}}^{n}}$

${\displaystyle \mathbf {T} ^{n}{\vec {b}}^{n}={\hat {e}}_{n}.}$

Puede ocurrir una simplificación importante cuando M es una matriz simétrica ; entonces los dos vectores están relacionados por b ⁿ _i = f ⁿ _{n +1− i} , es decir, son inversiones de filas entre sí. Esto puede ahorrar algunos cálculos adicionales en ese caso especial.

Obteniendo los vectores hacia atrás

Incluso si la matriz no es simétrica, entonces el n ^- ésimo vector hacia adelante y hacia atrás se puede encontrar a partir de los vectores de longitud n  − 1 de la siguiente manera. Primero, el vector directo se puede ampliar con un cero para obtener:

${\displaystyle \mathbf {T} ^{n}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\\\end{bmatrix}}={\begin{bmatrix}\ &\ &\ &t_{-n+1}\\\ &\mathbf {T} ^{n-1}&\ &t_{-n+2}\\\ &\ &\ &\vdots \\t_{n-1}&t_{n-2}&\dots &t_{0}\\\end{bmatrix}}{\begin{bmatrix}\ \\{\vec {f}}^{n-1}\\\ \\0\\\ \\\end{bmatrix}}={\begin{bmatrix}1\\0\\\vdots \\0\\\varepsilon _{f}^{n}\end{bmatrix}}.}$

Al pasar de T ^{n −1} a T ⁿ , la columna adicional agregada a la matriz no perturba la solución cuando se usa un cero para extender el vector directo. Sin embargo, la fila adicional agregada a la matriz ha perturbado la solución; y ha creado un término de error no deseado ε _f que aparece en último lugar. La ecuación anterior le da el valor de:

${\displaystyle \varepsilon _{f}^{n}\ =\ \sum _{i=1}^{n-1}\ M_{ni}\ f_{i}^{n-1}\ =\ \sum _{i=1}^{n-1}\ t_{n-i}\ f_{i}^{n-1}.}$

Este error volverá a aparecer en breve y se eliminará del nuevo vector directo; pero primero, el vector hacia atrás debe extenderse de manera similar (aunque invertida). Para el vector hacia atrás,

${\displaystyle \mathbf {T} ^{n}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\\\end{bmatrix}}={\begin{bmatrix}t_{0}&\dots &t_{-n+2}&t_{-n+1}\\\vdots &\ &\ &\ \\t_{n-2}&\ &\mathbf {T} ^{n-1}&\ \\t_{n-1}&\ &\ &\end{bmatrix}}{\begin{bmatrix}\ \\0\\\ \\{\vec {b}}^{n-1}\\\ \\\end{bmatrix}}={\begin{bmatrix}\varepsilon _{b}^{n}\\0\\\vdots \\0\\1\end{bmatrix}}.}$

Como antes, la columna adicional agregada a la matriz no perturba este nuevo vector hacia atrás; pero la fila extra sí. Aquí tenemos otro error no deseado ε _b con valor:

${\displaystyle \varepsilon _{b}^{n}\ =\ \sum _{i=2}^{n}\ M_{1i}\ b_{i-1}^{n-1}\ =\ \sum _{i=1}^{n-1}\ t_{-i}\ b_{i}^{n-1}.\ }$

Estos dos términos de error se pueden utilizar para formar vectores hacia adelante y hacia atrás de orden superior que se describen a continuación. Usando la linealidad de matrices, la siguiente identidad es válida para todos : ${\displaystyle (\alpha ,\beta )}$

${\displaystyle \mathbf {T} \left(\alpha {\begin{bmatrix}{\vec {f}}\\\ \\0\\\end{bmatrix}}+\beta {\begin{bmatrix}0\\\ \\{\vec {b}}\end{bmatrix}}\right)=\alpha {\begin{bmatrix}1\\0\\\vdots \\0\\\varepsilon _{f}\\\end{bmatrix}}+\beta {\begin{bmatrix}\varepsilon _{b}\\0\\\vdots \\0\\1\end{bmatrix}}.}$

Si se eligen α y β de modo que el lado derecho produzca ê ₁ o ê _n , entonces la cantidad entre paréntesis cumplirá la definición del n ^- ésimo vector hacia adelante o hacia atrás, respectivamente. Con esos alfa y beta elegidos, la suma vectorial entre paréntesis es simple y produce el resultado deseado.

Para encontrar estos coeficientes, son tales que: ${\displaystyle \alpha _{f}^{n}}$ ${\displaystyle \beta _{f}^{n}}$

${\displaystyle {\vec {f}}^{n}=\alpha _{f}^{n}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}+\beta _{f}^{n}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}}$

y respectivamente , son tales que: ${\displaystyle \alpha _{b}^{n}}$ ${\displaystyle \beta _{b}^{n}}$

${\displaystyle {\vec {b}}^{n}=\alpha _{b}^{n}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}+\beta _{b}^{n}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}.}$

Multiplicando ambas ecuaciones anteriores por uno se obtiene la siguiente ecuación: ${\displaystyle {\mathbf {T} }^{n}}$

${\displaystyle {\begin{bmatrix}1&\varepsilon _{b}^{n}\\0&0\\\vdots &\vdots \\0&0\\\varepsilon _{f}^{n}&1\end{bmatrix}}{\begin{bmatrix}\alpha _{f}^{n}&\alpha _{b}^{n}\\\beta _{f}^{n}&\beta _{b}^{n}\end{bmatrix}}={\begin{bmatrix}1&0\\0&0\\\vdots &\vdots \\0&0\\0&1\end{bmatrix}}.}$

Ahora, al ignorar y colapsar todos los ceros en el medio de los dos vectores anteriores, solo queda la siguiente ecuación:

${\displaystyle {\begin{bmatrix}1&\varepsilon _{b}^{n}\\\varepsilon _{f}^{n}&1\end{bmatrix}}{\begin{bmatrix}\alpha _{f}^{n}&\alpha _{b}^{n}\\\beta _{f}^{n}&\beta _{b}^{n}\end{bmatrix}}={\begin{bmatrix}1&0\\0&1\end{bmatrix}}.}$

Una vez resueltos (utilizando la fórmula inversa de la matriz de Cramer 2 × 2), los nuevos vectores hacia adelante y hacia atrás son:

${\displaystyle {\vec {f}}^{n}={1 \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}-{\varepsilon _{f}^{n} \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}}$

${\displaystyle {\vec {b}}^{n}={1 \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}0\\{\vec {b}}^{n-1}\end{bmatrix}}-{\varepsilon _{b}^{n} \over {1-\varepsilon _{b}^{n}\varepsilon _{f}^{n}}}{\begin{bmatrix}{\vec {f}}^{n-1}\\0\end{bmatrix}}.}$

Luego, al realizar estas sumas de vectores, se obtienen los enésimos vectores ^hacia adelante y hacia atrás de los anteriores. Todo lo que queda es encontrar el primero de estos vectores, y luego algunas sumas y multiplicaciones rápidas dan los restantes. Los primeros vectores hacia adelante y hacia atrás son simplemente:

${\displaystyle {\vec {f}}^{1}={\vec {b}}^{1}=\left[{1 \over M_{11}}\right]=\left[{1 \over t_{0}}\right].}$

Usando los vectores hacia atrás

Los pasos anteriores dan los N vectores hacia atrás para M. A partir de ahí, una ecuación más arbitraria es:

${\displaystyle {\vec {y}}=\mathbf {M} \ {\vec {x}}.}$

La solución se puede construir de la misma forma recursiva en que se construyeron los vectores hacia atrás. En consecuencia, debe generalizarse a una secuencia de intermediarios , tal que . ${\displaystyle {\vec {x}}}$ ${\displaystyle {\vec {x}}^{n}}$ ${\displaystyle {\vec {x}}^{N}={\vec {x}}}$

Luego, la solución se construye recursivamente observando que si

${\displaystyle \mathbf {T} ^{n-1}{\begin{bmatrix}x_{1}^{n-1}\\x_{2}^{n-1}\\\vdots \\x_{n-1}^{n-1}\\\end{bmatrix}}={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n-1}\end{bmatrix}}.}$

Luego, extendiendo con un cero nuevamente y definiendo una constante de error cuando sea necesario:

${\displaystyle \mathbf {T} ^{n}{\begin{bmatrix}x_{1}^{n-1}\\x_{2}^{n-1}\\\vdots \\x_{n-1}^{n-1}\\0\end{bmatrix}}={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n-1}\\\varepsilon _{x}^{n-1}\end{bmatrix}}.}$

Luego podemos usar el n ^-ésimo vector hacia atrás para eliminar el término de error y reemplazarlo con la fórmula deseada de la siguiente manera:

${\displaystyle \mathbf {T} ^{n}\left({\begin{bmatrix}x_{1}^{n-1}\\x_{2}^{n-1}\\\vdots \\x_{n-1}^{n-1}\\0\\\end{bmatrix}}+(y_{n}-\varepsilon _{x}^{n-1})\ {\vec {b}}^{n}\right)={\begin{bmatrix}y_{1}\\y_{2}\\\vdots \\y_{n-1}\\y_{n}\end{bmatrix}}.}$

Extendiendo este método hasta n = N se obtiene la solución . ${\displaystyle {\vec {x}}}$

En la práctica, estos pasos suelen realizarse al mismo tiempo que el resto del procedimiento, pero forman una unidad coherente y merecen ser tratados como un paso propio.

Bloquear algoritmo de Levinson

Si M no es estrictamente Toeplitz, sino Toeplitz en bloque , la recursividad de Levinson se puede derivar de la misma manera considerando la matriz de Toeplitz en bloques como una matriz de Toeplitz con elementos matriciales (Musicus 1988). Las matrices de bloques Toeplitz surgen naturalmente en los algoritmos de procesamiento de señales cuando se trata de múltiples flujos de señales (por ejemplo, en sistemas MIMO ) o señales cicloestacionarias.

Ver también

• Recursión dividida de Levinson
• Predicción lineal
• Modelo autorregresivo

Notas

1. Bojanczyk y col. (1995).
2. Brent (1999).
3. Krishna y Wang (1993).
4. "Copia archivada" (PDF) . Archivado desde el original (PDF) el 25 de marzo de 2012 . Consultado el 1 de abril de 2013 .{{cite web}}: CS1 maint: archived copy as title (link)
5. "Copia archivada" (PDF) . Archivado desde el original (PDF) el 15 de noviembre de 2009 . Consultado el 28 de abril de 2009 .{{cite web}}: CS1 maint: archived copy as title (link)
6. "Copia archivada" (PDF) . saaz.cs.gsu.edu . Archivado desde el original (PDF) el 18 de abril de 2007 . Consultado el 12 de enero de 2022 .{{cite web}}: CS1 maint: archived copy as title (link)
7. "Copia archivada" (PDF) . Archivado desde el original (PDF) el 5 de septiembre de 2006 . Consultado el 15 de agosto de 2006 .{{cite web}}: CS1 maint: archived copy as title (link)

Referencias

Definiendo fuentes

• Levinson, N. (1947). "El criterio de error Wiener RMS en el diseño y predicción de filtros". J. Matemáticas. Física. , v. 25, págs. 261–278.
• Durbin, J. (1960). "El ajuste de modelos de series temporales". Rev. Inst. En t. Estadística. , v. 28, págs. 233–243.
• Trinchera, WF (1964). "Un algoritmo para la inversión de matrices finitas de Toeplitz". J. Soc. Industria. Aplica. Matemáticas. , v. 12, págs. 515–522.
• Música, BR (1988). "Algoritmos de Levinson y Fast Choleski para matrices de Toeplitz y casi Toeplitz". RLE TR No. 538, MIT. [1]
• Delsarte, P. y Genin, YV (1986). "El algoritmo dividido de Levinson". Transacciones IEEE sobre acústica, habla y procesamiento de señales , v. ASSP-34(3), págs.

Más trabajo

• Bojanczyk, AW; Brent, RP; De Hoog, FR; Dulce, DR (1995). "Sobre la estabilidad de los algoritmos de factorización de Bareiss y Toeplitz relacionados". Revista SIAM sobre Análisis y Aplicaciones de Matrices . 16 : 40–57. arXiv : 1004.5510 . doi :10.1137/S0895479891221563. S2CID  367586.
• Brent RP (1999), "Estabilidad de algoritmos rápidos para sistemas lineales estructurados", Algoritmos rápidos y confiables para matrices con estructura (editores: T. Kailath, AH Sayed), capítulo 4 ( SIAM ).
• Manojo, JR (1985). "Estabilidad de métodos para la resolución de sistemas de ecuaciones de Toeplitz". SIAM J. Ciencias. Estadística. Computadora. , v. 6, págs. 349–364. [2]
• Krishna, H.; Wang, Y. (1993). "El algoritmo Split Levinson es débilmente estable". Revista SIAM de Análisis Numérico . 30 (5): 1498-1508. doi : 10.1137/0730078.

Resúmenes

• Bäckström, T. (2004). "2.2. Recursión de Levinson-Durbin". Modelado predictivo lineal del habla: restricciones y descomposición de pares de espectro lineal. Tesis doctoral. Reporte no. 71 / Universidad Tecnológica de Helsinki, Laboratorio de Acústica y Procesamiento de Señales de Audio. Espoo, Finlandia. [3]
• Claerbout, Jon F. (1976). "Capítulo 7: Aplicaciones de formas de onda de mínimos cuadrados". Fundamentos del procesamiento de datos geofísicos. Palo Alto: Publicaciones científicas de Blackwell. [4]
• Prensa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007), "Sección 2.8.2. Matrices de Toeplitz", Recetas numéricas: el arte de la informática científica (3.ª ed.), Nueva York: Cambridge University Press, ISBN 978-0-521-88068-8
• Golub, GH y Préstamo, CF Van (1996). "Sección 4.7: Toeplitz y sistemas relacionados" Computación matricial , Johns Hopkins University Press