Advances in the theory of nearest neighbor distributions

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en
dc.contributor.author Liitiäinen, Elia
dc.date.accessioned 2012-08-28T11:40:41Z
dc.date.available 2012-08-28T11:40:41Z
dc.date.issued 2010
dc.identifier.isbn 978-952-60-3305-1 (electronic)
dc.identifier.isbn 978-952-60-3304-4 (printed) #8195;
dc.identifier.issn 1797-5069
dc.identifier.uri https://aaltodoc.aalto.fi/handle/123456789/4846
dc.description.abstract A large part of non-parametric statistical techniques are in one way or another related to the geometric properties of random point sets. This connection is present both in the design of estimators and theoretical convergence studies. One such relation between geometry and probability occurs in the application of non-parametric techniques for computing information theoretic entropies: it has been shown that the moments of the nearest neighbor distance distributions for a set of independent identically distributed random variables are asymptotically characterized by the Rényi entropies of the underlying probability density. As entropy estimation is a problem of major importance, this connection motivates an extensive study of nearest neighbor distances and distributions. In this thesis, new results in the theory of nearest neighbor distributions are derived using both geometric and probabilistic proof techniques. The emphasis is on results that are useful for finite samples and not only in the asymptotic limit of an infinite sample. Previously, in the literature it has been shown that after imposing sufficient regularity assumptions, the moments of the nearest neighbor distances can be approximated by invoking a Taylor series argument providing the connection to the Rényi entropies. However, the theoretical results provide limited understanding to the nature of the error in the approximation. As a central result of the thesis, it is shown that if the random points take values in a compact set (e.g. according to the uniform distribution), then under sufficient regularity, a higher order moment expansion is possible. Asymptotically, the result completely characterizes the error for the original low order approximation. Instead of striving for exact computation of the moments through a Taylor series expansion, in some cases inequalities are more useful. In the thesis, it is shown that concrete upper and lower bounds can be established under general assumptions. In fact, the upper bounds rely only on a geometric analysis. The thesis also contains applications to two problems in nonparametric statistics, residual variance and Rényi entropy estimation. A well-established nearest neighbor entropy estimator is analyzed and it is shown that by taking the boundary effect into account, estimation bias can be significantly reduced. Secondly, the convergence properties of a recent residual variance estimator are analyzed. en
dc.format.extent Verkkokirja (1586 KB, 127 s.)
dc.language.iso en en
dc.publisher Aalto-yliopiston teknillinen korkeakoulu en
dc.relation.ispartofseries TKK dissertations in information and computer science, 18 en
dc.subject.other Computer science
dc.subject.other Mathematics
dc.title Advances in the theory of nearest neighbor distributions en
dc.type G4 Monografiaväitöskirja fi
dc.contributor.school Aalto-yliopiston teknillinen korkeakoulu fi
dc.contributor.department Tietojenkäsittelytieteen laitos fi
dc.contributor.department Department of Information and Computer Science en
dc.subject.keyword nearest neighbor en
dc.subject.keyword computational geometry en
dc.subject.keyword entropy en
dc.subject.keyword residual variance en
dc.subject.keyword correlation en
dc.subject.keyword nonparametric en
dc.identifier.urn URN:ISBN:978-952-60-3305-1
dc.type.dcmitype text en
dc.type.ontasot Väitöskirja (monografia) fi
dc.type.ontasot Doctoral dissertation (monograph) en


Files in this item

Files Size Format View

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record

Search archive


Advanced Search

article-iconSubmit a publication

Browse

My Account