Trigonométrie sphérique, identité de Yule entre PARCORs et algorithmes MCRR

Trigonométrie sphérique, identité de Yule entre PARCORs et algorithmes MCRR

Spherical Trigonometry, Yule's PARCOR Identity and FLRS Algorithms

François Desbouvries

Département Signal et Image, Institut National des Télécommunications 9, rue Charles Fourier F-91011 Evry

Page: 
303-318
|
Received: 
13 March 1995
| |
Accepted: 
N/A
| | Citation

OPEN ACCESS

Abstract: 

Yule's PARCOR Identity, in statistics, and the fundamental law of cosines, in spherical trigonometry, are indeed the same formula. This observation establishes a link between Fast Recursive Least Squares FRLS adaptive filtering and spherical trigonometry, since the fully—normalized FRLS lattice algorithm of Lee et al. consists of three particular applications of Yule's PARCOR Identity. In that framework, the six PARCORs propagated by the fully—normalized FRLS lattice filter are the cosines of the six elements of a spherical triangle, and this lattice algorithm is one solution to an important spherical triangle problem that arises naturally in navigation and astronomy. The practical interest of this new geometric interpretation is that one can take advantage of the well—trodden path of spherical trigonometry to derive unnoticed recursions among PARCORs, and thus among FRLS quantities (a particular case). These new formulas enable us to design alternatives to the original solution of Lee et al. We thus propose two new minimal (in the system theory sense) FRLS algorithms. One of these algorithms happens to be a normalized version of the QR—decomposition-based least squares lattice algorithm.

Résumé

L'identité de Yule, en statistique, et la loi des cosinus, en trigonométrie sphérique, sont une seule et même formule. Cette constatation met en lumière l'existence de liens entre filtrage adaptatif des Moindres Carrés Récursifs Rapides (MCRR) et trigonométrie sphérique, puisque les équations du treillis normalisé en angle de Lee et al. sont trois applications particulières de l'identité de Yule. De ce nouveau point de vue, les six coefficients de corrélation partielle (PARCORs) propagés par l'algorithme de Lee et al. sont les cosinus des six éléments d'un triangle sphérique, et les récurrences de ce treillis sont une solution particulière à un problème de triangle sphérique important qui admet des applications naturelles en navigation et en astronomie. L'intérêt pratique de cette nouvelle interprétation géométrique est que l'on peut exploiter l'outil trigonométrie sphérique pour établir des récurrences nouvelles entre PARCORs et donc, comme cas particulier, entre quantités intervenant dans les algorithmes MCRR. Ces relations nouvelles nous permettent de construire des alternatives à la solution originelle de Lee et al. Nous proposons ainsi deux algorithmes MCRR nouveaux, minimaux au sens de la théorie des systèmes, dont l'un se trouve être une version normalisée de l'algorithme en treillis à base de rotations de Givens.

Keywords: 

FLRS adaptive filtering, fully—normalized lattice, Yule's PARCOR identity, tetrahedron, spherical trigonometry, spherical triangle, Fast QRD—based LS Lattice filter

Mots clés

Filtrage adaptatif MCRR, treillis normalisé en angle, identité de Yule entre PARCORs, tétraèdre, trigonométrie sphérique, triangle sphérique, algorithme en treillis à base de rotations de Givens

1. Introduction
2. Interprétation Trigono-Métrique Classique Des PARCORs Dans Le Pla n
3. IYR Dans Le Tétraèdre Normalisé 3D
4. Connexions Avec La Trigonométrie Sphérique
5. Formules Nouvelles Entre PARCORs Induites Par La TS
6. Alternatives À La Solution De Lee Et Al.
7. Conclusion
8. Annexes
  References

[1] S . Haykin, Adaptive filter theory, 2nd edition, Prentice—Hall International , Englewood Cliffs, N . J ., 1991 .

[2] M . Morf, A . Vieira & D .T.L. Lee, « Ladder forms for identification and speech processing », Proceedings of the 1977 IEEE Conference on Decision and Control, New Orleans, LA, 1977, pp . 1074—78 .

[3] D .T.L . Lee, Canonical ladderform realizations and fast estimation algorithms, Ph . D . Dissertation, Stanford University, August 1980 .

[4] D .T.L . Lee & M . Morf, « Recursive square root ladder estimation algorithms » , Proceedings of the International Conference on Acoustics, Speech and Signal Processing, Denver, Co., 1980, pp . 1005—17 .

[5] D .T.L. Lee, M . Morf & B . Friedlander, « Recursive least squares ladder estimation algorithms », IEEE Transactions on Acoustics, Speech and Signal Processing, Vol . ASSP—29, N . 3, June 1981, pp. 627—641 .

[6] H . Lev—Ari & T. Kailath, « Ladder—form filters for nonstationary processes » , Proceedings of the 19th International Conference on Decision and Control , Albuquerque, December 10—12, 1980, pp . 960—61 .

[7] M . Morf, C.H . Muravchik & D .T. Lee, « Hilbert space array methods for finite rank process estimation and ladder realizations for adaptive signal processing », Proceedings of the International Conference on Acoustics, Speech and Signal Processing, Atlanta, 1981, pp. 856—859 .

[8] C .H . Muravchik, M . Morf, D .T . Lee & J . M . Delosme, « Hilbert space array methods for finite rank process modeling and ladder form realizations »,

Proceedings of the 20th IEEE Conference on Decision and Control, San Diego, Ca., December 1981, pp . 335—339 .

[9] G . Yule, « On the theory of correlation for any number of variables, treated by a new system of notations », Proc. Roy. Soc ., Vol . 79A, 1907, pp . 182—193 ; également dans : Statistical papers of George Udny Yule, London, England : Griffin, April 1978, pp. 85—94 .

[10] B. Porat, B . Friedlander & M . Morf, « Square—root covariance ladder algorithms », IEEE Transactions on Automatic Control, Vol . AC—27, N . 4, August 1982, pp. 813—29 .

[11] B . Porat, B . Friedlander & M . Morf, «Square—root covariance ladder algorithms », Proceedings of the International Conference on Acoustics , Speech and Signal Processing, Atlanta, 1981, pp . 877—80 .

[12] T. Kailath, « Time—variant and time—invariant lattice filters for nonstationary processes », présenté au : Workshop on Fast Algorithms for Linear Dynamical Systems, Aussois, France, Septembre 1981 ; et publié dans : Outils et Modèles Mathématiques pour l'Automatique, l'Analyse de Systèmes et le Traitement du Signal, Paris, éditions du CNRS, 1982, pp . 417—464 .

[13] H. Lev-Ari, T. Kailath & J . Cioffi, « Least—squares adaptive lattice and transversal filters : a unified geometric theory », IEEE Transactions on Information Theory, Vol. IT—30, N . 2, March 1984, pp . 222—236 .

[14] F. Desbouvries, « Recursive least—squares lattices and trigonometry in the spherical triangle », Proceedings of the International Conference on Acoustics, Speech and Signal Processing, Minneapolis, MN, April 27—30, 1993, pp . III—404—407 .

[15]F. Ling, « Givens rotation based least squares lattice and related algorithms » , IEEE Transactions on Signal Processing, N . 39—7, 1991, pp. 1541—51.

[16]I .K. Proudler, J.G. McWhirter & T.J . Shepherd, « Fast QRD—based algorithms for least squares linear prediction », Mathematics in Signal Processing II, J . G . McWhirter (ed .), Clarendon Press, Oxford, 1990, pp . 465—88 .

[17] I .K . Proudler, J.G. McWhirter & T.J. Shepherd, « Computationally efficient QR decomposition approach to least squares adaptive filtering », IEEE Proceedings—F, Vol . 138—4, August 1991, pp . 341—53.

[18] E .G . Kogbeliantz, Fundamentals of mathematicsfrom an advanced viewpoint , Vol. 4 : solid geometry and spherical trigonometry, Gordon and Breach, New York, 1969 .

[19]B . Friedlander, « Lattice filters for adaptive processing », Proceedings of the IEEE, Vol. 70, N . 8, August 1982, pp . 829–68 .

[20] B . Porat, Contributions to the theory and applications of lattice filters, Ph . D . Dissertation, Stanford University, August 1982 .

[21] D .T.M . Slock, Fast algorithms for fixed–order recursive least–squares parameter estimation, Ph. D . Dissertation, Stanford University, September 1989 .

[22] D .T.M . Slock, « Reconciling fast RLS lattice and QR algorithms », Proceedings of the International Conference on Acoustics, Speech and Signal Processing, Albuquerque, 1990, pp . 1591–94 .

[23] J .M . Cioffi & T. Kailath, « Fast, recursive–least–squares transversal filters for adaptive filtering », IEEE Transactions on Acoustics, Speech and Signal Processing, Vol. ASSP–32, N. 2, April 1984, pp . 304–337.

[24] T. Kailath, « Lectures on Wiener and Kalman filtering », 2nd printing, CISM courses and lectures, N . 140, Springer Verlag, 1981 .

[25] M . Morf, A. Vieira & T. Kailath, « Covariance characterization by partial autocorrelation matrices », The Annals of Statistics, Vol. 6, N. 3, 1978 , pp . 643–48 .

[26] S . Dégerine, « Canonical partial autocorrelation function of a multivariate time series », The Annals of Statistics, Vol. 18, N . 2, 1990, pp. 961–71 .

[27] S. Dégerine, « Sample partial autocorrelation function of a multivariate time series », Journal ofMultivariate Analysis 50, 1994, pp. 294–313 .

[28] G.H. Golub & C .F. Van Loan, Matrix Computations, 2nd edition, The John Hopkins University Press, Baltimore, 1993 .

[29] G. Papelier, Eléments de trigonométrie sphérique, 3ème édition, Vuibert , Paris, 1956 .

[30] L .M . Keils, W.F. Kerns & J .R . Bland, Plane and spherical trigonometry , McGraw–Hill, New York, 1951 .

[31] W. Chauvenet, A manual of spherical and practical astronomy, Vol . I : Spherical astronomy, 5th edition, J . B . Lippincott & co ., Philadelphia, 1876 .

[32] V. Kourganoff, Astronomie fondamentale élémentaire, Masson, Paris, 1961 .

[33] P. Bakouline, E . Kononovitch & V. Moroz, Astronomie générale, 3ème édition, Editions MIR, Moscou, 1981.

[34] A . Danjon, Astronomie générale, 2ème édition, J . & R . Sennac, Paris, 1959 .

[35] K .F. Gauss, Theoria Motus, 1809 ; Traduction en anglais : Theory of the Motion of the Heavenly Bodies Moving about the Sun in Conic Sections , Dover, New York, 1963 .

[36] R . Taton (éditeur), Histoire générale des sciences, tome I : la science antique et médiévale (des origines à 1450), Presses Universitaires de France, Paris ,1957 .

[37] T. Heath, A history of Greek mathematics, Vols . I & II, Dover Publications , Inc . New York, 1981 .

[38] W. W. Rouse Ball, A short account ofthe history ofmathematics, Dover Pub. , New York, 1960 .

[39] M . al–Biruni & M .T. Debarnat, La trigonométrie sphérique chez les Arabes de l'Est à la fin du Xème siècle, Publications de l'Institut Français de Damas , N . 114, Institut Français de Damas, 1985 (en Arabe et en Français) .

[40] E.G . Kogbeliantz, Fundamentals ofmathematics from an advanced viewpoint, Vol . 3 : geometry and geometric analysis ; chapter 17 : some facts about non-Euclidean geometry, Gordon and Breach, New York, 1969 .

[41] H. Lev–Ari, K.F. Chiang & T. Kailath, « Constrained–input / constrained–output stability for adaptive RLS lattice filters », IEEE Transactions on Circuits and Systems, Vol. CAS–38, N. 12, December 1991, pp. 1478–83.

[42] H . Andoyer, Cours d'astronomie, 3ème édition, Librairie scientifique J . Hermann, Paris, 1923 .

[43] W. Chauvenet, A treatise on plane and spherical trigonometry, 9th edition, J . B . Lippincott & co., Philadelphia, 1875 .

[44] P. Constan, Cours de trigonométrie sphérique à l'usage des marins qui ont en vue l'étude de l'astronomie ou de la géodésie, Société d'éditions géographiques, maritimes et coloniales, Paris 1941 .

[45] C. Pacé, Précis de trigonométrie plane, de géométrie sphérique et de trigonométrie sphérique, à l'usage des élèves de la marine marchande et des lieutenants au cabotage, Société d'éditions géographiques, maritimes et coloniales, Paris, 1951 .

[46] RA . Regalia, « Numerical stability properties of a QR–based fast least–squares algorithm », IEEE Transactions on Signal Processing, Vol. 41, N. 6 , June 1993, pp. 2096–2109.

[47] A . Benallal & A. Gilloire, « A new method to stabilize fast RLS algorithms based on first–order model of the propagation of numerical errors », Proceedings of the International Conference on Acoustics, Speech and Signal Processing, New York, 1988, pp . 1373–76 .

[48] D.T.M . Slock & T. Kailath, « Numerically stable fast transversal filters for recursive least squares adaptive filtering », IEEE Transactions on Signal Processing, Vol . 39, N . 1, January 1991, pp . 92–114 .