Paper Info
Title
Density estimation in linear time
Abstract
Abstract We consider the problem of choosing a density estimate from a set of distributions F, minimizing the L1-distance to an unknown distribution ([DL01]). Devroye and Lugosi [DL01] analyze two algorithms for the problem: Scheff´e tournament winner and minimum,distance estimate. The Scheff´e tournament estimate requires fewer computations than the minimum distance estimate, but has strictly weaker guarantees than the latter. We focus on the computational aspect of density estimation. We present two algorithms, both with the same guarantee as the minimum distance estimate. The first one, a modification of the minimum distance estimate, uses the same number (quadratic in |F |) of computations as the Scheff´e tournament. The second one, called “efficient minimum loss-weight estimate,” uses only a linearnumber of computations, assuming that F is preprocessed. We also give examples showing that the guarantees of the algorithms cannot be improved and explore randomized algorithms for density estimation.
Year
Venue
Keywords
2007
Clinical Orthopaedics and Related Research
randomized algorithm,linear time,density estimation
DocType
Volume
Citations 
Journal
abs/0712.2
4
PageRank 
References 
Authors
0.53
2
2
Name
Order
Citations
PageRank
Satyaki Mahalanabis172.28
Daniel Stefankovic224328.65