Amira Essaid

Arnaud Martin

Grégory Smits

Boutheina Ben Yaghlane

Uncertainty in Ontology Matching: a Decision Rule-based Approach

Keywords: Theory of belief functions, decision rule, Jousselme distance, ontology matching

Considering the high heterogeneity of the ontologies published on the web, ontology matching is a crucial issue whose aim is to establish links between an entity of a source ontology and one or several entities from a target ontology. Perfectible similarity measures, considered as sources of information, are combined to establish these links. The theory of belief functions is a powerful mathematical tool for combining such uncertain information. In this paper, we introduce a decision process based on a distance measure to identify the best possible matching entities for a given source entity.

Introduction

This paper proposes a decision rule based on a distance measure. This rule calculates the distance between a combined mass function and a categorical mass function and keep the hypotheses with the lowest distance. We propose this rule for its ability to give decision on composite hypotheses as well as its convenience to our domain of application, namely the semantic web and particularly the ontology matching where decision making is an important step.

Ontology matching is the process of finding for each entity of a source ontology O 1 its corresponding entity in a target ontology O 2 . This process can focus on finding simple mappings (1:1) or complex mappings (1:n or n:1). The first consists in matching only one entity of O 1 with only one entity of O 2 whereas the second consists in finding either for one entity of O 1 its multiple correspondences of entities in O 2 or matching multiple entities of O 1 with only one entity of O 2 . We are interested in this paper in finding simple mappings as well as the complex one of the form (1:n).

The matching process is performed through the application of matching techniques which are mainly based on the use of similarity measures. Since no similarity measure applied individually is able to give a perfect alignment, the exploitation of the complementarity of different similarity measures can yield to a better alignment. Combining these similarity measures may raise conflicts between the different results which should be modeled and resolved.

We suggest to use the theory of belief functions [START_REF] Dempster | Upper and Lower Probabilities Induced by a Multivalued Mapping[END_REF][START_REF] Shafer | A Mathematical Theory of Evidence[END_REF] as a tool for modeling the ontology matching and especially for combining the results of the different similarity measures. Due to the fact that we are working on an uncertain aspect and we are interested in finding complex matching which can be viewed as finding composite hypotheses formed from entities of two ontologies, we suggest to apply our proposed decision rule on the combined information and to choose for each entity of the source ontology, the entities of the target ontology with the lowest distance.

The remainder of this paper is organized as follows: we are interested in section 2 in defining the ontology matching process. In section 3, we recall the basic concepts underlying the theory of belief functions. In section 4, we present our decision rule based on a distance measure. Section 5 is devoted to the description of the credibilistic decision process for matching ontologies as well as the application of our proposed decision rule. Section 6 discusses an overview of some ontology matching approaches dealing with uncertainty. Finally, we conclude in section 7 and present future work.

Ontology Matching

The open nature of the semantic web [START_REF] Berners-Lee | The Semantic Web[END_REF] tends to encourage the development, for a domain of interest, of heterogeneous ontologies which differ from each other at the terminological level and/or the representational one. In order to mitigate the effect of semantic heterogeneity and to assure interoperability between applications that make use of these ontologies, a key challenge is to define an efficient and reliable matching between ontologies [START_REF] Euzenat | Ontology Matching[END_REF].

Formally, ontology matching is defined as a function A = f(O 1 , O 2 , A', p, r). In fact, from a pair of ontologies to match O 1 and O 2 , an input alignment A', a set of parameters p, a set of oracles and resources r, the function f returns an alignment A between these ontologies. We note that parameters and resources refer to thresholds and external resources respectively.

With the new vision of the web that tends to make applications understandable by machines, an automatic and semi automatic discovery of correspondences between ontologies is required. The reader may refer to [START_REF] Euzenat | Ontology Matching[END_REF] for an exhaustive state of the art of ontology matching techniques.

3 The Theory of Belief Functions

Definitions

The frame of discernment Θ = {θ 1 , θ 2 , . . . , θ n } is a finite non empty set of n elementary and mutually exclusive and exhaustive hypotheses related to a given problem. The power set of Θ, denoted by 2 Θ is defined as the set of singleton hypotheses of Θ, all possible disjunctions of these hypotheses as well as the empty set.

The basic belief assignment (bba) is the mapping from elements of the power set 2 Θ onto [0, 1] that satisfies:

m(∅) = 0, A⊆Θ m(A) = 1.
(

) 1
The value m(A) quantifies the part of belief exactly committed to the subset A of Θ.

A focal element A is an element of 2 Θ such that m(A) = 0. From a given bba , the corresponding credibility and plausibility functions are respectively defined as:

bel(A) = B⊆A,B =∅ m(B). (2)
and

pl(A) = A∩B =∅ m(B). (3)
The value bel(A) expresses the total belief that one allocates to A whereas the pl(A) quantifies the maximum amount of belief that might support a subset A of Θ.

Some special bbas are defined in the theory of belief functions. Among them, the categorical bba which is a bba with a unique focal element different from the frame of discernment Θ and the empty set ∅, and which is defined as m X (X) = 1.

Combination of Belief Functions

Let S 1 and S 2 be two distinct and independent sources providing two different bbas m 1 and m 2 defined on the same frame of discernment Θ. These two bbas are combined by either the conjunctive rule of combination or the disjunctive rule.

-The conjunctive rule of combination is used when the two sources are fully reliable. This rule is defined in [START_REF] Smets | The Combination of Evidence in the Transferable Belief Model[END_REF] as :

m 1 ∩ 2 (A) = B∩C=A m 1 (B) × m 2 (C). (4)
The conjunctive rule can be seen as an unnormalized Dempster's rule of combination [START_REF] Dempster | Upper and Lower Probabilities Induced by a Multivalued Mapping[END_REF] which is defined by:

m 1⊕2 (A) =            B∩C=A m 1 (B) × m 2 (C) 1- B∩C=∅ m 1 (B) × m 2 (C) ∀A ⊆ Θ, A = ∅ 0 if A = ∅ (5)
The Dempster's rule of combination is normalized through 1-B∩C=∅ m 1 (B)× m 2 (C) and it works under the closed world assumption where all the possible hypotheses of the studied problem are supposed to be enumerated on Θ. -The disjunctive rule is used when at least one of the sources is reliable without knowing which one of them. It is defined in [START_REF] Smets | The Combination of Evidence in the Transferable Belief Model[END_REF] by:

m 1 ∪ 2 (A) = B∪C=A m 1 (B) × m 2 (C). ( 6
)

Decision Making

Combining information provided by the different sources leads to a global one that has to be analyzed in order to choose the most likely hypothesis. Decision making can be held in two different ways.

-Decision on singletons: It means that the most likely solution to a given problem is one of the hypothesis of Θ. To determine this most likely solution, one may:

• Maximize the credibility: It consists on retaining the most credible hypothesis by giving the minimum of chances to each of the disjunctions. • Maximize the plausibility: It consists on retaining the most plausible hypothesis by giving the maximum of chances to each of the singletons. • Maximize the pignistic probability: It was introduced in [START_REF] Smets | Decision Making in the TBM: the Necessity of the Pignistic Transformation[END_REF] and it is the common used decision function because it represents a compromise between the maximum of credibility and the maximum of plausibility.

The pignistic probability consists on choosing the most probable singleton hypothesis by dividing the mass attributed to each hypothesis, different from the singleton hypothesis, by the hypotheses composing it.

It is given for each

A ∈ 2 Θ , A = ∅ by: betP (X) = A∈2 Θ ,X∈A m(A) |A|(1 -m(∅)) . ( 7
)
where |A| represents the cardinality of A. -Decision on unions of singletons: Few works were interested in making decision on composite hypotheses ( [START_REF] Denoeux | Analysis of Evidence-theoretic Decision Rules for Pattern Classification[END_REF], [START_REF] Appriou | Approche Générique de la Gestion de l'Incertain dans les Processus de Fusion Multisenseur[END_REF], [START_REF] Martin | Decision Support with Belief Functions Theory for Seabed Characterization[END_REF]). The approach proposed in [START_REF] Appriou | Approche Générique de la Gestion de l'Incertain dans les Processus de Fusion Multisenseur[END_REF] helps to choose a solution of a given problem by considering all the elements contained in 2 Θ . This approach weights the decision functions listed previously by an utility function depending on the cardinality of the elements.

For each A ∈ 2 Θ we have:

A = argmax X∈2 Θ (m d (X)pl(X)) (8)
where m d is a mass defined by:

m d (X) = K d λ X ( 1 |X| r ) (9)
r is a parameter in [0, 1] for choosing a decision. When r is equal to 0 it reflects a total indecision and when it is equal to 1 it means that we decide on a singleton. The value λ X is used to integrate the lack of knowledge about one of the elements X of 2 Θ . K d is a normalization factor.

Decision Rule Based on a Distance Measure

We aim in this paper to propose a decision rule helping us to choose the most likely hypothesis for a given problem after combining the information provided by different sources of information, i.e. bbas. This rule, based on a distance measure, is inspired from [START_REF] Smarandache | Contradiction Measures and Specificity Degrees of Basic Belief Assignments[END_REF] and is defined as:

A = argmin(d(m, m X )) (10)
The proposed rule aims at calculating the distance between m which is a combined bba (obtained after applying a combination rule) and m X is the categorical bba of X such that X ∈ 2 Θ . The most likely hypothesis to choose is the hypothesis whose categorical bba is the nearest to the combined bba.

In order to make a decision:

-First, we have to identify the elements for which we have to construct the categorical bba. In fact, we choose to work on elements of 2 Θ such that the cardinality of the element is less or equal to 2. This filtering is due to the fact that we want to limit the number of elements to be considered especially with a power set 2 Θ of large cardinality. -Then, we construct the categorical bba for each of the selected element.

-Finally, we calculate the distance between the combined bba and each of the categorical bbas. The minimum distance is kept and our decision corresponds to the categorical bba's element having the lowest distance with the combined bba.

For the calculation of the distance between the bbas, we use the Jousselme distance [START_REF] Jousselme | A New Distance Between Two Bodies of Evidence[END_REF] which is specific to the theory of belief functions because of the matrix D defined on 2 Θ . This distance has the advantage to take into account the cardinality of the focal elements. This distance is defined for two bbas m 1 and m 2 as follows:

d(m 1 , m 2 ) = 1 2 (m 1 -m 2 ) t D(m 1 -m 2 ) ( 11
)
where D is a matrix based on Jaccard distance as a similarity measure between focal elements. This matrix is defined as:

D(A, B) = 1 if A=B=∅ |A∩B| |A∪B| ∀A, B ∈ 2 Θ (12)
To illustrate the proposed decision rule, we take the following example. Let's consider the frame of discernment Θ = {θ 1 , θ 2 , θ 3 }. The list of elements for which we have to construct their categorical bba are {θ 1 , θ 2 , θ 3 , θ 1 ∪ θ 2 , θ 1 ∪ θ 3 , θ 2 ∪ θ 3 }. Suppose that we have two sources S 1 and S 2 providing two different bbas m 1 and m 2 defined on the frame of discernment Θ. The table 1 illustrates these two bbas as well as their combined bba obtained after applying the Dempster's rule of combination.

(θ1) = 0.4 m2(θ2) = 0.2 m comb (θ1) = 0.3478 m1(θ2 ∪ θ3) = 0.2 m2(Θ) = 0.8 m comb (θ2) = 0.1304 m1(Θ) = 0.4 m comb (Θ) = 0.3478 m comb (θ2 ∪ θ3) = 0.1739
The application of our proposed decision rule gives the results illustrated in table 2 where it shows for every element the distance obtained between the categorical bba of this element and the combined bba. Based on the results obtained in table 2, the most likely hypothesis to choose is the element θ 1 ∪ θ 2 .

Credibilistic Decision Process for Ontology Matching

In [START_REF] Essaid | Processus de Décision Crédibiliste pour l'Alignement des Ontologies[END_REF], we proposed a credibilistic decision process for ontology matching. In the following, we describe this process occurring mainly in three steps, then we will apply the proposed decision rule in order to find a correspondence for a given entity of the source ontology.

1-Matching ontologies:

We apply three name-based techniques (Levenshtein distance, Jaro distance and Hamming distance) for matching two ontologies O 1 and O 2 related to conference organization1 . We have the following results: This table shows that using the levenshtein distance, the entity Conference-Member matches to Conference fees with a confidence value of 0.687.

2-Modeling the matching under the theory of belief functions:

We are interested here in modeling the matching results obtained in the previous step under the theory of belief functions.

-Frame of discernment : It contains all the entities of the target ontology O 2 for which a corresponding entity in the source ontology O 1 exists. -Source of information: Every correspondence established by one of the matching techniques is considered as an information given by a source. -Basic Belief Assignments (bba): Once we get all the correspondences, we keep only those where an entity source e 1 ∈ O 1 has a correspondence when applying the three techniques. Then, we construct for each of the selected correspondence its mass function. The similarity measure obtained after applying a matching technique is interpreted as a mass. Due to the fact that for a source of information, the sum of mass functions has to be equal to 1, a mass will be affected to the total ignorance. Let's take the results illustrated in Table 3. In this table, we have information provided by three different sources respectively denoted by S e1 lev , S e1 jars and S e1 hamming , where e 1 = Conf erenceM ember. The bba related to the source S e1 lev is: m •

m e1 comb (Conf erence f ees) = 0.2849 • m e1 comb (Conf erence) = 0.5853 • m e1 comb (Θ) = 0.1298
3-Decision Making: Based on the combined bba which takes into account all the information provided by the different sources, we will be able in this step to choose for each entity of the source ontology its corresponding in the target ontology. For example, for the entity ConferenceMember, we will be able to decide if we have to match it with Conference fees or Conference or simply we will not have a precise decision but rather an uncertain one where we can match ConferenceMember to Conf erence f ees∪Conf erence. We are interested in our credibilistic process to get an uncertain decision. For this purpose, we apply our proposed decision rule. First, we construct the categorical bba of elements having a cardinality equal to 2. For the example illustrated in figure 1 we have:

-m(conf erence document ∪ conf erence) = 1 -m(conf erence ∪ conf erence f ees) = 1 -m(conf erence volume ∪ committee) = 1 -. . .
Then we calculate the distance between the combined bba obtained previously and each of the categorical bba. Our best alignment corresponds to the nearest element to the combined bba in other words the element whose categorical bba has the minimum distance with the combined bba. For the entity ConferenceMember of the ontology O 1 we find conf erence f ees ∪ conf erence with a distance equal to 0.52. This process is repeated for each entity of the source ontology in order to identify the most significant correspondences in the target ontology.

Related Works

Only few ontology matching methods have considered that dealing with uncertainty in a matching process is a crucial issue. We are interested in this section to present some of them where the probability theory [START_REF] Pan | A bayesian network approach to ontology mapping[END_REF] and the Dempster-Shafer theory ( [START_REF] Besana | A Framework for Combining Ontology and Schema Matchers with Dempster Shafer[END_REF], [START_REF] Nagy | DSSIM-Ontology mapping with uncertainty[END_REF], [START_REF] Wang | Combining Uncertain Outputs from Multiple Ontology Matchers[END_REF]) are the main mathematical models used. In [START_REF] Pan | A bayesian network approach to ontology mapping[END_REF], the authors proposed an approach for matching ontologies based on bayesian networks which is an extension of the BayesOWL. The BayesOWL consists in translating an OWL ontology into a bayesian network (BN) through the application of a set of rules and procedures. In order to match two ontologies, first the source and target ontologies are translated into BN 1 and BN 2 respectively. The mapping is processed between the two ontologies as an evidential reasoning between BN 1 and BN 2 . The authors assume that the similarity information between a concept C 1 from a source ontology and a concept C 2 from a target ontology is measured by the joint probability distribution P(C 1 , C 2 ).

In [START_REF] Besana | A Framework for Combining Ontology and Schema Matchers with Dempster Shafer[END_REF], the author viewed ontology matching as a decision making process that must be handled under uncertainty. He presented a generic framework that uses Dempster-Shafer theory as a mathematical model for representing uncertain mappings as well as combining the results of the different matchers. Given two ontologies O 1 and O 2 , the frame of discernment represents the Cartesian product e x O 2 where each hypothesis is the couple < e, e i > such as e ∈ O 1 and e i ∈ O 2 . Each matcher is considered as an expert that returns a similarity measure converted into a basic belief mass. The Dempster rule of combination is used to combine the results provided by a matcher. The pairs with plausibility and belief below a given threshold are discarded. The remaining pairs represent the best mapping for a given entity.

Although, the authors in [START_REF] Nagy | DSSIM-Ontology mapping with uncertainty[END_REF] handle uncertainty in the matching process, their proposal differ from that proposed in [START_REF] Besana | A Framework for Combining Ontology and Schema Matchers with Dempster Shafer[END_REF]. In fact, they use the Dempster-Shafer theory in a specific context of question answering where including uncertainty may yield to better results. Not like in [START_REF] Besana | A Framework for Combining Ontology and Schema Matchers with Dempster Shafer[END_REF], they did not give in depth how the frame of discernment is constructed. In addition to that, uncertainty is handled only once the matching is processed. In fact, the similarity matrix is constructed for each matcher. Based on this matrix, the results are modeled using the theory of belief functions and then they are combined.

In [START_REF] Wang | Combining Uncertain Outputs from Multiple Ontology Matchers[END_REF], the authors focused on integrating uncertainty when matching ontologies. The proposed method modeled and combined the outputs of three ontology matchers. For an entity e ∈ O 1 , the frame of discernment Θ is composed of mappings between e and all the concepts in an ontology O 2 . The different similarity values obtained through the application of the three matchers are interpreted as mass values. Then, a combination of the results of the three matchers is performed.

Conclusion and Perspectives

In this paper, we proposed a decision rule based on a distance measure. This decision rule helps to choose the most likely hypothesis for a given problem. It is based on the calculation of the distance between a combined bba and a categorical bba. We apply this rule in our proposed credibilistic decision process for the ontology matching. First, we match two ontologies. Then, the obtained correspondences are modeled under the theory of belief functions. Based on the obtained results, a decision making is performed by applying our proposed decision rule.

In the future, we aim at applying other matching techniques. We are interested also in constructing an uncertain ontology based on the obtained results after a decision making and handling experimentations to qualitatively assess the relevance of our approach.

S e 1 lev( 1 lev( 1 hamming(

 111 Conf erence f ees) = 0.687 and m S e 1 lev (Θ) = 1 -0.687 = 0.313. The bbas for the other sources are constructed in the same manner. -Combination: Let's resume the obtained bbas of the three sources. We have: • m S e Conf erence f ees) = 0.687 and m S e 1 lev (Θ) = 0.313 • m S e 1 jaro (Conf erence) = 0.516 and m S e 1 jaro (Θ) = 0.484 • m S e Conf erence) = 0.625 and m S e 1 hamming (Θ) = 0.375 Once we apply the Dempster's rule of combination, we obtain the following results:

Table 1 .

 1

		bba1 and bba2 and their combined bba
	bba1	bba2	combined bba
	m1

Table 2 .

 2 Results of the proposed decision rule

	Element Distance
	θ1	0.537
	θ2	0.647
	θ3	0.741
	θ1 ∪ θ2 0.472
	θ1 ∪ θ3 0.536
	θ2 ∪ θ3 0.529

Table 3 .

 3 Results of matching the entity ConferenceMember of O1 with entities of O2

	method	e2 ∈ O2	n
	Levenshtein Conf erence f ees 0.687
	Jaro	Conf erence	0.516
	Hamming	Conf erence	0.625

http ://oaei.ontologymatching.org/2013/conference/index.html


Luc Le Magoarou

Rémi Gribonval

CHASING BUTTERFLIES: IN SEARCH OF EFFICIENT DICTIONARIES

Keywords: Sparse representations, dictionary learning, low complexity, image denoising

Dictionary learning aims at finding a frame (called dictionary) in which training data admits a sparse representation. Traditional dictionary learning is limited to relatively small-scale problems, because dense matrices associated to high-dimensional dictionaries can be costly to manipulate, both at the learning stage and when using this dictionary for tasks such as sparse coding. In this paper, inspired by usual fast transforms, we consider a dictionary structure allowing cheaper manipulation, and we propose a learning algorithm imposing this structure. The approach is demonstrated experimentally with the factorization of the Hadamard matrix and on image denoising.

INTRODUCTION

Sparse representations using dictionaries are a common way of providing concise descriptions of high-dimensional vectors. With an appropriate dictionary D, one can find a sparse representation vector γ such that a vector x of interest can be approximated as x ≈ Dγ.

Traditionally, one can distinguish two ways of choosing a good dictionary for the data at hand. The dictionary can be either an analytic dictionary derived from a mathematical formula, such as the Fourier and Hadamard transforms or wavelets, or a learned dictionary, that is automatically inferred from training data. Analytic dictionaries are in general computationally efficient because of associated fast algorithms (e.g., the Fast Fourier Transform (FFT) [START_REF] Cooley | An algorithm for the machine calculation of complex Fourier series[END_REF] or the Discrete Wavelet Transform (DWT) [START_REF] Mallat | A theory for multiresolution signal decomposition : the wavelet representation[END_REF]), but in turn they lack adaptation to the data. On the other hand, learned dictionaries are in general better adapted to the data, but being dense matrices they are costly to manipulate. A survey on the topic can be found in [START_REF] Rubinstein | Dictionaries for Sparse Representation Modeling[END_REF].

In this paper the goal is to design dictionaries that are as well adapted to the data as learned dictionaries, while as fast to manipulate and as cheap to store as analytic ones. Generalizing approaches introduced recently in [START_REF] Rubinstein | Double sparsity: learning sparse dictionaries for sparse signal approximation[END_REF] and [START_REF] Olivier Chabiron | Toward fast transform learning[END_REF], we propose here a strategy to tackle this problem, that may seem unrealistic at first. We build on the simple observation that the fast transforms associated with analytic dictionaries can be seen as sequences of cheap linear transformations, indicating that such dictionaries can be expressed as 1 :

D = M j=1 Sj, (1)
where each factor Sj is sparse. For example, each step of the butterfly radix-2 FFT can be seen as a product with a sparse matrix having only two non-zero entries per row and column, which leads to the well-known complexity savings. The proposed approach consists in imposing this multi-layer sparse dictionary structure. With sparse enough factors, this potentially brings efficiency in terms of:

• Storage: The dictionary can be stored efficiently.

• Speed: The dictionary and its transpose can quickly multiply vectors and matrices. • Statistical relevance: Learning the dictionary requires fewer training examples because there are fewer parameters to estimate. Our goal is thus to "chase butterflies", i.e., to learn such dictionaries that somehow extend the butterfly structure of the FFT.

PROBLEM FORMULATION AND RELATED WORK

Notation. Throughout this paper, matrices are denoted by bold upper-case letters: A; vectors by bold lower-case letters: a; the ith column of a matrix A by: ai; and sets by calligraphical symbols: A. The standard vectorization operator is denoted by vec(•). The 0- norm is denoted by • 0 (it counts the number of non-zero entries),

• F denotes the Frobenius norm, and • 2 the spectral norm. By abuse of notations, A 0 = vec(A) 0. I is the identity matrix.

Objective. The goal of this paper is to obtain dictionaries structured as in [START_REF] Cooley | An algorithm for the machine calculation of complex Fourier series[END_REF]. To this end, we can either impose the multi-layer sparse structure while learning the dictionary (multi-layer sparse dictionary learning task), or impose it on a pre-learned dictionary (multi-layer sparse dictionary factorization task). Let X ∈ R d×n be a data matrix, each of its n columns xi being a training vector, D ∈ R d×a be a dictionary with a atoms and Γ ∈ R a×n be the corresponding sparse representation matrix such that X ≈ DΓ. Typically n a ≥ d. In this framework, multi-layer sparse dictionary learning boils down to a factorization of the data matrix X into M + 1 sparse factors (the rightmost factor being the sparse representation matrix Γ), while multi-layer sparse dictionary factorization reduces to a factorization of the dictionary D into M sparse factors. These two problems are very similar, and introducing the matrix Y to embody the matrix to factorize (X or D) and the integer Q to embody the desired number of factors, we propose to consider one general optimization problem:

Minimize S 1 ,...,S Q Y - Q j=1 Sj 2 F + Q j=1 gj(Sj), (2)
where the gjs are penalties promoting sparsity and possibly additional constraints, and the factors Sjs are of compatible sizes. We call (2) the Multi-layer Sparse Approximation (MSA) problem. Related work. Similar matrix factorization problems have been studied recently in several domains. In dictionary learning, two main lines of work have begun to explore this way. In [START_REF] Rubinstein | Double sparsity: learning sparse dictionaries for sparse signal approximation[END_REF], the authors propose the sparse-KSVD algorithm (KSVDS) to learn a dictionary whose atoms are sparse linear combinations of atoms of a so-called base dictionary. The base dictionary should be associated with a fast algorithm (it takes the form (1)), so that the whole learned dictionary can be efficiently stored and manipulated. It can be seen as having the Q-2 leftmost factors fixed in (2) (let us call it Dbase), the second factor being the sparse representation of the dictionary over the base dictionary (D = DbaseS2), and the first being the sparse representation matrix Γ = S1. One drawback with this formulation is that the learned dictionary is highly biased toward the base dictionary, which decreases adaptability to the training data. In [START_REF] Olivier Chabiron | Toward fast transform learning[END_REF], the authors propose to learn a dictionary in which each atom is the composition of several circular convolutions using sparse kernels with known supports, so that the dictionary is fast to manipulate. Their problem can be seen as ( 2), with the gjs corresponding to the M leftmost factors imposing sparse circulant matrices. This formulation is limited in nature to the case where the dictionary is well approximated by a product of sparse circulant matrices.

In statistics, a related problem is to approximately diagonalize a covariance matrix by a unitary matrix in factorized form [START_REF] Cooley | An algorithm for the machine calculation of complex Fourier series[END_REF], which can be addressed greedily [START_REF] Lee | Treeletsan adaptive multi-scale basis for sparse unordered data[END_REF][START_REF] Guangzhi Cao | The sparse matrix transform for covariance estimation and analysis of high dimensional signals[END_REF] using a fixed number of elementary Givens rotations. Here we consider a richer family of sparse factors and leverage recent non-convex optimization techniques. In machine learning, similar models were explored with various points of view. For example, sparse multi-factor NMF [START_REF] Lyu | On algorithms for sparse multifactor NMF[END_REF] can be seen as solving problem (2) with the Kullback-Leibler divergence as data fidelity term and all Sjs constrained to be non-negative. Optimization relies on multiplicative updates, while we rely on proximal iterations. In the context of deep neural networks, identifiability guarantees on the network structure have been established with a generative model where consecutive network layers are sparsely connected at random, and non-linearities are neglected [START_REF] Neyshabur | Sparse matrix factorization[END_REF][START_REF] Arora | Provable bounds for learning some deep representations[END_REF]. The network structure in these studies matches the factorized structure (1), with each of the leftmost factors representing a layer of the network and the last one being its input. Apart from its hierarchical flavor, the identification algorithm in [START_REF] Neyshabur | Sparse matrix factorization[END_REF][START_REF] Arora | Provable bounds for learning some deep representations[END_REF] differs from the proximal method proposed here.

An objective somewhat related to that of having a computationally efficient dictionary is that of being able to rapidly compute the sparse code Γ corresponding to the training data X given the dictionary D. Models addressing this issue have been proposed in [START_REF] Gregor | Learning fast approximations of sparse coding[END_REF] and [START_REF] Sprechmann | Learning efficient sparse and low rank models[END_REF]. Since most of sparse coding methods rely on products with the dictionary and its transpose, the method proposed here contributes also to this objective because dictionaries taking the form (1) naturally lead to fast vector and matrix multiplication.

OPTIMIZATION FRAMEWORK

We now express the considered optimization problem, and describe an algorithm with convergence guarantees to a stationary point.

Choice of the sparsity-inducing penalties

Considering a dictionary D = M j=1 Sj as in (1), the storage and multiplication cost of the dictionary are determined by the number of non-zero entries in the factors Sj. Indeed, storing/multiplying the dictionary in the factorized form will cost O( M j=1 Sj 0 ), whereas classical dictionary learning methods would typically provide dense dictionaries for which storing/multiplying would cost O(da). This simple statement allows to introduce the Relative Complexity (RC):

RC(D) := M j=1 Sj 0 /da. ( 3
)
This quantity is clearly positive and should not exceed 1 in order to yield complexity savings. In practice, we choose as sparsityinducing penalties the indicator functions δE j (•) of subsets Ejs of " 0 balls": {A ∈ R r j ×c j : A 0 ≤ pj}, hence RC ≤ M j=1 pj/da.

Coping with the scaling ambiguity.

To avoid scaling ambiguities, it is common [START_REF] Olivier Chabiron | Toward fast transform learning[END_REF][START_REF] Lyu | On algorithms for sparse multifactor NMF[END_REF] to normalize the factors and introduce a multiplicative scalar λ in the data fidelity term. This results in the optimization problem:

Minimize λ,S 1 ,...,S Q Ψ(S1, . . . , SQ, λ) := 1 2 Y -λ Q j=1 Sj 2 F + Q j=1 δE j (Sj), (4)
with Ej = {A ∈ R r j ×c j : A 0 ≤ pj, A F = 1}.

Proposed algorithm

The optimization problem ( 4) is highly non-convex, and the sparsity enforcing part is non-smooth. We leverage recent advances in non-convex optimization to express an algorithm with convergence guarantees to a stationary point of the problem. In [START_REF] Bolte | Proximal Alternating Linearized Minimization for nonconvex and nonsmooth problems[END_REF], the authors consider cost functions depending on N blocks of variables:

Ψ(x1, . . . , xN ) := H(x1, . . . , xN ) + N j=1 fj(xj), (5)
where the function H is smooth, and the fjs are proper and lower semi-continuous. To handle this cost function, the authors propose an algorithm called Proximal Alternating Linearized Minimization (PALM) [START_REF] Bolte | Proximal Alternating Linearized Minimization for nonconvex and nonsmooth problems[END_REF], that updates alternatively each block of variable by a proximal (or projected in our case) gradient step. PALM can be instantiated to handle the objective (4): there is indeed a match between (4) and ( 5) taking N = Q + 1, xj = Sj for j ∈ {1 . . . Q}, xQ+1 = λ, H the data fidelity term, fj(•) = δE j (.) for j ∈ {1 . . . Q} and fQ+1(•) = 0 (there is no constraint on λ). Although we do not discuss it here, it is shown in our technical report [START_REF] Le | Learning computationally efficient dictionaries and their implementation as fast transforms[END_REF] that all the conditions for PALM to converge to a stationary point of the objective are satisfied. Projection operator P E j . With Ejs defined as in Section 3.2, the projection operator PE j (•) simply keeps the pj greatest entries (in absolute value) of its argument, sets all the other entries to zero, and then normalizes its argument so that it has unit norm. Regarding the scalar λ, we can consider its constraint set as EQ+1 = R, hence the projection operator is simply the identity mapping, P R (x) = x. Gradient and Lipschitz moduli. To specify the iterations of PALM specialized to our problem, we fix the iteration i and the factor j, and denote S i j the factor that we are updating,

L := Q k=j+1 S i k what is on its left and R := j-1 k=1 S i+1
k what is on its right (with the convention k∈∅ S k = I). With these notations we have, when updating the jth factor Sj:

H(S i+1 1 , . . . , S i+1 j-1 , S i j , . . . , S i Q , λ i ) = 1 2 Y-λ i LS i j R 2 F .
The gradient of this smooth part of the objective with respect to the jth factor reads:

∇ S i j H(S i+1 1 , . . . , S i+1 j-1 , S i j , . . . , S i Q , λ i )=λ i L T (λ i LS i j R-Y)R T ,
which has a Lipschitz modulus with respect to S i F :

Lj(L, R, λ i ) = (λ i ) 2 R 2 2 . L 2 2 .
Once the first Q factors are updated we need to update λ. Denoting Ŷ = Q k=1 S i+1 k , we get:

H(S i+1 1 , . . . , S i+1 Q , λ i ) = 1 2 Y -λ i Ŷ 2
F , and the gradient with respect to λ reads:

∇ λ i H(S i+1 1 , . . . , S i+1 Q , λ i ) = λ i Tr( ŶT Ŷ) -Tr(Y T Ŷ).
An explicit version of the algorithm is given in Algorithm 1, in which the factors are updated alternatively by a projected gradient step (line 6) with a stepsize controlled by the Lipschitz modulus of the gradient (line 5). We can solve for λ directly at each iteration (line 9) because of the absence of constraint on it (see our report [START_REF] Le | Learning computationally efficient dictionaries and their implementation as fast transforms[END_REF] for more precisions on the convergence conditions of PALM). Initialization. Except when specified otherwise, initialization by default is done with λ 0 = 1, S 0 1 = 0 and S 0 j = I, j ≥ 2, with the convention that for rectangular matrices the identity has ones on the main diagonal and zeroes elsewhere.

Algorithm 1 PALM for Multi-layer Sparse Approximation (palm4MSA) Input: Data matrix or dictionary Y; desired number of factors Q; constraint sets Ej, j ∈ {1 . . . Q}; initialization {S 0 j } Q j=1 , λ 0 ; stopping criterion (e.g., number of iterations Ni). 1: for i = 0 to Ni -1 do 2:

for j = 1 to Q do 3: L ← Q k=j+1 S i k 4: R ← j-1 k=1 S i+1 k 5: Set c i j > (λ i ) 2 R 2 2 . L 2 2 6: S i+1 j ← PE j S i j -1 c i j λ i L T (λLS i j R -Y)R T 7:
end for 8:

Ŷ ← Q k=1 S i+1 k 9: λ i+1 ← Tr(Y T Ŷ)
Tr( ŶT Ŷ)

10: end for Output: The estimated factorization:

λ N i ,{S N i j } Q j=1 = palm4MSA(Y, Q, {Ej} Q j=1 , . . . )

Practical strategy

Algorithm 1 presented above factorizes a data matrix into Q sparse factors and converges to a stationary point of problem (4). However, while we are primarily interested in stationary points where the data fidelity term of the cost function is small, there is no guarantee that the algorithm converges to such a stationary point. This was observed on a very simple experiment where Algorithm 1 was used for a dictionary factorization task, with a dictionary Y = D with a known factorization in M factors: D = M j=1 Sj, such as the Hadamard dictionary. The naive approach consisted in taking directly Q = M in Algorithm 1, and setting the constraints so as to reflect the actual sparsity of the true factors. This simple strategy performed quite poorly in practice, and the attained local minimum was very often not satisfactory (high data fidelity term).

We noticed experimentally that taking fewer factors (Q small) and allowing more non-zero entries per factor led to better results in general. This observation suggested to adopt a hierarchical strategy. Indeed, when Y = Q j=1 Sj is the product of Q sparse factors, it is also the product Y = T1S1 of 2 factors with T1 = Q j=2 Sj, so that S1 is sparser than T1. Our strategy is then to factorize the input matrix Y in 2 factors, one being sparse (corresponding to S1), and the other less sparse (corresponding to T1). The process can then be repeated on the less sparse factor T1, and so on until we attain the desired number Q of factors. Denoting T k = Q j=k+1 Sj, a simple calculation shows that if we expect each Sj to have roughly O(h) non-zero entries per row, then T k cannot have more than O(h Q-(k+1) ) non-zero entries per row. This suggests to decrease exponentially the number of non-zero entries in T k with k. This strategy turns out to be surprisingly effective and the attained local minima are very good, as illustrated in the next section. In a sense, this hierarchical approach is similar to learning a deep neural network layer by layer, as done in [START_REF] Neyshabur | Sparse matrix factorization[END_REF][START_REF] Arora | Provable bounds for learning some deep representations[END_REF]. Our preliminary theoretical analysis of the proposed approach suggests that the results of [START_REF] Neyshabur | Sparse matrix factorization[END_REF][START_REF] Arora | Provable bounds for learning some deep representations[END_REF] could in fact be leveraged to explain the observed empirical success.

The proposed hierarchical strategy is summarized in Algo-rithm 2, where we need to specify at each step the constraint sets related to the two factors. For that, let us introduce some notation: E k will be the constraint set for the right factor and Ẽk the one for the left factor at the kth factorization. The global optimization step (line 5) is done by initializing palm4MSA with the current values of {Sj} k j=1 and T k . It is here to keep an attach to the data matrix Y. Roughly we can say that line 3 of the algorithm is here to yield complexity savings, whereas line 5 is here to improve data fidelity.

Algorithm 2 Hierarchical factorization

Input: The data matrix or dictionary Y, the desired number of factors Q and the constraint sets

E k and Ẽk , k ∈ {1 . . . Q -1}. 1: T0 ← Y 2: for k = 1 to Q -1 do 3: Factorize the residual T k-1 into 2 factors: λ ,{F2, F1} = palm4MSA(T k-1 , 2, { Ẽk , E k }, . . . ) 4: T k ← λ F2 and S k ← F1 5: Global optimization: λ, T k , {Sj} k j=1 = palm4MSA(Y, k + 1, Ẽk , {Ej} k j=1 , . . . ) 6: end for 7: SQ ← TQ-1 Output: The estimated factorization λ,{Sj} Q j=1 .
In the case of structured dictionary learning, the first factor S1 corresponds to the sparse coefficients matrix Γ, and the first iteration of factorization (k = 1) amounts to classical dictionary learning. It can thus be done with any classical dictionary learning method, such as K-SVD. Moreover, to avoid manipulating the coefficient matrix (which is often way bigger than the other factors) one can keep it fixed, and update it only by Orthogonal Matching Pursuit (OMP) [START_REF] Mallat | Matching pursuits with timefrequency dictionaries[END_REF] after the global optimization step (between lines 5 and 6). This simple modification of Algorithm 2 makes the hierarchical strategy look like a traditional dictionary learning algorithm [START_REF] Rubinstein | Dictionaries for Sparse Representation Modeling[END_REF] where update of the coefficients and update of the dictionary alternate, except that in the present case the dictionary update is different and seeks to make complexity savings (reducing RC), and the coefficient update can be done efficiently taking advantage of the dictionary structure.

EXPERIMENTS 4.1. Dictionary based image denoising

Our experimental scenario for the structured dictionary learning task follows the workflow of a classical dictionary based image denoising. First, n = 10000 patches xi of size 8 × 8 (dimension d = 64) are randomly picked from an input 512 × 512 noisy image (with PSNR= 22.1dB), and a dictionary is learned on these patches. Then the learned dictionary is used to denoise the entire input image by computing the sparse representation of all its patches in the dictionary using OMP, allowing each patch to use 5 dictionary atoms. The image is reconstructed by averaging the overlapping patches. Various dictionary learning methods were compared, each learning a four times overcomplete dictionary (D ∈ R 64×256 ). Settings of our algorithm. We tested several configurations for Algorithm 2, and we present here one that exhibits a good tradeoff between relative complexity (RC) and adaptation to the data (we call it MSA for Multi-layer Sparse Approximation). Inspired by usual fast transforms, we chose a number of factors Q close to the logarithm of the signal dimension d = 64, here Q = 5. The sizes of the factors are: Γ = S1 ∈ R 256×10000 , S2 ∈ R 64×256 and S3, . . . , SQ ∈ R 64×64 . Algorithm 2 was used with the modifications presented in the previous section i.e. the first factorization (k = 1 in Algorithm 2) is done by KSVD [START_REF] Aharon | An algorithm for designing overcomplete dictionaries for sparse representation[END_REF] Baselines. We compared Algorithm 2 with the following methods. All methods involve a coefficient update step which is performed using OMP allowing each patch to use 5 dictionary atoms:

• KSVD [START_REF] Aharon | An algorithm for designing overcomplete dictionaries for sparse representation[END_REF]. We used the implementation described in [START_REF] Rubinstein | Efficient Implementation of the K-SVD Algorithm using Batch Orthogonal Matching Pursuit[END_REF], running 50 iterations (empirically sufficient to ensure convergence). • Online Dictionary Learning (ODL) [START_REF] Mairal | Online learning for matrix factorization and sparse coding[END_REF], running 200 iterations (empirically sufficient to ensure convergence). • Sparse KSVD (KSVDS) [START_REF] Rubinstein | Double sparsity: learning sparse dictionaries for sparse signal approximation[END_REF], a method that seeks to bridge the gap between learned dictionaries and analytic dictionaries. The implementation of [START_REF] Rubinstein | Double sparsity: learning sparse dictionaries for sparse signal approximation[END_REF] is used, with Dbase the four times overcomplete 2D-Discrete Cosine Transform (DCT) matrix and 50 iterations, ensuring convergence in practice. The columns of the estimated dictionary D are 6-sparse in Dbase. Performance measures. The computational efficiency of the dictionary is measured through the Relative Complexity (RC) quantity introduced in Section 3.1. For the KSVDS method, we used the formula provided in [START_REF] Rubinstein | Double sparsity: learning sparse dictionaries for sparse signal approximation[END_REF] to compute RC. The quality of approximation at the learning stage and at the denoising stage is expressed using the classical PSNR measure (even though at the learning stage we are manipulating patches and not entire images). Discussion of the results. Table 1 summarizes the performance of the different methods. First of all, the proposed method is able to provide dictionaries that are much more computationally efficient than the others (RC= 0.13). Second, and perhaps more surprisingly, while the proposed method performs worse than the others at the learning stage, it outperforms them at the denoising stage. This indicates that its generalization properties are better [START_REF] Gribonval | Sample Complexity of Dictionary Learning and other Matrix Factorizations[END_REF][START_REF] Vainsencher | The sample complexity of dictionary learning[END_REF][START_REF] Maurer | K -dimensional coding schemes in Hilbert spaces[END_REF], which is consistent with the lower number of parameters to learn compared to KSVD and ODL. Regarding KSVDS, its poorer performance may be explained by the fact that it is highly biased toward its base dictionary. Moreover, we suspect the proposed factorized structure to have the interesting property of being more intrinsically unable to fit noise than standard dictionaries.

Retrieving the fast Hadamard transform

Here is presented an experiment regarding the dictionary factorization task. Consider a data matrix Y = D with a known factorization

CONCLUSION

We proposed a matrix factorization framework with convergence guarantees that provides a flexible tradeoff between computational efficiency and data fidelity. It shows promising results in image denoising and is able to automatically retrieve an ideally compact factorization of the fast Hadamard transform. Besides the obvious need to better understand the role of its parameters in the control of the desired tradeoff, a particular challenge will be to leverage the gained complexity to speed up the factorization process itself, in order to efficiently learn efficient dictionaries. Moreover, the algorithm underlying the factorization is very general, and it would be interesting to take advantage of its versatility in order to incorporate other structures in the factors. This line of work could lead for example to learn data-driven efficient wavelets on graphs [START_REF] David | Wavelets on graphs via spectral graph theory[END_REF], by constraining the support of the factors. Finally, a concern in the numerical analysis community is to be able to approximate certain integral operators with a butterfly structure [START_REF] Michael | An algorithm for the rapid evaluation of special function transforms[END_REF][START_REF] Candès | A fast butterfly algorithm for the computation of Fourier integral operators[END_REF]. The method proposed in this paper could help finding automatically such approximate fast transforms.

  by OMP allowing each patch to use 5 dictionary atoms. In this setting, E1 and Ẽ1 do not need to be specified, but implicitly correspond to E1 = {A ∈ R 256×10000 , ai 0 ≤ 5 ∀i ∈ {1 . . . 10000}} and Ẽ1 = {A ∈ R 64×256 , ai 2 = 1 ∀i ∈ {1 . . . 256}}. Regarding the other factorizations (k > 1 in Algorithm 2) we allowed in each factor 4 non-zero entries per column in average, so that the considered constraint sets were:E2 = {A ∈ R 64×256 , A 0 ≤ 1024, A F = 1} and for k ∈ {3 . . . Q -1}: E k = {A ∈ R 64×64 , A 0 ≤ 256, A F = 1}.In order to decrease RC for the learned dictionary at each new factorization, the number of nonzero entries in the residual was divided by 2 at each step, starting from p = 1.3 × 2048, leading to, for k ∈ {2 . . . Q -1}:Ẽk = {A ∈ R 64×64 , A 0 ≤ p 2 k-2 , A F = 1}.The stopping criterion for palm4MSA was a number of iterations Ni = 50.

Fig. 1 .

 1 Fig. 1. Example of denoising result. It is a zoom on a small part of the "house" standard image. in M factors, D = M j=1 Sj: in Section 3.4, we evoked the failure of Algorithm 1 for this factorization problem. In contrast, Figure 2 illustrates the result of the proposed hierarchical strategy (Algorithm 2) with D the Hadamard dictionary in dimension n = 32.The obtained factorization is exact and as good as the reference one in terms of complexity savings (2n log n non-zero entries in the factors), so in a way the chased butterflies were caught. The running time is less than a second. Factorization of the Hadamard matrix in dimension up to n = 1024 showed identical behaviour, with running time O(n 2 ) up to ten minutes.

Fig. 2 .

 2 Fig. 2. Hierarchical factorization of the Hadamard matrix of size 32 × 32. The matrix is iteratively factorized in 2 factors, until we have Q = 5 factors, each having p = 64 non-zero entries.

Table 1 .

 1 and S1 was updated only Image denoising results, averaged over the standard image database taken from [22] (12 standard grey 512 × 512 images). The best result of each column is bold.

		Learning	Denoising	Complexity
		(PSNR)	(PSNR)	(RC)
	KSVD	24.71	27.55	1.00
	ODL	24.62	27.51	1.00
	KSVDS	24.16	27.64	0.41
	MSA	23.63	29.38	0.13

This work was supported in part by the European Research Council, PLEASE project (ERC-StG-2011-277906).

The authors wish to thank Franc ¸ois Malgouyres and Olivier Chabiron for the fruitful discussions that helped in producing that work. 1 The product being taken from right to