Robust entropy estimation strategies based on edge weighted random graphs

Alfred O. Hero III; Olivier Michel

doi:10.1117/12.323804

22 September 1998 Robust entropy estimation strategies based on edge weighted random graphs

Alfred O. Hero III, Olivier Michel

Proceedings Volume 3459, Bayesian Inference for Inverse Problems; (1998) https://doi.org/10.1117/12.323804
Event: SPIE's International Symposium on Optical Science, Engineering, and Instrumentation, 1998, San Diego, CA, United States

Abstract

In this paper we treat the problem of robust entropy estimation given a multidimensional random sample from an unknown distribution. In particular, we consider estimation of the Renyi entropy of fractional order which is insensitive to outliers, e.g. high variance contaminating distributions, using the k-point minimal spanning tree. A greedy algorithm for approximating the NP-hard problem of computing the k-minimal spanning tree is given which is a generalization of the potential function partitioning method of Ravi et al. The basis for our approach is asymptotic theorem establishing that the log of the overall length or weight of the greedy approximation is a strongly consistent estimator of the Renyi entropy. Quantitative robustness of the estimator to outliers is established using Hampel's method of influence functions. The structure of the influence function indicates that the k-MST is a natural extension of the 1D, (alpha) -trimmed mean for multi- dimensional data.

Citation Download Citation

Alfred O. Hero III and Olivier Michel "Robust entropy estimation strategies based on edge weighted random graphs", Proc. SPIE 3459, Bayesian Inference for Inverse Problems, (22 September 1998); https://doi.org/10.1117/12.323804

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available