In this paper we study sparsity-inducing nonconvex penalty functions using Levy processes. We define such a penalty as the Laplace exponent of a subordinator. Accordingly, we propose a novel approach for the construction of sparsity-inducing nonconvex penalties. Particularly, we show that the nonconvex logarithmic (LOG) and exponential (EXP) penalty functions are the Laplace exponents of Gamma and compound Poisson subordinators, respectively. Additionaly, we explore the concave conjugate of nonconvex penalties. We find that the LOG and EXP penalties are the concave conjugates of the negatives of Kullback-Leiber (KL) distance functions. Furthermore, the relationship between these two penalties is due to asymmetricity of the KL distance.