Density estimation in linear time

Details Density estimation in linear time Density estimation in linear time

2007-12-18

arxiv.org/abs/0712.2869v1

Computer Science

Learning

11 pages

Scientific paper

We consider the problem of choosing a density estimate from a set of distributions F, minimizing the L1-distance to an unknown distribution (Devroye, Lugosi 2001). Devroye and Lugosi analyze two algorithms for the problem: Scheffe tournament winner and minimum distance estimate. The Scheffe 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 Scheffe tournament. The second one, called ``efficient minimum loss-weight estimate,'' uses only a linear number 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.

Affiliated with

Also associated with

No associations

Rating

Density estimation in linear time does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Density estimation in linear time, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Density estimation in linear time will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-548840