Luc Le Magoarou
email: luc.le-magoarou@inria.fr

Alexey Ozerov
email: alexey.ozerov@technicolor.com

Ngoc Q K Duong

Text-informed audio source separation. Example-based approach using non-negative matrix partial co-factorization

Keywords: informed audio source separation, Non-negative Matrix Partial Co-Factorization, excitation-filter model, speech alignment

The so-called informed audio source separation, where the separation process is guided by some auxiliary information, has recently attracted a lot of research interest since classical blind or non-informed approaches often do not lead to satisfactory performances in many practical applications. In this paper we present a novel text-informed framework in which a target speech source can be separated from the background in the mixture using the corresponding textual information. First, given the text, we propose to produce a speech example via either a speech synthesizer or a human. We then use this example to guide source separation and, for that purpose, we introduce a new variant of the non-negative matrix partial co-factorization (NMPCF) model based on a so-called excitation-filterchannel speech model. Such a modeling allows sharing the linguistic information between the speech example and the speech in the mixture. The corresponding multiplicative update (MU) rules are eventually derived for the parameters estimation and several extensions of the model are proposed and investigated. We perform extensive experiments to assess the effectiveness of the proposed approach in terms of source separation and alignment performance.

Introduction

Audio source separation, which aims at extracting individual sound sources from the observed mixture signal, offers a wide range of applications in, e.g., automatic speech recognition, hearing aids, movie dubbing, and so on. However, despite a lot of research effort, blind source separation still does not provide a satisfactory performance, and is difficult especially in under-determined cases where the number of sources exceeds the number of observed mixtures [START_REF] Vincent | The signal separation evaluation campaign (2007-2010): Achievements and remaining challenges[END_REF]. An emerging research trend, referred to as informed source separation, has been widely considered recently and was shown to be highly effective for certain source separation tasks. It consists in using some auxiliary information about the sources and/or the mixing process to guide the separation. For example, score-informed approaches rely on musical score to guide the separation in music recordings [START_REF] Ganseman | Source separation by score synthesis[END_REF][START_REF] Hennequin | Score informed audio source separation using a parametric model of non-negative spectrogram[END_REF][START_REF] Simsekli | Score guided musical source separation using generalized coupled tensor factorization[END_REF][START_REF] Fritsch | Score informed audio source separation using constrained nonnegative matrix factorization and score synthesis[END_REF], separation-by-humming (SbH) algorithms exploit a sound "hummed" by the user mimicking the source of interest [START_REF] Smaragdis | Separation by "humming": User-guided sound extraction from monophonic mixtures[END_REF][START_REF] Fitzgerald | User assisted source separation using nonnegative matrix factorisation[END_REF], and userguided approaches take into account knowledge about, e.g., user-selected F0 track [START_REF] Durrieu | Musical audio source separation based on user-selected F0 track[END_REF] or user-annotated source activity patterns along the spectrogram of the mixture [START_REF] Ozerov | Multichannel nonnegative tensor factorization with structured constraints for user-guided audio source separation[END_REF][START_REF] Lefèvre | Semi-supervised NMF with time-frequency annotations for single-channel source separation[END_REF] and/or that of the estimated sources [START_REF] Bryan | Interactive user-feedback for sound source separation[END_REF][START_REF] Duong | An interactive audio source separation framework based on non-negative matrix factorization[END_REF]. In line with this direction, there are also speech separation systems informed, e.g., by speaker gender [START_REF] Roweis | One microphone source separation[END_REF], by corresponding video [START_REF] Wang | Chambers. Video assisted speech source separation[END_REF], or by the natural language structure [START_REF] Mysore | A non-negative approach to language informed speech separation[END_REF]. However, while written text corresponding to the speech in the mixture is often available, e.g., in form of subtitles (an approximate speech transcrip-tion) associated to a movie or script (an exact speech transcription) in a movie production phase, to the best of our knowledge, none of the existing approaches, except our preliminary work [START_REF] Magoarou | Textinformed audio source separation using nonnegative matrix partial co-factorization[END_REF], exploits this information to guide the separation process.

With the above mentioned motivation, we introduce in this paper a novel framework that exploits the available textual information to guide the separation of target speech from the background in single-channel mixtures. The proposed approach is inspired by the synthesis-based score-informed music separation approaches [START_REF] Ganseman | Source separation by score synthesis[END_REF][START_REF] Fritsch | Score informed audio source separation using constrained nonnegative matrix factorization and score synthesis[END_REF] where a symbolic representation of the corresponding music sources (the score) is used to synthesize audio examples that are further used to guide the separation. In our scenario, the available text is used to generate a speech example, e.g., via a speech synthesizer, which shares the linguistic information with the speech in the mixture (since the example and the speech in the mixture contain the same uttered text). Note that, as compared to the music case in [START_REF] Ganseman | Source separation by score synthesis[END_REF][START_REF] Fritsch | Score informed audio source separation using constrained nonnegative matrix factorization and score synthesis[END_REF], such a task is intrinsically more challenging for speech. Indeed, in contrast to music, where the temporal mismatch between the sources and the score-synthesized examples is usually linear (the tempo may not be the same, but the rhythm is usually maintained), it is often non-linear for speech. Moreover, while the pitches of the same musical notes are usually on the same frequency locations, there is no guarantee that the pitches of two different speakers would be the same. In order to handle such kind of variations in both frequency and time between the latent source and the synthesized speech example, we develop a novel variant of the non-negative matrix partial co-factorization (NMPCF) model 1 . The proposed model is based on a so-called excitation-filter-channel (EFC), which is a new extension of the excitation-filter model [START_REF] Virtanen | Analysis of polyphonic audio using source-filter model and non-negative matrix factorization[END_REF][START_REF] Durrieu | Source/filter model for unsupervised main melody extraction from polyphonic audio signals[END_REF]. This formulation allows to jointly factorize the spectrogram of the speech example and that of the mixture, while sharing between them the common linguistic information and handling the variations of both the temporal dynamics, the recording conditions, and the speaker's prosody and timber.

As compared to our preliminary work [START_REF] Magoarou | Textinformed audio source separation using nonnegative matrix partial co-factorization[END_REF], this paper contains the following main additional contributions:

-On the methodological level, new structural constraints (inspired by [START_REF] Ozerov | A general flexible framework for the handling of prior information in audio source separation[END_REF]) on some matrices of the NMPCF model are introduced and investigated. These constraints have quite natural physical motivations. The first type of constraint, imposed on some matrix of activation coefficients, means that at most one element from the corresponding dictionary can be active at a given time, which can be viewed as a sort of extreme sparsity. A physical motivation behind is that in a monophonic speech signal at most one phoneme can be pronounced at a time and at most one pitch can be active at a time. The second constraint is imposed on a so-called synchronization matrix and simply means that the synchronization between the example and the speech in the mixture must be monotonous.

-On the experimental level, we study in depth the influence of some key parameters on the separation performance and assess explicitly the benefit of the introduced excitation-filter-channel model compared to the state-of-the-art excitation-filter model.

Furthermore, we evaluate the potential of the considered model in speech alignment task.

Moreover, we present in this manuscript a full list of equations for parameter updates. Finally, note that the proposed framework is applicable in both single-channel and multichannel mixtures. However, for simplicity we focus the presentation on the single-channel case in this paper. Extending the approach to the multichannel case is quite straightforward (e.g., one can be inspired by developments in [START_REF] Ozerov | A general flexible framework for the handling of prior information in audio source separation[END_REF] to do so). We have done it in practice by combining the considered spectral model with the spatial model introduced in [START_REF] Duong | Underdetermined reverberant audio source separation using a full-rank spatial covariance model[END_REF] in order to participate in the "Two-channel mixtures of speech and real-world background noise" separation task of the Signal Separation Evaluation Campaign (SiSEC 2013) [START_REF] Ono | The 2013 signal separation evaluation campaign[END_REF]. The structure of the rest of the paper is as follows. A general workflow of the proposed framework and some related work are presented in section 2. The NMPCFbased modeling as well as new structural constraints are then described in Section 3, followed by presentation of the model parameter estimation algorithms in section 4. The proposed approach is extensively studied and evaluated in various settings in terms of both source separation and speech alignment performances in section 5. Finally we conclude in section 6.

General workflow and related work

The general workflow of the proposed approach is depicted in Fig. 1 where a speech example corresponding to the same uttered words as the one of the speech in the mixture is assumed to be available. The proposed source separation algorithm takes as input the observed audio mixture and the speech example to guide the separation. The NMPCF model and the corresponding parameter estimation block will be described in details in sections 3 and 4, respectively. Finally, the targeted speech and background estimates are recon-structed from the estimated parameters via the standard Wiener filtering [START_REF] Févotte | Nonnegative matrix factorization with the Itakura-Saito divergence. With application to music analysis[END_REF] as described at the end of section 3. One can imagine several ways to generate a speech example that carries similar linguistic information to the speech in the mixture. We identify in the following four strategies to produce such an example (see Fig. 2). The first one (i) uses the text often provided with TV programs and DVD movies (subtitles or script) to produce a speech example using an automatic speech synthesizer. This scenario is probably among the easiest ones since it is totally automatic and does not require any intervention from the user. The three other ways we consider are semi-automatic and need the user speaking to produce the example. Depending on the availability of the information and on user's wishes, he/she can either (ii) simply read the text, (iii) mimic the speech in the mixture after having listened to it, or (iv) do both. In summary, we see that besides introducing the textinformed approach we introduce in fact several practical methods lying in-between the text-informed and the user-guided approaches. As such, method (i) is purely text-informed and method (iii) is purely user-guided, while methods (ii) and (iv) are in-between, since rely on both the text availability and an intervention from user.

Though the considered speech example-based textinformed strategies have not been presented yet in the existing works, except our preliminary study [START_REF] Magoarou | Textinformed audio source separation using nonnegative matrix partial co-factorization[END_REF], some related approaches would be worth to be mentioned. Pedone et al. [START_REF] Pedone | Phoneme-level text to audio synchronization on speech signals with background music[END_REF] proposed an algorithm for phonemelevel text to audio synchronisation applied to mixtures of speech and background music. This algorithm relies on the non-negative matrix factorization (NMF)-like framework where the excitation-filter models of English phonemes are pre-trained. In this light, given that there is a sort of latent speech modeling guided by text, it could be extended as well for text-informed speech separation. However, while this approach was not evaluated in terms of source separation and requires to learn the general phoneme models, our method exploits specific phonemes in a speech example, which is probably pronounced in a closer way to the speech in the mixture. By this difference, we believe that the proposed approach potentially brings better separation performance. Using a sound mimicking the one to be extracted from the mixture to guide the separation, Smaragdis et al. introduced a so-called Separation by Humming (SbH) approach based on the probabilistic latent component analysis (PLCA) [START_REF] Smaragdis | Separation by "humming": User-guided sound extraction from monophonic mixtures[END_REF] and FitzGerald [START_REF] Fitzgerald | User assisted source separation using nonnegative matrix factorisation[END_REF] reported a similar method based on the NMF. However, while the performance resulted from PLCA or NMF [START_REF] Fitzgerald | User assisted source separation using nonnegative matrix factorisation[END_REF] is limited due to the strong variations between the source and the example (e.g., pitch or temporal dynamic variation, as mentioned in the introduction), our proposed NMPCF framework models those variations explicitly.

Modeling framework

We first formulate the mixing problem and we describe separately the proposed excitation-filter-channel spectral models of the mixture and the speech example as well as explain why we chose this specific models. Finally we the present the NMPCF-based [START_REF] Simsekli | Score guided musical source separation using generalized coupled tensor factorization[END_REF] couplings between these two models. We further introduce novel structural constraints into the NMPCF model. Finally, we explain how the sources can be reconstructed given the estimated model parameters.

Problem formulation

Let us consider a single-channel mixture:

x(t) = s(t) + b(t) (1)
consisting of a target speech signal s(t) corrupted by a background signal b(t), where t denotes the discrete time index. The goal is to estimate speech, given the mixture x(t) and a speech example y(t).

Mixture model

Let X ∈ C F ×N be the Short-Time Fourier Transform (STFT) of x(t), F being the number of frequency bins and N the number of time frames. Equation (1) rewrites:

X = S + B, (2)
where S and B are the STFTs of the speech and the background, respectively. Defining the power spectrogram V X = |X| . [2] (A . [b] being the element-wise exponentiation of a matrix A by b), assuming that the speech and background signals are uncorrelated, V X can be approximated as:

V X ≈ VX = VS + VB , (3)
where VX , VS , VB ∈ R F ×N + are approximations of the power spectrograms of the mixture, the speech and the background, respectively.

We further constrain the speech by imposing a socalled excitation-filter-channel (EFC)2 structure on VS :

VS = Ve S ⊙ Vφ S ⊙ Vc S , (4)
with ⊙ being the Hadamard element-wise product, Ve S being a time-varying linear combination of comb filters modeling the pitch, Vφ S being a time-varying filter modeling the phonemes pronounced, and Vc S being a time-invariant filter modeling the recording conditions and speaker's vocal tract. Let us stress that, except if the contrary is stated, all the entries of matrices within power spectrogram models in this paper are assumed real and non-negative numbers.

All the matrices in Eq. ( 4) and matrix VB are further subject to NMF decompositions as follows:

-Ve S = W e H e S , W e ∈ R F ×I + being a pre-defined dictionary of combs representing all possible pitches of human voice and H e S ∈ R I×N + being the corresponding temporal activations.

-

Vφ S = W φ S H φ S , W φ S ∈ R F ×J +
being a dictionary of phoneme spectral envelopes and

H φ S ∈ R J×N + being the corresponding temporal activations. -Vc S = w c S i T N , w c S ∈ R F ×1
+ modeling both the spectral shape of the recording conditions filter and speaker's vocal tract, and i N being an N -length column vector of ones.

-VB = W B H B , W B ∈ R F ×K +
being a dictionary of background spectral shapes and H B ∈ R K×N + being the corresponding temporal activations.

Another assumption is made so as to constrain spectral shapes of matrices W φ S and w c S to be smooth [START_REF] Ozerov | A general flexible framework for the handling of prior information in audio source separation[END_REF]. Following [START_REF] Ozerov | A general flexible framework for the handling of prior information in audio source separation[END_REF], these matrices are constrained as follows : W φ S = PE φ S and w c S = Pe c S , where P ∈ R F ×L + is a pre-defined matrix of L so-called spectral blobs, that are used to construct W φ S and w c S with weights E φ S ∈ R L×J + and e c S ∈ R L×1 + , respectively. Finally, the mixture model can be summarized as:

V X ≈ VX = VS W e H e S Ve S ⊙ W φ S H φ S Vφ S ⊙ w c S i T N Vc S + VB W B H B .
(5)

Speech example model

Let Y ∈ C F ×N ′ be the STFT of y(t) and V Y = |Y| .[2] ∈ R F ×N ′ +
its power spectrogram. Note that in most cases N ′ = N due to the temporal mismatch between the example and the mixture. The example consists of only one clean speech source whose power spectrogram is approximated as:

V Y ≈ VY = Ve Y ⊙ Vφ Y ⊙ Vc Y , (6)
where Ve Y , Vφ Y and Vc Y are decomposed the same way as in section 3.2, i.e., Ve

Y = W e H e Y , Vφ Y = W φ Y H φ Y and Vc Y = w c Y i T N ′ .
The smoothness constraints are applied as well:

W φ Y = PE φ Y and w c Y = Pe c Y .
As a result, the spectrogram of the speech example is modeled as:

V Y ≈ VY = W e H e Y Ve Y ⊙ W φ Y H φ Y Vφ Y ⊙ w c Y i T N ′ Vc Y . (7)

Couplings between the mixture and example models

The role of the example is to guide source separation, thanks to the fact that it shares common linguistic information with the speech in the mixture. We model this sharing as follows:

-The phonemes pronounced in the mixture and those pronounced in the example are the same, thus we assume:

W φ S = W φ Y = W φ , and W φ is to be esti- mated. This assumption implies E φ S = E φ Y = E φ .
-The phonemes are pronounced in the same order in the mix and in the example, but not exactly temporally synchronized. Thus we represent H φ S as

H φ S = H φ Y D where D ∈ R N ′ ×N
+ is a so-called synchronization matrix [START_REF] Pedone | Phoneme-level text to audio synchronization on speech signals with background music[END_REF]. H φ Y and D are to be estimated.

The synchronization matrix D is constrained to be nonzero only within a vertical band of size B around an initial synchronization path found by a Dynamic Time Warping (DTW) algorithm [START_REF] Ellis | Dynamic time warp (DTW) in Matlab[END_REF] applied on the Mel-Frequency Cepstral Coefficients (MFCC) representations of the example and the mixture (see Fig. 4, bottomleft subplot). This constraint means that only a small desynchronization (whose maximal amplitude is specified by B) from the initial DTW path is allowed. Thanks to the property of the multiplicative update rules [START_REF] Févotte | Nonnegative matrix factorization with the Itakura-Saito divergence. With application to music analysis[END_REF] we use for parameter estimation (see section 4.2 below) to keep zero parameters unchanged, to maintain such a constraint it is enough to simply initialize matrix D as such. We have found experimentally in [START_REF] Magoarou | Textinformed audio source separation using nonnegative matrix partial co-factorization[END_REF] that this strategy was the best among other tested strategies, and the influence of the bandwidth B on the separation performance is studied experimentally in section 5.3.1 below.

It is worth noting that the above assumptions are reasonable since the mixture and the example contain utterances of the same sentences. The final NMPCF model is as follows:

V Y ≈ VY = W e H e Y ⊙ W φ H φ Y ⊙ w c Y i T N ′ , V X ≈ VX = W e H e S ⊙ W φ H φ Y D ⊙ w c S i T N + W B H B , (8)
where pre-defined and fixed parameters are W e , i T N ′ and i T N (in green), shared and estimated parameters are W φ and H φ Y (in red), and non-shared and estimated parameters are the others (in black). These couplings are visualized on Fig. 3. To summarize, the parameters to be estimated are3 :

θ = H e Y , H e S , E φ , H φ Y , D, e c Y , e c S , H B , W B , (9)
while W e , P, i T N and i T N ′ are pre-defined and fixed.

Structural constraints on the model parameters

We consider further constraints on the matrices constituting the spectral model in order to better fit the physical phenomena. It would for example make sense to constrain the speech to have only one active fundamental frequency at time, and also only one active phoneme at each time. These types of constraints can be translated within our modeling by allowing only one non-zero entry in each column of the matrices H e Y , H e S and H φ Y , respectively (see Fig. 4, top-right and middleright subplots). Such constraints have been considered in [START_REF] Ozerov | A general flexible framework for the handling of prior information in audio source separation[END_REF] under the name of Gaussian Scaled Mixture Model (GSMM).

In the same spirit, we can also further constrain the synchronization matrix D by allowing only one path from the top-left to the bottom-right corner to be nonzero (see Fig. 4, bottom-right subplot). This constraint means that we still allow a desynchronization of the path in D from the initial DTW path, but we require it to be monotonous as a DTW. Let us stress however that this constraint is not equivalent to setting the bandwidth B = 1, the desired non-zero path in D being still allowed to vary within a bandwidth B ≥ 1 around the initial DTW path. We call this constraint "D-Struct" below.

We study the influence of all these constraints on the separation performance and show experimental results in section 5.3.3 below.

Source reconstruction via Wiener filtering

Given the NMPCF model parameters θ (Eq. ( 9)) estimated, as described in the following section, a speech source STFT estimate Ŝ ∈ C F ×N is computed by the standard Wiener filtering as:

Ŝ = VS / VX ⊙ X, ( 10
)
where all the operations are element-wise, X is the mixture STFT; and VS and VX are computed, respectively, as in ( 3) and ( 4), given θ. A background source estimate is simply computed as B = X -Ŝ, and the corresponding time signals may then be obtained through inverse STFT using an adequate overlap-add procedure with dual synthesis window.

Fig. 4 Illustration of new structural constraints on matrices H e Y (only one pitch can be active at time), H φ Y (only one phoneme can be pronounced at time and D (the alignment between the example and the speech in the mixture must be monotonous). Matrices without (as those in Fig. 3) and with structural constraints are represented in the left and right columns, respectively.

Parameter estimation

This section is devoted to the estimation of model parameters θ summarized in Eq. [START_REF] Durrieu | Musical audio source separation based on user-selected F0 track[END_REF]. We first introduce the optimization cost in section 4.1. We then provide the corresponding Multiplicative Update (MU) rules in section 4.2 and describe some hints so as to how the structural constraints presented in Section 3.5 can be taken into account during the estimation process.

Cost function

The general principle of NMF-like parameter estimation is to minimize certain cost function measuring a divergence between the data matrix and its structural approximation. We consider here the Itakura-Saito (IS) divergence 4 and specify the cost function as follows:

C(θ) = F,N f,n=1 d IS (v X,f n |v X,f n )+λ F,N ′ f,n=1 d IS (v Y ,f n |v Y ,f n ) , (11)
where λ ∈ R + is a trade-off parameter that determines the example's influence on the estimation, 4 When applied to power spectrograms of audio signals, IS divergence was shown as one of the most suitable choices for NMF-like decompositions [START_REF] Févotte | Nonnegative matrix factorization with the Itakura-Saito divergence. With application to music analysis[END_REF], in particular thanks to its scale invariance property.

d IS (a|b) = a/b -log (a/b) -1 is the IS divergence, v Y ,f n , v X,f n ,
vY ,f n and vX,fn are, respectively, entries of data matrices V Y , V X and their structural approximations VY , VX from (8).

Parameter estimation via MU rules

To optimize the cost [START_REF] Lefèvre | Semi-supervised NMF with time-frequency annotations for single-channel source separation[END_REF] we use standard multiplicative update (MU) rules which can be derived following a recipe described in [START_REF] Févotte | Nonnegative matrix factorization with the Itakura-Saito divergence. With application to music analysis[END_REF]. The idea is to derive MU rules based on the cost function's gradient with respect to each parameter. Most of the resulting updates are very similar to those described, e.g., in [START_REF] Ozerov | A general flexible framework for the handling of prior information in audio source separation[END_REF], and are as follows:

H e Y ← H e Y ⊙ W eT W φ Y H φ Y ⊙ w c Y i T N ′ ⊙ V.[-2] Y ⊙ V Y W eT W φ Y H φ Y ⊙ w c Y i T N ′ ⊙ V.[-1] Y (12)
H e S ← H e S ⊙ W eT W φ S H φ S ⊙ w c S i T N ⊙ V.[-2] X ⊙ V X W eT W φ S H φ S ⊙ w c S i T N ⊙ V.[-1] X (13)
E φ ← E φ ⊙ P T λ W e H e Y ⊙ w c Y i T N ′ ⊙ V.[-2] Y ⊙ V Y H φ Y T + W e H e S ⊙ w c S i T N ⊙ V.[-2] X ⊙ V X H φ S T P T λ W e H e Y ⊙ w c Y i T N ′ ⊙ V.[-1] Y H φ Y T + W e H e S ⊙ w c S i T N ⊙ V.[-1] X H φ S T (14)
H φ Y ← H φ Y ⊙ λW φ Y T W e H e Y ⊙ w c Y i T N ′ ⊙ V.[-2] Y ⊙ V Y +W φ S T W e H e S ⊙ w c S i T N ⊙ V.[-2] X ⊙ V X D T λW φ Y T W e H e Y ⊙ w c Y i T N ′ ⊙ V.[-1] Y +W φ S T W e H e S ⊙ w c S i T N ⊙ V.[-1] X D T (15)
D ← D ⊙ H φ Y T W φ S T W e H e S ⊙ w c S i T N ⊙ V.[-2] X ⊙ V X H φ Y T W φ S T W e H e S ⊙ w c S i T N ⊙ V.[-1] X (16)
e c Y ← e c Y ⊙ P T W e H e Y ⊙ W φ Y H φ Y ⊙ V.[-2] Y ⊙ V Y i N ′ P T W e H e Y ⊙ W φ Y H φ Y ⊙ V.[-1] Y i N ′ (17)
e c S ← e c S ⊙ P T W e H e S ⊙ W φ S H φ S ⊙ V.[-2] X ⊙ V X i N P T W e H e S ⊙ W φ S H φ S ⊙ V.[-1] X i N (18)
H B ← H B ⊙ W B T V.[-2] X ⊙ V X W B T V.[-1] X (19)
W B ← W B ⊙ V.[-2] X ⊙ V X H B T V.[-1] X H B T (20)
Let us just note that the updates of shared parameters (E φ and H φ Y ) take into account both data matrices (V Y and V X ), all other NMPCF model parameters, as well as the trade-off parameter λ.

Updates with structural constraints

Note that due to the property of MU rules to keep zero parameters unchanged, these rules are not directly applicable with the structural constraints introduced in section 3.5. Indeed, with these constraints one needs re-estimating on each iteration an appropriate support for the corresponding matrix, while MU rules would get stuck from the first iteration in one support.

As such for updating activation matrices H e Y , H e S and H φ Y , which correspond to the GSMM modeling [START_REF] Ozerov | A general flexible framework for the handling of prior information in audio source separation[END_REF], we adopt exactly the same strategy as in [START_REF] Ozerov | A general flexible framework for the handling of prior information in audio source separation[END_REF]. In summary, this strategy consists in first updating locally all the entries of one matrix using the corresponding update among ( 12), ( 13) and [START_REF] Wang | Chambers. Video assisted speech source separation[END_REF], and in choosing one entry per column yielding the highest likelihood while setting to zero all the other entries (see [START_REF] Ozerov | A general flexible framework for the handling of prior information in audio source separation[END_REF] for more details). This strategy guarantees a local optimization of the cost [START_REF] Lefèvre | Semi-supervised NMF with time-frequency annotations for single-channel source separation[END_REF] in the sense that the cost is guaranteed to remain non-increasing after each update.

Regarding the "D-Struct" constraint for the synchronization matrix D, we elaborated a similar process. Each entry of D within the admissible area, i.e., within the B-bandwidth around the initial DTW path (as such we also maintain the previous constraint), is first locally updated using equation ( 16), and the corresponding local log-likelihood are computed. A monotonous path maximizing the corresponding accumulated loglikelihoods is then computed using the same DTW implementation [START_REF] Ellis | Dynamic time warp (DTW) in Matlab[END_REF] we used previously. However, we must acknowledge that this optimization strategy is rather ad hoc, since does not guarantee local optimization of the cost [START_REF] Lefèvre | Semi-supervised NMF with time-frequency annotations for single-channel source separation[END_REF]. We believe that making it locally-optimal would be possible, e.g., by adopting a sort of Hidden Markov Model (HMM)-based decoding instead of the DTW. Nevertheless, we do not address this issue in this work and leave it for future investigation.

Experiments

All the experiments and / or results presented in this section are new, except the results of the baseline methods in Table 3 below that are as in our previous contribution [START_REF] Magoarou | Textinformed audio source separation using nonnegative matrix partial co-factorization[END_REF]. We first describe the data, the parameter settings and initialization. We then study the influence of some parameters and constraints on the source separation performance. We compare the proposed method with state-of-the-art algorithms in various settings. Finally we evaluate the potential of our method in term of speech alignment.

Data

We evaluate our approach on synthetic data which consists of three sets: the mixtures, the speech examples, and the training set needed for some baseline approaches. All audio signals are mono and sampled at 16000 Hz.

The mixture set consists of eighty different mixtures created as follows. Ten speech signals (five for male voice and five for female voice) in English corresponding to ten different sentences were randomly selected from the test subset of the TIMIT database [START_REF] Garofolo | DARPA TIMIT: Acoustic-phonetic continuous speech corpus[END_REF]. Each chosen speech signal was used to produce eight mixtures by adding to it either music or effect background. These background sounds were extracted from real movie audio tracks and the Signal (speech) to Noise (background) Ratios (SNRs) were set to four different values: -5 dB, 0 dB, 5 dB and 10 dB.

The example set is built in accordance to the mixture set. For each of ten TIMIT sentences, twelve corresponding speech examples were created. Two of them were produced via speech synthesizers (one with male voice and one with female voice). 5 Other eight examples were produced by human speakers: two by a female native English speaker, two by a male native English speaker, two by a female non-native speaker (Spanish), and two by a male non-native speaker (French). Each of these speakers produced two examples: the first example by just reading the sentence, and another one by reading the sentence, listening to the mixture, and trying to mimic it. The last two examples were taken from the TIMIT test database, but by different speakers: one male and one female. Note that this example set covers three of the four generating scenarios mentioned in section 2 and schematized on figure 2.

The training set, which is used only in several baselines, consists of one hundred spoken sentences from different speakers: fifty males and fifty females. These speech signals were randomly selected from the TIMIT train database.

Parameter setting and initialization

The STFT is computed using a half-overlapping sine window of length 32 ms (i.e, 512 samples). Each column of the F × I excitation dictionary matrix W e is set to a harmonic comb with a given fundamental frequency (pitch). The pitch is varied from 100 Hz to 400 Hz covering mostly frequency range of human speech, with an increment of 1/8 of a tone. The entries in the last column of W e are set to the same constant value for representing unvoiced sounds. These settings lead to I = 186 columns in W e . The F × L matrix P of spectral blobs, which is used to constrain the dictionary of phonemes and the time-invariant channel filters, is built following the auditory-motivated Equivalent Rectangular Bandwidth (ERB) scale [START_REF] Ozerov | A general flexible framework for the handling of prior information in audio source separation[END_REF]. In our experiment L is set to 55. The two matrices W e and P are computed using the Flexible Audio Source Separation Toolbox (FASST) [START_REF] Ozerov | A general flexible framework for the handling of prior information in audio source separation[END_REF] routines.

All parameters in ( 9) are randomly initialized by positive values, except the synchronization matrix D that is initialized as described in section 3.4 (see also Fig. 4, bottom-left subplot).

Influence of some parameters and constraints on source separation performance

We assess the performance of our approach on test data when certain parameters vary and setting various constraints in order to find a good configuration for comparing with state-of-the-art methods. Source separation performance is measured by two well-known metrics: the Signal to Distortion Ratio (SDR) criterion [START_REF] Vincent | Performance measurement in blind audio source separation[END_REF] and the Overall Perceptual Score (OPS) criterion [START_REF] Emiya | Subjective and objective quality assessment of audio source separation[END_REF] computed for the target speech source only.

Study the of influence of trade-off parameter λ and bandwidth B

While the trade-off parameter λ determines the level of guidance by the example, the bandwidth B allows different level of variation in the synchronization between speech example and the mixture signal. We vary these two parameters in our experiment to assess source separation performance as follow:

Source separation performance as a function of bandwidth B. We test our algorithm on the full database mentioned in section 5.1 with different values of B ranging from 1 to 30, and the results are shown in Fig. 5 for both the SDR and the OPS, as well as for low SNRs (-5 dB and 0 dB) and high SNRs (5 dB and 10 dB). We see that for the SDR, there are slight variations (within 0.7 dB) and the maximum of the results averaged over all SNRs is reached for B = 15. On the contrary for the OPS, we have a monotone performance increase, and it seems that taking a higher B results in better performance. In our opinion such a behavior can be explained as follows. When the separation is less guided by the example (higher value of B) the reconstructed signal is less constrained and more smooth, which is translated by a better perceptual score. We have fixed B = 15 in all following experiments.

Source separation performance as a function of tradeoff parameter λ. In this section, in addition to the conventional strategy where the trade-off parameter λ is constant, we also investigate a new strategy where λ is gradually decreasing through the algorithm's iterations starting with some value λ 0 and ending with 0. We hope that such a constraint relaxation strategy (the example's influence virtually disappears with λ = 0) would lead to a better performance, at least for the perceptual score (OPS). We evaluate our algorithm on the full database with different values of constant λ and decreasing λ starting from λ 0 . The results are shown in Fig. 6, where the values of λ and λ 0 are also made proportional to N/N ′ in order to normalize for a possible difference between the mixture length N and the example length N ′ (for a consistent visualization on Fig. 6 we introduce the parameters

λ ′ = λ × N ′ /N and λ ′ 0 = λ 0 × N ′ /N ).
First it should be noted that, in contrast to our expectations, the decreasing λ strategy performs almost the same as the constant λ strategy in terms of both the SDR and the OPS measures, This observation shows that the coupling between the mixture and the speech example is mostly important during the first iterations of the algorithm, i.e., it is not very important whether this constraint is kept or relaxed at the end. This is possibly because the coupling with the speech example is essentially needed to drive a good mixture model initialization. Moreover, we see that the variations of the SDR are quite subtle, but the optimal average performance is reached in two point corresponding to the two different λ variation strategies. In all further experiments we chose the decreasing trade-off parameter strategy with initial λ 0 = 8.5× N N ′ . Now if we look at the OPS, we see that the lower the trade-off parameter, the better the performances, and it is possibly because of the same reason than for the bandwidth. Indeed, a lower trade-off parameter corresponds to a smaller amount of guidance by example.

Study the effect of the channel filter

Within the proposed NMPCF-based framework this experiment studies the effectiveness of newly introduced excitation-filter-channel (EFC) speech model compared to the existing excitation-filter (or source-filter) model used in most existing works [START_REF] Virtanen | Analysis of polyphonic audio using source-filter model and non-negative matrix factorization[END_REF][START_REF] Durrieu | Source/filter model for unsupervised main melody extraction from polyphonic audio signals[END_REF]. For that purpose, we compare the source separation performance achieved using the proposed EFC model and that obtained using the excitation-filter model (named EF). The implementation of this EF model within the proposed NMPCFbased approach is simply achieved by fixing channel vectors w c Y and w c S to be vectors of ones (see Eq. ( 8)) and by skipping their updates (in fact the updates of e c Y and e c S ) in the MU rules described in section 4.2. The evaluation is done on the full database and the results are summarized in Table 1. We clearly see that the mod- eling of channel information greatly improves the overall performance in both low SNR and high SNR conditions, especially in terms of SDR. It is explained by the fact that the channel part of the model captures the time-invariant part of the filter, and whereas in the EF configuration this time-invariant part is shared between the mixture and the model, it is not shared in the EFC configuration where they share only the time-varying part. It is indeed logic to share only the time-varying part between the two models because it really corresponds to the linguistic part of the speech, whereas the time-invariant part corresponds to the recording conditions and intrinsic characteristics of the speaker's vocal tract. The speaker of the example and the one of the mixture are not recorded in the same conditions and they may have very different intrinsic characteristics, thus forcing the time-invariant part of the filter to be the same in the two models would lead to a too strong constraint.

Method

Study the influence of structural constraints

In this section we investigate structural constraints introduced in section 3.5. The configuration in which the matrices H e Y , H e S and H φ Y are constrained to have only one non-zero entry per column is called GSMM. This setting means that we allow the model of the speech in the mixture and the model of the example to use only one pitch at a time, as well as only one phoneme spectral envelope at a time. The configuration in which we allow only one monotonous path to be non-zero in the matrix D is called D-Struct. This setting means that the synchronization matrix maps the frames dynamically along the iterations, and it can be viewed as resynchronizing at each iteration. For the D-Struct configuration we initialize D by doing a DTW and then we allow the path to vary in a band of width B = 15 around this initial path. We compared these two configurations with the basic NMPCF-based unconstrained method (the one described in section 3.4) and the results are shown in Table 2. We see that the D-Struct configuration leads to a decrease of performance. On the other hand, the GSMM configuration improves the performance in terms of the SDR, and especially for low SNRs, i.e., when the separation is difficult. This means that for a more difficult separation problem (low SNR as opposed to high SNR) a more constrained model is beneficial. Finally, in line with our previous observations the best OPS is always achieved by the most unconstrained model, i.e., the basic NMPCF.

Multichannel case

We extended our method to the multichannel case by combining the proposed NMPCF-based spectral model with the spatial model described in [START_REF] Duong | Underdetermined reverberant audio source separation using a full-rank spatial covariance model[END_REF]. This is actually quite straightforward since the proposed single-channel approach acts only in the spectral domain, whereas the one from [START_REF] Duong | Underdetermined reverberant audio source separation using a full-rank spatial covariance model[END_REF] acts only in the spatial domain. Therefore, in the same spirit as it is done in the general source separation framework from [START_REF] Ozerov | A general flexible framework for the handling of prior information in audio source separation[END_REF], the two can simply be "plugged" together to be used jointly. This extension to the multichannel case was done to participate in the Signal Separation Evaluation Campaign (SiSEC 2013). Due to lack of space the corresponding results as well as the those of other SiSEC 2013 participants are omitted here. However the interested reader can always find them in [START_REF] Ono | The 2013 signal separation evaluation campaign[END_REF].

Comparison with different state-of-the-art methods

In this section we compare the performance of the proposed approach with several relevant baselines and stateof-the-art methods.

Baselines non-informed by example The following approaches use neither speech example nor text information 6 :

-NMF: A standard NMF-based method with a general voice spectral dictionary W S ∈ R F ×J + (J = 128) which is first learned on the training set described in Section 5.1, and then fixed during the parameter estimation. 6 We implemented these approaches with help of the FASST [START_REF] Ozerov | A general flexible framework for the handling of prior information in audio source separation[END_REF].

-EFC-N: A method using the EFC mixture model [START_REF] Simsekli | Score guided musical source separation using generalized coupled tensor factorization[END_REF] in a non-supervised manner, as in [START_REF] Durrieu | Source/filter model for unsupervised main melody extraction from polyphonic audio signals[END_REF], i.e., filter matrices W φ S and H φ S are left free and not coupled with the example. In other words, this method corresponds to the proposed approach with λ = 0 in [START_REF] Lefèvre | Semi-supervised NMF with time-frequency annotations for single-channel source separation[END_REF].

-EFC-S: A method using the EFC mixture model [START_REF] Simsekli | Score guided musical source separation using generalized coupled tensor factorization[END_REF], which however is not supervised by example any more, but by our training data. In this approach filter dictionary W φ S is pre-learned on the training set and then fixed during parameter estimation, while H φ S is updated.

Baseline informed by example

We also consider as a baseline the SbH PLCA-based method [START_REF] Smaragdis | Separation by "humming": User-guided sound extraction from monophonic mixtures[END_REF], within the proposed general workflow, as shown on Fig. 1. Since the mixture V X and the example V Y are not aligned in general, we used V ′ Y = V Y D 0 as example for SbH, where D 0 is the initial synchronization computed with DTW as described in section 3.4. In other words, D 0 is the initial matrix D with B = 1. The SbH itself was implemented following [START_REF] Smaragdis | Separation by "humming": User-guided sound extraction from monophonic mixtures[END_REF]. This baseline is referred hereafter as SbH-DTW.

We compare these baseline methods with different configurations of our method, namely the most simple NMPCF configuration and the GSMM configuration. Table 3 shows average results for different mixture types in terms of both the SDR and the OPS measures.

We can see that the proposed method gives better average results than all the baselines, and especially on the mixtures with low SNRs (difficult cases). These results confirm that textual information is relevant to improve source separation performances. Indeed, it is not surprising that our method performs better than the NMF baseline, which is very basic and does not use a specific model for the speech signal. The fact that our method performs better than the EFC-N baseline indicates that having a speech example is more important for source separation than having a general speech model. Furthermore, the fact that our approach exhibits better performances than the EFC-S baselines is interesting, because it shows that the linguistic information contained in the example matters, and that it is not sufficient to have a general speech model. Finally, our method performs better than the SbH-DTW baseline, and it shows that it is advantageous to model explicitly the time and frequency variations between the example and the speech in the mixture. Moreover, we have a feeling that if the alignment between the mixture and the speech example were improved, the results would be even better.

Finally, an investigation of the performance of the proposed basic NMPCF-based method with respect to the example type variations (e.g., same vs. different gender between the target and the example speech, native vs. non-native speaker, human vs. speech synthesizer, etc.) can be found in our preliminary study [START_REF] Magoarou | Textinformed audio source separation using nonnegative matrix partial co-factorization[END_REF].

Speech alignment evaluation

This experiment aims at evaluating the temporal alignment between the mixture and the speech example resulted from our algorithm. This alignment is reflected in the final estimate of the synchronization matrix D and can be decoded using the DTW as in [START_REF] Pedone | Phoneme-level text to audio synchronization on speech signals with background music[END_REF]. Let us first define a ground truth and a performance measure for this task. All speech signals from the TIMIT database are supplied with the corresponding phonetic transcriptions that can be used as a ground truth for the alignment evaluation. Therefore, for this evaluation we have used the subsets of our mixture and example sets (see Sec. 5.1) corresponding to the signals from TIMIT. As for the performance measure, we considered D as a time warping matrix (we decoded a path in it, like in the DTW) and evaluated the proportion of time where D maps phonetically correctly the two sequences, based on the TIMIT transcriptions. This gave us a number between 0 and 1 that we called alignment score. We evaluated this score for different settings of our algorithm (those of the previous subsection), and compared it to the initial DTW (on the MFCCs with euclidean distance). Results are shown in Table 4. One can see that, unfortunately and somehow surprisingly, none of the considered advanced methods provides better alignment result than a very simple DTW used for the initialization. This is possibly due to the fact that our method was designed to perform source separation and not alignment in the first place, and alignment is just a by-product of the method. However, these results are interesting and we believe that improving the estimation of the alignment between the mixture and the speech example would lead to a further improvement of source separation performance of our approach. We leave this potential study for future work.

Conclusion

In this paper, we presented an informed speech source separation approach that takes into account the available textual information to guide the separation process via generation of a speech example. We proposed a novel NMPCF modeling framework that allows to efficiently handle different types of variations between the speech example and the speech in the mixture. We also extended the framework to allow incorporation of some novel so-called structural constraints that have quite natural physical motivation. We studied extensively the influence of some key model parameters and constraints on the separation quality. We have found that newly proposed GSMM structural constraints applied to both the excitation and the filter activations improves the results. Moreover, the experimental results over various settings confirm the benefit of the proposed approach over both the non-informed NMF-based baseline methods and a SbH state-of-the-art algorithm [START_REF] Smaragdis | Separation by "humming": User-guided sound extraction from monophonic mixtures[END_REF]. We have also evaluated several configurations of the proposed approach in terms of the alignment accuracy between the target speech and the example speech. We have found that none of the proposed advanced approaches improves the alignment accuracy over a basic DTW applied to the MFCC representations of the example and the mixture. Finally, we extended the method to multichannel mixtures and entered into the Signal Separation Evaluation Campaign (SiSEC 2013) [START_REF] Ono | The 2013 signal separation evaluation campaign[END_REF]. Future work will consist in exploiting some parameters of speech example NMF decomposition as hyper parameters of a prior distribution to guide the separation process. We also plan investigating within the proposed framework the so-called soft co-factorization strategies [START_REF] Seichepine | Soft nonnegative matrix co-factorizationwith application to multimodal speaker diarization[END_REF], where the the coupled matrices are not shared exactly, but only approximately. Finally, we will look for more appropriate algorithmic strategies for "D-Struct" constraint decoding (e.g., some strategies based on HMM decoding), and we will look for better alignment approaches to use for the synchronization matrix initialization.

Fig. 1

 1 Fig. 1 General workflow of the proposed approach.

Fig. 2

 2 Fig. 2 Possible ways of speech example production.

Fig. 3

 3 Fig.3NMPCF model for the speech example and the mixture.

Fig. 5

 5 Fig. 5 Performance evolution with respect to bandwidth B. The results are given for two performance measures: the SDR (top) and the OPS (bottom). Left column: the average over low SNRs (-5 dB and 0 dB), middle column: the average over high SNRs (5 dB and 10 dB), and right column: the average over all SNRs.

Fig. 6

 6 Fig. 6 Performance evolution with respect to constant tradeoff parameter λ (solid line) and decreasing trade-off parameter λ starting from λ 0 (dotted line). The results are given for two performance measures: the SDR (top) and the OPS (bottom). Left column: the average over low SNRs (-5 dB and 0 dB), middle column: the average over high SNRs (5 dB and 10 dB), and right column: the average over all SNRs.

Table 1

 1 Influence of the channel presence on the average performance. Results are shown in the form of SDR | OPS measure and the highest value of each column is in bold.

		low SNR	high SNR	Avg
	EF	0.09 | 26.7	4.58 | 28.7	2.33 | 27.7
	EFC	2.65 | 27.7	11.15 | 33.3	6.90 | 30.5

Table 2

 2 Influence of structural constraints on the average performance. Results are shown in the form of SDR | OPS measure and the highest value of each column is in bold.

	Method	low SNR	high SNR	Avg
	NMPCF	2.65 | 27.7	11.15 | 33.3	6.90 | 30.5
	"D-Struct"	1.32 | 27.7	8.10 | 31.0	4.71 | 29.4
	GSMM	4.44 | 25.1	10.36 | 27.9	7.40 | 26.5

Table 4

 4 Alignment score of different configurations. The highest value of each column is in bold.

	Method	low SNR	high SNR	Avg
	DTW	0.58	0.66	0.62
	NMPCF	0.39	0.39	0.39
	"D-Struct"	0.48	0.53	0.51
	GSMM	0.41	0.45	0.43

Table 3

 3 Comparison of different configurations of the proposed method with different baselines. Results are shown in the form of SDR|OPS measures and the highest value of each column is in bold.

		Method	-5dB	Speech + Music 0dB 5dB	10dB	-5dB	Speech + Effects 0dB 5dB	10dB	Avg
	Baselines	NMF EFC-N EFC-S SbH	-2.60|20.1 -1.82|24.3 -2.83|23.1 -2.21|10.5	2.22|19.8 3.07|23.4 2.34|22.8 3.40|14.6	7.05|18.7 8.38|22.9 7.19|23.0 6.80|17.4	11.58|20.0 11.74|22.1 11.73|20.8 7.97|21.3	-3.39|26.7 -1.38|24.9 -3.45|25.1 1.05|20.6	0.66|27.6 5.15|23.0 1.40|26.1 5.63|27.5	4.96|30.4 10.74|23.7 5.95|26.9 8.21|31.2	11.61|33.2 13.70|24.4 10.48|27.5 9.56|32.0	4.01|24.5 6.20|23.6 4.10|24.4 5.05|21.9
		NMPCF	-0.74|24.4	4.27|28.2	8.83|31.6	12.29|34.0	0.67|27.4	6.40|30.6	10.36|32.7	13.11|34.7	6.90|30.4
		GSMM	2.22|22.6	6.52|25.2	9.67|27.2	11.16|28.7	2.18|25.6	6.84|27.1	9.43|27.6	11.18|28.2	7.40|26.5

NMPCF model[START_REF] Simsekli | Score guided musical source separation using generalized coupled tensor factorization[END_REF] is a particular case of a more general generalized coupled tensor factorization (GCTF) model that was used as well for informed source separation[START_REF] Kim | Nonnegative matrix partial co-factorization for spectral and temporal drum source separation[END_REF].

The proposed EFC model is a new extension of the excitation-filter model[START_REF] Durrieu | Source/filter model for unsupervised main melody extraction from polyphonic audio signals[END_REF].

Keep in mind that W φ = PE φ , w c S = Pe c S and w c Y = Pe c Y .

We used "ivona" synthesizers www.ivona.com/en/ to create speech examples.

Acknowledgements The authors would like to thank S. Ayalde, F. Lefebvre, A. Newson and N. Sabater for their help in producing the speech examples, as well as the anonymous reviewers for their valuable comments.


Luc Le Magoarou

Rémi Gribonval

Strategies to learn computationally efficient and compact dictionaries

Dictionary learning is a branch of signal processing and machine learning that aims at expressing some given training data matrix as the multiplication of two factors: one dense matrix called dictionary and one sparse matrix being the representation of the data in the dictionary. The sparser the representation, the better the dictionary. However, manipulating the dictionary as a dense matrix can be computationally costly both in the learning process and later in the usage of this dictionary, thus limiting dictionary learning to relatively small-scale problems. In this paper we consider a general structure of dictionary allowing faster manipulation, and give an algorithm to learn such dictionaries over training data, as well as preliminary results showing the interest of our approach.

Introduction

The use of a dictionary to sparsely represent a certain type of data goes back to almost two centuries with the Fourier transform that was designed to sparsely represent heat flow at that time [START_REF] Fourier | Théorie analytique de la chaleur[END_REF]. The Fourier and the Hadamard transforms, as well as the wavelets to cite just a few rely on a "simple" mathematical formula that has been shown to yield fast algorithms [START_REF] Cooley | An algorithm for the machine calculation of complex fourier series[END_REF][START_REF] Mallat | A theory for multiresolution signal decomposition : the wavelet representation[END_REF].

On the other hand, more recently have arisen algorithms that learn a dictionary directly over training data, without using an analytical formula (see [START_REF] Rubinstein | Dictionaries for Sparse Representation Modeling[END_REF] and references therein for a survey on the topic). They consider some data matrix X ∈ R d×n , which is the collection of n training vectors x i ∈ R d , and can be approximated sparsely in a certain dictionary:

X ≈ DΓ, (1)
Γ having sparse columns. Such algorithms provide dictionaries that are well adapted to the data but they do not lead to fast algorithms because of the lack of structure of the dictionary, and storing D as a dense matrix may be impractical. Bridging the gap between analytical dictionaries that are not necessarily well adapted to the data at hand but lead to fast algorithms, and learnt dictionaries that are very well adapted to the data but do not lead to fast algorithms is an important challenge. The dictionary learning community started recently to tackle the problem, mainly in [START_REF] Rubinstein | Double sparsity: learning sparse dictionaries for sparse signal approximation[END_REF] and [START_REF] Chabiron | Toward Fast Transform Learning[END_REF], where the authors introduced new dictionary structures. The model we introduce below generalizes these works, as we will see in Sec.2.

In this paper we build on the very simple observation that the fast algorithms used to apply analytical transforms like the FFT or the DWT can be seen as consecutive multiplications of the input vector by sparse matrices. This fact implies that the analytical dictionaries associated with such fast transforms can be expressed as a product of sparse matrices, that is 1 :

D = M j=1 S j . ( 2
)
This structure is precisely what makes possible the appearance of fast algorithms (such as the butterfly FFT for example). 1 The product being taken from left to right:

N i=1 A i = A 1 • • • A N
Knowing that, it makes sense to learn a dictionary that has this form and is the product of several sparse matrices, making it intrinsically fast and easier to store. The problem at hand is unfortunately highly non-convex and the sparsity constraint is non-smooth, but recent advances in optimization like the algorithm proposed in [START_REF] Bolte | Proximal alternating linearized minimization for nonconvex and nonsmooth problems[END_REF] can be adapted to such problems with convergence guarantees as we will show in the next sections.

Model and optimization problem

Notation Throughout this paper, matrices are denoted by bold uppercase letters: A. Vectors are denoted by bold lowercase letters: a. The ith column of a matrix A is denoted by: a i . Sets are denoted by calligraphical symbols: A.

As stated in the introduction, we propose a new dictionary structure that intrinsically leads to fast algorithms although the dictionary is learnt over some training data. Our goal is to find a dictionary that sparsely represent the data, being itself a multiplication of sparse matrices.

The matrix factorization point of view

Let D ∈ R d×a be our dictionary with a atoms and Γ ∈ R a×n the corresponding sparse representation matrix such that X ≈ DΓ. In order to meet the requirements and be intrinsically fast, D must take the form of equation [START_REF] Bolte | Proximal alternating linearized minimization for nonconvex and nonsmooth problems[END_REF], where the S j s are sparse matrices in R aj ×aj+1 with a 1 = d and a M +1 = a. Now if we say that Γ is now called S M +1 for ease of notation, our goal is to find the sparse factors S j s such that:

X ≈ M +1 j=1 S j . (3)
We see with this equation that our structured dictionary learning problem amounts to a factorization of the data matrix into M + 1 sparse factors. Actually, this model is quite general and can encompass those introduced in [START_REF] Rubinstein | Double sparsity: learning sparse dictionaries for sparse signal approximation[END_REF] and [START_REF] Chabiron | Toward Fast Transform Learning[END_REF] as we will see. Such a multifactor representation of a data matrix has been introduced in the NMF framework in [START_REF] Lyu | On algorithms for sparse multifactor nmf[END_REF], for deep learning in [START_REF] Arora | Provable bounds for learning some deep representations[END_REF][START_REF] Neyshabur | Sparse matrix factorization[END_REF] and statistics in [START_REF] Lee | Treelets -an adaptive multi-scale basis for sparse unordered data[END_REF][START_REF] Cao | The sparse matrix transform for covariance estimation and analysis of high dimensional signals[END_REF].

Optimization objective

The proposed structured dictionary learning problem can be expressed as a constrained optimization problem. In its most general form, it can be stated as follows:

Minimize

Sj ,∀j∈{1•••M +1} X - M +1 j=1 S j 2 F Subject to S j ∈ U j , ∀j ∈ {1 • • • M + 1}, (4)
where the U j s are the sets in which each factor should lie.

In [START_REF] Rubinstein | Double sparsity: learning sparse dictionaries for sparse signal approximation[END_REF], the authors propose to constrain each atom of the dictionary to be a sparse linear combination of the atoms of a so-called base dictionary. This base dictionary is assumed to be asociated with a fast algorithm (it takes the form of equation ( 2)), thus leading to fast manipulation of the whole learnt dictionary. It is actually equivalent to solving the problem (4) with the M -1 leftmost factors being known (the base dictionary), S M and S M +1 = Γ to estimate, and U M and U M +1 denoting sparsity constraints. They give an algorithm to estimate jointly the dictionary and the representation. However, such a structure constrains the dictionary to be close to the base dictionary and thus does not provide full adaptability.

In [START_REF] Chabiron | Toward Fast Transform Learning[END_REF], the authors constrain each atom in the dictionary to be the composition of several circular convolutions with sparse kernels, thus leading again to fast manipulation of the learnt dictionary. They give an algorithm to estimate the dictionary knowing the representation and the support of each kernel. It is actually equivalent to solving the problem (4) with S M +1 being known, U i , ∀i ∈ {1 • • • M } denoting the intersection of sparsity constraints with the set of circulant matrices, and the support of each factor being known.

We propose to handle problem (4) in a more general form, namely we will not assume that any factor is known, and we will consider any U i s provided that we are able to perform the projection onto it (note that in practice, only the U i s that are included in the set of sparse matrices will be of interest).

Algorithm

We propose to apply an algorithm stemming from recent advances in non-convex and non-smooth optimization to problem (4). The algorithm is introduced in [START_REF] Bolte | Proximal alternating linearized minimization for nonconvex and nonsmooth problems[END_REF] and called PALM (Proximal Alternating Linearized Minimization). PALM is made to handle objective functions that take the form:

Ψ(x 1 , . . . , x p ) := p i=1 f i (x i ) + H(x 1 , . . . , x p ), (5)
where each x i ∈ R ni is a block of variables, H is only assumed to be C 1 and the f i s are only assumed to be proper and lower-semicontinuous (possibly indicator functions of constraint sets). The idea behind PALM is to alternate updates between different blocks of variables (Gauss-Seidel), performing a proximal gradient step for each block. PALM is guaranteed to converge to a critical point of the objective function. Problem ( 4) is obviously non-convex and thus the algorithm introduced in this paper is not guaranteed to converge toward the global minimum. Adapting PALM to the structured dictionary learning problem we just introduced is quite straightforward. One option is to take each S j as a block of variables, so that H is the objective function of problem ( 4) and the f i s are the indicator functions of the sets U j . The proximal operator of the indicator function of a set X reducing to the projection operator onto this set P X (.), the adaptation of PALM to our problem is given in Algorithm 1, where c i j is a stepsize depending on the Lipschitz modulus of the gradient ∇ Sj H (see [START_REF] Bolte | Proximal alternating linearized minimization for nonconvex and nonsmooth problems[END_REF] for more details).

Algorithm 1 PALM for structured dictionary learning

for i ∈ {1 • • • N iter} do for j ∈ {1 • • • M + 1} do Set S i+1 j = P Uj S i j -1 c i j ∇ Sj H S i+1 1 . . .S i j . . .S i M +1
end for end for [START_REF] Cao | The sparse matrix transform for covariance estimation and analysis of high dimensional signals[END_REF]

One practical example

Choosing the sets of constraints U j is crucial in order to avoid as much as possible local minima, but in order to have a fast dictionary, they have to be subsets of the following (set of k jsparse matrices in R aj ×aj+1 ):

S aj ×aj+1 kj = {U ∈ R aj ×aj+1 : aj+1 i=1 u i 0 0 ≤ k j }. (6)
In further work, we intend to set constraints such as the combination of sparsity and orthogonality, or some sort of structured sparsity, because we observed that the factorizations of the most famous analytical dictionaries are of this type. However in this paper we will consider the simplest constraints, namely we just want the matrices S j s to have at most k j nonzero entries. This means that we will have U j = S aj ×aj+1 kj . In this simple configuration, the projection operator P Uj (.) is simply the hard thresholding operator that sets all but the k j greatest entries (in absolute value) to zero.

Complexity savings In the setting we just described, the multiplication of a vector by the dictionary or its adjoint (and its storage) would cost O( M j=1 k j ) operations instead of O(da) operations for a dictionary without structure. The interest here is twofold: first at the learning stage since this algorithm requires multiplications by the dictionary at each iteration, second at the usage stage since it involves again multiplications by the dictionary and its adjoint. It is thus necessary to tune M and the k j s in order to have a significant complexity gain, namely M j=1 k j ≪ da. For example in the FFT case with d = a = 2 P , P ∈ N, the dictionary is factorized into M = log 2 d factors that are all 2d-sparse, thus we perform multiplication in O(2d. log 2 d) operations instead of O(d 2 ).

Preliminary result

We are still testing different settings for the algorithm, but it shows promising results in tasks such as denoising. To illustrate this, we present an example of result with d = 8, a = 20, n = 100, M = 3, k 4 = 100, k 1 = k 2 = k 3 = 20 and N iter = 1000. We generated randomly some data matrix X 0 following the model of equation ( 3) and we added white Gaussian noise B with a signal-to-noise ratio of 6dB to obtain X = X 0 +B. We ran Algorithm 1 in order to obtain X0 . We repeated the experiment 100 times and got an output signalto-noise ratio of 7.7dB in average. We also made the interesting though expected observation that in approximation task (when we just want to factorize some matrix in sparse factors), there is a trade-off between sparsity of the factors and expressiveness of their product: the more non-zero entries we allow, the better the performances are, but the complexity is also increased.

Conclusion

In this abstract, we first presented the dictionary learning problem and the growing concern in the community to make it more computationally efficient. We then introduced a new model that is a generalization of two previously existing ones and that leads to intrinsically fast dictionaries. We presented an algorithm with convergence guarantees to a stationary point that is able to learn such type of dictionary over some training data. We finished by showing briefly some preliminary results of our approach. In the future, we intend to set new configurations for this method. We could for example modify the constraints in order to avoid as much as possible the numerous local minima inherent to the problem.