Adaptive algorithms using higher-order statistics. Blind channel identification

Título de Doctor con Mención EuropeaEsta Memoria comienza en el capítulo 1 repasando algunos conceptos y métodos necesarios para el posterior desarrollo de la misma. En muchos casos supone una explicitación cuantitativa de lo expuesto en esta introducción: sistemas lineales y señales discretas que serán analizados mediante la transformada Z, en particular se tratará sobre la importantísima condición de fase mínima, momentos y cumulantes de alto orden con sus propiedades más útiles, técnicas paramétricas de identificación de sistemas, bases de los algoritmos adaptativos LMS y RLS y finalizará con una pequeña aplicación al campo de las comunicaciones. En la parte I se aborda el estudio de la familia de algoritmos RLS. El algoritmo RLS estándar ya se ha estudiado ampliamente en la bibliografía, su análisis se presenta en el capítulo 2 para familiarizarse con él y con las técnicas más usuales empleadas en su estudio. La adaptación del algoritmo RLS al empleo de estadística de orden superior se denomina algoritmo recursivo de variable instrumental (Recursive Instrumental Variable, RIV). Las propiedades de convergencia de este algoritmo fueron estudiadas por Swami para situaciones estacionarias, como aportación de esta Memoria se incluye un análisis de RIV para situaciones no estacionarias y el efecto que produce el ruido de estimación. Tanto el análisis de Swami como la aportación de esta Memoria se detallan en el capítulo 3 junto con la obtención del algoritmo. Sin embargo hay situaciones en las que la formulación matemática proporciona sistemas con más ecuaciones que incógnitas, en las cuales ni el algoritmo RLS ni el RIV pueden operar. Para solventar este problema se derivó el algoritmo RIV sobredeterminado, ORIV (Overdetermined Recursive Instrumental Variable). Este algoritmo se presenta en el capítulo 4 junto con un completo análisis de su convergencia, siendo dicho análisis aportación propia de esta Memoria. Dos consecuencias principales se pueden obtener de él: las condiciones bajo las cuales se produce un seguimiento óptimo de la evolución de los parámetros (tracking capabilities) y la obtención de una condición necesaria para convergencia (condición de ortogonalidad) válida para problemas sobredeterminados y que incluyan estadística de alto orden. Dado que el algoritmo ORIV es el más completo de los analizados hasta ahora, en el capítulo 5 se aplicará al problema de la identificación ciega de sistemas. La identificación ciega de sistemas, como parte integrante del procesado de señal, se beneficia de una gran cantidad de métodos existentes en esta área como puede ser la estimación paramétrica del espectro, dicha estimación paramétrica se puede adaptar sin problemas para resolver la identificación de sistemas. Pero también se puede beneficiar de otros campos como el de la teoría de control, a través del modelado Kalman, p.e. Además, está intimamente relacionado con el interesantísimo problema de la separación ciega de fuentes, con el que comparte aspectos comunes. En este capítulo la identificación de sistemas se realizará mediante un modelado paramétrico MA, para lo cual en primer lugar se rederivarán en el dominio del tiempo, por un lado la conocida ecuación de Giannakis-Mendel y por otro se propone una generalización de ella empleando exclusivamente estadística de orden superior. Los resultados obtenidos mediante el algoritmo ORIV se explican satisfactoriamente a la luz del análisis llevado a cabo en el capítulo anterior. Finalmente, para acabar esta primera parte, en el capítulo 6 se compara minuciosamente el algoritmo RIV con el ORIV, tanto teóricamente como mediante simulaciones. Como se aprecia, la familia RLS cubre una gran cantidad de problemas, tanto sobredeterminados como con estadística de alto orden. No ocurre lo mismo para la familia del LMS, donde sólo existen algoritmos adaptados al empleo de estadística de alto orden, como el LMS generalizado o GLMS, pero no hay ninguno capaz de resolver sistemas sobredeterminados ya sea con estadística de segundo orden o de alto orden. En la parte II se cubren estas deficiencias, con nuevas contribuciones. En primer lugar, tal y como se procedió en la parte de la familia RLS, aquí también se presenta en el capítulo 7 el algoritmo LMS junto con un análisis de su convergencia, por completitud y por presentar las técnicas e hipótesis más empleadas en el estudio de este tipo de algoritmos. El hilo conductor del resto de esta parte es el Principio de Ortogonalidad Sobredeterminado y Generalizado deducido en la parte I. De él se obtienen tres algoritmos distintos propuestos en esta Memoria. El primero de ellos, el GLMS, se rederiva dentro de este nuevo formalismo en el capítulo 8 y se analiza mediante teoría y simulaciones en profundidad, análisis no realizado anteriormente. En el capítulo 9 se analizan los otros dos algoritmos, los algoritmos Sobredeterminados y Generalizados tipo LMS, OGLMS (Overdetermined and Generalized LMS) 1 y 3. Se demuestra que el algoritmo OGLMS1 presenta mejores propiedades en convergencia que OGLMS3 y por tanto se selecciona para reducir su carga computacional y así asemejarse al típico LMS, dando lugar a un nuevo algoritmo. Este nuevo algoritmo, el algoritmo promediado OGLMS, AOGLMS (Averaged OGLMS) se analiza en el capítulo 10 junto con unas breves simulaciones que confirmen su buen comportamiento. Para finalizar esta segunda parte en el capítulo 11 se presentan nuevas versiones del algoritmo GLMS, con un pequeño análisis de su convergencia tanto teórico como experimental. La última parte de esta Memoria se centra exclusivamente en el problema de la identificación ciega, dejando a un lado los algoritmos adaptativos. El principal objetivo es beneficiarse todo lo posible de los métodos basados en estadística de segundo orden, que proporcionan estimadores menos ruidosos con menor cantidad de datos que los estimadores obtenidos con estadística de alto orden. Así, en los capítulos 12 y 13 se obtienen las expresiones explícitas que relacionan los coeficientes de la respuesta impulso de un sistema lineal, de orden 1 y 2 respectivamente, con la autocorrelación de la salida del mismo. Dado que de esta manera sólo se pueden obtener los sistemas que compartan el espectro de potencia, ya que estas técnicas no llevan información sobre la fase, en el capítulo \14 se propone un nuevo método que modifica ligeramente las expresiones obtenidas en los capítulos 12 y 13 de forma que incluya la información justa sobre la fase para que la solución tenga además la fase correcta. Este método contrasta con los métodos tradicionales, en los cuales se llevaba a cabo un proceso de búsqueda del sistema correcto dentro del conjunto de sistemas espectralmente equivalentes. Esta búsqueda a veces se lleva a cabo mediante un ajuste de los cumulantes reales (estimados) con los cumulantes de los sistemas candidatos. En el capítulo 15 se compara mediante simulaciones el nuevo método con estos métodos basados en ajustes por cumulantes (cumulant matching). Para finalizar se presentan las conclusiones más relevantes obtenidas en la Memoria.Many signal processing problems are defined in environments that can be time varying, or require a result immediately after every new data is obtained. In such situations, and in many others, the problem should be solved adaptively. An adaptive algorithm is capable of improving (updating) the knowledge about the problem in an efficient way for every new sample that arrives. The first adaptive algorithm to be developed was the Least Mean Square LMS algorithm and it imposes an orthogonality condition between the estimation error and the data vector used in the estimation, as required by the orthogonality principle for linear estimation. In this set-up only the second order statistics is used to solve the problem, which is equivalent to solve the Wiener-Hopf equations (a well known linear system of equations). The LMS lies in the stochastic gradient algorithms family. Generally speaking, the same problem can be solved using the Recursive Least Squares RLS algorithm, but because of its mathematical properties, it gives better results (estimates with lower variance using shorter data records) but with an increased computational cost. The RLS algorithm can be easily generalised to solve problems involving higher-order statistics (i.e. expected values of the product of more than two stochastic variables); this new algorithm is the Recursive Instrumental Variable RIV algorithm. In addition, sometimes the problem we are considering not only involves higher-order statistics but can also be overdetermined, think for instance in the blind identification of Moving Average models using the Giannakis-Mendel equations. This situation can also be covered by an algorithm of the Least Squares family: the Overdetermined Recursive Instrumental Variable ORIV algorithm. Nevertheless, all these situations are not covered by stochastic gradient algorithms. The main goal of chapters 16 and 17 is to fill this gap. It is true that in Aboutajdine96 the derived Generalised LMS algorithm can solve problems involving higher-order statistics, but it suffers from one important drawback: the matrix formed by the linear system of equations must be positive definite or negative definite, limiting the range of applicability. Also, no stochastic gradient algorithm has been designed to solve overdetermined systems of equations with higher-order statistics (the counterpart of ORIV in this family). To be more precise, chapters 16 and 17 are devoted to seek a new algorithm that can solve problems with associated overdetermined systems of equations involving higher-order statistics, not suffering from the mentioned drawback of GLMS. The ultimate goal is to design an algorithm of the stochastic gradient family (and hence with reduced computational complexity) enjoying as much as the properties of the ORIV algorithm. To reach this, the first step is to theoretically analyse the ORIV algorithm in chapter 16. From this theoretical study, a new orthogonality condition is obtained that is used in chapter 17 to propose a new algorithm meeting all required properties. Apart from this new orthogonality condition, the theoretical study covers the convergence in the mean and mean square for stationary and not stationary environments including estimation noise. Because good estimators require long memory (big forgetting factor) and tracking requires short memory(small forgetting factor), in average an optimal forgetting factor is found that weights both requirements. An analogous result for the RLS algorithm was found in Macchi91. To test the theoretical study the ORIV algorithm is applied to the blind identification of MA models. For this purpose a new general equation is derived in the time domain that contains as special cases the Giannakis-Mendel equation and its generalisation to 3rd and 4th order cumulants. Also, the novel proposed algorithm is tested via simulation in the identification of MA models; previously its convergence has been briefly theoretically studied. The final part of this work, chapter 18, is concerned with the blind identification of linear systems (channels) on batch mode. This chapter aims to solve the problem using second order statistics of the output and as little higher-order statistics as possible. The use of higher-order statistics is a must, because only from second order statistics the phase response can not be determined. A new method is derived that uses almost exclusively 2nd order statistics and uses higher-order statistics to compute just signs (a simple binary decision). This novel method is supposed to have all good properties of second order statistics (need of short data records, low estimate variances, etc.) and higher-order statistics (phase information) and to be only affected in an infinitesimal amount by the drawbacks of higher-order statistics (basically the need for longer data records). This new method is compared with other techniques that rely on the Spectrally Equivalent Minimum Phase system complemented by a phase selection step (such as cumulant matching, constant modulus of equalised signal, etc. All these techniques are analysed to provide a better understanding of their performance.Tesis Univ. Granada, Dpto. de Física Aplicad