Matthieu Kowalski
email: matthieu.kowalski@lss.supelec.fr

Kai Siedenburg
email: kai.siedenburg@mail.mcgill.ca

Monika Dörfler
email: monika.doerfler@univie.ac.at

Social Sparsity! Neighborhood Systems Enrich Structured Shrinkage Operators

Keywords: Structured Sparsity, Iterative Thresholding, Convex Optimization •

Sparse and structured signal expansions on dictionaries can be obtained through explicit modeling in the coefficient domain. The originality of the present article lies in the construction and the study of generalized shrinkage operators, whose goal is to identify structured significance maps and give rise to structured thresholding. These generalize Group Lasso and the previously introduced Elitist Lasso by introducing more flexibility in the coefficient domain modeling, and lead to the notion of social sparsity. The proposed operators are studied theoretically and embedded in iterative thresholding algorithms. Moreover, a link between these operators and a convex functional is established. Numerical studies on both simulated and real signals confirm the benefits of such an approach.

I. INTRODUCTION

A wide range of inverse problems arising in signal processing have benefited from sparsity. Introduced in the mid 90's by Chen, Donoho and Saunders [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF], the idea is that a signal can be efficiently represented as a linear combination of elementary atoms chosen from an appropriate dictionary. Here, efficiently may be understood in the sense that only few atoms are needed to reconstruct the signal. The same idea appeared in the machine learning community [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF], where often only few variables are relevant in inference tasks based on observations living in very high dimensional spaces.

The natural measure of the cardinality of a support set, and hence its sparsity, is the 0 "norm" which counts the number of non-zero coefficients. Minimizing such a penalty leads to a combinatorial problem which is usually relaxed into a 1 norm which is convex.

Solving an inverse problem by using the sparse principle can be done by the following steps: of the signal: Gabor dictionaries (for audio signals for example), wavelet dictionaries (for images) are commonly used, among others. The dictionary can even be learned directly on a class of signals [START_REF] Rubinstein | Dictionaries for sparse representation modeling[END_REF]. In order to be able to use the sparse principle, this step of choosing an appropriate dictionary is obviously crucial. • Choose a loss in order to link the observations, or measured signals, to the sought signals. While other loss functions, such as the logistic loss, may be used, in the current contribution, we focus on the classical 2 norm used with success in various problems.

• Apply an 1 penalty on the coefficients of the signal expanded in the dictionary. The resulting convex optimisation problem is known as the Basis Pursuit (Denoising) [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF] or the Lasso [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF]. This approach can be viewed as a synthesis model of the signal: one directly estimates its coefficients inside a dictionary in order to synthesize the signal from these coefficients.

One of the main limitations of this approach to sparse modeling is that all the coefficients are treated independently. Most natural signals are highly structured, however, and the structures which become visible in an analysis of a signal correspond to the physical prior which could be used for its processing. We instance such an observation on an audio signal.

A. From sparsity to the need of structures Fig. 1 displays the time samples of a glockenspiel signal, and two time-frequency representations using a modified discrete cosine transform (MDCT), one with a narrow band analysis window adapted for the tonal part (well localized in frequency) and one with a large band analysis window (well localized in time). Clearly, the time samples are not a sparse representation. The two time-frequency representations display only few "big" coefficients (in dark gray), while the organisation of these coefficients (their structure) depends on the choice of the basis. Hence an idea is to construct a dictionary as a union of two others, each adapted to the "morphological layer". Such an approach has been proposed in [START_REF] Daudet | Hybrid representations for audiophonic signal encoding[END_REF] as hybrid model for audio signals, and in [START_REF] Elad | Simultaneous cartoon and texture image inpainting using morphological component analysis (mca)[END_REF] as morphological model for images. A more theoretical study has been performed in [START_REF] Gribonval | Sparse representations in unions of bases[END_REF], where sufficient conditions that guarantee the uniqueness of a sparse representation in union of orthogonal bases were obtained.

In addition to these observations, we notice a grouping effect of the coefficients in both time-and frequency-direction, for each of the dictionaries used. The main motivation for the work presented in this article is to better understand how this grouping effect can be taken into account in this and similar situations, in order to obtain a more reliable sparse representation in a corresponding dictionary.

Our main contribution is to propose the concept of social sparsity: a certain, possibly weighted, neighborhood of a given coefficient is considered for deciding whether to keep or discard the coefficient under consideration. This idea was first introduced in [START_REF] Kowalski | Sparsity and persistence: mixed norms provide simple signals models with dependent coefficients[END_REF]; it was equipped with weights and evaluated for various audio applications in [START_REF] Siedenburg | Structured sparsity for audio signals[END_REF]. For the realization of the intuitive idea that a coefficient's neighborhood should be relevant for its impact, we construct structured shrinkage operators which are directly derived from classical proximity/shrinkage operators such as the Group-Lasso. However, while the classical proximity operators are directly linked to convex regression problems with mixed norm priors on the coefficients, the new, structured, shrinkage operators can not be directly linked to a convex minimization problem. While the convergence of related iterative algorithms for the classical shrinkage operators and their generalizations was studied in [START_REF] Kowalski | Sparse regression using mixed norms[END_REF] in a rather general setting, the theoretical properties of the new operators have not been considered so far. In the current contribution, we establish a formal relation between the structured shrinkage operators and the minimization of a convex functional by introducing an expansion operator, which maps the coefficient space into a higher-dimensional space. Exploiting this extension, the shrinkage operators are linked to a related convex problem, whose convergence properties are known. While proving convergence of the initial algorithm associated with the new shrinkage operators remains an open problem, numerical experiments show that its behavior is sufficiently similar to the behavior of the algorithm derived from the more formal convex formulation. By replacing an oblique by an orthogonal projection, we also propose another alternative operator, for which the convergence to a fixed point is warranted. Our framework also allows the inclusion of the recently introduced Latent-Group-Lasso [START_REF] Jacob | Group lasso with overlap and graph lasso[END_REF], [START_REF] Obozinski | Group lasso with overlaps: the latent group lasso approach[END_REF], to whose performance the new algorithms will also be compared.

B. Outline

Section II introduces the mathematical framework used for this article and Section III presents the state of the art related to this framework. The structured shrinkage operators are introduced in Section IV where their theoretical study is derived. We show in Section V some practical implementation of our approach and present numerical results of its performance in denoising tasks on audio and image-signals.

II. MATHEMATICAL FRAMEWORK

This section introduces notation used throughout the paper as well as some useful results from convex analysis.

A. Notation

We will denote the observed signal as y ∈ R L , obtained from the signal of interest s ∈ R L corrupted by an additive noise b ∈ R L , i.e. y = s + b .

The matrix of the dictionary is denoted by Φ ∈ C L,N and the synthesis coefficients of s in Φ are denoted by

α ∈ C N , such that y = s + b = Φα + b .
A sparse estimation of s is given by the Lasso [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF] or Basis Pursuit Denoising [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF]:

ŝ = Φ argmin α∈C N 1 2 y -Φα 2 2 + λ α 1 , λ > 0 . (1)
In this article we choose to use the general convex formulation

ŝ = Φ argmin α∈C N 1 2 y -Φα 2 2 + λΩ(α) (2)
where Ω is a convex penalty. Depending upon the choice made for Ω, different kinds of sparsity or structure can be enforced.

Remark 1. We choose to limit our purpose to the case of sparse regression, where the synthesis coefficients α of the signal of interest s are estimated from a single measurement y only corrupted by an additive noise. However, this approach can be extended to more general inverse problems where several signals have to be estimated from several measurements such as in source separation [START_REF] Kowalski | Beyond the narrowband approximation: Wideband convex methods for under-determined reverberant audio source separation[END_REF].

Remark 2. The functionals appearing in (1) and (2) are convex but not necessarily strictly convex. Then, the set of minimizers is not necessarily a singleton. However, with a slight abuse of notation, we choose the notation argmin to represent any minimizer, as the choice of a particular minimizer has no consequences for the rest of the paper. One can refer to [START_REF] Osborne | On the lasso and its dual[END_REF] and [START_REF] Tropp | Just relax: Convex programming methods for identifying sparse signals[END_REF] for discussions of the uniqueness of the 1 problem.

B. Short reminder of Convex optimization

The algorithms proposed in this paper are issued from convex optimization methods and rely on the notion of the proximity operator, introduced by Moreau [START_REF] Moreau | Proximité et dualité dans un espace hilbertien[END_REF], which allows to deal with non-smooth functionals.

Definition 1 (Proximity operator). Let ϕ : C N → C N be a lower semicontinuous, convex function. The proximity operator of ϕ denoted by prox ϕ : C N → C N is given by

prox ϕ (z) = argmin u∈C N 1 2 z -u 2 2 + ϕ(u). (3)
The most well-known example of such an operator is the shrinkage given by the 2 Tikhonov regularization and the soft-thresholding given by the 1 norm.

If one is able to compute the proximity operator of a convex regularizer Ω, then the minimizer of the convex functional (2) can be obtained by using proximal algorithms. The simplest proximal algorithm was found in the 1 case by several researchers using very different approaches. In [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF] Daubechies and coauthors derived the thresholded Landweber iterations using a surrogate and proved the convergence using Opial's fixed point Theorem. In [START_REF] Figueiredo | An em algorithm for wavelet-based image restoration[END_REF], Figueiredo et al. found the same algorithm thanks to an expectation/maximization formulation. A more general version using the proximity operators was given by the forward-backward algorithm studied by Combettes et al. [START_REF] Combettes | Signal recovery by proximal forwardbackward splitting[END_REF]. We will refer to this algorithm as the Iterative Shrinkage/Thresholding Algorithm (ISTA) as in [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF] and we restate it in Algorithm 1 for the problem studied here.

Algorithm 1: ISTA Initialization: α (0) ∈ C N , k = 1, γ = ΦΦ * repeat α (k) = prox λ γ Ω α (k-1) + 1 γ Φ * (y -Φα (k-1) ) ; k = k + 1; until convergence;
ISTA can be viewed as a generalization of the gradient descent for the non smooth functional (2). The algorithm is very simple, but converges slowly in practice. Recent advances in convex optimization lead to more efficient algorithms, we refer to [START_REF] Tseng | Approximation accuracy, gradient methods, and error bound for structured convex optimization[END_REF] for a thorough discussion of proximal algorithms and their accelerations. Algorithm 2 describes the Fast Iterative Shrinkage/Thresholding Algorithm as proposed in [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF]. The Algorithm 2: FISTA

Initialization: α (0) ∈ C N , k = 1, γ = ΦΦ * , z (0) = α (0) , τ (0) = 1. repeat α (k) = prox λ γ Ω z (k-1) + 1 γ Φ * (y -Φz (k-1) ) ; τ (k) = 1 2 1 + 1 + 4τ (k-1) 2 ; z (k) = α (k) + τ (k-1) -1 τ (k) (α (k) -α (k-1) ); k = k + 1 until convergence;
choice γ = ΦΦ * is a sufficient condition in order to ensure the convergence of ISTA and FISTA. In some cases, it can be useful to perform a line search for γ at each iteration (see [START_REF] Beck | A fast iterative shrinkage-thresholding algorithm for linear inverse problems[END_REF]). However, we observed that when the matrix ΦΦ * is not "too badly conditioned", such a line search does not bring any computational advantage. In particular in the experiments performed in Section V, the default constant choice for γ works well.

Having introduced practical algorithms to deal with convex functionals as in [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF], in the next section, we turn to reviewing some state-of-the-art approaches that go beyond the simple sparsity paradigm.

III. STATE OF THE ART

Considering grouping structures of coefficients appears as a natural idea in the sparse regression context. A simple way to obtain such groupings is the use of mixed norms, which allows to regroup coefficients. We first give the definition of mixed norms and their proximity operators which will be used later. Other kinds of grouping structures which appear in the literature are presented afterwards.

A. Mixed norms

Mixed norms were introduced by Benedek and Panzone [START_REF] Benedek | The space l p with mixed norm[END_REF] in the early 1960's in mathematics.

1) Definition on two levels: We give here the general definition as in [START_REF] Kowalski | Sparsity and persistence: mixed norms provide simple signals models with dependent coefficients[END_REF], [START_REF] Kowalski | Sparse regression using mixed norms[END_REF].

Definition 2 (Two-level mixed norms). Let x ∈ R N = R G×M be indexed by a double index (g, m) ∈ N 2 such that x = (x g,m ).
Let p, q ≥ 1, and w ∈ R N +, * be a sequence of strictly positive weights labeled by double index (g, m). We call w;p,q the mixed norm of x ∈ R N defined by

x w;p,q =   G g=1 M m=1 w g,m |x g,m | p q/p   1/q .
The cases p = +∞ and q = +∞ are obtained by replacing the corresponding sum by the supremum.

Two mixed norms appear quite naturally by playing with the different values of p and q: the 21 and 12 norms. The 21 norm was used with the name Group-Lasso [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF] (G-Lasso) in machine learning, but also Multiple Measurement Vectors [START_REF] Cotter | Sparse solutions to linear inverse problems with multiple measurement vectors[END_REF] or joint sparsity [START_REF] Fornasier | Recovery algorithm for vector-valued data with joint sparsity constraints[END_REF] in signal processing. In the context of regression, the main aim of such a norm is to keep or discard entire groups of coefficients. Indeed, if we consider the special case of an orthogonal basis, only the most energetic groups remain.

The 12 norm was introduced under the name of Elitist-Lasso [START_REF] Kowalski | Sparsity and persistence: mixed norms provide simple signals models with dependent coefficients[END_REF], [START_REF] Kowalski | Sparse regression using mixed norms[END_REF] (E-Lasso), and latter called Exclusive Lasso in [START_REF] Zhou | Exclusive lasso for multi-task feature selection[END_REF]. With such a penalty, and if Φ is an orthogonal basis, we keep the biggest coefficients relative to the others . Such behavior can be expected in applications such as source separation [START_REF] Kowalski | Beyond the narrowband approximation: Wideband convex methods for under-determined reverberant audio source separation[END_REF].

2) Extension to 3 levels: This notion of mixed norms can be extended to more than two levels. On three levels, the definition becomes [START_REF] Gramfort | Improving m/eeg source localization with an inter-condition sparse prior[END_REF] Definition 3 (Three-level mixed norms). Let x ∈ R N = R K×G×M be indexed by a triple index (k, g, m) ∈ N 3 such that x = (x k,g,m ). Let p, q, r ≥ 1 and w ∈ R N +, * a sequence of strictly positive weights. We call w;p,q,r the mixed norm of x defined by

x w;pqr =    K k=1   G g=1 M m=1 w k,g,m |x k,g,M | p q/p   r/q    1/r .
The cases p = +∞, q = +∞ and r = +∞ are obtained by replacing the corresponding sum by the supremum.

The 212 mixed norm was used with success in Magnetoencephalography inverse problems [START_REF] Gramfort | Improving m/eeg source localization with an inter-condition sparse prior[END_REF] and could be called Elitist-Group-Lasso (EG-Lasso).

3) Proximity Operators: In order to optimize certain convex problems using mixed norms, their proximity operator needs to be computed. The following proposition summarizes the different operators for various norms, cf. [START_REF] Kowalski | Sparse regression using mixed norms[END_REF].

Proposition 1 (Proximity operators for mixed norms). Let x ∈ R N and z ∈ R N . Let w ∈ R N +, * be a vector of weights. We suppose that x, z and w are indexed by (g, m).

G-Lasso w;21 norm: In this case, the vector of weights w is used to weight each group, i.e. ∀m, w g,m = w g .

The proximity operator associated to the w;21 norm is given by x = prox λ . w,21 (z) where x reads for each coordinate:

x g,m = z g,m 1 - λ √ w g z g 2 + ,
and z g is the vector formed by the coefficients indexed by m.

E-Lasso w;12 norm: Let r g,m def = |z g,m |/w g,m and for each g, let the indexing denoted by m g be defined such that ∀m g , r g,m g +1 ≤ r g,m g and re-order the z g,m according to this index. Let the index M g be such that:

λ Mg m g =1 w 2 g,m g r g,m g -r g,Mg < r g,Mg ≤ λ Mg+1 m g =1 w 2 g,m g r g,m g -r g,Mg
The proximity operator x = prox λ . w,12 (z) is given coordinate-wise:

x g,m = z g,m |z g,m |   |z g,m | - λ 1 + λK wg Mg m g =1 |z g,m g |   + , where K wg = Mg m g =1 w 2
g,m g . EG-Lasso w;212 norm: Let x be indexed by (h, g, m). Let w ∈ R N be a vector of positive weights such that ∀m, w h,g,m = w h,g . Let us define r h,g

def = z h,g 2 / √ w h,g .
For each h, let the indexing denoted by g h be defined such that ∀g h , r h,g h +1 ≤ r h,g h . Let the index G h be such that:

λ G h g h =1 w h,g h r h,g h -r h,G h < r h,G h ≤ λ G h +1 g h =1 w h,g h r h,g h -r h,G h .
Denoting by [z h,g h ] = √ w h,g h z h,g h 2 and supposing that they are ordered by g h , then x = prox λ . 2 w;212 (z) is given, for each coordinate (h, g, m), by:

x h,g,m = z h,g,m       1 - λ √ w h,g 1 + λK w h G h g h =1 [z h,g h ] z h,g 2       + ,
where

K w h = G h g h =1 w h,g h . Remark 3.
The proximity operators of the 121 mixed norms and of general mixed norms defined on more than three levels are not computable in a closed form. In fact, one needs to compute a "Group-Lasso" proximity operator with weights varying in groups, which does not admit a closed form.

It is interesting to note that in [START_REF] Szafranski | Hierarchical penalization[END_REF] a hierarchical formulation of the dependencies leads to a 1, 4 3 mixed norm. Notice that the mixed norms as defined here do not consider any overlap between the groups. The need for overlapping groups was recognized by many authors, see [START_REF] Jacob | Group lasso with overlap and graph lasso[END_REF], [START_REF] Fuchs | Extension of the global matched filter to structured groups of atoms: Application to harmonic signals[END_REF]- [START_REF] Peyré | Group sparsity with overlapping partition functions[END_REF], and different strategies have been proposed.

B. A step beyond mixed norms

In [START_REF] Jacob | Group lasso with overlap and graph lasso[END_REF], [START_REF] Obozinski | Group lasso with overlaps: the latent group lasso approach[END_REF], starting from the observation that the Group-Lasso discards all coefficients in a given group, the authors define a new norm in order to deal with overlapping groups: the Latent-Group-Lasso. This definition of a new convex penalty leads to the desired results: all coefficients belonging to the same group are kept, even if they also belong to another group which is discarded. The remaining support is thus a union of groups instead of the complement of a union as in the Group-Lasso. However, in general, there is no closed form for the proximity operators corresponding to the Latent-Group-Lasso. The authors propose a reformulation and solution of the convex problem by introducing a latent variable in a high dimensional space through the duplication of the variables belonging to overlapping groups.

In the particular case where the groups are all the subsets of a given cardinality, the proximity operator can be computed exactly. This particular case corresponds in fact to the so called k-support norm [START_REF] Argyriou | Sparse prediction with the ksupport norm[END_REF], which is closely related to the elastic net [START_REF] Zou | Regularization and variable selection via the elastic net[END_REF]. Furthermore, iterative algorithms exist, cf. [START_REF] Mosci | A primal-dual algorithm for group sparse regularization with overlapping groups[END_REF] if one needs to compute the proximity operator in the general case.

Despite the "discarding" behavior of the Group-Lasso, mixed norms with overlaps have been studied in [START_REF] Bayram | Mixed norms with overlapping groups as signal priors[END_REF]. Again, the proximity operator has no closed form, but an iterative scheme is proposed. The mixed norm with overlaps corresponds actually to a particular case of the regularizer proposed in [START_REF] Peyré | Group sparsity with overlapping partition functions[END_REF], where a partition function is introduced to construct a convex penalty.

As we will see in Section IV-C2, all these methods are closely related. The study of the proposed structured shrinkage operators naturally leads to convex functionals which correspond to the problems proposed in the previously mentioned contributions.

Various other kinds of structures have been proposed for refining the model of group based sparsity. For example, in [START_REF] Jenatton | Proximal methods for hierarchical sparse coding[END_REF] a hierarchy on groups was introduced. Such a behavior allows for sparsity inside the group, in addition to sparsity between the groups. In particular, their hierarchical sparse coding included the sums of convex penalties such as a 21 + 1 composite norm, also known as the HiLasso [START_REF] Sprechmann | C-hilasso: A collaborative hierarchical sparse modeling framework[END_REF]. Such a composite norm was used with success for Magnetoencephalography inverse problems with respect to timefrequency dictionaries [START_REF] Gramfort | Functional brain imaging with m/eeg using structured sparsity in timefrequency dictionaries[END_REF]. In [START_REF] Jenatton | Structured variable selection with sparsity-inducing norms[END_REF], the authors studied a very general mixed norm, allowing to generalize the Group-Lasso and the hierarchical sparse coding.

In [START_REF] Micchelli | A family of penalty functions for structured sparsity[END_REF], the authors propose a family of "convex penalty functions, which encode this prior knowledge by means of a set of constraints on the absolute values of the regression coefficients". In practice, the structure is encoded by means of an auxiliary variable. This formulation is general enough to obtain the Lasso and the Group-Lasso as special cases. The drawback of this flexibility may lie in the difficulty to define the desired structure, and the computational complexity of optimization when the problem lives in a high dimensional space.

In addition to the convex approaches, several other solutions were proposed for the structured sparsity problem. Among others, we can cite the model-based compressive sensing [START_REF] Baraniuk | Modelbased compressive sensing[END_REF], and approaches based on coding theory [START_REF] Huang | Learning with structured sparsity[END_REF] or Bayesian methods (see e.g. [START_REF] Zhang | Exploiting correlation in sparse signal recovery problems: Multiple measurement vectors, block sparsity, and time-varying sparsity[END_REF] and references therein).

IV. STRUCTURED SHRINKAGE

One of the main shortcomings of the various "structured block sparsity" approaches exposed above, is that the definition of the groups must be done a priori. However, in many situations, we just have a general idea of the grouping structure, and fixing the groups can be too rigid.

Instead of defining groups, and therewith keeping or discarding entire blocks of coefficients, a notion of neighborhoodbased selection was proposed in [START_REF] Kowalski | Structured sparsity: from mixed norms to structured shrinkage[END_REF]. The introduction of this neighborhood gives rise to "social sparsity": a decision can be made coefficient by coefficient by taking into account the "weight" of a coefficient's neighborhood. The latter still has to be defined a priori, but the possibility of overlap between neighborhoods instead of groups relaxes the rigor of the (Group-)Lasso approaches. For application, neighborhoods then should be chosen according to the grouping structures observed in the specific signal class under observation, as e.g. the persistence of tonal and transient parts in audio signals noted above or the father-son persistence in wavelet expansions of images to be addressed below.

In order to present this approach, we first give the definition of the neighborhood and re-state the shrinkage operators empirically introduced in [START_REF] Kowalski | Structured sparsity: from mixed norms to structured shrinkage[END_REF] and equipped with weights in [START_REF] Siedenburg | Structured sparsity for audio signals[END_REF].

A. Structured shrinkage operators

To exploit structures in the synthesis coefficients, (like persistence in time or frequency in audio signals as in Fig. 1 in the introductory Section I), we will refine some classical shrinkage operators by taking into account the neighborhood of a coefficient. To an index k in a set I, we associate a weighted neighborhood N (k) = {k ∈ I : w

(k) k = 0} with weights w (k) k such that w (k) k ≥ 0 for all k ∈ I, w (k) k > 0 and k ∈N (k) w (k) 2 k = 1.
This notion of neighborhood is illustrated on Fig. 2.

N(k2) k1 k2 N(k1) Fig. 2.
The neighborhood of the coefficient k 1 is given by the red window, and the neighborhood of the coefficient k 2 by the blue one. These two neighborhoods share one coefficient. When considering the red group, coefficients are weighted by some weights

w k 1 k > 0, k ∈ N (k 1 )
. Outside the red group, the weights are equal to zero. When considering the blue group, coefficients are weighted by some weights

w k 2 k > 0, k ∈ N (k 2 ).
Once the neighborhood is defined, we can define shrinkage operators on it. These operators are constructed with the shrinkage operators given by the proximity operator corresponding to the Group/ Elitist/ Elitist-Group-Lasso defined in Section III, Proposition 1, by considering the "groups" formed by the neighborhood.

1) WG-Lasso: We first introduce the Windowed-Group-Lasso [START_REF] Kowalski | Structured sparsity: from mixed norms to structured shrinkage[END_REF] shrinkage operator, defined as

S wgl λ (α) : C N → C N α → α such that for all k , α k = α k     1 - λ k ∈N (k) w (k) k |α k | 2     + . (4)
The idea of this shrinkage operator is to select a coefficient if the energy of its neighborhood is sufficiently large. Consequently, an isolated "big" coefficient can be discarded, but a "small" coefficient in the middle of big ones can be kept. Such a notion of neighborhood can also be found earlier in [START_REF] Cai | Incorporating information on neighbouring coefficients into wavelet estimation[END_REF], where a similar thresholding rule was studied in the context of SURE wavelet estimation.

2) WE-Lasso: Instead of considering a positive correlation between the coefficient in the neighborhood, one can consider a negative correlation as in the Elitist-Lasso. This leads to the following shrinkage operator, which we will call the Windowed-Elitist-Lasso. For each neighborhood N (k), let the indexing denoted by k be defined such that ∀k ∈ N (k), w

(k) k +1 |α k +1 | ≤ w (k) k |α k |. Let the index K k be such that: λ K k k =1 w (k) k α k -w (k) K k α K k < α K k ≤ λ K k +1 k =1 w (k) k α k -w (k) K k α K k
Then the Windowed-Elitist-Lasso shrinkage operator is given by

S wel λ (α) : C N → C N α → α such that k , α k = α k |α k |     |α k | - λ 1 + λK w k K k k =1 k ∈N (k) w (k) k |α k |     + . (5)
where

K w k = K k k =1 k ∈N (k) w (k) 2 k .
These two heuristic shrinkage operations are computed on singly-indexed coefficients by taking into account their neighborhood. Thus the definition of neighborhood induces a double indexing in the end: one to index the neighborhood, another to index the element which belongs to a neighborhood. The shrinkage is then defined by applying the proximity operator given by the Group-Lasso or the Elitist-Lasso by using this induced double indexing.

3) PE-Lasso: Now, if we consider a set of coefficients which is already doubly indexed by (g, m), we can define two kinds of neighborhoods: a first neighborhood on m and a second neighborhood on g. This will lead to triply-indexed coefficients and we can apply the Elitist-Group-Lasso shrinkage operator, as done above with Group-Lasso and Elitist-Lasso, to obtain the Persistent-Elitist-Lasso [START_REF] Kowalski | Structured sparsity: from mixed norms to structured shrinkage[END_REF].

To an index (g, m) in a structured set I = I g × I m , we associate a weighted neighborhood N (g, m) = {m ∈ I m : w w

(g,m)
g,m α 2 g,m . For each g, let the indexing denoted by m g be defined such that ∀m g , [α] g,m g +1 ≤ [α] g,m g and re-order the [α] according to this index. Let the index M g be such that:

λ Mg m g =1 [α] g,m g -[α] g,Mg < [α] g,Mg ≤ λ Mg+1 m g =1 [α] g,m g -[α] g,Mg .
Then the Persistent-Elitist-Lasso shrinkage operator [START_REF] Kowalski | Structured sparsity: from mixed norms to structured shrinkage[END_REF] is given by

S pel λ (α) : C N → C N α → α
where for all g, m ,

α g,m = α g,m       1 - λ 1 + λM g Mg m g =1 [α] g,m g α m ∈N (g,m) 2       + . (6)
Here, a coefficient will be selected if its neighborhood is sufficiently energetic compared to the others. Such a structure is illustrated in Fig. 3.

Group (g)

Member (m) Fig. 3. Persistent Elitist-LASSO. Coefficients are doubly index by (g,m). For each we are considering the left and the right neighbor to define the neighborhood. Then, an E-Lasso selection is done between these groups.

The new operators constructed above are based on the shrinkage/thresholding operators of the proximity operators associated to the convex prior given in Proposition 1. In the present form, they are not directly associated to a convex problem themselves. In the following, we set up an explicit connection between the proximity operators from Proposition 1 and the newly introduced structured shrinkage operators (4) - [START_REF] Gribonval | Sparse representations in unions of bases[END_REF]. For this purpose, the next subsection defines a mapping into a bigger space where the proximity operator can be applied.

B. Neighborhoods with latent variables

The neighborhoods, and the groups they implicitly induce, can be formally defined via an expansion operator. This operator maps the original coefficients into a bigger space, where its image consists of copies of the coefficients such that independent groups can be defined over the neighborhood of the coefficients.

Definition 4 (Expansion operator)

. Let α ∈ C N . Let E : C N → C N ×N be an expansion operator such that α = (α 1 , . . . , α N ) → ( w (1) 1 α 1 , . . . , w (1)
N α N , . . . , w

(N ) 1 α 1 , . . . , w (N ) N α N ) with w (j) i ≥ 0 and j w (j) i = 1 for all i.
In practice, the non-zeros weight are the same as the weights as in the definition of the social shrinkage operators above. We thus have constructed one group for each coefficient, regrouping all its neighborhood by "copying" the coefficients. Due to the condition on the weights, we can state the following proposition which will be crucial later on. Proposition 2. E is isometrical, and E * (E(α)) = α.

Proof: Let E be an expansion operator as defined in Definition 4. Then, for any α ∈ C N , we have

E(α) 2 = i j | w (j) i α i | 2 = i |α i | 2 j w (j) i = i |α i | 2 = α 2 .
Hence the proposition. Let E denotes the matrix associated with E. This matrix can be viewed as a N 2 × N matrix where each row contains at most only one non-zero element, corresponding to the weights associated to the elements of a neighborhood:

E = [E 1 , . . . , E N ] T , (7)
with

E i ∈ R N ×N E i = [ w (i) 1 e T 1 , . . . , w (i)
N e T N ] T , where e j is the j th canonical base vector of R N . A similar expansion matrix has also been used in the context of overlapping groups in [START_REF] Peyré | Group sparsity with overlapping partition functions[END_REF], [START_REF] Chen | Smoothing proximal gradient method for general structured sparse learning[END_REF].

A direct consequence is that one can simply go back to the original space by using the adjoint operator. However, in order to be able to establish a link between the heuristic shrinkage operators previously defined and the common proximity operator, we need to introduce the following left inverse of E:

D : C N ×N → C N z = (z 1 1 , . . . , z 1 N , . . . , z N 1 , . . . , z N N ) → x such that ∀k, x k = 1 w (k) k z k k (8)
One can easily check that we have DE = I and then ED is a bi-orthogonal (oblique) projection. Moreover D is such that

DD T = diag 1 w (k) k
. Using these operators, one immediately obtains the following proposition linking the heuristic structured shrinkage and the proximity operators from Section III-A. Proposition 3. Let S be the shrinkage operator of the WG-Lasso (4), WE-Lasso (5) or PE-Lasso [START_REF] Gribonval | Sparse representations in unions of bases[END_REF] and Ω the regularizer of the G-Lasso, E-Lasso and GE-Lasso, respectively (see Prop. 1). Let E be the expansion operator [START_REF] Kowalski | Sparsity and persistence: mixed norms provide simple signals models with dependent coefficients[END_REF] and D its left inverse [START_REF] Siedenburg | Structured sparsity for audio signals[END_REF]. Then

S λ = D • prox λΩ • E
Proof: For the sake of brevity, we give the proof for the WG-Lasso, i.e. Ω = • 21 . The proofs for WE-Lasso and PE-Lasso are similar.

Thanks to the introduction of the expanded operator E in Definition 4, we have for α ∈ R N and for a given neighborhood N on its indices:

N k=1 ∈N (k) w (k) |α | 2 = Eα 21 .
Then, z = prox λΩ (Eα) is given coordinatewise by:

∀ ∈ N (k), z k = w (k) α k     1 - λ k ∈N (k) w (k) k |α k | 2     + .
Therefore, by Definition (8) of D the claim follows.

Having established the link between social shrinkage and proximity operators, we can construct various algorithms to deal with the problem of "social sparsity".

C. Algorithms for social sparsity

We proceed by introducing heuristic algorithms, based on popular algorithms presented in Section III, in order to embed the previously introduced "social-shrinkage" operators. We then derive a more conventional convex approach thanks to the previously introduced expansion operator, and compare the advantages and shortcomings of the different algorithms.

1) ISTA with social sparsity operator: A natural question is how these operators behave if they are used inside iterative thresholding algorithms. Algorithm 3 rewrites ISTA with a given shrinkage operator S.

Algorithm 3: ISTA with heuristic shrinkage Initialization:

α (0) ∈ C N , k = 1, γ = ΦΦ * repeat α (k) = S λ/γ α (k-1) + 1 γ Φ * (y -Φα (k-1) ) ; k = k + 1; until convergence;
As the shrinkage operators S defined in Equations ( 4), ( 5) and ( 6) are not even non-expansive, the convergence study of Algorithm 3 is difficult and remains an open problem. However, experiments show a very good behavior of Algorithm 3 with any left inverse of E. Our observations are specified in the following Conjecture 1. Let S be the shrinkage operator of the WG-Lasso (4), WE-Lasso (5) or PE-Lasso (6), and set γ = ΦΦ * . Let us introduce the operator

T (α) = S λ/γ α + 1 γ Φ * (y -Φα) . (9)
Then the sequence {α k }, generated by Algorithm 3, converges to a fixed point of T .

Moreover, we have also used the same shrinkage operators with FISTA, and have observed the same accelerating effect on the speed of convergence compared to the switch from ISTA to FISTA in the classic convex case.

In the next subsection, we conceptually link the heuristic ISTA with the optimization of a convex functional.

2) Neighborhood as a convex prior: Thanks to the expansion operator E, we can introduce new convex priors which are closely related to our shrinkages, which we denote as cvx-*.

Definition 5 (Social Sparsity Convex Regularizers). Let α ∈ C N and let E be the expansion operator [START_REF] Kowalski | Sparsity and persistence: mixed norms provide simple signals models with dependent coefficients[END_REF].

cvx-Windowed-Group-Lasso:

Ω wgl (α) = N k=1 ∈N (k) w (k) |α | 2 = Eα 21 ( 10
)
cvx-Windowed-Elitist-Lasso:

Ω wel (α) = N k=1   ∈N (k) w (k) |α |   2 = Eα 2 12 ( 11
)
cvx-Persistent-Elitist-Lasso:

Ω pel (α) = |Im| m=1   |Ig| g=1 ∈N (g,m) w (g,m) |α | 2   2 = Eα 2 212 (12)
A natural convex functional is then

F (α) = 1 2 y -Φα 2 + λΩ(α) , (13)
where Ω is one of the convex penalty defined above, and one can look for α = argmin

α∈C N F (α) .
Such an approach was also proposed to deal with "overlapping" groups in [START_REF] Peyré | Group sparsity with overlapping partition functions[END_REF]. Moreover, if all the weights in E are equal, then we found the mixed norms with overlaps studied in [START_REF] Bayram | Mixed norms with overlapping groups as signal priors[END_REF]. Notice that the operator E appears in the penalty, and can then be thought of as an analysis prior. Using the results discussed in [START_REF] Elad | Analysis versus synthesis in signal priors[END_REF], we can reformulate it as a constrained synthesis problem:

α = E T argmin u,s.t.u=EE T u y -ΦE T u 2 + λ u *
where * is the corresponding (possibly squared) norm used to define the penalty Ω (say

Ω wgl (α) = Eα * = Eα 21 ). Interestingly, as u = EE T u ⇒ Du = E T u, we have α = E T argmin u,s.t.u=EE T u F E (u) = D argmin u,s.t.u=EE T u F D (u) ,
with the two following functionals:

F E (u) = y -ΦE T u 2 + λ u * ( 14
)
and

F D (u) = y -ΦDu 2 + λ u * . ( 15
)
The functional [START_REF] Tropp | Just relax: Convex programming methods for identifying sparse signals[END_REF], which corresponds to a pure synthesis approach, is actually exactly the problem of the latent-Group-Lasso [START_REF] Jacob | Group lasso with overlap and graph lasso[END_REF], [START_REF] Obozinski | Group lasso with overlaps: the latent group lasso approach[END_REF].

Seeking an estimate of α as a minimizer of F , it is possible to apply an algorithm as the one proposed in [START_REF] Chaux | Nested iterative algorithms for convex constrained image recovery problems[END_REF], where the proximity operator of the sum of two convex functions is derived from a Douglas Rachford Algorithm. We present such an algorithm with the "ISTA" framework in Algorithm 4, but it can be embedded in FISTA instead. Other approaches such as augmented Lagrangian can also be used (see [START_REF] Peyré | Group sparsity with overlapping partition functions[END_REF]).

Algorithm 4: Proximal algorithm to minimize F [START_REF] Osborne | On the lasso and its dual[END_REF].

Initialization: α (0) ∈ C N , k = 1, γ = ΦΦ * repeat -ISTA loop- α k+1/2 = α (k) + 1 γ Φ * (y -Φα); v = Eα k+1/2 ; repeat -Douglas-Rachford loop- u = EE T ( v+Ey 2 ); v = v + prox λ γ . * (2u -v) -u until convergence; α k+1 = E T u; k = k + 1; until convergence;
Coming back to ISTA with social-shrinkage operators, Algorithm 3, we can rewrite the main iteration as

S λ γ (α + 1 γ Φ * (y -Φα)) = D argmin u F E (u, Eα) + γ 2 u -Eα 2 .
where F E (u, Eα) is the linearization of F E in Eα:

F E (u, Eα) = 1 2 y-Φα 2 + EΦ * (y-Φα), u-Eα + u * .
Moreover, using a latent variable z such that α = Dz, due to the bi-orthogonality of ED, the main iteration of Algorithm 3 becomes

z (k) = ED prox λ γ . * z(k-1) α k = Dz k where z(k-1) = z (k-1) + E γ Φ * (y -ΦE T z (k-1) )
This can be seen as a the gradient-proximal step followed by an oblique projection. This remark further leads to the application of the natural left inverse E T instead of D in Proposition 3. We thus obtain a new "WG-Lasso-like" shrinkage operator, the orth-WG-Lasso:

S λ (α) : C N → C N α → α
where for all k ,

α k = α k j w (j) k     1 - λ j ∈N (j) w (j) j |α j | 2     + . (16)
One can see in [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF] that in this case, a coefficient will be set to zero only if all the coefficients belonging to its neighborhood are also set to zero. In this case, Algorithm 3 can be seen as the composition of a proximity operator and an orthogonal projection:

z (k) = EE T prox λ γ . * z(k-1) (17)
α k = E T z k where z(k-1) = z (k-1) + E γ Φ * (y -ΦE T z (k-1) )
As EE T is an orthogonal projection, this algorithm converges to a fixed point by applying [47, Theorem 6.3 and Corollary 6.5].

In summary, the introduction of the social sparsity operators has led to various algorithms related to the minimization of [START_REF] Osborne | On the lasso and its dual[END_REF]. Additionally to Conjecture 1 on the convergence of ISTA in conjunction with the social sparsity operators, we remarked that the social sparsity operators are the composition of an oblique projection and a proximity operator, which makes it possible to instead use an orthogonal projection approach. Thirdly, we noted that ( 13) can be minimized directly using a Douglas-Rachford algorithm to compute the proximity operator of the corresponding regularizer Ω. Finally, we have established a link to the previously existing methods [START_REF] Jacob | Group lasso with overlap and graph lasso[END_REF], [START_REF] Bayram | Mixed norms with overlapping groups as signal priors[END_REF], [START_REF] Peyré | Group sparsity with overlapping partition functions[END_REF]. Let us stress that using the social sparsity operators (such as WG-Lasso or orth-WG-Lasso) in ISTA as proposed in Algorithm 3 enables to always work directly on the coefficients α without the need of the latent variables. Indeed, an obvious advantage of the WG-Lasso and orth-WG-Lasso over cvx-WG-Lasso and the latent-Group-Lasso is their computational speed. WG-Lasso can be computed in O(N K) operations where N is the number of coefficients, and K the size of the neighborhood. orth-WG-Lasso has a similar complexity in O(2N K) while cvx-WG-Lasso must be solved by convex optimization. Moreover, both cvx-WG-Lasso and the latent-Group-Lasso have a fingerprint memory proportional to N K, while their social structured sparse operator WG-Lasso and orth-WG-Lasso have a fingerprint memory proportional to N , independently of the size of the neighborhood.

V. SOCIAL SPARSITY IN PRACTICE

While the idea of social sparsity was motivated from the stance of time-frequency analysis in the introduction, it can be in fact employed with any type of dictionary. Here, we focus on time-frequency and wavelet-dictionaries and evaluate the developed concepts with respect to audio and image denoising tasks. Although we formally proposed a variety of different shrinkage operators above, their practical exploration will stay confined to the WG-Lasso for the sake of brevity. For applications using other social sparse operators, see [START_REF] Siedenburg | Structured sparsity for audio signals[END_REF], [START_REF] Kowalski | Beyond the narrowband approximation: Wideband convex methods for under-determined reverberant audio source separation[END_REF], [START_REF] Gramfort | Improving m/eeg source localization with an inter-condition sparse prior[END_REF].

The following numerical evaluation proceeds in three steps. Firstly, the behavior of the WG-Lasso (4) and its counterparts cvx-WGL [START_REF] Jacob | Group lasso with overlap and graph lasso[END_REF], orth-WGL ( 16) is characterized by experiments in significance map estimation and denoising employing synthetic signals and a MDCT-dictionary. In order to set our results into context, we additionally include both the basic Lasso and the latent-Group-Lasso in evaluations. Testing for real-life audio signals, it is secondly argued that WGL is a valuable alternative to the state of the art in audio denoising in conjunction with Gabor dictionaries. Finally, it is suggested how to use the social sparse approach with waveletdictionaries for image denoising.

Concerning the choice of weights, the necessary condition j w (j) i = 1 on the weights in order to have the isometrical property and the condition i w

(j) i = 1
given in the definition of the neighborhood are of course totally compatible. The simplest case is when each coefficient is repeated the same number of times, say K, and then the non zero weights are equal to 1 K . When a "sliding" window is used, the condition is obviously satisfied. Such a window also bears the advantage that the corresponding sums in the persistent shrinkage operators can be computed by fast convolution algorithms. However, it can be interesting to have an asymmetric or a smoother window. A more detailed link between (audio) signal characteristics and optimal neighborhood choice is given in [START_REF] Siedenburg | Audio denoising by generalized timefrequency thresholding[END_REF]. Here, we rather stick with basic neighborhood shapes in order to clearly present the underlying principles.

Finally, let us note that for all the experiments, we chose to initialize the algorithms with the null vector. We interestingly observed that WG-Lasso and orth-WG-Lasso was scarcely sensitive to the choice of the initialization: we always obtained the same results, independent of the particular initialization.

A MatLab toolbox available at http://homepage.univie.ac.at/monika.doerfler/StrucAudio.html provides most of the social shrinkage operators and corresponding algorithms for audio denoising.

A. Time-Frequency Dictionaries

Time-frequency dictionaries as Gabor frames (a.k.a. the short-time Fourier transform) or the MDCT are extensively used in a variety of audio-processing tasks. In order to show the relevance of the social sparsity approach, we perform two kinds of experiments. First, we simulate a signal in order to show the ability of our approach to accurately recover its significance map (i.e. the set of non-zero coefficients). Then, we compare several approaches for a standard denoising problem on real audio signals.

1) Simulations in the orthogonal basis case: Let us assume that {ϕ (k) } k=1,...,N is a MDCT basis. The following experiment uses such an orthonormal basis with window lengths of 2048 samples. The time-persistent neighborhoods are constructed by setting for any time-frequency index k = (g, m), N (k) = N (g, m) = {(g -2, m), . . . , (g, m), . . . , (g + 2, m)} with g referring to time indices, i.e. each neighborhood comprises two coefficients before and after the centered one.

Here, we consider signals of the form y = k∈∆ x k ϕ k + b where b is an additive Gaussian noise, and ∆ is a structured sparse significance map. The latter is generated using fixed frequency Markov chains as introduced in [START_REF] Molla | A hybrid scheme for encoding audio signal using hidden markov models of waveforms[END_REF], drawing the synthesis coefficients x k from a standard normal distribution. An example of such a map is displayed in Fig. 4. This produces an overall signal to noise ratio of about 5 dB. We first compare the ability of various approaches (Lasso, WG-Lasso, orth-WG-Lasso, latent-Group-Lasso and cvx-WG-Lasso) to recover the significance map ∆. For such a task, we use Type 1 and Type 2 errors defined in the following.

Type 1:

π 1 = P{(t, f ) / ∈ ∆ | (t, f ) ∈ ∆} ; Type 2: π 2 = P{(t, f ) ∈ ∆ | (t, f ) / ∈ ∆}.
where ∆ is the estimated significance map. In other words, Type 1 error refers to the number of false positives, Type 2 error to the number of false-negatives. Fig. 5 depicts the two error types as functions of the estimated significance map size. Clearly, the three structured estimators WG-Lasso, cvx-WG-Lasso and orth-WG-Lasso outperform the non-structured Lasso and the latent-Group-Lasso. While the behavior of cvx-WG-Lasso and orth-WG-Lasso seem to be almost indistinguishable, WG-Lasso appears to perform slightly worse regarding type one errors in a certain sparsity range. However, it exhibits behavior very similar to the two minimizationfunctional-based estimators for Type 2 errors. Fig. 6 shows the corresponding denoising results measured in SNR (dB). We choose to display evolution of the SNR versus the number of non-zeros coefficient, and versus the hyperparameter λ. While the WG-Lasso achieves significantly higher SNR than the plain Lasso, its convex counterpart, cvx-WG-Lasso performs slightly better, although only for much higher number of non-zero coefficients. In terms of SNR there does not seem to be a difference between the orth-WG-Lasso and the WG-Lasso, that the WG-Lasso achieves the same SNR with fewer coefficients. In conclusion, the experiments using signals generated from structured significance maps demonstrate that the WG-Lasso behaves not identically, but quite similar to its convex and orthonormal counterparts. It thus appears as an efficient alternative to these operators, tractable for many real-life applications.

In light of Fig. 7, it is visible that the cardinality of the social sparsity maps presents a fast transition with respect to hyperparameter λ, compared to the Lasso approach. And even for the latent-Group-Lasso, the size of the estimated significance map starts to decrease for smaller λ. Moreover, as shown on the top of Fig. 6, the SNR of the three socialsparsity approaches reaches its maximum quickly and then decreases slowly. A practical implication of these remarks is that the hyperparameter tuning for social sparsity operators might be more straight-forward than in the Lasso case, since a fairly good SNR can be reached by choosing λ within the transition phase, which shows a sharp and thus more determined behaviour.

The performances of the latent-Group-Lasso may appear slightly disappointing here. However, we must insist that in the proposed experiments, we used a sliding window in time to construct the neighborhood. In this situation, the discarding versus selecting problem, which was the main motivation of the latent-group-lasso, is less important. Indeed, in this particular situation, configurations obtained by discarding groups or selecting them can be very close.

2) Real signals and the overcomplete case: We proceed to demonstrate the benefits of the social sparse approach for audio denoising, using "real-life" signals and an overcomplete Gabor-dictionary. The latter dictionary was also employed by the state of the art in audio denoising, namely the Block-Thresholding algorithm [START_REF] Yu | Audio denoising by time-frequency block thresholding[END_REF]. To compare these approaches, we use WG-Lasso with a neighborhood extending over time with 4 coefficients before and after the center coefficient and employ a tight Gabor-frame with Hann-window of length 1024 samples and overlap 4. The chosen test signal is a 6-sec excerpt of a Jazz-quintet producing a complex mixture of drums, double-bass, piano, saxophone and trumpet. In [START_REF] Yu | Audio denoising by time-frequency block thresholding[END_REF], the variance of the noise is supposed to be known, but we choose here to use its value as a parameter of the method. Then, all algorithms depend on only one parameter, which can be tuned according to the variance of the noise.

Fig. 8 shows the corresponding denoising results measured in SNR as functions of the hyperparameter λ for groundnoise levels of 0 and 20 dB SNR. While the Lasso performs constantly worse, Block-Thresholding performs better than WG-Lasso for the 0 dB noise level, and vice versa for the 20

neighbors

Lasso WG-Lasso orthWG-Lasso cvxWG-Lasso Latent-G-Lasso Fig. 7. Evolution of the cardinality of the estimated map dB case. Let us note that WG-Lasso, orth-WG-Lasso and cvx-WG-Lasso perform almost identically. The latent-Group-Lasso performs a bit worse than the other structured methods. We also have noticed that the dependence between the size of the maps and the hyperparameter λ is similar to our observations in the simulated case. In particular, WG-Lasso reaches its maximum for sparser significance maps than the orth-WG-Lasso and cvx-Lasso.

For the same signal and noise level of 20 dB, Fig. 9 compares different sizes of neighborhoods (each extending in time). It seems clear that the algorithm is relatively robust w.r.t. the choice of the neighborhood: there is a significant increase in performance from the Lasso to WGL with 2 coefficients in time, before and after the center, but further enlarging the neighborhood does not change results dramatically.

It has to be noted that in terms of SNR, block-thresholding seems to be favorable for some other signals and noise levels we tested. On the contrary, the social sparse approach Fig. 8. SNR vs hyperparameter λ for the six operators Lasso, WG-Lasso, orth-WG-Lasso, cvx-WG-Lasso, latent-G-Lasso and Block-Thresholding using a 6 sec complex audio signal containing drums, double-bass, piano, saxophone and trumpet. bears many important advantages over block-thresholding: It is computationally much more efficient (in our setting around a factor 2, obviously depending on the number of iterations) and seems to provide perceptually preferable results, cf. [START_REF] Siedenburg | Audio denoising by generalized timefrequency thresholding[END_REF]. It should also be noticed that no post-processing was executed here on the results given by the various *-Lasso approaches, and in particular, we did not perform any Wiener estimate contrary to the Block-Thresholding algorithm. Such a postprocessing can increase the SNR [START_REF] Yu | Audio denoising by time-frequency block thresholding[END_REF], but we choose to show the raw results of the *-Lasso.

From a computational point of view, cvx-WG-Lasso is very time-consuming and intractable in practice. Fig. 10 depicts the evolution of the value of the functional (13) over the number of iterations for cvx-WG-Lasso, and the FISTA and ISTA versions of the orth-WG-Lasso and WG-Lasso for the 20 dB case and λ 10 -3 . cvx-WG-Lasso was implemented with ISTA with only one iteration of the Douglas-Rachford inner loop: this strategy appeared to be the most efficient to obtain our results; in particular, FISTA was divergent in practice because of its sensibility to the error done to approximate the proximity operator with the Douglas-Rachford inner loop. We close the practical investigation of audio denoising with a comparison of the time-frequency maps given by the Lasso, WG-Lasso and orth-WG-Lasso in the 20 dB case for λ 10 -3 . One can observe in Fig. 11 very structured timefrequency maps for WG-Lasso and orth-WG-Lasso compared to the Lasso, and in particular their ability to keep high frequency coefficients. Moreover, it can be seen, that sparsity is more expressed in the map obtained with WG-Lasso; this observation confirms the results shown Fig. 10, namely, that WG-Lasso promotes sparser representations than orth-WG-Lasso.

B. Wavelet Dictionaries

While the proposed approach might be particularly intuitive for exploiting persistence in time-frequency representations, it turns out to be similarly promising in conjunction with wavelet dictionaries for applications in image processing, for instance.

Here, structures such as sharp edges are sparsely represented, but at the same time exhibit persistence properties along the wavelet tree: if a given coefficient is active, it is highly likely that its respective "father" is so, as well. We hence explore the usage of an asymmetric neighborhood system which emphasizes this directed relation between "father and son", as depicted in Fig. 12.

Notice that the idea of taking into account the persistence of the wavelet coefficients along the tree is not new. Several works propose to modelize this case of "structured sparsity" such as [START_REF] Baraniuk | Modelbased compressive sensing[END_REF], [START_REF] Huang | Learning with structured sparsity[END_REF], [START_REF] Shapiro | Embedded image coding using zerotrees of wavelet coefficients[END_REF].

Initial experiments on image denoising were conducted using the well-known Lena-image to which a Gaussian white noise was added, yielding a peak signal to noise ratio (PSNR) of 20 dB. Fig. 13 compares the performance of the WGLoperator using the described neighborhood system with the plain Lasso estimate, depicting PSNR of the reconstruction as function of the number of non-zero coefficients. Clearly, WG-Lasso outperforms the Lasso leading to a gain in SNR of about 1 dB.

VI. CONCLUSION Social sparsity operators allow to shrink dictionary coefficients with respect to their weighted neighborhoods. In summary, three different but related approaches were presented: While the convergence of the last two approaches can be proven, the convergence of the oblique projected proximal algorithm remains an open problem. Moreover, the algorithm can be accelerated with FISTA as for classical convex optimization. These approaches are complemented by the latent-Group-Lasso which corresponds to the unconstrained synthesis version of the proposed convex functional. In particular for WG-Lasso, various experiments on both simulated and real signals demonstrate a very good behavior in denoising tasks: its performance is comparable to the state of the art Block-Thresholding algorithm but it is considerably faster.

Further studies will be devoted to two aspects. On the one hand, a theoretical study of the oblique-projected proximal algorithm must be conducted. On the other hand, we plan to build a practical audio restoration algorithm, using social sparsity operators as the WG-Lasso with hybrid decompositions [START_REF] Daudet | Hybrid representations for audiophonic signal encoding[END_REF] and a few instinctive, or ideally none, hyperparameters.

Fig. 1 .

 1 Fig. 1. Time-frequency images. Top: signal samples, bottom-left: representation adapted to transients. Bottom-right, representation adapted to tonals.

  defined on I |I| , such that w (g,m)g,m ≥ 0 for all (g, m) ∈ I, m ∈ I m , and w

Fig. 4 .

 4 Fig. 4. Time-frequency significance map with 9% non-zero coefficients.

Fig. 5 .

 5 Fig. 5. Top: type 1 error. Bottom: type 2 error.

Fig. 6 .λ

 6 Fig. 6. Top: snr vs non zeros coeff. Bottom: snr vs hyperparameter λ

Fig. 9 .

 9 Fig. 9. Comparison of different neighborhood sizes for the WGL operator.Each neighborhood extends in time with 0 (Lasso case), 2, 4 and 8 coefficients before and after the center index.

Fig. 10 .

 10 Fig. 10. Functional (13) value with respect to the time for the five algorithms used.

Fig. 11 .Fig. 12 .

 1112 Fig.11. Time-Frequency maps. From top to bottom: original signal, noisy signal, Lasso, WG-Lasso, orth-WG-Lasso

Fig. 13 .

 13 Fig. 13. Top: snr vs non zeros coeff. Bottom: snr vs hyperparameter λ

ACKNOWLEDGMENT

The authors would like to warmly thank Bruno Torrésani for fruitful discussions and his previous advice. The authors further express their gratitude to the anonymous reviewers for their constructive and valuable remarks.

This work was supported by the Austrian Science Fund (FWF) : T384-N13 and the WWTF project Audio-Miner (MA09-024).