phytopathogenic fungi is of utmost importance as it may open new avenues to combat diseases. A strong host specialization is commonly observed for biotrophic and hemi-biotrophic fungal species or for necrotrophic fungi with a narrow host range, whereas necrotrophic fungi with broad host range are considered generalists [START_REF] Liang | Mechanisms of Broad Host Range Necrotrophic Pathogenesis in Sclerotinia sclerotiorum[END_REF][START_REF] Newman | The Evolutionary and Molecular Features of Broad Host-Range Necrotrophy in Plant Pathogenic Fungi[END_REF]. However, some degrees of specialization towards given hosts have been reported in generalist fungi and the underlying mechanisms remain to be determined.

Botrytis cinerea is a polyphagous necrotrophic phytopathogen with a particularly wide host range and it is notably responsible for grey mould disease on many fruits, such as tomato and grapevine. Because of its importance as a plant pathogen, its relatively small genome size and its taxonomical position, it has been targeted for early genome sequencing and a first reference genome was provided in 2011 [START_REF] Amselem | Genomic Analysis of the Necrotrophic Fungal Pathogens Sclerotinia sclerotiorum and Botrytis cinerea[END_REF]. Other genomes were subsequently sequenced for other strains, and most importantly a gapless assembled version of the initial reference genome B05.10 was provided to the community [START_REF] Van Kan | A gapless genome sequence of the fungus Botrytis cinerea[END_REF]). This genomic resource has supported advances in various aspects of the biology of B. cinerea such as the production of specialized metabolites, which plays an important role in host-plant colonization, or more recently in the production of small RNAs which interfere with the host immune system, representing a new class of non-proteinaceous virulence effectors [START_REF] Dalmais | The Botrytis cinerea phytotoxin botcinic acid requires two polyketide synthases for production and has a redundant role in virulence with botrydial[END_REF][START_REF] Weiberg | Fungal Small RNAs Suppress Plant Immunity by Hijacking Host RNA Interference Pathways[END_REF]).

In the present study, [START_REF] Simon | Botrytis cinerea strains infecting grapevine and tomato display contrasted repertoires of accessory chromosomes, transposons and small RNAs[END_REF] use PacBio long-read sequencing for Sl3 and Vv3 strains, which represent genetic clusters in B. cinerea populations found on tomato and grapevine. The authors combined these complete and high-quality genome assemblies with the B05.10 reference genome and population sequencing data to perform a comparative genomic analysis of specialization towards the two host plants. Transposable elements generate genomic diversity due to their mobile and repetitive nature and they are of utmost importance in the evolution of fungi as they deeply reshape the genomic landscape [START_REF] Lorrain | Transposable Elements in Fungi: Coevolution With the Host Genome Shapes, Genome Architecture, Plasticity and Adaptation[END_REF]. Accessory chromosomes are also known drivers of adaptation in fungi [START_REF] Möller | Evolution and genome architecture in fungal plant pathogens[END_REF]. Here, the authors identify several genomic features such as the presence of different sets of accessory chromosomes, the presence of differentiated repertoires of transposable elements, as well as related small RNAs in the tomato and grapevine populations, all of which may be involved in host specialization. Whereas core chromosomes are highly syntenic between strains, an accessory chromosome validated by pulse-field electrophoresis is specific of the strains isolated from grapevine. Particularly, they show that two particular retrotransposons are discriminant between the strains and that they allow the production of small RNAs that may act as effectors. The discriminant accessory chromosome of the Vv3 strain harbors one of the unraveled retrotransposons as well as new genes of yet unidentified function.

I recommend this article because it perfectly illustrates how efforts put into generating reference genomic sequences of higher quality can lead to new discoveries and allow to build strong hypotheses about biology and evolution in fungi. Also, the study combines an up-to-date genomics approach with a classical methodology such as pulse-field electrophoresis to validate the presence of accessory chromosomes. A major input of this investigation of the genomic determinants of B. cinerea is that it provides solid hints for further analysis of host-specialization at the population level in a broad-scale phytopathogenic fungus.

After revisions, all comments and suggestions of both reviewers were addressed. I consider this manuscript to be suitable for publication with PCI recommendation. I have no further comments.

Reviewed by Thorsten Langner, 23 Sep 2022

The authors have addressed all my previous comments and I have no additional comments.

I also want to thank the authors for including the CHEF gel analysis (suggested by reviewer 1) in their revision, which is a nice confirmation and adds value to the genomics analysis.

Decision by Sebastien Duplessis, posted 24 May 2022

Dear authors, You will find here two complementary reviews of your manuscript. I concur with both reviewers to acknowledge the quality of the work, analyses and interpretations done; also, the text reads very well and only a few edits are suggested.

As you will see, both reviewers provide suggestions to support further some of your analyses or claims (or eventually to revisit and/or tone down some of said claims).

During my first read, I had questions relating to reviewer 1's comments about the use of the GC% signature. Then after another round, I found the comment of reviewer 2 also very pertinent regarding how the age of TE may affect the quality of mapping, and indeed more precisions about the QC you used would be welcome. Finally, both reviewers propose means for managing their comments which will be helpful to reach a manuscript that could be recommended. I am interested in your answers to the first main comment from reviewer 2. As for the first comment from reviewer 1, I do not know how easy this can be routinely handled in the authors' laboratory? I am looking forward to reading a revised version of this manuscript and your answers to the constructive comments from these reviewers.

With my best regards.

Sebastien

Reviewed by Cecile Lorrain, 13 Apr 2022

Accessory chromosomes in microbes are well-known drivers of evolution and rapid adaptation in many species. Botrytis cinerea strains infecting grapevine and tomato display contrasted repertoires of accessory chromosomes, transposons and small RNAs. The authors have identified new accessory chromosomes in this species, highlighting the importance of high quality sequencing to unravel fungal evolution and biology.

The manuscript is clearly written and the results are well-supported by the produced genomic data and in depth analyses.

I have two main recommendations to improve the manuscript: 1-To further support the presence of accessory chromosomes in the newly sequenced strains, the authors could perform a pulsed-field gel electrophoresis. This potentially would compensate for the scarcity of telomeric repeats in some chromosomes. 2-RIP and GC content: even though RIPped sequenced have low GC content, GC content alone is not the best signature for RIP, since many species exhibit TEs with low %GC but do not have RIP. It can reflect the tendency of TEs to accumulate mutations over time. I suggest the authors, if they want to emphasize the presence of RIP signatures on TEs, to run The RIPper (https://theripper.hawk.rocks/#/home). This userfriendly tool search for RIP indexes in whole-genome or TEs sequences. Also, authors could search for the presence of DNMTs (especially dim2 and RID) genes which are know to be involved in RIP in fungi.

Minor:

-In line 31-33, the authors state that generalists could actually be represented by different co-existing populations specialised in infecting different host species. It would be nice to have the demonstration that it is the case for B. cinerea, just right after the scenario statement. The demonstration comes only from lines 49-61. I would move this part line 36 and finish the paragraph with the different gene catalogues. -L421-423: remove sentence "Both inactive and active TEs can additionally generate genomic rearrangements by homologous recombination as discussed below."

Reviewed by Thorsten Langner, 07 Apr 2022

The study "Botrytis cinerea strains infecting grapevine and tomato display contrasted repertoires of accessory chromosomes, transposons and small RNAs" describes the genomic features of three genetically diverse, host-adapted lineages of B. cinerea, including a novel accessory chromosome in the grapevine infecting G1 lineage. The authors further show that certain classes of transposable elements are enriched or specific to this lineage and suggest that transposon-derived small RNAs might act as lineage specific effectors. While transposon-derived siRNAs and their potential role in host specificity of B. cinerea have already been described in the literature, the novelty in this study is to extend the analysis to larger numbers of isolates which allows conclusions on the population scale and representative chromosome level assemblies, which allowed to associate certain TE classes to specific chromosomal locations including a novel accessory chromosome. Overall, this study is well done, and most conclusions are supported by the data that is presented.

I only have a few comments that I suggest should be addressed: Page 15, line 304:

Here, the authors state that predominantly TEs with high GC content produce small RNAs and this appears again in the discussion, but the data is not shown. In my opinion this is an interesting finding which should be supported by data. Otherwise, it is hard to tell how clear the correlation between GC content and small RNA expression is, especially given that the majority of TEs appears to be in the >40%GC category (Figure S11). In addition, the spatial distribution of siRNA-producing TEs in the chromosome level assemblies could add additional value. I suggest to either show this type of analysis or to remove statements and conclusions that are not supported by the results. I also wonder if the age of TEs and extent of RIP influences the mapping quality of TE derived small RNAs to the consensus and the filtering/masking. This could potentially have an important impact on the overall conclusions of the small RNA producing TEs. Could the authors please comment which quality controls they have done? In the methods section it says, "Quality controls have been done, including PCA…", however it is hard to tell if any of these controls address the impact of mapping/filtering (e.g. how many reads that map to TEs were discarded during the filtering process? Among those reads, is there a bias that could influence conclusions about GC richness/small RNA expression?). Page 17, line 348 onwards:

The PCR results and the mapping results are somewhat inconsistent for some isolates. Mapping shows presence of gypsy6 across all tested G1 isolates (Vv1,Vv3,Vv5,Vv14) but PCR fails to detect gypsy6 in these strains. I think the PCR results should thus be interpreted with caution, as presence/absence analysis by PCR can sometimes be problematic. This discrepancy should at least be discussed. Additionally, there are only few details regarding the PCR assay in the paper. It would help if the authors could provide the template sequences used to design the primers and variation of TEs (e.g. alignment of identified TEs similar to what they have done in Figure S8 for the Boty TE, with focus on the primer binding sites). Could variation of TE sequences contribute to absence of PCR products? This could explain the differences between mapping and PCR detection.

Minor comments: Page 12, line 213: "Fifteen consensus were previously identified" should probably read "…consensus sequences…"? Page 19, lines 388/390: These two sentences read a bit contradictory. Maybe it would be worth rephrasing this to point out the lineage specificity of the acc. Chr BCIN19 as a clear difference to 17/18 for which lineage specificity was not supported.

Page 15, lines 291 and following"…producing the higher amount of small RNAs…" should be changed to "…highest amount.."

Figure S3 :

 S3 Figure S3: Colors of lines and dots should be explained in the figure legend. Similarly, solid and dashed lines should be explained. Page 11, line 202: The abbreviation "IPR domains" should be spelled out.

Evaluation round #1 DOI or URL of the preprint: https://doi.org/10.1101/2022.03.07.483234 Version of the preprint: 2 Author's Reply, 13 Sep 2022 Download author's replyDownload tracked changes file

Conflict of interest:

The recommender in charge of the evaluation of the article and the reviewers declared that they have no conflict of interest (as defined in the code of conduct of PCI) with the authors or with the content of the article.

Reviews

Toggle reviews

Reviewed by Cecile Lorrain, 23 Sep 2022

The authors made a great effort to perform complementary experiments to support the presence of new accessory chromosomes in B. cinerea.


Recommendation

A novel approach for engineering biological systems by interfacing computer science with synthetic biology [START_REF] Green | Toehold Switches: De-Novo-Designed Regulators of Gene Expression[END_REF]. These are single-stranded RNA molecules harboring the necessary elements for translation initiation of the downstream gene: a ribosome-binding site and a start codon. Conformation change of toehold switches is triggered by an RNA molecule, which enables translation.

To exploit the most out of toehold switches, automation of their design would be highly advantageous. Cisneros and colleagues [START_REF] Cisneros | Toeholder: a Software for Automated Design and In Silico Validation of Toehold Riboswitches[END_REF] developed a tool, "Toeholder", that automates the design of toehold switches and performs in silico tests to select switch candidates for a target gene. Toeholder is an open-source tool that provides a comprehensive and automated workflow for the design of toehold switches. While web tools have been developed for designing toehold switches [START_REF] To | A comprehensive web tool for toehold switch design[END_REF], Toeholder represents an intriguing approach to engineering biological systems by coupling synthetic biology with computational biology. Using molecular dynamics simulations, it identified the positions in the toehold switch where hydrogen bonds fluctuate the most. Identifying these regions holds great potential for modifications when refining the design of the riboswitches. To be effective, toehold switches should provide a strong ON signal and a weak OFF signal in the presence or the absence of a target, respectively. Toeholder nicely ranks the candidate toehold switches based on experimental evidence that correlates with toehold performance (based on good ON/OFF ratios).

Riboswitches are highly appealing for a broad range of applications, including pharmaceutical and medical purposes [START_REF] Blount | Riboswitches as antibacterial drug targets[END_REF][START_REF] Giarimoglou | A Riboswitch-Driven Era of New Antibacterials[END_REF][START_REF] Tickner | Riboswitches for Controlled Expression of Therapeutic Transgenes Delivered by Adeno-Associated Viral Vectors[END_REF], thanks to their adaptability and inexpensiveness. The Toeholder tool developed by Cisneros and colleagues is expected to promote the implementation of toehold switches into these various applications. Melamed,posted 02 Dec 2022,validated 05 Dec 2022 Dear François, Thank you for resubmitting your manuscript entitled "Toeholder: a Software for Automated Design and In Silico Validation of Toehold Riboswitches". You have successfully addressed all the comments from the reviewers. However, before we recommend on this manuscript there are minor revisions that are needed.

Decision by Sahar

-Figure 2: The text is smaller in comparison to the other figures. Please enlarge it.

-Please consider dividing the "4.2 Toeholder conception and validation" subtitle into two subtitles.

-7.Data availability: please add the DOIs of your data, scripts and code in this section.

-Please add a section "10. Supplementary material" with the DOI/URL to your supplementary files (Supplementary video 1). Thank you for the opportunity to consider your manuscript at PCI Genomics. The two reviewers found the work interesting but also raised some concerns. We would like to invite you to submit a revision if you can address the reviewers' key concerns, especially those raised by reviewer 1. The main comment of reviewer 1 is related to the interpretation of the in silico results. Please consider if you can add experimental data to support the method or alternatively revise the text so it will better represent the applicability of the method.

We hope that the comments below will prove constructive, and I would be happy to discuss any plans for a revision once you've had a chance to consider the points raised by the reviewers.

Best Regards, Sahar Sahar Melamed, PhD

Recommender at PCI Genomics

Reviewed by Wim Wranken, 18 May 2022

You developed a computational pipeline to design 'toehold' riboswitches for specific RNA trigger sequences. The pipeline predicts which toehold switch design adheres to the secondary structure of a known toehold switch, through a combination of RNA secondary structure prediction and subsequent free energy prediction of that structure to assess its stability. A further in silico validation of the method via molecular dynamics is included.

While the method is in itself well designed and likely very helpful in relation to toehold switch design, the interpretation of the in silico results is overly optimistic. Typically, in silico methods are very good at separating what might work from what likely does not work (in this case, a particular toehold switch), but here there is no assessment of how reliable your method is, as validated by experimental data. This is an essential component that is missing in your study: is there (independent) data available on toehold switches that are know to work, and is your approach able to detect/score those? Do you have any independent experimental data that illustrates that this method in fact works well (you mention the iGEM project A.D.N.did this use your approach, and if so how well did it work)?

In addition, RNA is a notoriously flexible molecule issue, how well can the silico RNA predictions that you are using account for that -do your 'free energy' calculations take entropy into account? What could go wrong in these calculations? These issues are not addressed -but should be.

Finally, your statements should always mention 'predicted' when this is where your information comes from, e.g. page 10, section 3.2, should say 'predicted secondary structure' -as this is what it is, there is no experimental validation. You should address these issues, or tone down your statements about the real-life applicability of your method, as at the moment it is impossible to assess whether your pipeline works in reality (or not).

Reviewed by anonymous reviewer, 10 Jul 2022

I found the preprint clear well written, with only a few typos and formatting issues (listed below). As a nonspecialist reviewer, there were two terms that I found difficult to understand and I recommend that the authors include a few words of explanation about each of them in the paper to make it more accessible to a broad readership: "orthogonality" and "overregard". I also found some sentences that sounded quite finalist, and recommend reformulating them to avoid this: "nature has explored many different regulatory mechanisms"; "capable of regulating transcription and translation to optimize the use of resources" (I suggest "capable of regulating transcription and translation, thereby optimizing the use of resources" that does not convey this finalist undertone).

Minor typos and formatting issues: 1) please put line numbers in your resubmitted preprint -it is tricky to provide feedback without them 2) in part 1.1., "RNA molecules, which typically" should be "RNA molecules that typically"

3) "have led to several different designs.-" please remove the unnecessary hyphen 4) "a ribosome binding site" -> "a ribosome-binding site" 5) in panel 3.2 of Figure 2, "cannonical" -> "canonical" 6) in part 3.1, "did not unwind which would lead" -> "did not unwind, which would have lead" 7) in part 4.1, "was stable in the conditions" -> "was stable under the conditions" 8) "with their complementary sequences fluctuates the most often during the simulation" -> "with their complementary sequences fluctuated most often during the simulation"

  of the preprint: https://doi.org/10.1101/2021.11.09.467922 Version of the preprint: 1 Author's Reply, 07 Nov 2022 Download author's reply Decision by Sahar Melamed, posted 13 Jul 2022 Dear Dr. Cisneros,

Conflict of interest:

The recommender in charge of the evaluation of the article and the reviewers declared that they have no conflict of interest (as defined in the code of conduct of PCI) with the authors or with the content of the article.

Author's Reply, 09 Dec 2022

Download author's replyDownload tracked changes file

Answer to reviewers (Round #2) : Dear François, Thank you for resubmitting your manuscript entitled "Toeholder: a Software for Automated Design and In Silico Validation of Toehold Riboswitches". You have successfully addressed all the comments from the reviewers. However, before we recommend on this manuscript there are minor revisions that are needed.

-Figure 2: The text is smaller in comparison to the other figures. Please enlarge it.

Response: Main text was standardized to 18pt in figure 2.

-Please consider dividing the "4.2 Toeholder conception and validation" subtitle into two subtitles.

Response: 4.2 was subdivided into 4.2 Toeholder conception and 4.3 Toeholder validation.

-7.Data availability: please add the DOIs of your data, scripts and code in this section.

Response: DOIs were added to the section.

-Please add a section "10. Supplementary material" with the DOI/URL to your supplementary files (Supplementary video 1).

Response: Section 10 was created and DOI was added for Supplementary video 1.

On behalf of all authors on this paper, thank you very much for you feedback and thorough review of this paper! We enjoyed the process of submitting to PCI, and look forward to future collaborations.

Francois and Angel


Matthieu Kowalski
email: kowalski@cmi.univ-mrs.fr

Sparse Regression Using Mixed Norms

Keywords: Sparse regression, Structured regression, Mixed norms, FOCUSS, Thresholded Landweber iterations

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, multilayered 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.

Introduction

Over the last few years, sparsity has emerged as a general principle for signal modeling. In a few words, whenever a signal may be represented sparsely, i.e. characterized by a small amount of data, many signal processing tasks become significantly easier. Among the successes of sparse methods, one may mention applications to signal coding and compression [START_REF] Daudet | Towards a hybrid audio coder[END_REF], denoising (Basis Pursuit Denoising and related techniques [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF]), source separation [START_REF] Févotte | Sparse regression with structured priors: Application to audio denoising[END_REF] and many others.

Most sparsity based approaches start by expanding signals on a given waveform family (basis, frame, dictionary, . . . ), and process the coefficients of the expansion individually. Therefore, an assumption on the coefficients independence is implicitly done, although the latter is generally too coarse a modeling. A good example is provided by the (sparse) time-frequency representations displayed on Figure 2 (Section 5), where significant coefficients are clearly organized in structured sets (vertical or horizontal lines). Such structures are clearly not accounted for when coefficients are treated individually.

On the one hand, we propose sparse expansion methods that explicitly introduce a notion of structured sparsity. On the other hand we combine this approach with multilayered signal expansion approaches, which aim at decomposing signals in sums of significantly different components (termed "layers") (see [START_REF] Berger | Removing noise from music using local trigonometric bases and wavelet packets[END_REF][START_REF] Daudet | Hybrid representations for audiophonic signal encoding[END_REF][START_REF] Daudet | Towards a hybrid audio coder[END_REF][START_REF] Starck | Image decomposition via the combination of sparse representation and a variational approach[END_REF]).

In this paper, structured sparsity is modeled by introducing a coupling between coefficients in the same structured set. Some probabilistic approaches have implemented this kind of structured modeling with success (see [START_REF] Févotte | Sparse regression with structured priors: Application to audio denoising[END_REF][START_REF] Kowalski | Random models for sparse signals expansion on unions of basis with application to audio signals[END_REF]). In the framework of variational formulations, such a coupling may be introduced by suitable regularization terms, that combine sparsity and persistence.

Such regularization terms have been considered by Fornasier and Rauhut [START_REF] Fornasier | Recovery algorithm for vector-valued data with joint sparsity constraints[END_REF] and Teschke and Ramlau [START_REF] Teschke | An iterative algorithm for nonlinear inverse problems with joint sparsity constraints in vector valued regimes and an application to color image inpainting[END_REF], under the name of joint sparsity: these authors have studied mixed norms p,1 , focusing on multichannel signals. Our approach is based on mixed norms, which may be introduced whenever signal expansions on doubly labeled families are considered1 :

s = i,j α i,j φ i,j ,
where {φ i,j } are the waveforms of a given basis or frame.

Considering the mixed norm p,q norm defined as

α p,q =    i   j |α i,j | p   q/p    1/q ,
we shall be mainly concerned with the regression problem

min α    s - i,j α i,j φ i,j 2 2
+ λ α q p,q    , with λ > 0 a fixed parameter. When {φ i,j } is a basis, we give practical estimates for the regression coefficients α i,j , obtained by generalized soft thresholding. These estimates are summarized in Theorem 3. When {φ} i,j is a frame, the latter estimates may be plugged in a Landweber iteration scheme to yield a minimizer of the corresponding functional. This former case is well adapted when the observation of the signal is noisy. In the case of a noiseless observation, we shall be interested by an exact reconstruction regression problem min α α q p,q such that s = i,j α i,j φ i,j .

We also show that the FOCal Underdetermined System Solver (FOCUSS) algorithm [START_REF] Rao | An affine scaling methodology for best basis selection[END_REF][START_REF] Cotter | Sparse solutions to linear inverse problems with multiple measurement vectors[END_REF] may be adapted to yield minimizers of that functional.

The extension to multilayered signal expansion exploits several doubly labeled families: in the case of two layers, one seeks expansions of the form

s = i,j α i,j φ i,j + k, β k, ψ k, ,
with prescribed sparsity and persistence assumptions on the coefficients sets α and β. In a variational formulation, we consider the following regression problem min

α,β    s - i,j α i,j φ i,j - k, β k, ψ k, 2 2
+ λ α q p,q + µ β q p ,q    .

The thresholded Landweber iterations are studied with this more general formulation, and a modification of the FOCUSS algorithm is provided if an exact reconstruction estimate is required.

The paper is organized as follows. Mixed norms are defined in Section 2, and we give an overview of how some mixed norms have been used in the literature. Section 3 uses the FOCUSS algorithm to minimize these norms subject to an equality constraint, and extends the algorithm for multilayered expansion. The noisy signal estimation problem is studied in Section 4: after a reminder on the corresponding regularized FOCUSS algorithm, we discuss the thresholded Landweber iteration used to minimize the functional. Section 5 gives a simple illustration of possible uses of the algorithms, in order to illustrate the relevance of mixed norms for easily modeling dependences between coefficients.

Mixed norms

This section recalls the definition of the weighted mixed norms we shall be concerned with and some useful properties. To our knowledge, the corresponding mixed norm spaces were introduced and studied in [START_REF] Benedek | The space l p with mixed norm[END_REF], and some main properties are summarized in [START_REF] Samarah | A Shur test for weighted mixed-norm spaces[END_REF].

We use the following notation. Let the vector x ∈ 2 (C), labeled using a double index, be such that x = (x 1 , . . . , x k , . . .) and for all k, x k = (x k,1 , . . . , x k, , . . .). This double index is purely conventional and is used to introduce some dependences between coefficients Example 1 For example, x can denote the coefficients of a time-frequency or a time-scale expansion of a signal. In this particular context, we shall denote by (k, ) the index, with k the time index and the frequency index. Then, x k, represents the coefficient at time k and frequency , the vector x k represents all the frequency coefficients at time k, and we denote by x ., the vector which contains all the time coefficients at frequency . Definition 1 Let w ∈ 2 (R) be such that for all k, , w k, > 0. Let p ≥ 1 and q ≥ 1. We call (weighted) mixed norm of x ∈ 2 (C), the norm w;p,q defined by

x w;p,q =   k w k, |x k, | p q/p   1/q . ( 1
)
The cases p = +∞ and q = +∞ can be obtained by replacing the corresponding norm by the supremum.

Let us stress that not all vectors in 2 (C) have finite mixed-norm. However, applications of mixed norms will consider signal in some specific functional spaces for which the mixed-norms will be finite. A short recall of such spaces is made at the end of this section.

The mixed norm w;p,q can be seen as a "composition" of the norms w;p and q :

x w;p,q = k x k q w;p

1/q = W ., |x ., | p 1/p q , (2)
where |x ., | p = (|x 1, | p , . . . , |x k, , . . . | p ), and where W ., = diag(w 1, , . . . , w k, , . . .), i.e W ., is the diagonal matrix with diagonal entries equal to the vector of weights (w 1, , . . . , w k, , . . .).

Remark 1

The mixed norms generalize the usual p norms. Indeed, if p = q: x w;p,p = x w;p .

Mixed norms explicitly introduce coupling between coefficients instead of the usual independence assumption behind the p norms. This point will be made more explicit in Section 4, with the Bayesian formulation of the regression problem. The coupling is strongly dependent of the choice of p and q. Indeed, if we consider a vector as sparse/concentrated if it contains a lot of values close to zero, minimising an p norm encourages sparsity for small values of p (p < 2) and diversity for large values (p ≥ 2). Thus, p are usually used as measures of diversity for small values of p (p < 2) and sparsity for large values (p ≥ 2) (see [START_REF] Rao | An affine scaling methodology for best basis selection[END_REF] and references therein for a more detailled discution about sparsity/diversity measures). Mixed norms allow one to mix those two concepts. Used as regularization terms in a regression context, they enforce some specific types of joint sparsity and diversity, as we shall see below.

In this framework, it is preferable to have to deal with a convex optimization problem in order to have guaranties of global optimability. Convexity is given by the following proposition Proposition 1 If p ≥ 1 and q ≥ 1 then the norm w;p,q is convex. The strict convexity is obtained for p > 1 and q > 1.

PROOF. This property is a consequence of the homogeneity of the norm and the triangle inequality.

Mixed norms make it possible to favor certain kind of structures we can find in signals. Classical properties of norms (and, in particular, convexity) allow us to use them in regression problems. The following subsection recalls some models already studied which use a mixed norm to group variables.

Mixed norms in the literature

Some specific instances of mixed norms are already used in various situations. This section presents functional spaces characterized by mixed norms, and statistical regression problems which use particular mixed norms.

Characterization of some functional spaces

First, let us recall a few examples of functional spaces that can be defined in terms of mixed norms. The Besov, Triebel-Lizorkin spaces and the modulation spaces are characterized with mixed norms. Besov and Triebel-Lizorkin spaces are described in [START_REF] Rychkov | On restrictions and extensions of the Besov and Triebel-Lizorkin spaces with respect to Lipschitz domains[END_REF], and [START_REF] Feichtinger | Modulation spaces: Looking back and ahead[END_REF] gives a good overview for modulation spaces.

Let s ∈ R and 0 < p, q ≤ ∞. Let φ 0 ∈ S, S denoting the Schwartz space, following some specific properties (see [START_REF] Rychkov | On restrictions and extensions of the Besov and Triebel-Lizorkin spaces with respect to Lipschitz domains[END_REF]) and φ j (t) = 2 j φ 0 (2 j t). The Besov space B s p,q is defined by

B s p,q =      f ∈ S : f B s p,q =   j 2 jsq φ j * f q p   1/q < ∞     
.

The Besov norm f B s p,q can be viewed as a mixed norm with w = {2 jsq }. For some particular ranges of values of p, q, s, Besov spaces are known to be spaces of sparse functions (or distributions), i.e. spaces within which nonlinear approximation converge faster than linear ones [START_REF] Mallat | A wavelet tour of signal processing[END_REF][START_REF] Cohen | On the importance of combining wavelet-based nonlinear approximation with coding strategies[END_REF].

The Triebel-Lizorkin space F s p,q is defined by

F s p,q =      f ∈ S : f F s p,q =   j 2 jsq |φ j * f | q   1/q p < ∞      .
The Triebel-Lizorkin norm f F s p,q can also be viewed as a mixed norm with w = {2 jsq }. In comparison with Besov spaces, the roles of the two indices are interchanged [START_REF] Gröchenig | Nonlinear approximation with local Fourier bases[END_REF].

The modulation spaces are characterized also with mixed norms. Let {g m,n } m∈Z,n∈Z be a Gabor frame: f belongs to the modulation space M w p,q if and only if [START_REF] Samarah | Local Fourier bases and modulation spaces[END_REF]   m∈Z n∈Z

w p m,n | f, g m,n | p q/p   1/q < ∞ .

Statistical regression and inverse problems

Several sparse regression techniques have been studied in a supervised learning context. The most classical one is the 1 regression, known as the lasso estimate [START_REF] Tibshirani | Regression shrinkage and selection via the lasso[END_REF], well known in the signal processing community as the Basis pursuit denoising [START_REF] Chen | Atomic decomposition by basis pursuit[END_REF].

The group-lasso [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF] introduced by Yan and Lin, uses the mixed norm 2,1 . This norm was introduced to preserve entire groups of individuals. More recently Fornasier and Rauhut studied more generally some p,1 mixed norm for inverse problems in [START_REF] Fornasier | Recovery algorithm for vector-valued data with joint sparsity constraints[END_REF], and Teschke and Ramlau used these norms in [START_REF] Teschke | An iterative algorithm for nonlinear inverse problems with joint sparsity constraints in vector valued regimes and an application to color image inpainting[END_REF]. Cotter et al. [START_REF] Cotter | Sparse solutions to linear inverse problems with multiple measurement vectors[END_REF] used this kind of norms in the same context and provided a comparison of two classes of algorithms: Matching Pursuit and FOCUSS. Another example is provided by the hierarchical penalization [START_REF] Szafranski | Hierarchical penalization[END_REF] introduced by Szafranski and Grandvalet, leading to a mixed norm 4 3 ,1 , which is obtained after a hierarchical modeling of the variables.

In the statistical community, mixed norm were used by Peng Zhao et al in [START_REF] Zhao | The composite absolute penalties family for grouped and hierarchical variable selection[END_REF], under the name of "Composite Absolute Penalties". That paper more particularly studies algorithms using the ∞,1 mixed norm.

In the following sections, we focus on regression problems. We show how classical algorithms used with p norms regularization can be extended to the use of mixed norms. Moreover, we give general algorithms able to handle the structure in layers for signal, like the morphological component analysis [START_REF] Starck | Image decomposition via the combination of sparse representation and a variational approach[END_REF]. Although the p,1 -like mixed norms were specifically used in the literature, we give results for general p,q mixed norms, and in particular, we show that the 1,q mixed norms are also relevant.

Signal estimation under equality constraint

We first address the problem of function or signal estimation subject to an exact reconstruction, in the finite dimensional case. We prove that the FOCUSS algorithm can be adapted to tackle the case of mixed norms, and we generalize it for a decomposition into layers. We limit ourselves to the finite dimension setting to follow the original setting of FOCUSS. The generalisation to infinite dimension requires to deal with Lagrange multipliers in Banach spaces [START_REF] Kurcyusz | On the existence and nonexistence of lagrange multipliers in banach spaces[END_REF] and then is not straightforward.

Let y ∈ C M . Let x ∈ C N with N = K × L be such that x = (x 1 , . . . , x K ) and for all k, x k = (x k,1 , . . . , x k, , . . . , x k,L ). Let A ∈ C M ×N be a matrix whose columns are the vectors of a dictionary of C M , with M ≤ N . We consider the cases p ≤ 2 and q ≤ 2 (p, q = 0) with the straightforward definition of the "mixed norms" for p < 1 or q < 1. These cases allow us to promote sparsity in some directions of the index lattice, while the problem remains convex for 1 ≤ p, q ≤ 2.

Minimization of a mixed norm

We want to solve the problem: min x sgn(pq) x q w;p,q subject to y = Ax .

(

Problem (3) can be solved with the FOCUSS algorithm [START_REF] Rao | An affine scaling methodology for best basis selection[END_REF], which has been designed to minimize a diversity measure (or equivalently, to maximise the sparsity of the solution), subject to an equality constraint.

In order to use FOCUSS, we have to write the gradient of the diversity measure under a factorized form. Denoting by E(x) the diversity measure of x, the factorized form of the gradient reads

∇ x E(x) = α(x)Π(x)x .
where x denotes the conjugate of x, α(x) is a scalar and Π(x) is a matrix. For example, with the p diversity measure E (p) (x) = x p p , α(x) = |p| and Π(x) = diag(|x n | p-2 ). In our case, we choose the w;p,q diversity measure, i.e. E (p,q) (x) = sgn(pq) x q w;p,q . The partial derivative with respect to x k, is

∂E (p,q) (x) ∂x k, = sgn(p)|q| w k, xk, |x k, | p-2 x k q-p w k ;p , Then α(x) = sgn(p)|q| and Π(x) = diag(w k, |x k, | p-2 x k q-p w k ;p ) (4)
FOCUSS is a simple iterative scheme to solve (3) given by the following algorithm 2 :

Algorithm 1 Let x (0) ∈ C N be a bounded feasible solution of (3) Do x (m+1) = Π -1 (x (m) )A * (AΠ -1 (x (m) )A * ) -1 y until convergence where a feasible solution x (0) of (3) is a vector which satisfies the constraint equality of the problem, and A * denotes the Hermitian transpose of A.

Remark 2 To initialize the algorithm, a simple bounded feasible solution is the solution with the minimum 2 norm obtained by the Moore-Penrose pseudo inverse of A: x (0) = A + y .

Theorem 1 Starting from a bounded feasible solution x (0) ∈ C N , the sequence of iterates generated by Algorithm 1 is convergent, and minimizes the w;p,q diversity measure, for p, q < 2 (p, q = 0). PROOF. We rewrite and adapt the original proof in [START_REF] Rao | An affine scaling methodology for best basis selection[END_REF]. The main point is to prove that E (p,q) (x (m+1) ) < E (p,q) (x (m) ).

To prove the convergence of the algorithm, we have to check the assumptions of the global convergence theorem [START_REF] Bazaraa | Nonlinear Programming: Theory and Algorithms[END_REF], which we restate here for the sake of completeness.

Theorem 2 Let A be an algorithm on a set X, and suppose that, given x (0) , a sequence {x (m) } is generated, satisfying

x (m+1) = A(x (m) ) .
Let a solution set Γ ⊂ X be given, and suppose the following (i) All points x (m) are contained in a compact set S ⊂ X.

(ii) There is a continuous function (the descent function)

Z on X such that (a) If x / ∈ Γ, then Z(y) < Z(x), ∀y ∈ A(x) ; (b) If x ∈ Γ, then Z(y) ≤ Z(x), ∀y ∈ A(x) ; (iii) The mapping A is closed at point outside Γ.
Then, the limit of any convergent sub-sequence of x (m) is a solution, and Z(x (m) ) → Z(x ) for some x ∈ Γ.

We define here Γ = x : Ax = y, and x = P (AP ) + y ,

where P = Π -1 (x ) 1/2 .
In the problem we consider, point iii) does not matter, because A is here a continuous function. Point i) can be proved exactly as in [START_REF] Rao | An affine scaling methodology for best basis selection[END_REF]. Then only the point ii) remains to be proved.

To prove point ii), we use the same technique as the one used in the original proof, and we make use of Hölder's inequality: if

x i , y i ≥ 0, r > 1, 1 r + 1 s = 1, then i x i y i ≤ i x r i 1 r i y s i 1 s
.

The inequality is reversed for r < 1 (r = 0).

One can write x (m+1) as a function of the minimal 2 norm solution b (m+1) of the problem AP (m+1) b = y,

where

P (m+1) = diag w -1/2 k, |x (m) k, | 2-p 2 x k p-q 2
w k ;p . Then we have x (m+1) = P (m+1) b (m+1) .

2 One can remark that the algorithm does not depend on α(x) .

Let us introduce b such that bk, = w

1/2 k, sgn(x (m) k, )|x (m) k, | q 2 x (m) k q-p 2 w k ;p which is a suboptimal solution of AP (m+1) b = y. If x (m+1) = x (m) (i.e. the algorithm has not converged), then b (m+1) 2 2 < b 2 2 = k w k, |x (m) k, | p x (m) k q-p w k ;p (5) = k x (m) k q-p w k ;p w k, |x (m) k, | p = k x (m) p q-p w k ;p x (m) k p w k ;p = x (m) q w;p,q .
We can stress that x

(m+1) k, = |x (m) k, | 2-p 2 x (m+1) k p-q 2 w k ;p b (m+1) k,
, and then, for 0 < p < 2 and 0 < q < 2

E(x (m+1) ) = k w k, |x (m+1) k, | p q/p = k w k, |x (m) k, | p(2-p) 2 x (m) k p(p-q) 2 w k ;p |b (m+1) k, | p q/p = k x (m) k q(p-q) 2 w k ;p w k, |x (m) k, | p(p-2) 2 |b (m+1) k, | p q/p ≤ k x (m) k q(p-q) 2 w k ;p w k, |x (m)
k, | p q(2-p) 2p |b (m+1) k, | 2 pq 2p = k x (m) k q(p-q) 2 w k ;p x (m) k q(2-p) 2 w k ;p b (m+1) k q 2 = k x (m) k 2q-q 2 2 w k ;p b (m+1) k q 2 ≤ k x (m) k q w k ;p 2-q 2 k b (m+1) k 2 2 q 2 < x (m) q w;p,q 2-q 2
x (m) q w;p,q

q 2 = E(x (m) ) ,
where we have used in the 4th line Hölder's inequality with r = 2 2-p , s = 2 p , and in the 7th line the Hölder inequality with r = 2 2-q , s = 2 q . Point ii) is then proved. The cases p = 2 or q = 2 are simple enough to not be specifically written. The cases p < 0 or q < 0 are similar, but we used the reversed Hölder's inequality.

Extension to multilayered expansions

In some situations, the signals under consideration contain significantly different features (termed layers), which are accurately encoded using different bases or frames. This leads to regression problems with dictionaries built as unions of these bases or frames. Then, it makes sense to use different (mixed) norms on the corresponding coefficients. FOCUSS may be adapted to this new situation, as we show below.

For simplicity, we limit the present discussion to the case of two layers only. The generalization to an arbitrary number of layers is straightforward. The problem can be formulated as follows. Let y ∈ C M and x =   x [1] x [2]   ∈ C N , with M < N and for all i ∈ {1, 2},

x [i] ∈ R Ni , with N i = K i × L i . Suppose that x [i] = (x [i] 1 , . . . , x [i] Ki ) and for all k ∈ {1, . . . , K i }, x [i] k = (x [i] k,1 , . . . , x [i] k, , . . . , x [i] k,Li ). Let A ∈ C M ×N be such that A = A 1 A 2 , with A i ∈ C M ×Ni for i ∈ {1, 2}
. Now that all the notations are introduced, we want to solve the following optimization problem:

min x1,x2 sgn(p 1 q 1 )λ 1 x [1] q1 w [1] ;p1,q1 + sgn(p 2 q 2 )λ 2 x [2] q2
w [2] ;p2,q2

subject to y = Ax = A 1 x [1] + A 2 x [2] , (6)
with λ 1 > 0 and λ 2 > 0 fixed. We denote the diversity measure by

E(x) = sgn(p 1 q 1 )λ 1 x [1] q1 w [1] ;p1,q1 + sgn(p 2 q 2 )λ 2 x [2] q2
w [2] ;p2,q2

= sgn(p

1 q 1 )λ 1 K1 k1=1 L1 1=1 w [1] k1, 1 |x [1] k1, 1 | p1 q1/p1 + sgn(p 2 q 2 )λ 2 K2 k2=1 L2 2=1 w [2] k2, 2 |x [2] k2, 2 | p2 q2/p2 (8)
= E 1 (x [1] ) + E 2 (x [2] ) .

In order to write the gradient of E in factorized form, we calculate the partial derivatives

∂E(x) ∂x [1] k1, 1 = sgn(p 1 )λ 1 |q 1 |w [1] k1, 1 x [1] k1, 1 |x [1] k1, 1 | p1-2 x [1] k1
q1-p1 w [1] ;p1

∂E(x) ∂x [2] k2, 2 = sgn(p 2 )λ 2 |q 2 |w [2] k2, 2 x [2] k2, 2 |x [2] k2, 2 | p2-2 x [2] k2 q2-p2 w [2] ;p2 . (10)
The gradient of the diversity measure E can be written in factorized form with α(x) = 1 and Π(x) =   Π 1 (x [1] ) 0 0 Π 2 (x [2] )   where Π 1 (x [1] ) = sgn(p 1 )λ 1 |q 1 | diag(w

[1] k1, 1 |x [1] k1, 1 | p1-2 x [1] k1 q1-p1 w [1] ;p1 ) and Π 2 (x [2] ) = sgn(p 2 )λ 2 |q 2 | diag(w [2] k2, 2 |x [2] k2, 2 | p2-2 x [2] k2 q2-p2
w [START_REF] Benedek | The space l p with mixed norm[END_REF] ;p2 ) . A first idea would be to apply the FOCUSS Algorithm 1 without any change. Unfortunately, the resulting algorithm does not converge in this case: the diversity measure E is not decreasing during the iterations. To modify the algorithm in order to ensure the decrease of the diversity measure and henceforth the convergence, let us take again the ideas of the previous proof, with the same notations. We rewrite inequality (5) as

b (m+1) 2 2 = b [1] (m+1) 2 2 + b [2] (m+1) 2 2 ( 12
)
< b 2 2 = x (m) q w;p,q (13)
= x [1] (m) q w;p,q + x [2] (m) q w;p,q .

To prove that E decreases strictly during the iterations, we would like to have b [1] (m+1) 2 2 < x [1] (m) q w;p,q (resp. b [2] (m+1) 2 2 < x [2] (m) q w;p,q ) and b [2] (m+1) 2 2 ≤ x [2] (m) q w;p,q (resp. b [1] (m+1) 2 2 ≤ x [1] (m) q w;p,q ). Therefore, we slightly modify the FOCUSS algorithm to guarantee that the energy decreases strictly.

Algorithm 2

Let x (0) ∈ R N be a bounded feasible solution. Do

x [1]

(m+1) = Π -1 1 (x [1] (m) )A * 1 (AΠ -1 (x (m) )A * ) -1 y x [2] (m+1) = Π -1 2 (x [2] (m) )A * 2 (AΠ -1 (x (m) )A * ) -1 y if E(x (m+1) ) ≥ E(x (m) ) then if E 1 (x [1] (m+1) ) > E 1 (x [1] (m) ), then x [1] (m+1) = x [1] (m) else x [2] (m+1) = x [2] (m) % (i.e E 2 (x [2] (m+1) ) > E 2 (x [2] (m) ) )%endif endif until convergence
This way, we ensure that E 1 or E 2 decrease stricly during the iterations, so that the energy E decreases strictly. This ensures the convergence of the algorithm to the desired result.

The FOCUSS algorithms allow us to estimate the coefficients in a dictionary, under an exact signal reconstruction constraint. The observation of a signal is often noisy, so it can be useful to relax the strict equality constraint when estimating the signal and its layers. FOCUSS and the above generalization can be modified as in [START_REF] Rao | Subset selection in noise based on diversity measure minimization[END_REF] to take the noise into account; however, this does not seem to be the most efficient algorithm in this case, as we shall see in the next section, where an alternative approach is also proposed.

Signal estimation in the presence of noise

In this section, we deal with the infinite dimensional case. Let y ∈ H, with H ⊂ L 2 (R) a separable Hilbert space, let x ∈ 2 (C) and a linear operator A : 2 (C) → H. We are interested here by the noisy case: i.e. the case of observations of the form y = Ax + b, where b ∈ H is an unspecified noise. We follow the classical variational formulation of the problem: the regression is made by minimizing the 2 error between the observed signal and its estimate, regularized by a mixed norm. Hence, we consider the following functional to minimize

Φ(x) = 1 2 y -Ax 2 2 + λ q x q w;p,q , (15)
with λ ∈ R * + . In a Bayesian setting, the choice of 2 norm for the data fidelity term is usually justified by assuming a Gaussian i.i.d. distribution for the noise. The mixed norm corresponds to a prior on the coefficients of the form

p(x) = exp{- λ q x q w;p,q } (16) = k exp{- λ q x k q w;p } , (17)
which is a product of Gibbs distributions. This Bayesian formulation shows the coupling between coefficients as stressed in Section 2. More generally, in a multilayered signal decomposition setting (see Subsection 3.2 above) our aim is to minimize a functional of the form:

Φ(x) = 1 2 y -Ax 2 2 + I i=1 λ i q i x [i] qi wi;pi,qi , (18)
with λ i ∈ R * + . In the finite dimensional case, in order to minimize [START_REF] Kowalski | Sparsity and persistence: mixed norms provide simple signals models with dependent coefficients[END_REF], the FOCUSS algorithm can be adapted as suggested in [START_REF] Rao | Subset selection in noise based on diversity measure minimization[END_REF]. We provide here the modified algorithm for I = 2 only for the sake of simplicity

Algorithm 3

Let x (0) ∈ R N be a bounded feasible solution. Do

x [1]

(m+1) = Π -1 1 (x [1] (m) )A * 1 (AΠ -1 (x (m) )A * + Id) -1 y x [2] (m+1) = Π -1 2 (x [2] (m) )A * 2 (AΠ -1 (x (m) )A * + Id) -1 y if E(x (m+1) ) ≥ E(x (m) ) then if E 1 (x [1] (m+1) ) > E 1 (x [1] (m) ), then x [1] (m+1) = x [1] (m) else x [2] (m+1) = x [2] (m) %(i.e. E 2 (x [2] (m+1) ) > E 2 (x [2] (m) )) %endif endif until convergence with Π 1 (x [1] ) = sgn(p 1 )λ 1 |q 1 | diag(w [1] k1, 1 |x [1] k1, 1 | p1-2 x [1] k1 q1-p1 w [1] ;p1 ) , (19)
and

Π 2 (x [2] ) = sgn(p 2 )λ 2 |q 2 | diag(w [2] k2, 2 |x [2] k2, 2 | p2-2 x [2] k2 q2-p2 w [2] ;p2 ) . ( 20
)
Unlike the algorithm given by Rao et al. in [START_REF] Rao | Subset selection in noise based on diversity measure minimization[END_REF], one can notice the presence of the term (AΠ -1 (x (m) )A * + Id) instead of (AΠ -1 (x (m) )A * + λId). This is because in our case, the λ i must be integrated in the matrix Π i to be able to write the algorithm.

This algorithm can perform the minimization for any p, q < 2 (p, q = 0). However, it is not very efficient and becomes very slow for high dimensional problems, due to a matrix inversion involved at each iteration.

A valuable alternative is provided by thresholded Landweber iteration algorithm, like the algorithm introduced by Daubechies et al. in [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF]. In the next subsection, we study the simple case where A is unitary (and corresponds to the operator of an orthogonal basis). In this case, the iterative thresholding algorithm is developed for 1 ≤ p, q ≤ 2. Although this algorithm is more restrictive in terms of admissible values for p and q than FOCUSS, it is really faster.

The unitary case

In this subsection, A is assumed to be an unitary operator: denoting by A * the adjoint of A, A * A = AA * = Id. This allows us to introduce some useful operators associated with a given mixed norm. Moreover, the regression problem formulated in the unitary case gives a good idea of the influence of the mixed norms when they are used as a penalty term.

Regression in the unitary case is equivalent to the optimization problem:

min x 1 2 y -Ax 2 2 + λ q x q w;p,q , (21)
which can be written like the minimization with respect to x of

Φ(x) = 1 2 y -Ax 2 2 + λ q k w k, |x k, | p q/p = 1 2 y -Ax 2 2 + λ q k x k q w k ;p . ( 22
)
Several cases have to be dealt with: -p > 1 and q > 1 Φ is differentiable at all points.

-p > 1 and q = 1 Φ is not differentiable at points x k = 0.

-p = 1 and q ≥ 1 Φ is not differentiable at points x k, = 0.

As A is an unitary operator, we have

y -Ax 2 2 = A * y -x 2 2 = k, ([A * y] k, -x k, ) 2 .
Let ỹ = A * y and θ x k, (resp. θ ỹk, ) be the argument of x k, (resp. ỹk, ). We have, for all k,

|ỹ k, -x k, | 2 = |ỹ k, | 2 + |x k, | 2 -2|x k, ||ỹ k, | cos(θ ỹk, -θ x k, ) .
Then, one can differentiate the functional Φ with respect to the modulus of x k, , for a fixed pair k, , and obtains

|x k, | = |ỹ k, | cos(θ ỹk, -θ x k, ) -λw k, |x k, | p-1 x k q-p w k ;p . ( 23
)
The differentiation of Φ with respect to

θ x k, gives 2|x k, ||ỹ k, | sin(θ ỹk, -θ x k, ) = 0 . (24)
From ( 23) and ( 24), one can deduce that θ x k, = θ ỹk, and state that variational equations are equivalent to the following system:

|x k, | = |ỹ k, | -λw k, |x k, | p-1 x k q-p w k ;p arg(x k, ) = arg(ỹ k, ) (25)
The variational equations are coupled, so that their solution may be difficult to obtain. The following discussion shows that an analytical solution can be obtained in most cases, otherwise an iterative algorithm is given to obtain the solution. It will appear that the solution is obtained by a shrinkage operation, as suggested by the variational equations. In all cases, the argument of x k, is the same as ỹk, .

4.1.1. p > 1 and q > 1 Let us introduce the function

F : 2 (C) → 2 (R), |v| → F(|v|) = |v| + λW k |v| p-1 v q-p w;p .
F is bijective, and the system has a unique solution which can be obtained numerically.

p > 1 and q = 1

For the particular case p = 2 and q = 1, Proposition 2 below gives an analytical expression of the solution. The more general cases 1 < p < 2 and q = 1 are solved using fixed point Algorithm 4 (see below).

Proposition 2 Let A be a unitary operator. We suppose that, for all k, , w k, = w k . The solution of Problem [START_REF] Mallat | A wavelet tour of signal processing[END_REF], where p,q = 2,1 is given by3

x k, = ỹk, 1 - λ √ w k ỹk 2 + .
PROOF. The proof is postponed to Appendix A.1.

Let us stress that the weighting term w k in the solution above, depends only on the index k, and does not depend on the index . Hence, we can rewrite the solution in vector form:

x k = ỹk 1 - λ √ w k ỹk 2 + . ( 26
)
Remark 3 The result given in Proposition 2 shows a mixture of a weighting (remembering the 2 minimization), and a thresholding (remembering the 1 minimization) which acts on an entire group of variables. In this case, the groups with many "big"(or "significant") coefficients are kept (i.e. not set to zero) over the groups with small coefficients. The coupling appears to be between significant coefficients. Furthermore, note that this solution is identical to the group-lasso estimate, given in [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF].

For the more general case q = 1 and 1 < p < 2 we cannot give any analytical expression for the solution, and Equation ( 25) must be solved numerically. In the finite dimensional case a simple iterative thresholding algorithm can be constructed. PROOF. The proof is postponed to Appendix A.2

Remark 4 Fornasier and Rauhut studied more specifically this kind of mixed norms in [START_REF] Fornasier | Recovery algorithm for vector-valued data with joint sparsity constraints[END_REF]. They show that the solution is given by a shrinkage operator and give the analytical solutions for the norms 1 , 2,1 and

∞,1 .
The study of the shrinkage operator for the p,1 mixed norm was also done by Teschke and Ramlau in [START_REF] Teschke | An iterative algorithm for nonlinear inverse problems with joint sparsity constraints in vector valued regimes and an application to color image inpainting[END_REF] for non linear inverse problems. Here, we gave Algorithm 4 to find the minimizer of 21 with q = 1 and 1 < p < 2, in the unitary case, and Proposition 3 gave a sufficient condition for the convergence.

p = 1 and q > 1

We show here that the solution is obtained by a coordinatewise soft-thresholding. The following proposition gives the threshold analytically for the case q = 2, and shows how to obtain a numerical estimation for the other cases.

Proposition 4 Let A be a unitary operator. The solution of Problem (21), with p,q = 1,q is given by a soft thresholding operator.

For each k, we denote yk, k (resp. wk, k ) the coefficients

|ỹ k, k | (resp. wk, k ) sorted such that the r k, k = |ỹ k, k | w k, k
are ordered by descending order (for each k). The threshold is given by w k, ξ k , with ξ k the (unique) solution in R + of the following equation

ξ 1 q-1 k + λ 1 q-1 L w k ξ k = λ 1 q-1 |ỹ k | w k , with |ỹ k | w k = L k =1 wk, yk, and L w k = L k k =1 w2 k, k . The quantity L k is the number such that r k,L k +1 ≤ λ L k +1 k =1 w 2 k, k (r k, k -r k,L k +1 ) q-1 and r k,L k > λ L k k =1 w 2 k, k (r k, k -r k,L k ) q-1 .
In particular, for q = 2, the threshold w k, ξ k is equal to

λw k, 1 + L w k λ |ỹ k | w k .
PROOF. The proof is postponed to Appendix A.3.

Remark 5 This proposition generalises the result given in the wavelet and Besov spaces framework in [START_REF] Chambolle | Nonlinear wavelet image processing: variational problems, compression, and noise removal through wavelet shrinkage[END_REF].

In the case q = 2, the 1,2 norm is associated with the problem called elitist-lasso [START_REF] Kowalski | Sparsity and persistence: mixed norms provide simple signals models with dependent coefficients[END_REF] (as opposite of grouplasso). Let us point out some properties of this estimator in the following two remarks. These properties illustrate the expected consequence of using this mixed norm in the context of regression.

Remark 6 After a suitable rewriting, the solution is obtained by a mixture of 2 -like weighting and 1 -like soft thresholding:

|x k, | = |ỹ k, | - λ 1 + λL w k |ỹ k | w k = |ỹ k, | 1 - λw k, 1 + λL w k - λ 1 + λL w k L k l=1,y l =y wk,l yk,l .
This mixture of weighting and thresholding is here very different from the one we obtained for the case of the mixed norm 2,1 (see Proposition 2). Here, we weight each coefficient, before comparing it to a threshold which depends on the norm of the group k. Contrary to the 2,1 mixed norm, the coupling is not between the significant coefficients: a coefficient appears significant if the others are unsignificant. In other words, only the largest coefficients -compared to the others -are kept, for each index k.

Remark 7 Let us take a look at the particular case λ >> 1 and w k, = 1 for all k, , for the 1,2 mixed norm. Then, for a fixed k, at least one coefficient is not set to zero. Indeed, if all the coefficients are set to zero, then |ỹ k | = 0 and no coefficient is thresholded, which is a contradiction. Consequently, the 1,2 mixed norm cannot give estimates as sparse as the 1 norm. This property is the consequence of the structures and illustrate well the coupling between significant and unsignificant coefficients as explained before in Remark 6.

Summary of the main results

Here, we summarize the preceeding results in a single theorem: Theorem 3 Let x ∈ 2 (C) and z ∈ 2 (C). Let 1 ≤ p, q ≤ 2 and w = (w k, ) a sequence of stricly positive weights such that x q w;p,q = k ( w k, |x k, | p ) q/p . Then, the solution of the following optimization problem

min x 1 2 z -x 2 2 + λ x q w;p,q ,
is given by S λ w;p,q (z), with S λ w;p,q a "generalized" soft-thresholding (or shrinkage) operator defined coordinatewise by, for all k, :

v k, → arg(v k, ) (|v k, | -ξ k, (λ)) + ,
where the ξ k, (λ), simply denoted by ξ k, , are given here after.

-If p > 1 and q > 1. Then, the thresholds are given a posteriori, the solution being given by the inverse of

F : 2 (R) → 2 (R), |v| → F(|v|) = |v| + λW k |v| p-1 v q-p w;p ; -If p = q = 1 then ξ k, = λw k, . -If p = q = 2 then ξ k, = λw k, 1+λw k, .
-If p = 1 and 1 < q < ∞. For each k, we denote žk, k (resp. wk, k ) the coefficients

|z k, k | (resp. wk, k ) sorted such that the r k, k = |z k, k | w k, k
are ordered by descending order. The threshold is ξ k, = w k, ξ k , where ξ k is the solution on R + of

ξ 1 q-1 k + λ 1 q-1 L w k ξ k = λ 1 q-1 |z k | w k , with |z k | w k = L k k =1
wk, k žk, k and L k is the quantity verifying:

r k,L k +1 ≤ λ L k +1 k =1 w 2 k, (r k, k -r k,L k +1 ) q-1 and r k,L k > λ L k k =1 w 2 k, (r k, k -r k,L k ) q-1
.

and L w k = L k k =1 w2 k, k .
In particular, if p = 1 and q = 2,

ξ k, = λw k, 1 + L w k λ |z k | w k .
-If p = 2 and q = 1, and for a fixed k, w k, = w k ∀ . Then

ξ k, = λ √ w k |z k, | z k 2 ;
-If 1 < p < 2 and q = 1. Then the solution is given by Algorithm 4 in finite dimension.

Remark 8 Theorem 3 gives the so-called proximity operator associated with the mixed norm p,q . Proximity operators were introduced by Moreau [START_REF] Moreau | Proximit et dualit dans un espace hilbertien[END_REF] in the 60's and nicely used more recently by Combettes et al. in particular in [START_REF] Combettes | Signal recovery by proximal forward-backward splitting[END_REF] to minimize some nondifferentiable convex functionals.

The previous theorem shows that the minimizer is obtained by a soft-thresholding operator. This remark gives us the following corollary Corollary 1 Let x ∈ 2 (C). Let A : 2 (C) → H be an unitary operator. Let 1 ≤ p, q ≤ 2 and w = (w k, ) a strictly positive sequence such that x q w;p,q = k ( w k, |x k, | p ) q/p . Then, for all y ∈ H, there exists a strictly positive sequence ξ = (ξ k, ) (which depends on y) such that the minimum of the functional Φ(x) = y -Ax 2 2 + x q w;p,q , coincides with the minimum of the functional

Φ(x) = y -Ax 2 2 + x ξ;1 .
We saw how to obtain an estimation of the minimizer when A is a unitary operator, and we defined operators allowing us to obtain the solution. Next section generalizes this problem, and shows that the corresponding iterative algorithm inspired by Daubechies et al. in [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF] and by Teschke in [START_REF] Teschke | Multi-frames representations in linear inverse problems with mixed multi-constraints[END_REF] may be extended to this new setting, with the same convergence properties.

A thresholded Landweber iteration

We study here a more general case than Problem [START_REF] Mallat | A wavelet tour of signal processing[END_REF]. A is now a general linear operator, and we want to exploit the structure in layers which can appear in a signal. In the particular case where A is the matrix of a dictionary constructed as a union of orthogonal bases, one can apply the Block Coordinate Relaxation algorithm, as it was shown in [START_REF] Kowalski | Sparsity and persistence: mixed norms provide simple signals models with dependent coefficients[END_REF]. The algorithm studied here is more general, and can be applied to any linear operator A, e.g. a matrix corresponding to frame (or union of frames), convolution operator, etc.

Let us introduce the functional

Φ(x) = 1 2 y - I i=1 A i x [i] 2 2 + I i=1 λ i q i Ψ i (x [i] ) = 1 2 y -Ax 2 2 + λΨ(x) . ( 27
)
with y ∈ H, for all i, A i is a linear operator and A = A i . Let x = (x [1] , . . . , x [I] ) ∈ 2 (C) I and λ = ( λ1 q1 , . . . , λ I q I ) ∈ R * I + . We have Ax = i A i x [i] and Ψ(x) = (Ψ 1 (x [1] ), . . . , Ψ I (x [I] )) T . Here, the penalty term is the mixed norm introduced before. So we have Ψ i (x [i] ) = x [i] w [i] ;pi,qi . To solve Problem [START_REF] Samarah | Local Fourier bases and modulation spaces[END_REF], following [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF][START_REF] Teschke | Multi-frames representations in linear inverse problems with mixed multi-constraints[END_REF], we introduce a surrogate functional

Φ sur (x, a) = 1 2 y -Ax 2 2 + C 2 x -a 2 2 - 1 2 Ax -Aa 2 2 + λΨ(x) (28) = 1 2 I i=1   k C(x [i] k, ) 2 -2x [i] k, [A * i y + Ca [i] -A * i Aa] k, + λ i q i K k=1 w [i] k, |x [i] k, | pi qi/pi   (29) + 1 2 y 2 2 + C a 2 2 -Aa 2 2 ,
with C such that C > C 1 + . . . + C I , where each C i bounds the operator norm of A * i A i . Then, the solution of the associated variational problem verifies, for all i, k, :

x [i] k, = C -1 [A * i y + Ca [i] -A * i Aa] k, - λ i C w [i] k, |x [i] k, | pi-1 x [i] k qi-pi w [i] k ;pi (30)
arg

x [i] k, = arg [A * i y + Ca [i] -A * i Aa] k, (31)
In the usual situation of the 1 norm [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF][START_REF] Teschke | Multi-frames representations in linear inverse problems with mixed multi-constraints[END_REF], the introduction of the surrogate functional decouples the problem into scalar problems. In our case, it also performs some decoupling, yielding vector subproblems of smaller dimension, which can be solved as described in Section 4.1. Consequently, the solution of ( 30) is obtained from

z = C -1 [A * i y+Ca [i] -A * i Aa], using the operators S λi/C w [i]
;pi,qi given by Theorem 3 in Section 4.2, for all i.

Proposition 5 Let a be fixed. The surrogate functional Φ sur (x, a) has a minimizer given by

argmin x (Φ sur (x, a)) = S(C -1 [ỹ + Ca -A * Aa]) , where S = S λ1/C w [1] ;p1,q1 , . . . , S λ I /C w [I] ;p I ,q I .
PROOF. The surrogate functional decouples the variational equations, so we just have to exploit the work done in Section 4.1.

Then, we can deduce the following iterative algorithm

Algorithm 5 Let x (0) ∈ 2 (C) Do For i = 1 : I x [i] (m+1) = S λi/C wi;pi,qi (C -1 [A * i y + Cx [i] (m) -A * i Ax (m) ]) = arg(C -1 [A * i y + Cx [i] (m) -A * i Ax (m) ]) C -1 A * i y + Cx [i] (m) -A * i Ax (m) -ξ [I] (m) + EndFor until convergence where the ξ [i] (m)
are the vectors containing the thresholds ξ

[i] (m) k,
. These thresholds are given by the operators

S λi/C w [i]
;pi,qi , associated with the adequate pi,qi mixed norm, applied to

z = C -1 [A * i y + Cx [i] (m) -A * i Ax (m)
]. Theorem 3 explains how to obtain these thresholds in practice.

As in [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF][START_REF] Teschke | Multi-frames representations in linear inverse problems with mixed multi-constraints[END_REF], we show that the preceeding algorithm converges, and then that limit is the desired minimizer (i.e. a solution of Problem ( 27)).

Theorem 4 Let I ∈ N. For all i ∈ {1, . . . I}, let A i be a linear operator, A i : 2 (C) → H. Let A be the linear operator such that A = A i and C such that C > A * A . Suppose y is an element of H, and the sequence of weights w is uniformly bounded from below by a stricly positive number. Then, the sequence of iterates generated by Algorithm 5 with x (0) arbitrarily chosen in 2 (C), converges weakly to a fixed point which is a minimizer of functional [START_REF] Samarah | Local Fourier bases and modulation spaces[END_REF]:

Φ(x) = 1 2 y - i A i x [i] 2 2 + i λ i Ψ i (x [i] ) = 1 2 y -Ax 2 2 + λΨ(x) .
PROOF. The proof follows the lines originally given by Daubechies et al. in [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF], and summarized in various papers (see e.g. [START_REF] Teschke | Multi-frames representations in linear inverse problems with mixed multi-constraints[END_REF]) to prove the weak convergence of a thresholded Landweber iteration. We just have to check [9, Lemma 3.6] (or [30, Lemma 14]), and [9, Proposition 3.10] ([30, Proposition 17]). We choose to postpone these proofs to Appendix A.4.

The same algorithm and the weak convergence can be obtained with the approach of proximal algorithm introduced by Combette et al. in [START_REF] Combettes | Signal recovery by proximal forward-backward splitting[END_REF] The weak convergence of the thresholded Landweber algorithm allows us to state the following theorem Theorem 5 Let I ∈ N. For all i ∈ {1, . . . I}, let A i be a linear operator, A i : 2 (C) → H. Let A be the linear operator such that A = A i and C such that C > A * A There exists a (non unique) sequence of R + ξ = (ξ

[i] k, ) such that Φ(x) = y -Ax 2 2 + λΨ(x) and Φ(x) = y -Ax 2 2 +
x ξ;1 have the same minimum reached at the same point x . Moreover, a choice of ξ is given coordinatewise by

ξ (i] k, = λ i w [i] k, |x [i] k, | pi-1 x [i] k qi w [i] k ;pi,qi if x [i] k, = 0 ≥ B otherwise.
where

B = I i=1 min{ξ (i] k, | x [i] k, = 0} -4/pi y (2pi(6+qi-pi)-4qi)/(piqi) 2
.

PROOF. Eq. ( 30) tells us that the minimum of Φ is attained at x such that, for any

C > A * A |x [i] k, | = C -1 [A * y + Cx [i] -A * i Ax ] k, - λ i C w [i] k, |x [i] k, | pi-1 x [i] k qi-pi w [i] k ;pi .
We denote by x the minimizer of Φ(x), which is the limit of the sequence x(m) generated by Algorithm 5 applied to Φ. Lemma 1 ensure that there exist a uniform bound B(x (0) ) such that x(m) ≤ B(x (0) ). Then, ξ k, ≥ B(x (0) ) for x k, = 0 ensure that x k, = 0. As the convergence does not depend of the choice of x(0) , we can choose ξ k, ≥ B(0) where B is given by Lemma 1.

Hence, with ξ

[i] k, = λ i w [i] k, |x [i] k, | pi-1 x [i] k qi-pi w [i] k ,pi when x [i]
k, = 0, we have

x = argmin x Φ(x) = argmin x Φ(x) = x .
Moreover, for all i ∈ {1, . . . I}

x [i] ξ (i] ;1 = λ i k, | x [i] k, =0 w [i] k, |x [i] k, | pi-1 x [i] k qi-pi w [i] k ;pi |x [i] k, | = λ i k x [i] k qi-pi w [i] k ;pi w [i] k, |x [i] k, | pi = λ i x [i] qi w [i] ;pi,qi then λΨ(x ) = x ξ;1 and Φ(x * ) = Φ(x ).
Using the previous theorem, we can state Theorem 6 The sequence x (n) of iterates generated by Algorithm 5 with x (0) arbitrarily chosen in 2 (C), converges strongly to a fixed point which is a minimizer of functional [START_REF] Samarah | Local Fourier bases and modulation spaces[END_REF].

PROOF. Let x be the weak limit of x (n) . Let Φ and ξ be defined by applying Theorem 5 to Φ. Let x(m) the sequence of iterates generated by Algorithm 5 applied to Φ. By Theorem 5 this sequence convergesstrongly (see [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF]) -to x which is a minimiser of Φ and Φ.

With L the operator defined by L = √ CId -A * A, we have

Φ sur (x (n) , x(m) ) = Φ(x (n) ) + L(x (n) -x(m) ) 2 2 . Moreover, lim n→∞,m→∞ Φ sur (x (n) , x(m) ) = Φ sur (x , x ) = Φ(x ) .
Then, for any ε > 0, there exist N, M , such that for all n > N and m > M ,

L(x (n) -x(m) ) 2 2 = |Φ sur (x (n) , x(m) ) -Φ(x (n) )| < ε .
Finally, for all n > N and m > M , with µ a stricly positive lower bound for the spectrum of L * L we have

x (n) -x 2 2 ≤ x (n) -x(m) 2 2 + x(m) -x 2 2 < 1 µ L(x (n) -x(m) ) 2 2 + < ( 1 µ + 1)ε .
Therefore, we can conclude that the sequence of x (n) converges strongly to the fixed point x .

We have now several algorithms to solve some specific regression problems. Next section gives some illustrations of these algorithms and provides hints regarding the influence of the mixed norms.

Two illustrations

We choose to limit ourselves to two illustrations for our algorithms, in the field of audio signal processing. The first one is an application to signal declicking and illustrates the thresholded Landweber algorithm. The FOCUSS algorithm is illustrated by a decomposition of an audio signal in "transients + tonal" layers, following [START_REF] Daudet | Hybrid representations for audiophonic signal encoding[END_REF][START_REF] Daudet | Towards a hybrid audio coder[END_REF]. These technique may be similarly applied to image processing problems in a straightforward manner.

Illustration of the thresholded Landweber algorithm

Our declicking example is a "toy example" which allows us to show the consequences of using the mixed norms compared to the classical 1 norm. In this example we limit ourselves to the 1,2 norm. This choice is justified in Remark 9 below.

We choose a 44.1 KHz sampled, 3 secondes long (2 17 samples) trumpet signal. We add to this signal random clicks simulated by Dirac pulses with amplitudes ±1 to obtain a Signal to Noise Ratio (SNR) equal The signal is then decomposed in a Gabor frame with a 2048 sample long Gaussian window, with a time shift of 128 samples, and 2 samples in frequency. As it can be seen on the time-frequency representation in Figure 2, the clicks appear clearly as vertical lines that are sparse in time, but cover all the frequencies. Several strategies could be imagined to declick the signal. First, we used the thresholded Landweber algorithm with a 1 norm penalty and compared it with the same algorithm using a mixed norm penalty.

The functional Φ that one wants to minimize is the following:

Φ(x) = 1 2 y -Ax 2 2 + λ q   k |x k, | p q/p   , (32)
where y is the clicked signal and A the matrix corresponding to the operator of the Gabor frame; p and q are chosen as follows -p = q = 1: this correspond to the classical 1 norm.

-p = 1 and q = 2: the index k corresponds to the time, and the index corresponds to the frequency. This choice is made to promote sparsity in frequency. The minimization of Φ was performed for various values of λ: the bigger the λ, the smaller the number of nonzero coefficients. Figure 3 provides the SNR as a function of the number of retained coefficients. The mixed norm obviously outperforms the classical 1 norm. To clearly illustrate the consequence of using the mixed norm, Figure 4 shows the time-frequency representation of the Gabor coefficients, for a comparable number of retained coefficients of 1 and 1,2 norms. The time-frequency representations clearly show that the clicks are better eliminated with the 1,2 mixed norm than with the classical 1 norm: the 1 norm keeps more vertical lines which correspond to clicks. Moreover, the partial harmonics are better preserved by the mixed norm. Thus, when a click appears at time index k, one expects that the threshold is higher than at a time index without a click.

We did not use the 2,1 mixed norm because this norm keeps entire groups (the sparsity are on the groups, not on the coefficients). This structure in "lines" does not seem to be very adapted to estimate the trumpet signal: the partials can evolve slowly in time, and their number may jump from a time frame to another. However, this structure in lines could be adapted to estimate only the clicks, and then obtain the clean signal in the residual of the functional. This strategy corresponds to an another functional than (32) and we did not try this strategy here.

Illustration of the FOCUSS algorithm

To illustrate the modified FOCUSS algorithm, we choose a xylophone signal of 0.7 sec long (2 15 samples) represented in Figure 5. The goal is to provide a decomposition in two layers "transient + tonal" subject to an exact reconstruction constraint. To this end, we choose to expand the signal in a dictionary constructed as the union of two MDCT (Modified Discrete Cosine Transform) bases. The first MDCT basis is chosen with a 4096 sample long window (about 90 msec) and is adapted for the tonal layer. The second one is chosen with a 128 sample long window and is adapted for the transient layer. The MDCT coefficients of transient layer are represented in Figure 5. The classical strategy is to minimize the 1 norm of all the coefficients. Each layer is then obtained by the inverse transform of the corresponding MDCT coefficients. This minimization is done by the original FOCUSS algorithm.

Our adaptation of FOCUSS is used with two mixed norms. For the tonal layer the p1,q1 mixed norm is chosen to promote sparsity in frequency with p 1 = 1.2 and q 1 = 2 (and k is the time index and the frequency index). For the transient layer, with k the frequency index and the frequency one, we choose a p2,q2 mixed norm with p 2 = 1 and q 2 = 1/2. This last choice was made to obtain a very sparse layer, but with a "structured sparsity". In order to balance the penalty with the two mixed norms terms, we choose λ 1 = 1 and λ 2 = 5.

in Figure 6, we provide the MDCT coefficients of the transient layer estimated by the 1 norm and the mixed norms. One can see that the estimate obtained by the mixed norm is sparser than the 1 estimate, and one can observe that the chosen mixed norm promote some structures compared to the 1 norm.

Conclusion and outlooks

In this paper we showed that when the data can be labelled by a double index, mixed norms can help easily introduce sparsity structure. This indexing can indeed be used to introduced a hierarchy throught the coefficients. This hierarchy is then explicitly used in the model through mixed norms p,q . Then, one can play on both p and q to promote different structured sparsity.

Mixed norms p,q are well adapted to two differents situations in regression:

-Signal estimation subject to an exact reconstruction; -Noisy signal estimation. Two algorithms were presented, corresponding to these different problems. For the sake of clarity, we summarize their strengths and weaknesses in Table 1.

FOCUSS Iterative thresholding

Range of p and q p, q ≤ 2 and p, q = 0 1 ≤ p, q ≤ 2, and for any p ≤ 1 if q = 2. The cases q = 1 and 1 ≤ p < 2 use an iterative algorithm which works for suitably chosen λ.

Speed -+

Ease of implementation + + Optimization subject to equality constraint + Not designed for Optimization subject to inequality constraint -+ Table 1 Compared advantages and shortcomings of the algorithms.

Let us notice that in the particular case of regression in an union of orthogonal bases, the Block Coordinate Relaxation (BCR) algorithm with mixed norms [START_REF] Kowalski | Sparsity and persistence: mixed norms provide simple signals models with dependent coefficients[END_REF] provides a valuable alternative to the thresholded Landweber iteration presented here. Our numerical experiments (not provided here) seem to show that both algorithms perform quite similarly.

The behavior of the iterative thresholding algorithms was illustrated on a specific example in order to stress the influence of mixed norms compared to the classical 1 norm. The audio signals were chosen for the intuitive structures provided by their time-frequency representations. But let us stress that mixed norm are certainly not specific of audio signal and can be used on any applications with structures given by a suitable double indexing of the coefficients of the signal's expansion.

The p,1 -like norms have already enjoyed significant succes in the statistical community for variable selection [START_REF] Yuan | Model selection and estimation in regression with grouped variables[END_REF][START_REF] Szafranski | Hierarchical penalization[END_REF][START_REF] Zhao | The composite absolute penalties family for grouped and hierarchical variable selection[END_REF], and were more specifically studied and applied for color image restoration in [START_REF] Fornasier | Recovery algorithm for vector-valued data with joint sparsity constraints[END_REF] and [START_REF] Teschke | An iterative algorithm for nonlinear inverse problems with joint sparsity constraints in vector valued regimes and an application to color image inpainting[END_REF]. Our work studied mixed norms in a general manner, and we want to stress the utility of the 1,q -like norms to promote structures without imposing sparsity only on grouped variables (see remark 6 in section 4.1.3, and remark 9 in section 5). The simple example provided here encourages us to use mixed norms in signal restoration. The preceding paper [START_REF] Kowalski | Sparsity and persistence: mixed norms provide simple signals models with dependent coefficients[END_REF] gave promising results in multichannel denoising and multilayered "tonal + transients + noise" decomposition. In [START_REF] Kowalski | Under-determined source separation via mixed-norm regularized minimization[END_REF], the thresholded Landweber iteration with the 1,2 norms was applied with success to source separation of underdetermined convolutive mixtures. Some natural extensions can also be studied, as mixed norms with more than a two levels index, or using the sum of mixed norms (as in elastic-net [START_REF] Zou | Regularization and variable selection via the elastic net[END_REF] which uses a sum of 1 and 2 penalty, or the regularization penalty proposed in [START_REF] Fornasier | Recovery algorithm for vector-valued data with joint sparsity constraints[END_REF][START_REF] Fornasier | Iterative thresholding algorithms[END_REF]) for the regularization term in the context of regression. Furthermore, it could be interesting to use mixed norms for the data term in the transformed domain. Indeed, the 2 norm is used in a Bayesian context to model Gaussian noise. The use of such norms could be adapted to penalise noise which is known not to be Gaussian.

∂s(|x

k |) ∂|x k, | =         -λw k,1 |x k,1 | p-1 w k, |x k, | p-1 (1 -p) x k 1-2p w k ;p . . . -λ(1 -p)w 2 k, |x k, | 2p-2 x k 1-2p w k ;p -λ(p -1)w k, |x k,1 | p-2 x k, 1-p w k ;p . . .         = -λw k, |x k, | p-1 (1 -p) x k 1-2p w k ;p         w k,1 |x k,1 | p-1 . . . w k, |x k, | p-1 . . .         -λ(p -1)w k, |x k, | p-2 x k 1-p w k ;p            0 . . . 1 0 . . .            .
Since we want to give an upper bound for the 1 norm of s, we use the general mean inequality: let the following quantities

M p = 1 N n=1 w n N n=1 w n |x n | p 1 p . If α < β, then M α < M β for all α and β in R * . Denoting by L w k = L =1 w k,
, and as we have 1 < p < 2, we can give an upper bound for the 1 norm: w k .

∂s(|x k |) ∂|x k, | 1 ≤λ(p -1) x k 1-2p w k ;p w k, |x k, | p-1 x k p-1 w k ;p-1 + w k, |x k, | p-2 x k 1-p w k ;p ≤λ(p -1) x k 1-2p w k ;p x k p-1 w k ;p-1 x k p-1 w k ;p-1 + x k p-2 w k ;p-2 x k 1-p w k ;p ≤λ(p -1) L 2 p w k x k 1-2p w k ;p x k p-1 w k ;p x k p-1 w k ;p + L 2(p-1) p(p-2) w k x k p-2 w k ;p-2 x k 1-p w k ;p-2 (means inequality) ≤λ(p -1) L 2 p w k x k -1 w k ;p + L 2(p-1) p(p-2) w k x k -1 w k ;p-2 ≤ λ(p -1) x k -1 w k ;p-2 L 2 p + 2 p(p-2) w k + L 2(p-1) p(p-2) w k ≤λ(p -1) y k -1 w k ;p-2 2L 2(p-1) p(p-2) w k ≤ λ(p -1) max k ( y k -1 w k ;p-2 ) 2L
If one chooses λ small enough, one can make this quantity strictly smaller than 1. So that, the application s is contractive, which ensures the convergence of the algorithm.

A.3. Proof of Proposition 4

For all k, , we have from ( 25 are ordered by decreasing order. We denote the ordered coefficients by yk, k (resp. wk, k ).

We must have yk,L k +1 w k,L k +1 ≤ ξ k < yk,L k w k,L k , then, from (25) L k is such that

r k,L k +1 ≤ λ L k +1 k =1 w 2 k, k (r k, k -ξ k ) q-1 and r k,L k > λ L k k =1 w q k, k (r k, k -ξ k ) q-1
.

And finally, L k is such that

r k,L k +1 ≤ λ L k +1 k =1 w 2 k, k (r k, k -r k,L k +1 ) q-1 and r k,L k > λ L k k =1 w 2 k, k (r k, k -r k,L k ) q-1
.

Then, |ỹ k | w k = L k k =1
wk, k yk, k , and the thresholds ξ k can be found by solving in R + the equation

ξ 1 q-1 k + λ 1 q-1 L w k ξ k = λ 1 q-1 |ỹ k | w k .
One can easily verify that this equation has a unique solution on R + . Then we have

|x k, | = (|ỹ k, | -w k, ξ k ) + .
In the case q = 2, w k, ξ k = λw k,

1+Lw k λ |ỹ k | w k .
A.4. Proof of Theorem 4

We need to prove the following Lemma in order to be able to prove that the sequence x (m) converges weakly to a fixed point, following [START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF].

Lemma 1 We can uniformly bound below the sequence formed by w by a strictly positive real number. Then the x (m) are uniformly bounded in m.

PROOF. The sequence formed by w is bounded from below by a strictly positive number, so we have w k, ≥ c, uniformly in (k, ), with c > 0.

We can write Ψ(x (m) ) ≤ Φ(x (m) ) ≤ Φ(x (0) ) , because Φ(x (m) ) is a non-increasing sequence ([9, Lemma 3.5]), the Ψ(x (m) ) are then uniformly bounded.

So, for all i x [i] (m) qi w,pi,qi ≤ Φ(x (0) ) , (A.3) and then, for all k, x

[i] (m) k qi w,pi ≤ Φ(x (0) ) . (A.4)

For all i, we can bound Furthermore, we can show that

x [i] (m) 2 2 x [i] (m) 2 2 ≤ k |x [i] (m) k, | 2
x [i] (m) k 2 2 ≤ c -2/pi max(w (2-pi)/pi |x [i] (m) k, | 2-pi ) x [i] (m) k pi w,pi ≤ c -2/pi x [i] (m) k 2-pi w,pi x [i] (m) k pi w,pi = c -2/pi x [i] (m) k 2
w,pi , and then, as we have 2 -q i /p i ≥ 0

x [i] (m) 2 ≤ c -4/pi max k ( x [i] (m) k 2(2-qi/pi) w,pi ) max k ( x [i] (m) k 2-pi w,pi ) x [i] (m) qi
w,pi,qi , which, with Equations (A.3) and (A.4), allow us to give an uniform upper bound for x (m) 2 .

We also need to prove that the obtained fixed point is a minimizer of Functional [START_REF] Samarah | Local Fourier bases and modulation spaces[END_REF]. To do so, we denote by x a fixed point of Algorithm 5. We have Φ sur (x + h; x ) = Φ(x + h) + C h 2 2 -Ah 2 2 . We first prove that, if x is a critical point of Φ sur (x, x (m) ), then Φ sur (x + h, x (m) ) -Φ sur (x, x (m) ) ≥ C h 2 2 . For this, we calculate ∂Φ sur (x, a): ∂Φ sur (x, a) = -A * (y -Ax) + 2C(x -a) -2A * (Ax -Aa) + λ∂Ψ(x) , so that, one can check that Φ sur (x + h, x (m) ) -Φ sur (x, x (m) ) = ∂Φ sur (x, x (m) )h + C h 2 2 + λ{Ψ(x + h) -Ψ(x) -∂Ψ(x)h} . As x is a critical point, i.e. for all v in ∂Φ sur (x, x (m) ) and for all h, we have ∂Φ sur (x, x (m) )h = 0, then Φ sur (x + h, x (m) ) -Φ sur (x, x (m) ) = C h 2 2 + 2λ{Ψ(x + h) -Ψ(x) -∂Ψ(x)h} . By definition of the sub-gradient, an element v belong to ∂Ψ(x)if and only if for all y Ψ(x) + v, yx ≤ Ψ(y). In particular, for y = x + h, this give for all h and for all v ∈ ∂Ψ(x) Ψ(x) + v, h ≤ Ψ(y) i.e. 0 ≤ Ψ(x + h) -Ψ(x) -∂Ψ(x)h .

Finally

Φ sur (x + h, x (m) ) -Φ sur (x, x (m) ) ≥ C h 2 2 . As Φ sur (x , x ) = Φ(x ) and Φ sur (x + h, x ) = Φ(x + h) + C h 2 2 -Ah 2 2 , we can conclude that for all h:

Proposition 3 (

 3 ỹ k, ) ỹk, -λw k, |x k, | p-1 x k q-p w k ;p + endfor Let ỹ ∈ C K×L and L w k = L =1 w k, .Fixed point algorithm 4 converges for y k w k ;p-2 ) .

Fig. 1 .

 1 Fig. 1. Trumpet signal (left) and its clicked version (right).

to 20 .

 20 33 dB. The time representation of the samples of the original signal and its clicked version are provided in Figure 1.

Fig. 2 .

 2 Fig. 2. Time-frequency representation of the Gabor coefficients for the original trumpet signal (left) and its clicked version (right).

Fig. 3 .Fig. 4 .Remark 9

 349 Fig. 3. Evolution of the SNR as a function of the number of coefficients. solid line: 12 mixed norm, dashed line: 1 norm.

Fig. 5 .

 5 Fig. 5. Left: the xylophone signal. Right: MDCT coefficients of the signal, with a window of length 128 samples.

Fig. 6 .

 6 Fig. 6. MDCT coefficients of two estimates of the transient layer for the xylophone. Left: 1 estimate. Right: 1,1/2 estimate.

)w k ; 1 == 2 )

 12 |x k, | = |ỹ k, | -λ w k,ν x k |ỹ k, |-|x k, | w k,, which gives, for all k, ν, such that x k,ν = 0 and x k, = 0|x k,ν | = |ỹ k,ν | -w k,ν (|ỹ k, | -|x k, |) w k, . With L w k = ν:|x k,ν | =0 w 2 k,ν , and |ỹ k | w k = ν:|x k,ν | =0 w k,ν |y k,ν | , we have |x k, | =   |ỹ k, | -λw k, ν w k,ν |x k,ν |) k,ν | =0 w k,ν |ỹ k,ν | -w k,ν (|ỹ k, | -|x k, |) k,ν | =0 w k,ν |ỹ k,ν |   -L w k |ỹ k, | -|x k, | w k, |ỹ k, | -λw k, |ỹ k | w k -L w k |ỹ k, | -|x k, |wDenoting by ξ k = λ x k w k ;1 , we must now determine the set {ν : |x k,ν | = 0} = {ν : |y k,ν | > w k, ξ k }. To do so, for each k, we sort the |y k, k | (resp. w k, k ) such that the r k, k = ỹk, k w k, k

  w,pi ) x [i] (m) qiw,pi,qi .

The approach of[START_REF] Fornasier | Recovery algorithm for vector-valued data with joint sparsity constraints[END_REF][START_REF] Teschke | An iterative algorithm for nonlinear inverse problems with joint sparsity constraints in vector valued regimes and an application to color image inpainting[END_REF] clearly applies directly to this more general situation.

For x ∈ R, we shall set x + = max(0, x) .

Acknowledgement

The author wishes to gratefully thank Bruno Torrésani, Sandrine Anthoine and Liva Ralaivola for their precious advices and help during this work. Φ(x + h) ≥ Φ(x ) + Ah 2 2 , which concludes the proof.

Appendix A. Proofs

A.1. Proof of Proposition 2

From (25), we have, for all k, such that

Then for all ν, λw k x k -1

, which gives

Then, we obtain

which is the desired result.

A.2. Proof of Proposition 3 (convergence of the fixed point algorithm)

We prove that for all k, the sequence of vectors x k converges to an unique fixed vector. We denote by s the soft-thresholding operator which maps |x

To prove the proposition, we simply apply Picard's fixed point theorem to s.

We have