Graphes de représentation minimaux, entropies et divergences : applications
Minimal spanning trees, entropies and divergences: applications
OPEN ACCESS
A non parametric approach for entropy estimation was recently proposed by the authors. Based on the statistical properties of minimal spanning trees, it was established that a suitably normalized sum of the edge weights converges to the Rényi entropy of the underlying process. Motivated by these results, in this paper we apply the MST approach to several practical problems including: denoising, clustering and mixture separation. First we briefly recall basic concepts and properties of MST. Then details are given on applications to general denoising or clustering problems, including trajectory detection in the time-frequency plane.
Résumé
Il a été récemment établi que la longueur d’un graphe de représentation minimal (Minimal Spanning Tree, MST) construit sur un ensemble de réalisations d’un processus aléatoire permet d’estimer l’entropie de ce dernier, dans un contexte non paramétrique. Dans cette étude, après avoir rappelé les principales définitions et propriétés des MST, nous en illustrons l’intérêt à travers leur mise en œuvre dans le cadre de problèmes de débruitage, de séparation de mélange statistique ou de détection de trajectoire dans le plan temps-fréquence, pour l’analyse de signaux non stationnaires.
k-Minimal spanning Tree, f-divergence, Rényi entropy, mixture separation, denoising, time frequency analysis
Mots clés
Graphes de représentation minimaux, f -divergences, Entropie statistique de Rényi, Séparation de mélange, Débruitage, Temps fréquence
[1] A.E. Badel, O. Michel, A.O. Héro : « Comparaisons de systèmes et arbres de régression », Traitement du Signal, 15-2 1998, pp 103-118.
[2] D. Banks, M. Lavine, and H.J. Newton, « The minimal spanning tree for nonparametric regression and structure discovery, » in Computing Science ans Statistics. Proceedings of the 24th Symposium on the Interface, H.J. Newton, editor, pp. 370-374, 1992.
[3] M. Basseville, « Distances measures for signal processing and pattern recognition », Signal Processing, vol. 18, 1989, pp. 349-369.
[4] M. Basseville, « Information : entropies, divergences et moyennes, » IRISA, publication interne n°1020, mai 1996.
[5] M. Basseville, I.V. Nikiforov, « Detection of abrupt changes – Theory and applications. », Prentice Hall Information and System Sciences Series, 1993.
[6] J. Bearwood, J.H. Halton, and J.M. Hammersley, « The shortest path through many points, » Proc. Cambridge Philosophical Society, vol. 55, pp. 299-327, 1959.
[7] J. Beirlant, E.J. Dudewica, L. Györfi, and E. van der Meulen, « Nonparametric entropy estimation : an overview, » Intern. J. Math. Stat. Sci., vol. 6 n°1, pp. 17-39, 1997.
[8] F. Chapeau-Blondeau, F. Janez, J.L. Ferrier, « A dynamic adaptative relaxation scheme applied to the euclidean Steiner minimel tree problem. », SIAM J. Optim., vol. 7, n°4, pp. 1037-1053, nov. 1997.
[9] C. Chiang, M. Sarrafzadeh, and C.K.Wong, « Powerful global router : Based on Steiner min-max trees, » in IEEE International Conference on computer-Aided Design, pp. 2-5, Santa Clara, CA, 1989.
[10]I. Csiszár and J. Korner, Information theory : coding theorems for discrete memoryless systems, Academic Press, Orlando FL, 1981.
[11]C. Dussert, G. Rasigni, J. Palmari, and A. Llebaria, « Minimal spanning tree : new approach for studying order and disorder, » Phys. Rev. B, vol. 34, n°5, pp. 3528-3531, 1986.
[12]T.S. Ferguson, « Mathematical Statistics – A decision theoric approach. », Academic Press, Orlando FL, 1967.
[13]K. Fukunaga, « Statistical pattern recognition. », Academic Press, San Diego CA, 1990.
[14]A. Gersho, R.M. Gray, « Vector Quantization and Signal Compression », Kluver Academic Press, 1992.
[15]J. Havrda, F. Chàrvat, « Quantification methods of classification processes, » KIBERNETIKA CISLO 1, ROCNIK 3 pp. 30-34, 1967.
[16]R. Hoffman and A.K. Jain, « A test of randomness based on the minimal spanning tree, » Pattern Recognition Letters, vol. 1, pp. 175-180, 1993.
[17]A.O. Hero, O. Michel : « Robust estimation of point process intensity features using k-minimal spanning tree. », proc. of ISIT, International Symposium on Information theory, 1997, Ulm, Germany, pp. 74.
[18]A.O . Hero, O. Michel : « Robust entropy estimation strategies based on edge weighted randoms graphs (with connections). », SPIE, International Symposium on Optical Science, Engineering and Instrumentation, July 1998, San Diego, USA.
[19]A.O. Hero, O. Michel : « Asymptotic theory of greedy approximations to minimal K-point random graphs. », IEEE Trans. on Information theory, vol.45, n°6, pp. 1921-1938, septembre 1999.
[20]A.O. Hero, O. Michel : « Estimation of Rényi information divergence via pruned minimal spanning trees. », proc. of IEEE Workshop on HOS, Caesarea, Israel, pp. 264-268, 1999.
[21]O. Michel, A.O. Hero : « Pruned MST’s for entropy estimation and outlier rejection. », IEEEE-IT workshop on DECI, Detection, Classification and Imaging, Santa-Fe, NM, USA., Feb 99. Communication invitée.
[22]O. Michel, P. Flandrin and A.O. hero : « Détection de structures dans le plan temps-fréquence à l’aide de graphes minimaux. », Gretsi.99, Vannes, France, 99. 713-716.
[23]O. Michel, P. Flandrin and A.O. Hero : « Automatic extraction of time-frequency skeletons with minimal spanning trees. », ICASSP’2000 communication No. SPTM – L3.5, Istanbul, Turquie.
[24]R. Ravi, M. Marathe, D. Rosenkrantz, and S. Ravi, « Spanning trees short or small, » in Proc. 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 546-555, Arlington, VA, 1994.
[25]R. Ravi, M. Marathe, D. Rosenkrantz, and S. Ravi, « Spanning trees – short or small, » SIAM Journal on discrete Math, vol. 9, pp. 178-200, 1996.
[26]C. Redmond and J.E. Yurich, « Limit theorems and rates of convergence for Euclidean functionals, » Ann. Applied Probab., vlo. 4 n°4, pp. 1057-1073, 1994.
[27]A. Rényi, « On measures of entropy and information, » in Proc. 4th Berkeley Symp. Math. Stat and Prob., volume 1, pp. 547-561, 1961.
[28]M.I. Shamos, D. Hoey, « Closest-point problems, » in Proc. 16th Annual Symp. on Foundations of computer sciences, pp. 151-162, 1975.
[29]D. Siegmund, « Sequential analysis : tests and confidence intervals. », Springer Verlag, New-York, 1985.
[30]J.M. Steele, « Growth rates of euclidean minimal spanning trees with power weighted edges, » Ann. Probab., vol. 16, pp. 1767-1787, 1988.
[31]P. Viola and W. Wells, « Alignment by maximization of mutual information, » in Proc. of 5th Int. Conf. on Computer Vision. MIT, volume 1, pp. 16-23, 1995.
[32]A.A. Zelikovsky and D.D. Lozevanu, « Minimal and bounded trees, » in Proc. of Tezelz Congres XVIII Acad. Romano-Americaine, pp. 25-26, Kishinev, 1993.