Univariate Lp and lp Averaging, 0 < p < 1, in Polynomial Time by Utilization of Statistical Structure

Algorithms

关键词: average;    heavy-tailed distribution;    L^p average;    l^p average;    median;    mode;    polynomial time;    radial monotonicity;    statistical structure;    univariate;   

DOI  :  10.3390/a5040421

来源: mdpi

【 摘 要 】

We present evidence that one can calculate generically combinatorially expensive L^p and l^p averages, 0 < p < 1, in polynomial time by restricting the data to come from a wide class of statistical distributions. Our approach differs from the approaches in the previous literature, which are based on a priori sparsity requirements or on accepting a local minimum as a replacement for a global minimum. The functionals by which L^p averages are calculated are not convex but are radially monotonic and the functionals by which l^p averages are calculated are nearly so, which are the keys to solvability in polynomial time. Analytical results for symmetric, radially monotonic univariate distributions are presented. An algorithm for univariate l^p averaging is presented. Computational results for a Gaussian distribution, a class of symmetric heavy-tailed distributions and a class of asymmetric heavy-tailed distributions are presented. Many phenomena in human-based areas are increasingly known to be represented by data that have large numbers of outliers and belong to very heavy-tailed distributions. When tails of distributions are so heavy that even medians (L¹ and l¹ averages) do not exist, one needs to consider using l^p minimization principles with 0 < p < 1.

【 授权许可】

CC BY   
© 2012 by the authors; licensee MDPI, Basel, Switzerland.