Univariate \(L^p\) and \(l^p\) averaging, \(0<p<1\), in polynomial time by utilization of statistical structure (Q1736520)

Summary: 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 \textit{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^1\) and \(l^1\) averages) do not exist, one needs to consider using \(l^p\) minimization principles with \(0<p<1\).