A Unified Framework for Constructing Nonconvex Regularizations

Sparse recovery has attracted tremendous research interest in various areas including statistical learning [1] and compressive sensing [2]. Its goal is to recover an unknown sparse signal $\mathbf{x}\in\mathbb{R}^{N}$ from under-determined noisy measurements $\mathbf{y}=A\mathbf{x}+\boldsymbol{\varepsilon}\in\mathbb{R}^{m}$ with $m\ll N$ and $\boldsymbol{\varepsilon}$ being the noise vector. As is known, this sparse signal of interest can be well recovered by solving the Lasso problem [3] $\min_{\mathbf{x}\in\mathbb{R}^{N}}\frac{1}{2}\lVert\mathbf{y}-A\mathbf{x}\rVert_{2}^{2}+\lambda\lVert\mathbf{x}\rVert_{1}$ ($\lambda>0$ is a tuning parameter) or the constrained $\ell_{1}$-minimization [4]. Due to the fact that the $\ell_{1}$ norm is just a loose approximation of the $\ell_{0}$ norm, the Lasso is biased and does not have the oracle property [5].

To overcome this issue, a large number of nonconvex methods have been proposed to better approximate the $\ell_{0}$ norm and promote sparsity. Generally, a nonconvex regularization method possesses a form of

where $J_{\theta}(\cdot)$ denotes a nonconvex regularization or penalty function depending on some parameter or vector of parameters $\theta$. In particular, a separable regularization function has a formulation as $\sum_{j=1}^{N}F_{\theta}(|x_{j}|)$. This separable framework includes many popular nonconvex methods as its special cases, such as $\ell_{p}(0<p<1)$ [6, 7], Capped-L1 [8], transformed $\ell_{1}$ (TL1) [9], smooth clipped absolute deviation (SCAD) [5], minimax concave penalty (MCP) [10], three-order polynomial (TOP) method [11], exponetial-type penalty (ETP) [12, 13], error function (ERF) method [14], and the very recent generalized error function (GERF) method [15], to name a few. It was called $F$-minimization in [16], and its exact and robust reconstruction conditions were investigated when $F_{\theta}(\cdot)$ satisfies some desirable properties such as subadditivity.

These nonconvex regularization methods enjoy attractive theoretical properties and have achieved great success in various scenarios. However, in practice, it is still unclear how to construct a valid and effective nonconvex regularization function. More specifically, how to construct the function $F_{\theta}(\cdot)$ in the separable nonconvex regularization term remains unanswered. In this paper, we set out to fill in this gap between theory and practice by proposing a unified framework for constructing the nonconvex regularization based on the probability density function. It provides a fairly general framework, making many existing nonconvex regularization methods as its special cases. More importantly, many new nonconvex regularization functions can be constructed within this framework.

The paper is organized as follows. In Section II, we present the unified framework. In Section III, we discuss the theoretical analysis results. In Section IV, we study a new nonconvex method based on the Weibull penalty. Finally, conclusions are included in Section V.

We propose to construct the following nonconvex regularization term for sparse recovery:

where $F_{\theta}(x)=\int_{0}^{x}f_{\theta}(\tau)d\tau$ is the cumulative distribution function (CDF) of a probability density function (PDF) $f_{\theta}(\cdot)$ defined on $[0,\infty)$.

In what follows, we first give some examples of the distributions supported on $[0,\infty)$ (or on a bounded interval) and their corresponding nonconvex sparse recovery methods. As we can see from Table I, we are able to find the corresponding probability distributions for almost all the existing popular separable nonconvex methods. In addition, some new nonconvex methods can be constructed through provided distributions, for instance the Weibull distribution and the Chi-squared distribution.

If a probability distribution is supported on the whole real line, then we can instead use its folded version supported on $[0,\infty)$ to construct the corresponding regularization function. Some examples are listed as follows:

• •

  Folded Normal distribution: $f_{\sigma}(x)=\frac{2}{\sqrt{2\pi}\sigma}e^{-\frac{x^{2}}{2\sigma^{2}}}$ with $F_{\sigma}(x)=\mathrm{erf}(\frac{x}{\sqrt{2}\sigma})$. In this case, it corresponds to the ERF method proposed in [14].

• •

  Folded Student’s t-distribution: $f_{\nu}(x)=\frac{2\Gamma(\frac{\nu+1}{2})}{\sqrt{\nu\pi}\Gamma(\frac{\nu}{2})}(1+\frac{x^{2}}{\nu})^{-\frac{\nu+1}{2}}$, where $\nu$ is the degrees of freedom and $\Gamma(\cdot)$ is the gamma function. In the special case of $\nu=1$, it reduces to the Folded Cauchy distribution with $f(x)=\frac{2}{\pi(1+x^{2})}$ and $F(x)=\frac{2}{\pi}\arctan(x)$, so that it goes to the ”arctan” method proposed in [17].

• •

  Folded Laplace distribution is exactly the Exponential distribution.

We display plots for the PDFs and CDFs of some well-known distributions in Figure 1. As shown, all the CDFs are continuous, non-decreasing, and satisfy that $F_{\theta}(0)=0$ and $F_{\theta}(+\infty)=1$. The PDFs of the Exponential, the Folded Normal and the Uniform distributions are non-increasing, such that their CDFs are concave. Whereas, the PDFs of the Rayleigh and the Weibull with $k=1.5$ are strongly unimodal, making their CDFs being not concave. These properties will be closely related to the theoretical analysis and solving algorithms for the corresponding nonconvex regularization methods.

Next, we provide some useful properties for the regularization functions $J_{\theta}(\cdot)$ constructed based on the probability density functions. We start with the following proposition, which shows the distribution of $J_{\theta}(\mathbf{x})$ when the entries of $\mathbf{x}$ are assumed to be random. Its proof is straightforward and so is omitted.

In addition, the constructed regularization or penalty term $J_{\theta}(\cdot):\mathbb{R}^{N}\rightarrow[0,N]$ can also be viewed as a sparsity measure, which possesses the following appealing properties:

• •

  $J_{\theta}(\cdot)$ is continuous in $\mathbb{R}^{N}$ so that it is stable with respect to small perturbations of the signal.

• •

  $J_{\theta}(\mathbf{x})=0$ if and only if $\mathbf{x}=\mathbf{0}$.

• •

  $J_{\theta}(\mathbf{x})=J_{\theta}(-\mathbf{x})$ for any $\mathbf{x}\in\mathbb{R}^{N}$.

• •

  $0\leq J_{\theta}(\mathbf{x})\leq\lVert\mathbf{x}\rVert_{0}\leq N$.

• •

  If $|\mathbf{x}|\preceq|\mathbf{y}|$ (i.e., $|x_{j}|\leq|y_{j}|$ for all $j\in[N]$), then we have $J_{\theta}(\mathbf{x})\leq J_{\theta}(\mathbf{y})$ due to the non-decreasing property of the CDF $F_{\theta}(\cdot)$.

• •

  If $f_{\theta}(\cdot)$ is non-increasing (i.e., $f_{\theta}^{\prime}(\cdot)\leq 0$), then both $F_{\theta}(\cdot)$ and $J_{\theta}(\cdot)$ are concave. In addition, in this case we have $J_{\theta}(\cdot)$ is subadditive, that is, for any $\mathbf{x},\mathbf{y}\in\mathbb{R}^{N}$, $J_{\theta}(\mathbf{x}+\mathbf{y})\leq J_{\theta}(\mathbf{x})+J_{\theta}(\mathbf{y})$. This additive property holds when $\mathbf{x},\mathbf{y}$ have disjoint supports.

To illustrate the penalty function $J_{\theta}(\cdot)$ as a sparsity measure, we show the corresponding sparsity levels computed via $J_{\theta}(\cdot)$ constructed based on the Exponential, the Rayleigh and the Weibull distributions for a compressible signal of length $50$ generated with its entries decay as $j^{-2}$ with $j\in\{1,2,\cdots,50\}$ in Figure 2. As we can see, for a compressible signal with very small but non-zero entries, all the $J_{\theta}(\cdot)$ with proper values of $\theta$ provided better sparsity measures than the traditional $\ell_{0}$ norm which equals $50$ here.

In this section, we discuss the recovery analysis results for the following constrained noiseless $J_{\theta}$-minimization:

where $J_{\theta}(\cdot)$ is constructed as in (2). Throughout this section, we assume that the function $J_{\theta}(\cdot)$ fulfills the subadditive property.

We start with the definition of a generalized version of the null space property (NSP) [18], which guarantees an exact sparse recovery for our proposed $J_{\theta}$-minimization (3).

Under the subadditivity of $J_{\theta}(\cdot)$, it is straightforward to obtain the following sufficient and necessary condition for an exact sparse recovery.

Moreover, we are able to show that by choosing a proper $\theta$, one can obtain a solution arbitrarily close to the unique solution of $\ell_{0}$ minimization via (3) based on the $\Delta_{q}$-spherical section property given in [15]. The proofs of the following results are quite similar to that given earlier in [15] and so are not reproduced here. Our results established in this present paper extend those given in [15] for the GERF method to any subadditive $J_{\theta}$-minimization method constructed as in (2).

In this section, we study a new sparse recovery method constructed via the Weibull distribution with PDF $f(x;k,\sigma)=\frac{k}{\sigma}(x/\sigma)^{k-1}e^{-(x/\sigma)^{k}},x\geq 0$, where $k>0$ is the shape parameter, $\sigma>0$ is the scale parameter, and CDF $F(x;k,\sigma)=1-e^{-(x/\sigma)^{k}}$. Hereafter, we denote the Weibull penalty (WBP) by

We hide its dependency on the parameters in $WBP(\mathbf{x})$ to keep the notation simple. The parameters $k$ and $\sigma$ control the degree of concavity of the penalty function $WBP(\mathbf{x})$. We refer this new sparse recovery method based on the Weibull penalty as ”WBP”. It is very flexible and includes the ETP method in [12, 13] as its special case of $k=1$.

Then, we can obtain the following proposition that characterizes the asymptotic behaviors of $WBP(\mathbf{x})$.

To prove (b), we have $1-e^{-|0/\sigma|^{k}}=0$ and $\forall\,x>0$,

In order to demonstrate this proposition, in Figure 3 we plot the objective functions of the Weibull penalty $WBP(\cdot)$ in $\mathbb{R}$ for various values of $k$ and $\sigma$. All the functions are scaled to attain the point $(1,1)$ for a better comparison. As expected, regardless of some constant, the Weibull penalty with a shape parameter $k$ is an interpolation of the $\ell_{0}$ and $\ell_{k}$ penalty. More specifically, it approaches the $\ell_{0}$ penalty as $\sigma$ approaches $0$, while it approaches the $\ell_{k}$ penalty as $\sigma$ approaches $+\infty$.

In this paper, we provide a unified framework for constructing the nonconvex separable penalty through the probability distribution. The theoretical recovery results in terms of the null space property and the spherical section property are presented. In addition, a new nonconvex method based on the Weibull penalty is used in sparse recovery.