Approximating L1-distances between mixture distributions using random projections

Details Approximating L1-distances between mixture distributions using random projections Approximating L1-distances between mixture distributions using random projections

2008-04-08

arxiv.org/abs/0804.1170v1

Computer Science

Data Structures and Algorithms

Scientific paper

We consider the problem of computing L1-distances between every pair ofcprobability densities from a given family. We point out that the technique of Cauchy random projections (Indyk'06) in this context turns into stochastic integrals with respect to Cauchy motion. For piecewise-linear densities these integrals can be sampled from if one can sample from the stochastic integral of the function x->(1,x). We give an explicit density function for this stochastic integral and present an efficient sampling algorithm. As a consequence we obtain an efficient algorithm to approximate the L1-distances with a small relative error. For piecewise-polynomial densities we show how to approximately sample from the distributions resulting from the stochastic integrals. This also results in an efficient algorithm to approximate the L1-distances, although our inability to get exact samples worsens the dependence on the parameters.

Affiliated with

Also associated with

No associations

Rating

Approximating L1-distances between mixture distributions using random projections 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 Approximating L1-distances between mixture distributions using random projections, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximating L1-distances between mixture distributions using random projections will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-539827