Approximating L1-distances between mixture distributions using random projections

The Sixth Workshop on Analytic Algorithmics and Combinatorics

Satyaki Mahalanabis ; Daniel Sˇtefankovicˇ

Others  :  http://www.siam.org/proceedings/analco/2009/anl09_011_mahalanabiss.pdf
PID  :  18269

来源: CEUR

【 摘 要 】

We consider the problem of computing L1-distancesbetween every pair of probability densities from a givenfamily, a problem motivated by density estimation [15].We point out that the technique of Cauchy randomprojections [10] in this context turns into stochasticintegrals with respect to Cauchy motion.For piecewise-linear densities these integrals can besampled from if one can sample from the stochasticintegral of the function x 7→ (1, x). We give anexplicit density function for this stochastic integraland present an efficient (exact) sampling algorithm.As a consequence we obtain an efficient algorithm toapproximate the L1-distances with a small relativeerror.For piecewise-polynomial densities we show how toapproximately sample from the distributions resultingfrom the stochastic integrals. This also results in anefficient algorithm to approximate the L1-distances,although our inability to get exact samples worsens the dependence on the parameters.