text: Recently, penalties promoting signals that are sparse within and across groups have been proposed. In this letter, we propose a generalization that allows to encode more intricate dependencies within groups. However, this complicates the realization of the threshold function associated with the penalty, which hinders the use of the penalty in energy minimization. We discuss how to sidestep this problem, and demonstrate the use of the modified penalty in an energy minimization formulation for an inverse problem.
  @cite_13: This paper addresses the problem of sparsity penalized least squares for applications in sparse signal processing, e.g., sparse deconvolution. This paper aims to induce sparsity more strongly than L1 norm regularization, while avoiding non-convex optimization. For this purpose, this paper describes the design and use of non-convex penalty functions (regularizers) constrained so as to ensure the convexity of the total cost function F to be minimized. The method is based on parametric penalty functions, the parameters of which are constrained to ensure convexity of F. It is shown that optimal parameters can be obtained by semidefinite programming (SDP). This maximally sparse convex (MSC) approach yields maximally non-convex sparsity-inducing penalty functions constrained such that the total cost function F is convex. It is demonstrated that iterative MSC (IMSC) can yield solutions substantially more sparse than the standard convex sparsity-inducing approach, i.e., L1 norm minimization.
  @cite_14: We propose a novel group regularization which we call exclusive lasso. Unlike the group lasso regularizer that assumes covarying variables in groups, the proposed exclusive lasso regularizer models the scenario when variables in the same group compete with each other. Analysis is presented to illustrate the properties of the proposed regularizer. We present a framework of kernel based multi-task feature selection algorithm based on the proposed exclusive lasso regularizer. An efficient algorithm is derived to solve the related optimization problem. Experiments with document categorization show that our approach outperforms state-of-theart algorithms for multi-task feature selection.
  @cite_4: We propose a new penalty function which, when used as regularization for empirical risk minimization procedures, leads to sparse estimators. The support of the sparse vector is typically a union of potentially overlapping groups of co-variates defined a priori, or a set of covariates which tend to be connected to each other when a graph of covariates is given. We study theoretical properties of the estimator, and illustrate its behavior on simulated and breast cancer gene expression data.
  @cite_28: Convex optimization with sparsity-promoting convex regularization is a standard approach for estimating sparse signals in noise. In order to promote sparsity more strongly than convex regularization, it is also standard practice to employ non-convex optimization. In this paper, we take a third approach. We utilize a non-convex regularization term chosen such that the total cost function (consisting of data consistency and regularization terms) is convex. Therefore, sparsity is more strongly promoted than in the standard convex formulation, but without sacrificing the attractive aspects of convex optimization (unique minimum, robust algorithms, etc.). We use this idea to improve the recently developed ‘overlapping group shrinkage’ (OGS) algorithm for the denoising of group-sparse signals. The algorithm is applied to the problem of speech enhancement with favorable results in terms of both SNR and perceptual quality.
  @cite_6: Mixed norms are used to exploit in an easy way, both structure and sparsity in the framework of regression problems, and introduce implicitly couplings between regression coefficients. Regression is done through optimization problems, and corresponding algorithms are described and analyzed. Beside the classical sparse regression problem, multi-layered expansion on unions of dictionaries of signals are also considered. These sparse structured expansions are done subject to an exact reconstruction constraint, using a modified FOCUSS algorithm. When the mixed norms are used in the framework of regularized inverse problem, a thresholded Landweber iteration is used to minimize the corresponding variational problem.
  @cite_24: We introduce a new penalty function that promotes signals composed of a small number of active groups, where within each group, only a few high magnitude coefficients are nonzero. We derive the threshold function associated with the proposed penalty and study its properties. We discuss how the proposed penalty threshold function can be useful for signals with isolated nonzeros, such as audio with isolated harmonics along the frequency axis, or reflection functions in exploration seismology where the nonzeros occur on the boundaries of subsoil layers. We demonstrate the use of the proposed penalty threshold functions in a convex denoising and a nonconvex deconvolution formulation. We provide convergent algorithms for both formulations and compare the performance with state-of-the-art methods.
  @cite_19: This paper addresses signal denoising when large-amplitude coefficients form clusters (groups). The L1-norm and other separable sparsity models do not capture the tendency of coefficients to cluster (group sparsity). This work develops an algorithm, called 'overlapping group shrinkage' (OGS), based on the minimization of a convex cost function involving a group-sparsity promoting penalty function. The groups are fully overlapping so the denoising method is translation-invariant and blocking artifacts are avoided. Based on the principle of majorization-minimization (MM), we derive a simple iterative minimization algorithm that reduces the cost function monotonically. A procedure for setting the regularization parameter, based on attenuating the noise to a specified level, is also described. The proposed approach is illustrated on speech enhancement, wherein the OGS approach is applied in the short-time Fourier transform (STFT) domain. The OGS algorithm produces denoised speech that is relatively free of musical noise.
  @cite_16: In a number of signal processing applications, problem formulations based on the l 1 norm as a sparsity inducing signal prior lead to simple algorithms with good performance. However, l 1 norm is not flexible enough to handle certain signal structures that are represented using a few groups of coefficients. Formulations that make use of mixed norms provide an alternative that can handle such signals by forcing sparsity on a group level and allowing non-sparse distributions within the groups. However, conventional mixed norms allow only non-overlapping groups - a restriction that leads to characteristics unlikely for natural signals. In this paper, we investigate mixed norms with overlapping groups. We consider a simple denoising formulation that gives a convex optimization problem and provide an algorithm that solves the problem. We use the algorithm to evaluate the performance of mixed norms with overlapping groups as signal priors.
  @cite_10: Sparse regression often uses l p norm priors (with p < 2). This paper demonstrates that the introduction of mixed-norms in such contexts allows one to go one step beyond in signal models, and promote some different, structured, forms of sparsity. It is shown that the particular case of the l1,2 and l2,1 norms leads to new group shrinkage operators. Mixed norm priors are shown to be particularly efficient in a generalized basis pursuit denoising approach, and are also used in a context of morphological component analysis. A suitable version of the Block Coordinate Relaxation algorithm is derived for the latter. The group-shrinkage operators are then modified to overcome some limitations of the mixed-norms. The proposed group shrinkage operators are tested on simulated signals in specific situations, to illustrate and compare their different behaviors. Results on real data are also used to illustrate the relevance of the approach.
  @cite_25: Summary. We consider the problem of selecting grouped variables (factors) for accurate prediction in regression. Such a problem arises naturally in many practical situations with the multifactor analysis-of-variance problem as the most important and well-known example. Instead of selecting factors by stepwise backward elimination, we focus on the accuracy of estimation and consider extensions of the lasso, the LARS algorithm and the non-negative garrotte for factor selection. The lasso, the LARS algorithm and the non-negative garrotte are recently proposed regression methods that can be used to select individual variables. We study and propose efficient algorithms for the extensions of these methods for factor selection and show that these extensions give superior performance to the traditional stepwise backward elimination method in factor selection problems. We study the similarities and the differences between these methods. Simulations and real examples are used to illustrate the methods.
  @cite_17: For high-dimensional supervised learning problems, often using problem-specific assumptions can lead to greater accuracy. For problems with grouped covariates, which are believed to have sparse effects both on a group and within group level, we introduce a regularized model for linear regression with l1 and l2 penalties. We discuss the sparsity and other regularization properties of the optimal fit for this model, and show that it has the desired effect of group-wise and within group sparsity. We propose an algorithm to fit the model via accelerated generalized gradient descent, and extend this model and algorithm to convex loss functions. We also demonstrate the efficacy of our model and the efficiency of our algorithm on simulated data. This article has online supplementary material.
summary: The sparsity characteristic sought in this letter is different than that sought in many papers using group-based penalty functions. Specifically, @cite_25 @cite_6 @cite_4 @cite_16 @cite_19 @cite_17 aim to promote signals that can be represented with a few groups, where within groups, the coefficients are less stringently penalized. In contrast, @cite_6 @cite_10 @cite_14 @cite_24 aim a similar characteristic as the proposed penalty. In this collection, the SWAG penalty @cite_24 , which the proposed penalty aims to modify, separates from the rest in that it is a non-convex penalty. In @cite_24 , it was argued that this property reduces the bias in the non-zero estimates produced by the threshold function (see also @cite_28 @cite_13 for related discussions). For a more detailed comparison between the SWAG penalty and the penalties in @cite_6 @cite_10 @cite_14 , we refer to @cite_24 .