La recursión de Levinson o recursión de Levinson-Durbin es un procedimiento en álgebra lineal para calcular recursivamente la solución de una ecuación que involucra una matriz de Toeplitz . El algoritmo se ejecuta en el tiempo Θ ( n 2 ) , lo que es una gran mejora con respecto a la eliminación de Gauss-Jordan , que se ejecuta en Θ ( n 3 ).
El algoritmo de Levinson-Durbin fue propuesto primero por Norman Levinson en 1947, mejorado por James Durbin en 1960, y posteriormente mejorado a 4 n 2 y luego 3 n 2 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 recursividad de Levinson (particularmente la recursión de Levinson dividida) tiende a ser más rápida computacionalmente, 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 recursividad de Levinson, pero usa el espacio O ( n 2 ) , mientras que la recursividad 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, solo débilmente estable (es decir, exhibe estabilidad numérica para sistemas lineales bien acondicionados ). [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 ) para 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ños (normalmente n <256). [7]
Derivación
Fondo
Las ecuaciones matriciales siguen la forma:
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íes un vector conocido , yes un vector desconocido de números x i aún por determinar.
Por el bien de este artículo, ê i es un vector compuesto enteramente por ceros, excepto por su i- ésimo lugar, que tiene el valor uno. Su longitud 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 n es una matriz n × n que copia el bloque n × n superior izquierdo de M , es decir, T n ij = M ij .
T n es también una matriz de Toeplitz; lo que significa que se puede escribir como:
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 descartarse 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 n- ésimo "vector directo", denotado, como el vector de longitud n que satisface:
El n- ésimo "vector hacia atrás"se define de manera similar; es el vector de longitud n que satisface:
Puede ocurrir una simplificación importante cuando M es una matriz simétrica ; entonces los dos vectores están relacionados por b n i = f n n + 1− i , es decir, son filas inversas entre sí. Esto puede ahorrar algunos cálculos adicionales en ese caso especial.
Obtener los vectores al revés
Incluso si la matriz no es simétrica, entonces el n º hacia adelante y hacia atrás vector se puede encontrar a partir de los vectores de longitud n - 1 como sigue. Primero, el vector hacia adelante puede extenderse con un cero para obtener:
Al pasar de T n −1 a T n , la columna adicional agregada a la matriz no perturba la solución cuando se usa un cero para extender el vector hacia adelante. Sin embargo, la fila extra 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:
Este error se devolverá en breve y se eliminará del nuevo vector de avance; pero primero, el vector hacia atrás debe extenderse de manera similar (aunque al revés). Para el vector al revés,
Como antes, la columna extra agregada a la matriz no perturba este nuevo vector hacia atrás; pero la fila extra lo hace. Aquí tenemos otro error no deseado ε b con valor:
Estos dos términos de error se pueden usar 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:
Si α y β se eligen de modo que el lado derecho produzca ê 1 o ê n , entonces la cantidad entre paréntesis cumplirá la definición del n- ésimo vector hacia adelante o hacia atrás, respectivamente. Con los alfa y beta elegidos, la suma vectorial entre paréntesis es simple y produce el resultado deseado.
Para encontrar estos coeficientes, , son tales que:
y respectivamente , son tales que:
Multiplicando ambas ecuaciones anteriores por se obtiene la siguiente ecuación:
Ahora, todos los ceros en el medio de los dos vectores anteriores se ignoran y se colapsan, solo queda la siguiente ecuación:
Con estos resueltos (mediante el uso de la fórmula inversa de la matriz de Cramer 2 × 2), los nuevos vectores hacia adelante y hacia atrás son:
La realización de estas sumas de vectores, a continuación, da el n º reenviar y vectores hacia atrás desde 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:
Usando los vectores al revés
Los pasos anteriores dan los N vectores hacia atrás para M . A partir de ahí, una ecuación más arbitraria es:
La solución se puede construir de la misma forma recursiva en que se construyeron los vectores hacia atrás. Respectivamente, debe generalizarse a una secuencia de intermedios , tal que .
Luego, la solución se construye de manera recursiva al notar que si
Luego, extendiendo con un cero nuevamente y definiendo una constante de error cuando sea necesario:
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:
Extender este método hasta que n = N produce la solución.
En la práctica, estos pasos a menudo se realizan 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 un bloque Toeplitz, la recursividad de Levinson se puede derivar de la misma manera al considerar la matriz de bloques de Toeplitz como una matriz de Toeplitz con elementos de matriz (Musicus 1988). Las matrices de bloques de 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
- ^ Bojanczyk y col. (1995).
- ^ Brent (1999).
- ^ Krishna y Wang (1993).
- ^ http://www.maths.anu.edu.au/~brent/pd/rpb143tr.pdf
- ^ "Copia archivada" (PDF) . Archivado desde el original (PDF) el 15 de noviembre de 2009 . Consultado el 28 de abril de 2009 .Mantenimiento de CS1: copia archivada como título ( enlace )
- ^ https://web.archive.org/web/20070418074240/http://saaz.cs.gsu.edu/papers/sfast.pdf
- ^ http://www.math.niu.edu/~ammar/papers/amgr88.pdf
Referencias
Definición de fuentes
- Levinson, N. (1947). "El criterio de error Wiener RMS en el diseño y la predicción de filtros". J. Math. Phys. , v. 25, págs. 261-278.
- Durbin, J. (1960). "El ajuste de modelos de series de tiempo". Rev. Inst. En t. Stat. , v. 28, págs. 233–243.
- Trinchera, WF (1964). "Un algoritmo para la inversión de matrices finitas de Toeplitz". J. Soc. Indust. Apl. Matemáticas. , v. 12, págs. 515–522.
- Musicus, BR (1988). "Algoritmos de Levinson y Choleski rápido para matrices de Toeplitz y Almost 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. 470–478.
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 Matriciales . 16 : 40–57. arXiv : 1004.5510 . doi : 10.1137 / S0895479891221563 .
- Brent RP (1999), "Estabilidad de algoritmos rápidos para sistemas lineales estructurados", Algoritmos confiables rápidos para matrices con estructura (editores — T. Kailath, AH Sayed), cap.4 ( SIAM ).
- Manojo, JR (1985). "Estabilidad de métodos para resolver sistemas de ecuaciones de Toeplitz". SIAM J. Sci. Stat. Computación. , v. 6, págs. 349–364. [2]
- Krishna, H .; Wang, Y. (1993). "El algoritmo de 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 Levinson-Durbin". Modelado predictivo lineal del habla: restricciones y descomposición de pares de espectro de líneas. 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]
- Presione, 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 Loan, CF Van (1996). "Sección 4.7: Cálculos matriciales de Toeplitz y sistemas relacionados" , Johns Hopkins University Press