We present evidence that one can calculate generically combinatorially expensive Lp and lp 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 Lp averages are calculated are not convex but are radially monotonic and the functionals by which lp 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 lp 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 lp minimization principles with 0 < p < 1.
References
[1]
Gribonval, R.; Nielsen, M. Sparse Approximations in Signal and Image Processing. EURASIP Book Ser. Signal Process. Commun. 2006, 86, 415–416.
[2]
Lai, M.-J.; Wang, J. An unconstrained lq minimization with 0 < q ≤ 1 for sparse solution of under-determined linear systems. SIAM J. Optim. 2010, 21, 82–101.
[3]
Chartrand, R. Exact reconstruction of sparse signals via nonconvex minimization. IEEE Signal Process. Lett. 2007, 14, 707–710, doi:10.1109/LSP.2007.898300.
[4]
Candès, E.J.; Wakin, M.B. An introduction to compressive sampling. IEEE Signal Process. Mag. 2008, 25, 21–30, doi:10.1109/MSP.2007.914731.
[5]
Auquiert, P.; Gibaru, O.; Nyiri, E. Fast L1-Ck polynomial spline interpolation algorithm with shape-preserving properties. Comput. Aided Geom. Design 2011, 28, 65–74, doi:10.1016/j.cagd.2010.10.002.
Candès, E.J.; Li, X.; Ma, Y.; Wright, J. Robust principal component analysis? J. ACM 2011, 58, 1–37.
[8]
Ke, Q.; Kanade, T. Robust L1 norm factorization in the presence of outliers and missing data by alternative convex programming. In Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2005), San Diego, CA, USA, 20？25 June 2005; Schmid, C., Soatto, S., Tomasi, C., Eds.; IEEE Computer Society: Los Alamitos, CA, USA, 2005; pp. 739–746.
[9]
Kwak, N. Principal component analysis based on L1-norm maximization. IEEE Trans. Pattern Anal. Mach. Intell. 2008, 30, 1672–1680, doi:10.1109/TPAMI.2008.114.
[10]
Dodge, Y. Statistical Data Analysis Based on the L1 Norm and Related Methods. Neuchatel, Switzerland, 4–9 August 2002; Birkh？user: Basel, Switzerland, 2002.
[11]
Nolan, J.P. Multivariate stable distributions: Approximation, estimation, simulation and identification. In A Practical Guide to Heavy Tails; Adler, R.J., Feldman, R.E., Taqqu, M.S., Eds.; Birkh？user: Cambridge, MA, USA, 1998; pp. 509–525.
Faloutsos, M.; Faloutsos, P.; Faloutsos, C. On power-law relationships of the internet topology. Comp. Comm. Rev. 1999, 29, 251–262, doi:10.1145/316194.316229.
[14]
Willinger, W.; Govindan, R.; Jamin, S.; Paxson, V.; Shenker, S. Scaling phenomena in the Internet: Critically examining criticality. Proc. Natl. Acad. Sci. USA 2002, 99, 2573–2580, doi:10.1073/pnas.012583099.
[15]
Rachev, S.T.; Menn, C.; Fabozzi, F.J. Fat-Tailed and Skewed Asset Return Distributions: Implications for Risk Management, Portfolio Selection, and Option Pricing; John Wiley: Hoboken, NJ, USA, 2005.
[16]
Reed, W.J.; Jorgensen, M.A. The double Pareto-lognormal distribution—A new parametric model for size distributions. Comm. Statist. Theory Methods 2004, 33, 1733–1753, doi:10.1081/STA-120037438.
[17]
Foucart, S.; Lai, M.-J. Sparsest solutions of underdetermined linear systems via lq-minimization for 0 < q ≤ 1. Appl. Comput. Harmon. Anal. 2009, 26, 395–407, doi:10.1016/j.acha.2008.09.001.
[18]
Ge, D.; Jiang, X.; Ye, Y. A note on the complexity of Lp minimization. Math. Program. 2011, 129, 285–299, doi:10.1007/s10107-011-0470-2.
[19]
Gribonval, R.; Nielsen, M. Highly sparse representations from dictionaries are unique and independent of the sparseness measure. Appl. Comput. Harmon. Anal. 2007, 22, 335–355, doi:10.1016/j.acha.2006.09.003.
[20]
Wang, M.; Xu, W.; Tang, A. On the Performance of Sparse Recovery via Lp-minimization (0 ≤ p ≤ 1). IEEE Trans. Info. Theory 2011, 57, 7255–7278, doi:10.1109/TIT.2011.2159959.
[21]
Wilcox, R.R. Introduction to Robust Estimation and Hypothesis Testing, 2nd ed.; Elsevier: Burlington, MA, USA, 2005.
