## 1 Introduction  
Minimization principles based on the \(l^{1}\) and \(L^{1}\) norms have recently rapidly become more common due to discovery of their important roles in sparse representation in signal and image processing [1, 2], compressive sensing [3, 4], shape-preserving geometric modeling [5, 6] and robust principal component analysis [7, 8, 9]. In compressive sensing and sparse representation, it is known that, under proper sparsity conditions (for example, the restricted isometry property [3, 4]), \(l^{1}\) solutions are equivalent to \"\(l^{0}\) solutions\", that is, the sparsest solutions, an important result because it allows one to find the solution of a combinatorially expensive \(l^{0}\) maximum-sparsity minimization problem by a polynomial-time linear programming procedure for minimizing \(l^{1}\) functionals. When the data follow heavy-tailed statistical distributions and the tails of the distributions are \"not too heavy,\" various \(l^{1}\) minimization principles, in the form of calculation of medians and quantiles, are primary choices that are efficient and robust against the many outliers [10, 11, 12]. Such distributions correspond to the uncertainty in many human-based phenomena and activities, including the Internet [13, 14], finance [15, 16] and other human and physical phenomena [16]. \(l^{1}\) minimization principles are applicable also to data from light-tailed distributions such as the Gaussian, but, for such distributions, are less efficient than classical procedures (calculation of standard averages and variances). When tails of the distributions are so heavy that even \(l^{1}\) minimization principles do not exist, one needs to consider using \(l^{p}\) minimization principles with \(0<p<1\), a topic on which investigation has recently started [2, 3, 17, 18, 19, 20]. \(l^{p}\) minimization principles, \(0<p<1\), are of interest because they produce solutions that are in general sparser, that is, closer to \(l^{0}\) solutions, than \(l^{1}\) minimization principles [20]. However, when \(0<p<1\), solving \(l^{p}\) minimization principles is generically combinatorially expensive (NP-hard) [18], because \(l^{p}\) minimization principles can have arbitrarily large numbers of local minima. (\"Generically\" means \"in the absence of additional information.\") Investigations about polynomial-time \(l^{p}\) minimization, \(0<p<1\), have focused on (1) obtaining local rather than global solutions [2, 18, 20] and (2) achieving a global minimum by restricting the class of problems to those with sufficient sparsity [3, 17, 19] (the approach used in compressive sensing). However, local solutions often differ strongly from global solutions and sparsity restrictions are often not applicable. The fact that the \(l^{0}\) solution is, relative to other potential solutions, the sparsest solution does not imply that this solution is sparse to any specific degree. The sparsest solution may not be sparse in any absolute sense at all; it is just sparser than any other solution. The approach that we will investigate in the present paper shares with compressive sensing the strategy of restricting the nature of the problem to achieve polynomial-time performance. However, we do so not by requiring sparsity to some _a priori_ set level but rather by restricting the data to come from a wide class of statistical distributions, an approach not previously considered in the literature. This restriction turns out to be mild, often verifiable and often realistic since the problem as posed is often meaningful only when the data come from a statistical distribution. The approach in this paper differs from the approaches in the previous literature on \(l^{p}\) minimization principles also in a second way, namely, in that it starts the investigation of \(l^{p}\) minimization principles from consideration of their continuum analogues, \(L^{p}\) minimization principles.