Basile De Loynes
email: basile.deloynes@ensai.fr

Fabien Navarro
email: fabien.navarro@univ-paris1.fr

Baptiste Olivier
email: baptiste.olivier@orange.com

Localized Fourier Analysis for Graph Signal Processing

Keywords: Nonparametric regression, Multiscale statistics, Variance estimation, Concentration inequalities, Graph signal processing, Spectral graph theory, Graph Laplacian, Harmonic analysis on graphs

We propose a new point of view in the study of Fourier analysis on graphs, taking advantage of localization in the Fourier domain. For a signal f on vertices of a weighted graph G with Laplacian matrix L, standard Fourier analysis of f relies on the study of functions g(L)f for some filters g on I L , the smallest interval containing the Laplacian spectrum sp(L) ⊂ I L . We show that for carefully chosen partitions I L = 1≤k≤K I k (I k ⊂ I L ), there are many advantages in understanding the collection (g(L I k )f ) 1≤k≤K instead of g(L)f directly, where L I is the projected matrix P I (L)L. First, the partition provides a convenient modelling for the study of theoretical properties of Fourier analysis and allows for new results in graph signal analysis (e.g. noise level estimation, Fourier support approximation). We extend the study of spectral graph wavelets to wavelets localized in the Fourier domain, called LocLets, and we show that well-known frames can be written in terms of LocLets. From a practical perspective, we highlight the interest of the proposed localized Fourier analysis through many experiments that show significant improvements in two different tasks on large graphs, noise level estimation and signal denoising. Moreover, efficient strategies permit to compute sequence (g(L I k )f ) 1≤k≤K with the same time complexity as for the computation of g(L)f .

Introduction

Graphs provide a generic representation for modelling and processing data that reside on complex domains such as transportation or social networks. Numerous works combining both concepts from algebraic and spectral graphs with those from harmonic analysis (see for example [START_REF] Rk | Spectral graph theory[END_REF][START_REF] Ronald R Coifman | Diffusion wavelets[END_REF][START_REF] Belkin | Towards a theoretical foundation for laplacian-based manifold methods[END_REF] and references therein) have allowed to generalize fundamental notions from signal processing to the context of graphs thus giving rise to Graph Signal Processing (GSP). For an introduction to this emerging field and a review of recent developments and results see [START_REF] David I Shuman | The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains[END_REF] and [START_REF] Ortega | Graph signal processing: Overview, challenges, and applications[END_REF]. In general, two types of problems can be distinguished according to whether the underlying graph is known or unknown. The first case corresponds to the setup of a sampled signal at certain irregularly spaced points (intersections of a transportation network, nodes in a computer network, . . . ). In the second case, a graph is constructed from the data itself, it is generally interpreted as a noisy realization of one or several distributions supported by a submanifold of the Euclidean space. In this latter context, the theoretical submanifold is somehow approximated using standard methods such as k-NN, ε-graph and their Gaussian weighted versions. In any of these cases, the framework is actually similar: it consists of a graph (given by the application or by the data) and signals are real-valued functions defined on the vertices of the graph.

Notions of graph Fourier analysis for signals on graphs were introduced and studied over the past several years [START_REF] David I Shuman | The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains[END_REF][START_REF] Sandryhaila | Discrete signal processing on graphs: Frequency analysis[END_REF][START_REF] David I Shuman | Vertex-frequency analysis on graphs[END_REF][START_REF] Sardellitti | On the graph fourier transform for directed graphs[END_REF]. The graph Fourier basis is given by the eigenbasis (χ ) of the Laplacian matrix L. The Graph Fourier Transform (GFT) consists in representing a signal f in the Fourier basis ( f, χ ) , and by analogy with the standard case, the eigenvalues of L play the role of frequencies. From this definition, it follows that many filtering techniques are written in terms of vectors g(L)f , for some filter functions g which act on the spectrum of L (scaling, selecting, ...). Fourier analysis on graphs has been successfully applied to many different fields such as stationary signals on graphs [START_REF] Perraudin | Stationary signal processing on graphs[END_REF], graph signal energy study [START_REF] Girault | Irregularity-aware graph fourier transforms[END_REF], convolutional neural networks on graphs [START_REF] Defferrard | Convolutional neural networks on graphs with fast localized spectral filtering[END_REF].

Graph wavelets are an important application of graph Fourier analysis, and several definitions of graph wavelets were proposed [START_REF] Crovella | Graph wavelets for spatial traffic analysis[END_REF][START_REF] Ronald R Coifman | Diffusion wavelets[END_REF][START_REF] Gavish | Multiscale wavelets on trees, graphs and high dimensional data: theory and applications to semi supervised learning[END_REF][START_REF] Leonardi | Tight wavelet frames on multislice graphs[END_REF][START_REF] Tanaka | m-channel oversampled graph filter banks[END_REF][START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF]. When performing Fourier analysis of a signal, there is no guarantee that localization of a signal in the frequency domain (a.k.a Fourier domain) implies localization in the graph domain. This phenomenon is illustrated by the fact that the eigenvectors corresponding to the upper part of Laplacian spectrum tend to be more oscillating than those from the bottom of the spectrum (see for example [START_REF] Tremblay | Networks and signal : signal processing tools for network analysis[END_REF]Fig. 1.6,p. 28] for an illustration). To overcome this problem, [START_REF] David K Hammond | Wavelets on graphs via spectral graph theory[END_REF] developed a fairly general construction of a frame enjoying the usual properties of standard wavelets: each vector of the frame is defined as a function g(sL)δ m (where δ m is a Kronecker signal, having zero values at every vertex except m) and is localized both in the graph domain and the spectral domain at fine scale s. The transform associated with this frame is named Spectral Graph Wavelet Transform (SGWT), and it was used in numerous subsequent works [START_REF] Susnjara | Accelerated filtering on graphs using lanczos method[END_REF][START_REF] Behjat | Signal-adapted tight frames on graphs[END_REF][START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF].

Signals which are sparse in the Fourier domain form an important class of graph signals. Indeed, there is a tight relationship between sparsity in the Fourier domain and the notion of regularity of a signal f on the vertices of a graph G which comes from the Laplacian matrix L of G. Intuitively, a smooth signal will not vary much between two vertices that are close in the graph. This regularity property can be read in the Fourier domain: a very smooth signal will be correctly represented in the Fourier domain with a small number of eigenvectors associated with the lower spectral values; on the contrary, non-smooth signals (i.e. highly oscillating) are represented with eigenvectors corresponding to the upper part of the spectrum. Both the types of signal are said frequency sparse.

In this paper, we propose to exploit localization in the Fourier domain to improve graph Fourier analysis. More precisely, we consider vectors of the form g(L I k )f instead of vectors g(L)f in graph Fourier analysis, where L I k is defined as the matrix LP I k (L) and P I k (L) denotes the projection onto the eigenspaces whose eigenvalue is contained in subset I k . Localized Fourier analysis is motivated by problems and properties defined on strict subsets of the spectrum sp(L) (e.g. any problem defined in terms of frequency sparse graph signals). As a central application of Fourier localization, we introduce the Fourier localized counterpart of SGWT, that we call LocLets for Localized graph wavelets. We prove that various frame constructions can be written in terms of LocLets, hence benefiting from all the advantages of localization discussed in this paper.

Defining I L as the smallest interval containing the entire spectrum sp(L), the local Fourier analysis consists in choosing a suitable partition I L = k I k into subintervals on which standard Fourier analysis is performed. Such an analysis on disjoint intervals naturally benefits from several interesting properties. In particular, when f is modeled by a Gaussian random vector with independent entries, the disjointness of subintervals preserves these properties in the sense that random variables (g(L I k )f ) k are still Gaussian and independent. This simple observation has important consequences to study the graph problem at stake. In this work, it allows us to propose some noise level estimator from the random variables sequence (g(L I k )f ) k , and to provide a theoretical analysis of the denoising problem. Disjointness of subsets (I k ) k also provides simple strategies to parallelize Fourier analysis computations.

We also consider the general problem given by a noisy signal on a graph f = f + ξ, where ξ is some random Gaussian vector with noise level σ. We provide results for two important tasks: the estimation of σ when the latter is unknown, and the denoising of noisy signal f in order to recover signal f . We show that for frequency sparse signals, localization allows to adapt to the unknown Fourier support of signal f . Theoretical guarantees and practical experiments show that localized Fourier analysis can improve state-of-the-art denoising techniques, not only in precision of the estimator f of f , but also in time computations.

We provide an efficient method to choose a partition I L = k I k for the Fourier localized vectors g(L I k )f to be sufficiently informative. Using well-known techniques for efficient graph Fourier analysis (a.k.a Chebyshev filter approximations), we propose scalable methods to perform localized Fourier analysis with no computational overhead over standard fast Fourier graph analysis. In particular, all methods introduced in the paper avoid the computation of the entire eigendecomposition of L which is a major computational advantage when considering large graphs in applications.

The paper is structured as follows. Section 2 presents the relevant notions and techniques necessary to perform localized Fourier analysis. In Section 2.2, we introduce LocLets, the Fourier localized extension of SGWT. Section 3 is devoted to the study of the denoising problem for signals on graphs. The section provides results about noise level estimation, and signal denoising. Additional properties of LocLets, such as computational aspects and relationships with known wavelet transforms, are further developed in Section 4. In Section 5, we analyze the experiments made to support the interesting properties of localized Fourier analysis highlighted in this paper. Finally, the proofs are gathered in Section 7.

Localized Fourier analysis for graph signals

In this section, we introduce the central notion studied in this paper: localization of graph Fourier analysis. First, we recall the relevant notions of graph Fourier analysis. Then we provide examples from previous works that motivates localization in the Fourier domain. We also introduce LocLets, an important application of Fourier localization to SGWT. Finally, we discuss briefly the particular case of graphs sampled from a manifold.

Functional calculus and Fourier analysis for graph signals

Let G = (V, E) be an undirected weighted graph with V the set of vertices, E the set of edges, n = |V| the number of nodes (the size of G), and (W ij ) i,j≤n the weights on edges. Let us introduce the diagonal degree matrix whose diagonal coefficients are given by D ii = 1≤j≤n W ij for 1 ≤ i ≤ n. The resulting non-normalized Laplacian matrix L of graph G is defined as L = D -W . The n non-negative eigenvalues of L, counted without multiplicity, are denoted by λ 1 , . . . , λ n in the decreasing order. In the sequel, sp(L) stands for the spectrum of L. The corresponding eigenvectors are denoted χ 1 , . . . , χ n .

Given a graph G, the GFT of a real-valued function f defined on the vertices of G is nothing but the representation of f in the orthonormal basis of eigenvectors of L. Namely, for a signal f : G → R, the -th Fourier coefficient of f , denoted f ( ), is given by f ( ) = f, χ . The Fourier support supp( f ) of signal f is the set of indices such that f ( ) = 0. We will see in Section 2.2 that graph wavelets can be defined in a similar manner.

Functional calculus is a powerful technique to study matrices, and constitutes the heart of GSP. For a function g defined on some domain D g , sp(L) ⊂ D g , functional calculus reads as

g(L) = 1≤ ≤n g(λ ) χ , • χ .
Interpreting the eigenvalues λ , = 1, . . . , n, as the fundamental frequencies associated with a graph, the linear map g(L) is generally seen as a filter operator in terms of signal analysis.

Also, spectral projections of matrix L can be made explicit with the help of functional calculus, by setting g = 1 I . More precisely, for any subset I ⊂ I L , consider the map P I (L) given by:

P I (L) = 1≤ ≤n 1 I (λ ) χ , • χ l = : λ ∈I χ , • χ .
Then, P I (L) is nothing but the spectral projection on the linear subspace spanned by the eigevectors associated with the eigenvalues belonging to I. In the sequel, n I = |I ∩ sp(L)| will stand for the number of eigenvalues contained in subset I ∩ sp(L).

Spectral projections are a practical tool to focus on some part of the spectrum sp(L). More precisely, let I L = 1≤k≤K I k be a partition of interval I L into disjoint subsets (I k ) k . Since intervals I k are disjoints, functional analysis of L reduces to that of its projections L I k = LP I k (L) in the sense of the identity:

g(L) = 1≤k≤K g(L I k ).
In this paper, one will study the extent to which Fourier analysis on large graphs is improved when considering local Fourier analysis on each subset I k instead of global Fourier analysis on I L .

LocLets: a localized version of SGWT

This section introduces an important application of the localized graph Fourier analysis, namely the notion of localized SGWT.

Construction of a SGWT

Let f : G → R be a signal on the graph G. Let ϕ, ψ : R → R be respectively the scaling and kernel functions (a.k.a. father and mother wavelet functions), and let s j > 0, 1 ≤ j ≤ J, be some scale values. The discrete SGWT is defined in [START_REF] David K Hammond | Wavelets on graphs via spectral graph theory[END_REF] as follows:

Wf = (ϕ(L)f T , ψ(s 1 L)f T , . . . , ψ(s J L)f T ) T .
The adjoint matrix W * of W is:

W * (η T 0 , η T 1 , . . . , η T J ) T = ϕ(L)η 0 + J j=1 ψ(s j L)η j . (1)
We also recall from [START_REF] David K Hammond | Wavelets on graphs via spectral graph theory[END_REF] that a discrete transform reconstruction formula using SGWT coefficients (c j,m ) 0≤j≤J 1≤m≤n is obtained by the formula

(W * W) -1 W * (c j,m ) j,m ,
where (W * W) -1 stands for a pseudo-inverse of the matrix W * W.

Remark 1. From a theoretical point of view, no more assumptions on the scale values s j are required. However, the choice in practice of the scale values depends simultaneously on the mother wavelet ψ and the maximal spectral value of the Laplacian L. In [START_REF] David K Hammond | Wavelets on graphs via spectral graph theory[END_REF], these values s j are suitably chosen accordingly with the graphs considered in the experiments. Besides, for our experiments, we follow the construction of [START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF] in which s j = b j for some real b > 1 (see also Section 4.2.1 for the details).

Motivation for considering Fourier localized graph signals

The definition of SGWT as given in [START_REF] David K Hammond | Wavelets on graphs via spectral graph theory[END_REF] is closely related to its counterpart from traditional wavelet transform by the action of the transform on the Fourier domain. Equation ( 9) in [START_REF] David K Hammond | Wavelets on graphs via spectral graph theory[END_REF] highlights the following decomposition of wavelet coefficients in the frequency domain:

ψ(sL)f (x) = 1 2π +∞ -∞ ψ * (sω) f (ω)e iωx dω, (2)
where ψ * (sω) = ψs (ω) denotes the Fourier coefficient of a scaled version ψ s of the mother wavelet ψ, and

x → e iωx are the eigenfunctions of the one-dimensional Laplacian L = ∂ 2 ∂x 2 on the real line. On the other hand, a similar formula holds for the case of graph wavelets where integration over frequencies is replaced by summation over Laplacian eigenvalues. It is given by Equation ( 22) in [START_REF] David K Hammond | Wavelets on graphs via spectral graph theory[END_REF]:

ψ(sL)f (n) = ψ(sλ ) f ( )χ (n). (3)
Equations 2 and 3 suggest strong similarities between the role of frequencies for wavelets on the real line and the role of Laplacian eigenvalues for graph wavelets. For example, an explicit mapping between frequencies and Laplacian eigenvalues is exhibited in part III.C of [START_REF] Leonardi | Tight wavelet frames on multislice graphs[END_REF] for the case of the cycle graph.

As an important consequence, filtering in the frequency domain for traditional time signals is similar to filtering Laplacian spectrum in the graph setting. This similarity has guided authors of [START_REF] Leonardi | Wavelet frames on graphs defined by fmri functional connectivity[END_REF] who propose an analog of Meyer wavelets [START_REF] Meyer | Principe dincertitude, bases hilbertiennes et algebres doperateurs[END_REF] for graphs by applying traditional Meyer filters on the graph Fourier domain. As for the traditional case, smoothness for graph Meyer wavelets can be guaranteed by calibrating Meyer filters so that the Fourier support of wavelet functions is concentrated in the bottom of the Laplacian spectrum. A larger list of tight frames candidates obtained from traditional wavelets defined on the Fourier domain is provided in Table 1 of [START_REF] Leonardi | Tight wavelet frames on multislice graphs[END_REF].

Other examples of signals with limited frequency support have inspired graph counterparts with restricted Fourier supports. In [START_REF] Anis | Towards a sampling theorem for signals on arbitrary graphs[END_REF][START_REF] Chen | Discrete signal processing on graphs: Sampling theory[END_REF][START_REF] Puy | Random sampling of bandlimited signals on graphs[END_REF][START_REF] Ricaud | Fourier could be a data scientist: From graph fourier transform to signal processing on graphs[END_REF], k-bandlimited graph signals are supported on the eigenspaces associated with the k smallest eigenvalues and define an equivalent of ω-bandlimited signals. Compressive sampling is an application of this type of signals both in the traditional [START_REF] Emmanuel | Stable signal recovery from incomplete and inaccurate measurements[END_REF][START_REF] David | Compressed sensing[END_REF][START_REF] Candes | Sparsity and incoherence in compressive sampling[END_REF] and in the graph [START_REF] Puy | Random sampling of bandlimited signals on graphs[END_REF] settings. While low-pass frequency filters are usually used to capture the smooth part of a signal, high-pass filters have the ability to point out anomalies in smooth signals. Such applications of high-pass filters can be found in [START_REF] Chen | Multi-scale anomaly detection algorithm based on infrequent pattern of time series[END_REF] for optical laser measurements and time signals, but also in [START_REF] Sandryhaila | Discrete signal processing on graphs: Frequency analysis[END_REF] for anomalies detection in temperature measurements on a graph of weather stations. The latter application was also considered in Section V.D of [START_REF] Chen | Discrete signal processing on graphs: Sampling theory[END_REF] to illustrate the use of filter banks that split the graph signal into two bandlimited signals. Authors of [START_REF] Tanaka | Spectral domain sampling of graph signals[END_REF][START_REF] Tanaka | Generalized sampling on graphs with subspace and smoothness priors[END_REF] introduce graph sampling methods in the Fourier domain taking advantage of periodic patterns and extending to the graph setting sampling techniques designed for shift-invariant signals [START_REF] Yonina | Beyond bandlimited sampling[END_REF]. The sampling task for time signals was addressed in [START_REF] Herley | Minimum rate sampling and reconstruction of signals with arbitrary frequency support[END_REF][START_REF] Yue | A theory for sampling signals from a union of subspaces[END_REF] in the case of multiband signals supported on a disjoint union of frequency subsets. This suggests providing methods adapted to disjoint subsets in the Fourier domain also for the case of multiband graph signals.

All the examples discussed above share a common feature: their Fourier support is localized in the Fourier domain in the sense that such signals f satisfy f = P I (L)f for some subset I ⊂ I L , I ∩ sp(L) = sp(L). For k-bandlimited signals, I is a set containing only the k smallest eigenvalues of L; for highpass filters, I contains only the largest eigenvalues; for periodic signals, I is a set such that I ∩ sp(L) = {λ i mod m | λ i ∈ sp(L)} for some period m; and for multiband signals, I is a disjoint union I = k I k of intervals (I k ) k . The current paper proposes methods to study these graph signals that we call Fourier localized signals.

Definition of LocLets

Spectral graph wavelet functions are given by (ϕ(L)δ m , ψ(s j L)δ m ) 1≤j≤J,1≤m≤n . We define a LocLet function to be the projection of a graph wavelet function onto a subset of eigenspaces of L. Definition 2. Let (ϕ(L)δ m , ψ(s j L)δ m ) 1≤j≤J,1≤m≤n be the family functions induced by a SGWT. Then, for any subset I ⊂ I L , 1 ≤ j ≤ J and 1 ≤ m ≤ n, set:

ϕ m,I = ϕ(L I )δ m = :λ ∈I ϕ(λ ) δ m ( )χ ψ j,m,I = ψ(s j L I )δ m = :λ ∈I ψ(s j λ ) δ m ( )χ ,
where δ m (•) = δ m , χ • is the graph Fourier transform of δ m . The functions (ϕ m,I , ψ j,m,I ) 1≤j≤J,1≤m≤n are called Localized waveLets functions (LocLets). The functions ϕ m,I , ψ j,m,I are said to be localized at I.

Let I L = 1≤k≤K I k be some partition. Then, the localized SGWT transfom of f with respect to partition (I k ) 1≤k≤K , denoted by W (I k ) k f , is defined as the family

W (I k ) k f = (W I k f ) k where W I k f = (ϕ(L I k )f T , ψ(s 1 L I k )f T , ...) T , 1 ≤ k ≤ K.
Similarly to Equation (1), the adjoint transform is given by

W I k * (η T 0 , η T 1 , . . . , η T J ) T = ϕ(L I k )η 0 + J j=1 ψ(s j L I k )η j , 1 ≤ k ≤ K.
As already observed, localized SGWT of a signal f contains more precise information about signal f than its standard SGWT. The latter can easily be obtained from the former since subsets (I k ) k are pairwise disjoint and formula g(sL) = 1≤k≤K g(sL I k ) holds for all filter g, and in particular for g = ϕ or g = ψ.

When the partition I L = 1≤k≤K I k is carefully chosen, we show that the SGWT localization provides interesting features such as independence of random variables in denoising modelling, or considerable improvements in denoising tasks.

Remark 3. The functions ϕ m,I , ψ j,m,I are localized in the Fourier domain in the sense that the support of their Fourier transforms are contained in a subset I of I L . A different localization property, observable in the graph domain, is considered in [START_REF] David K Hammond | Wavelets on graphs via spectral graph theory[END_REF]. We refer to the latter property as graph domain localization in the current paper.

A property about the graph domain localization at fine scales is stated in [START_REF] David K Hammond | Wavelets on graphs via spectral graph theory[END_REF]Theorem 5.5] but this result appears to be not informative in general for the case of Fourier localized functions ϕ m,I , ψ j,m,I . For instance, any function of the form ψ1 I vanishes in a neighborhood of 0 as soon as 0 / ∈ I, as observed in Section 2.3 of [START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF]. However, other graph domain localization results were obtained by the authors of [START_REF] Thierry Coulhon | Heat kernel generated frames in the setting of dirichlet spaces[END_REF] for the case of frames considered in [START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF] and discussed in our Section 4.2.1. In addition, the weaker graph localization property [START_REF] David K Hammond | Wavelets on graphs via spectral graph theory[END_REF]Lemma 5.2] for powers of the Laplacian still holds in our Fourier localized setting since in practice we approximate any function x → ψ(s j x)1 I (x) by a Chebyshev polynomial of order N (see Section 4).

Fourier localization for weighted graphs sampled from manifolds

In some applications, the underlying graph is unknown and is built from the data. In this case, the resulting graph is thought as a random sampling of a low-dimensional sub-manifold embedded in a higher dimensional Euclidean space.

More precisely, let M be a Riemannian manifold of dimension d embedded in R m with m > d. A popular way to define a graph from a finite set of points {x 1 , . . . , x n } ⊂ M consists in defining a weighted adjacency matrix W = (W ij ) i,j≤n as follows:

W ij = k x i -x j 2 2 2ε , (4)
where • 2 2 stands for the Euclidean distance in R m and ε > 0 is some parameter called the bandwidth of the kernel k. A typical choice for the kernel k is the exponential function k(x) = exp(-x), x ∈ R. As an example, the swissroll graph of Section 5 is built following this idea.

A whole part of the literature is dedicated to the question of the convergence of the discrete (normalized or non-normalized) Laplacian matrices L n,ε toward the Laplace-Beltrami operator ∆ M (see [START_REF] Rosenberg | The Laplacian on a Riemannian manifold[END_REF] for a detailed exposition of this classical object from differentiable geometry). The discretized operator L n,ε depending on two parameters, the convergence as n → ∞ and/or ε → 0 have been considered in [START_REF] Hein | From graphs to manifolds-weak and strong pointwise consistency of graph Laplacians[END_REF][START_REF] Singer | From graph to manifold Laplacian: the convergence rate[END_REF][START_REF] Coifman | Diffusion maps[END_REF][START_REF] Giné | Empirical graph Laplacian approximation of Laplace-Beltrami operators: large sample results[END_REF][START_REF] Belkin | Towards a theoretical foundation for laplacian-based manifold methods[END_REF][START_REF] Marshall | Manifold learning with bi-stochastic kernels[END_REF]. Loosely speaking, theses results are devoted to the approximation of ∆ M f by L n,ε f at the sample points. Furthermore, it is shown in [START_REF] Ulrike Von Luxburg | Consistency of spectral clustering[END_REF][START_REF] García Trillos | Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator[END_REF] that, under mild conditions, eigenvalues and eigenfunctions of ∆ M are well approximated by those of L n,ε . As a consequence of particular interest, bandlimited (or even multiband) signals on the manifold M, when sampled at the points {x 1 , . . . , x n } ⊂ M, are expected to be bandlimited (multiband) with respect to the graph Laplacian L n,ε (with slight differences when considering the normalized or the non-normalized Laplacian). It is worth noting that the sample points {x 1 , . . . , x n } do not have to lie exactly in the manifold M but can be disrupted by a noise. The spectral properties are preserved by standard spectral perturbation arguments (see [START_REF] Kato | Perturbation theory for linear operators[END_REF]) providing the noise level is sufficiently small. Such a perturbation argument is discussed at some point in [START_REF] Coifman | Diffusion maps[END_REF] and remains valid in our context.

To conclude this discussion, let us point out that the choice of a Gaussian kernel in (4), while popular, is quite arbitrary. The results in [START_REF] García Trillos | Error estimates for spectral convergence of the graph Laplacian on random geometric graphs toward the Laplace-Beltrami operator[END_REF] are stated for a rather general kernel including non-smooth kernels. In addition, a variable bandwidth kernel is also considered in [START_REF] Berry | Variable bandwidth diffusion kernels[END_REF].

Local Fourier analysis and graph functions denoising

The denoising problem is stated as follows: given an observed noisy signal f of the form f = f + ξ where ξ is a n-dimensional Gaussian vector distributed as N (0, σ2 Id), provide an estimator of the a priori unknown signal f . This section shows how localized Fourier analysis helps in estimating the noise level σ when it is unknown, and in recovering the original signal f when the latter is sparse in the Fourier domain. In what follows, we will focus on random variables of the form P I k f I k 2 where f is the noisy signal and I k is a subset in the partition I L = k I k . To keep the notations light, n k , f k , ξ k and f k will stand for n I k , P I k f , P I k ξ and P I k f respectively. In addition, the cumulative distribution function of a random variable X will be denoted by Φ X .

Noise level estimation for frequency sparse signals

Since in real application the noise level σ remains unknown in general, new estimators σ based on localization properties in the spectrum are introduced in the sequel.

Noise level estimation from projections along sp(L)

For any filter g defined on I L and any subset I ⊂ I L , simple computations give rise to

E( f T g(L I ) f ) = f T g(L I )f + σ 2 Tr(g(L I )). (5)
Since both f T g(L I ) f and Tr(g(L I )) are known, Equation ( 5) suggests building estimators from the ex-

pression f T g(L I ) f Tr(g(L I ))
. In [START_REF] Basile De Loynes | Data-driven thresholding in denoising with spectral graph wavelet transform[END_REF], the noise level is estimated by f T L f Tr(L) which can be seen as the graph analog of the Von Neumann estimator from [START_REF] John Von Neumann | Distribution of the ratio of the mean square successive difference to the variance[END_REF]. The main drawback of this estimator is its bias.

Theoretically, without any assumption on the signal f , the bias term f T g(L I )f Tr(g(L I )) is minimized when g = 1 {λ * } where * = argmin{| f ( )| : λ ∈ sp(L)}. The computation of such filters would require the complete reduction of L which does not scale well with the size of the graph. Instead, these ideal filters will be approximated by filters of the form g = 1 I k , for I k a subset in the partition I L = k I k . It is worth noting that with k * = argmin k f k 2 , the function g * = 1 I k * achieves the minimal bias of the estimator among all filters of the form g = k α k 1 I k .

Discarding some intervals I k with n k = 0, it can be assumed without loss of generality that n k = 0 for all 1 ≤ k ≤ K. Also, observe that the random variable f k 2 2 can be decomposed as follows

f k 2 2 = f k 2 2 + ξ k 2 2 + 2 f k , ξ k , (6)
where

ξ k 2 2
σ 2 and f k ,ξ k σ are random variables distributed as χ 2 (n k ) and N (0, f k

if n k = n k ; 3. for k such that f k = 0, c k is distributed as σ 2 n k Γ n k where Γ n k ∼ χ 2 (n k ).

The case of frequency-sparse signals

When the signal f is sparse in the Fourier domain, the condition f k = 0 is met for most of the intervals

I k ⊂ I L . Let us define I f = k:I k ∩supp f =∅ I k
to be the union of subsets I k intersecting the Fourier support supp( f ) of f . Also, denote by I f = I L \I f its complement set. In order to take advantage of Fourier sparsity, let us introduce the quantities σ mean and σ med as follows:

σ mean (c) 2 = 1 |{k : I k ⊂ I f }| k:I k ⊂I f c k and σ med (c) 2 = median k:I k ⊂I f (c k ). ( 7
)
The following concentration inequalities show that σ mean and σ med are natural estimators of the noise level σ.

Proposition 5. Let K f = |{k : I k ⊂ I f }|, n 0 = min{n k : k, I k ⊂ I f }, n ∞ = max{n k : k, I k ⊂ I f }, V f = 2σ 4 k:I k ⊂I f 1/n k and B f = 2σ 2 /n 0 .
Then the following concentration inequalities hold: 1. for all t ≥ 0,

P σ mean (c) 2 -σ 2 ≥ t ≤ exp   - K 2 f t 2 V f (1 + B f + 1 + 2B f K f t V f )   ,
and for all 0 ≤ t ≤ σ 2 ,

P σ mean (c) 2 -σ 2 ≤ -t ≤ exp - K 2 f t 2 2V f ; 2. for all t ≥ 0, with β = n 0 /n ∞ , P σ 2 med ≥ β -1 σ 2 + 2σ 2 β -1 t ≤ exp K f 2 ln 4p + (t)(1 -p + (t)) ,
and for all 0

≤ t ≤ 1 such that p -(t) ≤ 1/2, P σ 2 med ≤ βσ 2 -σ 2 βt ≤ exp K f 2 ln 4p -(t)(1 -p -(t)) , where p + (t) = P(Γ n∞ ≥ n ∞ + 2n ∞ t) and p -(t) = P(Γ n 0 ≤ n 0 -n 0 t).
Obviously, the Fourier support supp( f ) and the subset I f remain generally unknown in applications and have to be approximated. Let us recall that the main issue for estimating σ comes from the bias term

f k 2 2
n k in Equation [START_REF] Berry | Variable bandwidth diffusion kernels[END_REF], and in particular when the value σ 2 is negligible compared to

f k 2 2
n k . Therefore, a suitable candidate to approximate I f will be some subset J f ⊂ I L for which the impact of larger values

f k 2 2
n k is minimized. This is made clear by Proposition 6 below. The latter involves the following concentration bounds for Gaussian random variables: for all 0 < α < 1

P(| f k , ξ k | ≥ t α,σ f k 2 ) ≤ α where t α,σ = σ × -2 ln α 4 . ( 8
)
Proposition 6. Let 0 < α < 1. Let t α,σ be defined by Equation [START_REF] Chen | Discrete signal processing on graphs: Sampling theory[END_REF]. Assume that f = 0 and that the following inequality holds:

f k 2 2 + 2t α,σ f k 2 σ 2 ≥ Φ -1 n k n Γn -Γn k 1 - 3α 2 .
Then, the quantities

b k = ξ k 2 2 + f k 2 2 + 2 ξ k , f k n k and b = ξ 2 2 n satisfy P(b k ≥ b ) ≥ 1 -α.
By invariance under permutations, one may assume without loss of generality that the values c k are ordered in the decreasing order. Proposition 6 quantifies the fact that the highest values of c k correspond most likely to the indices k for which f k = 0. Consequently, setting J f (r) = k∈{r,r+1,...K-r} I k for all 1 ≤ r ≤ K 2 , the estimators introduced in Equation ( 7) may be rewritten replacing the unknown subset I f by its known approximation J f (r). So we define the estimators

σ r mean (c) 2 = 1 |{k : I k ⊂ J f (r)}| k:I k ⊂J f (r) c k and σ r med (c) 2 = med k:I k ⊂J f (r) (c k ).
It is worth noting that from the symmetry of the subset J f (r), it follows that the value σ r med actually does not depend on parameter r, and one will write σ med in place of σ r med .

Denoising Frequency Sparse Signals

Let us begin with a result illustrating that localized Fourier analysis in I L provides strong benefits in noise reduction tasks when the underlying signal is frequency sparse.

Proposition 7. Assume f = f I for some subset I ⊂ I L . Then E f -f I 2 2 = E f -f 2 2 -σ 2 I ∩ sp(L) .
In particular, denoising of f boils down to denoising of f I = f I + ξ I .

While Proposition 7 asserts a trivial denoising solution in the Fourier domain, i.e. simply destroying the projection f I = ξ I , this approach is no longer that immediate when considering the graph domain observations since the Fourier support of f is unknown in practice and needs to be estimated. Based on the χ 2 -statistics, Algorithm 1 is designed for this purpose. To the best of our knowledge, previous works that proposed method for Fourier support recovery for graph noisy signals [START_REF] Segarra | Aggregation sampling of graph signals in the presence of noise[END_REF] involve the complete eigendecomposition of matrix L. The methodology suggested below makes use of projectors on eigenspaces which can be approximating with Chebyshev polynomials as detailed in the next Section 4.

Heuristically, if I contains the support of the Fourier transform of f , on the complementary subset I we only observe pure white Gaussian noise so that

P I f 2 2 = f I 2 2 is distributed as σ 2 χ 2 (n I ) with n I = |I ∩ sp(L)|.
On the other hand, on I the square of the Euclidean norm of a non-centered Gaussian vector is observed. Consequently, the quantity P χ 2 (n I ) > σ -2 P I f 2 2 is typically very close to zero whereas P χ 2 (n -n I ) > σ -2 P I f 2 2 remains away from 0. To put it in a nutshell, sliding a window along the spectrum of L, Algorithm 1 performs a series of χ 2 -test.

With the objective to provide theoretical guarantees that χ 2 -tests approach supp( f ) correctly, it is important to turn the condition on the p k -value into a condition involving only the values f k 2 and σ. The next lemma shows that for sufficiently large values of the ratio f k 2 σ , the inequality p k ≤ α holds so that the corresponding components supp( f k ) of the Fourier domain are legitimately included in the support estimate I.

Algorithm 1: Support approximation in the Fourier domain for noisy signal Data: noisy signal f , a subdivision I 1 , I 2 , . . . , I K , estimated n k = |I k ∩ spL|, k = 1, . . . , K, threshold α ∈ (0, 1) Result: f I = P I (L) f , where I is an approximation of the Fourier support of f

1 for k = 1, . . . , K 2 Compute f k 2 2 = P I k (L) f 2 2 ; 3 Compute p k = P(σ 2 Γ n k > f k 2
2 ) and Γ n k ∼ χ 2 (n k );

4 Compute f I = k: p k ≤α P I k f . Lemma 8. Let 0 < α < 1 and let Γ n k , Γ n k be two i.i.d χ 2 (n k ) random variables.
Assume that:

f k 2 σ f k 2 σ -2 t α/2,σ σ ≥ Φ -1 Γn k -Γ n k 1 - α 2 ,
where t α,σ is defined by Equation (8). Then p k ≤ α.

In contrast to Lemma 8, the lemma below states that condition p k > α holds for sufficiently small values of ratio σ

-1 f k 2 . Lemma 9. Let 0 < α < 1 and let Γ n k be a χ 2 (n k ) random variable. For 0 < β < 1, set t β,k = σ 2 Φ -1 Γn k (1 -β). Assume that f k 2 + t β,k σ 2 < Φ -1 Γn k 1 - α 1 -β .
Then p k > α.

Compared to Proposition 7, the result below quantifies the error resulting by approximating the support running Algorithm 1. Note that the requirement to have a constant sequence (n k ) k is used for statement clarity but similar assertions hold for the case

n k = n k . Proposition 10. Set f I = k:p k ≤α P I k f . Assume that n k = n 1 for all 1 ≤ k ≤ K. Then, 1. the Fourier support approximation 2 -error satisfies f -f I 2 2 ≤ |{k, I k ⊂ I f , p k > α}| t α/2,σ + t 2 α/2,σ + σΦ -1 Γn 1 -Γ n 1 1 - α 2 2 2 . ( 9
)
2. the Noise 2 -error on Fourier support:

E f I -f I 2 2 = |{k, p k ≤ α}|n 1 σ 2 . ( 10
)
Lemma 9 asserts that the set {k, p k > α} is small when most of the values f k 2 are large enough compared to noise level σ for I k ∩ supp f = ∅. In such a case, Fourier support approximation 2 -error is small. Regarding the noise 2 -error, the inclusion {k, p k ≤ α} ⊂ {k, I k ∩ supp f = ∅} holds by Lemma 9. Moreover, Lemma 8 asserts that the set {k, p k ≤ α} contains the entire set {k, I k ∩ supp f = ∅} for sufficiently large values of σ -1 f k 2 when I k ∩ supp f = ∅. For such favorable situations, the noise 2 -error is exactly n 1 σ|{k, I k ⊂ I f }|, the amount of noise on the extended support I f . The second step gives an estimate of the original signal using a thresholding procedure on each element f I and f I . On the one hand, the methodology developed in [START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF] is prohibitive in terms of time and space complexity as soon as the underlying graphs become moderately large. On the other hand, the fast SGWT remains an approximating procedure. If a signal happens to be very frequency-sparse, then an even more optimal strategy is possible: first, the support I in the frequency domain is approximated with the help of Algorithm 1; then, the procedure of [START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF] is applied to P I f (the low-rank part) and LocLets on P I (L)f . This idea is made precisely in Algorithm 3. Estimator f produced in Algorithm 3 satisfies a tighter oracle bound inequality than the one given in [START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF]Theorem 3]. This theoretical guarantee is widely supported by our experiments described in Section 5. Following notations from [27, Equation ( 21)], we denote by OB(f I ) the oracle bound obtained from an oracle estimator of f I from a noisy f I exploiting some knowledge about the unknown signal f I . We refer to [START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF] for precise details.

Theorem 11. Let I, f be respectively the support approximation and the estimator of f obtained from Algorithms 1 and 3 with threshold value t 2 = 0. Then we have

E f -f 2 2 ≤ E f -f I 2 2 + (2 log(n I ) + 1)(σ 2 + OB(f I )).
The right-hand side in the inequality of Theorem 11 has a more explicit expression in terms of α, σ using Proposition 10. Up to the error made by approximating the support with Algorithm 1, the 2 -risk is essentially bounded by the 2 -risk of the Parseval frame procedure from [START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF] on the low-rank projection

f I of f , that is E f -f 2 2 (2 log(n I ) + 1)(σ 2 + OB(f I )).
To conclude, Theorem 11 provides a theoretical guarantee that the support approximation improves the denoising performances obtained from [START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF].

Properties of LocLets

In this section, we highlight important properties for the application of Fourier localization in practice. First we discuss computational analysis, and methods to apply our techniques to large graphs. Then we study the relationships of LocLets with well-known graph wavelet constructions.

Fast LocLet Transform and Computational Analysis

In the case of large graphs, GSP requires a special care for being efficient since functional calculus relies a priori on the complete reduction of the Laplacian. Actually, several efficient methods were designed to retrieve only partial information from the eigendecomposition as matrix reduction techniques (see for instance [START_REF] Sridhar Mahadevan | Fast spectral learning using lanczos eigenspace projections[END_REF][START_REF] Susnjara | Accelerated filtering on graphs using lanczos method[END_REF]) or polynomial approximations [START_REF] David K Hammond | Wavelets on graphs via spectral graph theory[END_REF][START_REF] David I Shuman | Chebyshev polynomial approximation for distributed signal processing[END_REF][START_REF] Di Napoli | Efficient estimation of eigenvalue counts in an interval[END_REF]. In this paper, the widely adopted latter approach with Chebyshev polynomials approximation is preferred and briefly recalled below (we refer the reader to [50, Section III.C.] for a brief but more detailed description of Chebyshev approximation).

Chebyshev approximations

Roughly speaking, the idea is to approximate the function g with its Chebyshev expansion g N at order N . More precisely, the Chebyshev polynomials of the first kind (T i ) i≥0 are defined from the second order recursion T 0 (x) = 1, T 1 (x) = x, |x| ≤ 1, and

T i (x) = xT i-1 (x) -T i-2 (x), for i ≥ 2. Then, the matrix L is normalized as L = 2 λ 1 L -I n so that sp( L) ⊂ [-1, 1]
. This gives rise to some function g : [-1, 1] → R with the property g(L) = g( L). In fact, g(x) = g( λ 1 2 (x + 1)) for all x ∈ [-1, 1]. Then g(L) has the following truncated Chebyshev expansion g(L) ≈ g N (L):

g N (L) = 0≤i≤N a i ( g)T i ( L),
where N is the maximal degree of polynomials T i used in the expansion, and a i ( g) is the i-th coefficient in the N -th order Chebyshev expansion of function g. Following [START_REF] David K Hammond | Wavelets on graphs via spectral graph theory[END_REF], for any filter g on sp(L) and any signal f on graph G, the approximation g N (L) provides a vector value close to g(L)f with time complexity O(|E|N ).

The object presented in the sequel involves in particular the spectral projection P I (L)f of a signal f for any subset I ⊂ I L which can be derived from the Chebyshev expansion of the indicator function g = 1 I . This observation actually appears in several recent works [START_REF] Di Napoli | Efficient estimation of eigenvalue counts in an interval[END_REF][START_REF] Fan | Spectrum-adapted polynomial approximation for matrix functions[END_REF]. More importantly for our study, this efficient estimation is part of the Hutchinson stochastic trace estimator technique [START_REF] Hutchinson | A stochastic estimator of the trace of the influence matrix for Laplacian smoothing splines[END_REF], providing us with an effective method to estimate n I = Tr(L I ). Finally, the present paper focuses on the computation of a sequence g(L I k ) 1≤k≤K (or its vector counterpart g(L I k )f ) instead of a single g(L) (resp. g(L)f ). While a naive estimation would suggest that the computational complexity is then multiplied by a factor K compared to the complexity of the computation of g(L), we argue in the following that there is in fact no significant computational overhead.

Sharing Chebyshev polynomial matrices among filters

Let us assume that it is needed to compute the estimated values of g k (L)f for a given signal f for several filters g k , k = 0, . . . , K. Then the following two-step strategy can be adopted: (1) pre-compute Chebyshev expansions g k (x) ≈ g k,N (x) = 0≤i≤N a i ( g k )T i (x) for all k = 0, . . . , K; independently, compute Chebyshev approximation vectors T i ( L)f for all 0 ≤ i ≤ N ; (2) combine the previous results to compute the Chebyshev approximation g k,N (L)f of g k (L)f :

g k,N (L)f = 0≤i≤N a i ( g k )T i ( L)f.
The complexity of the first step is dominated by the N matrix-vector multiplications required to obtain T i ( L)f . So the first step has complexity O(|E|N ). The second step adds N weighted matrices a i ( g k )T i ( L) together, which is an operation of complexity O(N n 2 ) at most. As an important matter of fact, the overall complexity for this procedure is bounded by O(|E|N + N n 2 ), which is independent of the number of filters g k , and the same as for the computation of g(L).

Sharing matrices among filters has several examples of applications in the current paper:

1. Computation of g(L I k )f for all 1 ≤ k ≤ K: the equation g(L I k )f = g(1 I k (L)L)f holds so that we can consider filters g k (x) = g(1 I k (x)x).

2. Computation of g(sL)f for several scale values s: consider filters of the form g s (x) = g(sx).

3. Computation of n I k for all 1 ≤ k ≤ K: Hutchinson's stochastic estimation computes averages of f T i P I k (L)f i for some random vectors f i (i ≤ n H ) whose computational complexity is dominated by the approximation of vectors P I k f i . Considering filters g k (x) = 1 I k (x), and sharing random vectors (f i ) i among all approximations of n k , we end up with a complexity of O(n H N |E|), independent of value K.

In particular, Algorithm 1 has complexity O(n H N |E| + N n 2 ). Indeed, its efficiency is calibrated on the computations of sequences ( f k 2 ) 1≤k≤K and (n k ) 1≤k≤K whose computational analysis was discussed previously. It is worth observing that values n k do not depend on signal f and should be estimated only once in the case where several signals f 1 , f 2 , . . . are to be denoised.

Optimizing storage of LocLets coefficients

The storage of wavelet coefficients (W I k f ) 1≤k≤K requires a priori K times the storage cost associated with the original transform Wf . When matrix reduction techniques are used to compute wavelets transform [START_REF] Susnjara | Accelerated filtering on graphs using lanczos method[END_REF], one may reduce the storage consumption of the localized SGWT by suitably choosing the impulse functions (δ m ) m . For instance, assume that for each subset I

Connections with Well-know Frames

A family F = {r i } i∈I of vectors of R V is a frame if there exist A, B > 0 satisfying for all f ∈ R V A f 2 2 ≤ i∈I | f, r i | 2 ≤ B f 2 2 .
A frame is said to be tight if A = B. This section gives two examples of frames introduced in the literature which can be realized as a LocLets representation and thus benefit from the advantages given by localization in the spectrum.

Parseval frames

Parseval frames are powerful representations to design wavelets with nice reconstruction properties [START_REF] Leonardi | Tight wavelet frames on multislice graphs[END_REF][START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF].

In this section, we investigate the extent to which Parseval frames can be obtained from some LocLet representation. We show that for a particular choice of partition I L = k I k , there exist frames which are Parseval frames and composed only of LocLets functions.

A finite collection (ψ j ) j=0,...,J is a finite partition of unity on the compact [0, λ 1 ] if

ψ j : [0, λ 1 ] → [0, 1] for all j ≤ J and ∀λ ∈ [0, λ 1 ], J j=0 ψ j (λ) = 1. ( 11
)
Given a finite partition of unity (ψ j ) j=0,...,J , the Parseval identity implies that the following set of vectors is a tight frame:

F = ψ j (L)δ i , j = 0, . . . , J, i ∈ V .
Some constructions of partition of unity involve functions (ψ j ) j that have almost pairwise disjoint supports i.e. supp(ψ j ) ∩ supp(ψ j ) = ∅ as soon as |j -j | > 1. For such partition of unity, set I 0 = supp(ψ 0 ), I J = I 0 = supp(ψ J ) and I j = supp(ψ j ) ∩ supp(ψ j+1 ) for all 1 ≤ j ≤ J -1. Then, the sequence (I j ) 0≤j≤J defines a finite partition of [0, λ 1 ], [0, λ 1 ] = 0≤j≤J I j , such that:

ψ 0 1 I 0 = 1 I 0 , (ψ j + ψ j+1 )1 I j = 1 I j , 0 < j < J, and ψ J 1 I J = 1 I J . ( 12
)
An alternative tight frame can be constructed using a LocLet representation as shown in the following proposition.

Proposition 12. Assume Equations ( 11) and ( 12) hold and set, for all

1 ≤ k ≤ J, ϕ n,k = √ ψ 0 (L I k )δ n , ψ 1,n,k = √ ψ k (L I k )δ n and ψ 2,n,k = √ ψ k (L I k+1 )δ n for all 1 ≤ k ≤ J. Then (ϕ n,k , ψ j,n,k ) 1≤j≤2, 1≤m≤n, 1≤k≤J is a tight frame.
The resulting tight frame of Proposition 12 is actually frame of LocLets if additionally the functions ψ j is of the form ψ j = ψ 1 (s j .) for some scale parameter s j , 1 ≤ j ≤ J. This is typically the case for the frames introduced in [START_REF] Leonardi | Tight wavelet frames on multislice graphs[END_REF][START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF]. In these papers, the partition of unity is defined as follows: let ω : R + → [0, 1] be some function with support in [0, 1], satisfying ω ≡ 1 on [0, b -1 ] and set ψ 0 (•) = ω(•) and for j = 1, . . . , J

ψ j (•) = ω(b -j •) -ω(b -j+1 •) with J = log λ 1 log b + 2.
In particular, the functions ψ k have supports in intervals

J k = [b k-2 , b k
]. Thus, one may define disjoint intervals (I k ) k as follows:

I k = [b k-1 , b k ]. We have J k = I k ∪ I k+1
, so that Equations ( 12) hold whereas the scaling property ψ j = ψ 1 (b -1 .) is straightforward. By Proposition 12, the set of vectors

ψ 0 (L I k )δ n , ψ 1 (s k L I k )δ n , ψ 1 (s k L I k+1 )δ n , n, k is a tight frame of LocLets. Observe that the transform (W I k ) I k each component W I k of the LocLet transform (W I k ) I k only admit two scale parameters s k , s k-1 .

Spectrum-adapted tight frames

Let us consider another family of tight frames tailored to the distribution of the Laplacian L eigenvalues proposed in [START_REF] Shuman | Spectrumadapted tight graph wavelet and vertex-frequency frames[END_REF]. As shown below, these frames can be written in terms of a warped version of LocLets, and up to some approximation, in terms of (non-warped) LocLets. First, let us briefly recall the construction from [START_REF] Shuman | Spectrumadapted tight graph wavelet and vertex-frequency frames[END_REF]. The notion of warped SGWT is introduced in [START_REF] Shuman | Spectrumadapted tight graph wavelet and vertex-frequency frames[END_REF] to adapt the kernel to the spectral distribution. Given a warping function ω : I L → R, the warped SGWT is defined as:

W ω f = (ϕ(ω(L))f T , ψ(s 1 ω(L))f T , . . . , ψ(s J ω(L))f T ) T .
As for our spectral localization, the objective of warping is to take benefits from the distribution of sp(L) along interval I L . While the two techniques show similarities (e.g. estimation of sp(L) distribution), they are meant to answer different problems: warped SGWT is a technique to adapt the whole spectrum to some task (e.g. producing a tight frame), whereas localized SGWT is designed to answer problems related to localized subsets in the spectrum (e.g. denoising a frequency sparse signal). Here we show that the advantages of both LocLets and warped SGWT are obtained when the two methods are combined in a warped LocLet representation.

Let ω be some warping function on I L chosen in the form ω(•) = log(Cω 0 (•)) where ω 0 stands for the cumulative spectral distribution of L and C is some normalization constant as shown in [START_REF] Shuman | Spectrumadapted tight graph wavelet and vertex-frequency frames[END_REF]. Then, let γ > 0 be an upper bound on sp(L) and let R, J be two integers such that 2 ≤ R ≤ J. Setting ω γ,J,R = γ J+1+R , Corollary 2 in [START_REF] Shuman | Spectrumadapted tight graph wavelet and vertex-frequency frames[END_REF] asserts that the family (g m,j ) m,j of functions defined below is a tight frame

g m,j = g j (λ ) δ m ( )χ , (13)
where functions g j arise from some kernel g as

g j (λ) = g(ω(λ) -jω γ,J,R ) = g log Cω(λ) e jω γ,J,R .
Typically in [START_REF] Shuman | Spectrumadapted tight graph wavelet and vertex-frequency frames[END_REF], the kernel g takes the form

g(λ) =   0≤j≤J a j cos 2πj cos λ Rω γ,J,R + 1 2   1 [-Rω γ,J,R ,0] (λ).
for some sequence (a j ) j satisfying j (-1) j a j = 0.

The following proposition states that Equation ( 13) admits an alternative form involving only (warped) LocLets functions. Proposition 13. Setting ψ(λ) = g(log(Cλ)) for λ > 0, consider the family of warped LocLets defined for all 0 ≤ k ≤ R -1, 1 ≤ m ≤ n and 1 ≤ j ≤ J by

ψ j,m,I k = ∈I k ψ(s j ω 0 (λ )) δ m ( )χ with I k = e (k-R)ω γ,J,R C , e (k-R+1)ω γ,J,R C .
Then, the following identity holds for all j = 1, . . . , J and all m = 1, . . . , n

g m,j = 1≤k≤R-1 ψ j,m,I k .

Experiments on suites of large matrices

This section details experiments made on large graphs to validate the Fourier localization techniques introduced in that paper. After describing the experimental settings, we describe the outcomes of several experiments showing strong advantages in the use of Fourier localization in practice.

Choice of spectral partition

I L = k I k
In order to keep the problem combinatorially tractable, it is necessary to reduce the choice of possible partitions of I L into subintervals I k . That is why, the partitions considered in the sequel are regular in the sense that all intervals have the same length λ 1 /K for some integer K ≥ 1. Thereafter, the parameter K is chosen so that the eigenvalues are distributed as evenly as possible in each interval I k . Without prior information, it is indeed natural not to favor one part of the spectrum over another. Most importantly, 3.0 in the view of the concentration property of the median around the noise level σ 2 of Proposition 5, it is essential to keep the parameter β as close to one as possible.

K elbow = 22 E N (K) MRE N (K) (b) minnesota graph
In order to implement the ideas above, it is necessary to estimate the spectral measure of L which can be described by the so-called spectral density function:

ϕ L (λ) = 1 n n =1 δ(λ -λ ) for all λ ∈ I L .
There are several techniques for such an approximation among which the Kernel Polynomial Method (see, e.g. [START_REF] Silver | Densities of states of mega-dimensional hamiltonian matrices[END_REF][START_REF] Wang | Calculating the density of states and optical-absorption spectra of large quantum systems by the plane-wave moments method[END_REF]). The latter approximates the spectral density ϕ L with the help of matrix Chebyshev expansion (ϕ N L ) N (see [START_REF] Lin | Approximating spectral densities of large matrices[END_REF] for a detailed presentation). Now, let (I k ) 1≤k≤K be some regular partition of I L and (n k ) 1≤k≤K be the corresponding numbers of eigenvalues in each I k . Choosing the parameter K ≥ 1 so that the entropy defined by

E(K) = - 1≤k≤K n k n log n k n
is maximal ensures that the eigenvalues are as equally distributed in each interval as possible. In application, the Kernel Polynomial Method provides an approximation n N k of n k and the corresponding empirical entropy E N (K) is used as a proxy for the theoretical one.

Empirically, the entropy increases logarithmically and then stabilizes from a certain elbow value K elbow as illustrated in Figure 1. This elbow value is displayed in dashed lines in Figure 1. In the experiments, we choose this value K elbow motivated by two reasons. First, as the intervals become shorter it is more difficult to obtain a uniform distribution of the eigenvalues into those intervals. The second reason is related to the quality of the estimate n N k of n k as the sample size decreases. To illustrate this fact, we consider the Mean Relative Error (MRE) defined by

MRE N (K) = 1≤k≤K |n k -n N k | n .
As highlighted by Figure 1, the empirical entropy actually stabilizes when the Chebyshev approximation, in terms of MRE, is no longer sharp enough.

The experimental settings

Following [START_REF] Fan | Spectrum-adapted polynomial approximation for matrix functions[END_REF], we propose to validate our techniques on an extended suite of large matrices extracted from the Sparse Matrix Collection in [START_REF] Davis | The University of Florida sparse matrix collection[END_REF]. Most of these matrices have an interpretation as the Laplacian matrix of a large graph. We define matrix L from the following matrices of the suite:si2 (n = 769), minnesota (n = 2642), cage9 (n = 3534), saylr4 (n = 3564) and net25 (n = 9520). We extend this graph collection with the well-studied swissroll graph Laplacian matrix (n = 1000). We sample randomly signals whose supports are sparse in the Fourier domain. We will use the notation f i-j for normalized signals supported on a sub-interval of I L containing exactly the eigenvalues λ i , λ i+1 , . . . , λ j . As an example, f n-n is a constant signal while f 1-2 is a highly non-smooth signal supported on the eigenspaces of large eigenvalues λ 1 , λ 2 . For experiments, the signals were calculated from the knowledge of sp(L), and relevant projections of random functions on the graph.

We have compared the performances of Algorithms 2 and 3 against the thresholding procedure described in [START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF]. As the denoising method in [START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF] requires the computation of the whole spectral decomposition of the Laplacian, it does not scale to large graphs. We stress here that we provide a fair comparison with [START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF], only in terms of denoising performance, and with no computational considerations. Moreover, we choose for LocLets to use the most naive thresholding procedure by considering a global and scale independent threshold level.

For all the experiments below, the SGWT and LocLets are built upon the scale and kernel functions giving rise to the Parseval frame of [START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF], whose construction is recalled in Section 4.2.1. More precisely, set respectively ϕ = √ ζ 0 and ψ = √ ζ 1 for the scale and kernel functions with ζ 0 (x) = ω(x), and

ζ 1 (x) = ω(b -1 x) -ω(x)
, where we choose b = 2 and ω is piecewise linear, vanishes on [1, ∞) and is constant equal to one on (-∞, b]. The scales are of the form s j = b -j+1 for j = 1, . . . , J where J is chosen similarly to [START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF].

In what follows, 'PF' stands for Parseval Frame and refers to the estimator of [START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF]; the estimators implemented by Algorithm 2 and Algorithm 3 are referred to as 'LLet' and 'LLet+PF' respectively. The notation 'SNR in ' refers to the trivial model releasing the noisy signal f , corresponding to the classical input noise level measurement, and serves as a worst-case baseline for other models. Below, the latter methodology is shown to outperform all the others for very frequency-sparse signals. It is also worth recalling that 'LLet+PF' benefits from the dimension reduction property of LocLets. More precisely, whereas the whole eigendecomposition of L is required to apply 'PF', for Parseval frame denoising in the context of 'LLet+PF', only a low-rank spectral decomposition is needed, namely the decomposition of L I for I the estimate of supp f . For all our experiments, we set α = 0.001 for Algorithm 1. For the denoising experiment, we compute the best SNR result r D over a large grid of values (t 1 , t 2 ), and for each denoising method D with D ∈ {'SNR in ','PF','LLet','LLet+PF'}. Then, we calculate two metrics: the maximum M D and average value µ D of the values r D over 10 random perturbations of the signal f . We recall that a good quality in denoising is reflected by a large value of the SNR metric.

Analysis of our experiments

Noise level estimation

We have evaluated the performances of estimators σ r mean and σ med in the estimation of the unknown noise level σ from 10 realizations of the noisy signal f = f + ξ for a given noise level σ. Figure 2 (resp. Figure 3 ) shows the best performances of each estimator on the minnesota (resp. net25 ) graph for the non-regular but frequency sparse signal f 1392-1343 (resp. f = f 4971-5020 ), when parameter K ranges in {5, 10, 20, 30, 40, 50} and for level of noise σ = 0.01 (resp. σ = 0.001).

Figure 2 illustrates that both estimators σ r mean and σ med can provide good estimates of σ. Best performances are obtained for values of parameter K below the elbow value K elbow (minnesota) = 22 introduced in Section 5.1. We observe that performances drop considerably if almost no localization is used (for instance, for parameter values K = 1 or K = 2, σ ∼ 0.021 in the experiment of Figure 2, far from the performances for K ≥ 5 for estimating σ = 0.01).

Figure 3 shows that localization is necessary, namely K ≥ 10 or even K ≥ 20, in order to reach the best performances for the large net25 graph. Contrary to experiments for the minnesota graph, estimators 5 10 20 [START_REF] Herley | Minimum rate sampling and reconstruction of signals with arbitrary frequency support[END_REF] σ r mean and σ med underestimate the value of σ. Also, best values of K range between 10 and 30 for net25 graph, compared to best values K = 5 and K = 10 for minnesota graph (see Figure 2). This illustrates the idea that noise level estimation strongly depends on the underlying graph structure. As a consequence, a parameter K selection has to take graph and signal information into account to be relevant. Interestingly, the elbow values K elbow (minnesota) = 22 and K elbow (net25) = 22 provide performances which are not optimal, but close to the best possible ones.

In Figure 4, performances for various values of parameter r are displayed for a fixed parameter K = K elbow (minnesota). While it is true that σ r mean can perform better than σ r med , it happens only for very specific values of r, which a priori depend on the signal regularity. Without any further parameter selection, these observations suggest using the most robust estimator σ med in practice.

Sparse signal denoising

As a first denoising experiment, we have compared the performances of 'LLet', 'PF' and 'LLet+PF' for a fixed value K = K elbow given by the rule of thumb described in Section 5.1. For each matrix in the Extended Matrices Suite, we have experimented the denoising task on two frequency-sparse signals, one regular and the other non-regular. Several values of noise level σ were used, corresponding to values of SNR in ranging in [START_REF] Bercu | Concentration inequalities for sums and martingales[END_REF][START_REF] Defferrard | Convolutional neural networks on graphs with fast localized spectral filtering[END_REF]. Results from experiments are displayed in Tables 5. [START_REF] Belkin | Towards a theoretical foundation for laplacian-based manifold methods[END_REF].2 and 2. The first obvious observation is that 'LLet+PF' performs better than its competitors in almost all situations. The gain is sometimes considerable since we observed a gap of 5dB in µ D -metric between 'LLet+PF' and its closest concurrent 'PF' in some cases, and up to 7dB in M D -metric. These experiments confirm the theoretical guarantees obtained in Theorem 11. The benefits of localization are reduced for graph net25 : Table 2 shows that the more conservative choice K = 5 is better than K = 25. It appears that for net25, the spectrum sp(L) is localized at a small number of distinct eigenvalues, hence diminishing the advantages Another interesting observation is that 'LLet' may outperform 'PF' in some specific signal and noise level configurations, as shown in Table 5.3.2. This is a very favorable result for localized Fourier analysis, since 'LLet' appears to be a technique which is more accurate and more efficient as well compared to 'PF' in some situations. However in many cases, 'LLet' performances drop down compared to the more stable thresholding techniques 'PF' and 'LLet+PF', which use thresholds adapted to the wavelet basis.

We also provide experimental results to understand the extent to which our results depend on the partition size parameter K. A few remarks are suggested by Figure 5: • The best performances are not obtained for the elbow value K elbow , suggesting searching for a more task-adapted size of partition K.

• Good performances persist for values of K much larger than K elbow , and in particular for regular signals.

• For large values of K, there is a severe drop in performances. As explained before, the error generated by Chebyshev's approximation grows with the number of intervals in the partition, which makes the approximation of the support more difficult.

Conclusion and future works

We have introduced a novel technique to efficiently perform graph Fourier analysis. This technique uses functional calculus to perform Fourier analysis on different subsets of the graph Laplacian spectrum. In this paper, we have demonstrated that localization in the spectrum provides interesting improvements in theoretical results for some graph signal analysis tasks. New estimators of the noise level were introduced, taking advantage of the convenient modelling of the denoising problem given by localization, and for which concentration results were proved. Localization allows also to study theoretically the denoising procedure with wavelets, and fits with the design of many well-known techniques (e.g. tight frames for graph analysis). Through many experiments, we have validated that localization techniques introduced in this paper improve on state-of-the-art methods for several standard tasks.

Although we provide a rule of thumb to choose a partition I L = 1≤k≤K I k for which denoising results show good performances, experiments suggest that our elbow rule is not optimal in most cases. There is certainly an interesting topic in searching for a suitable partition I L = 1≤k≤K I k that would be more adapted to a specific task (e.g. denoising). To extend the current work, it would also be interesting to consider other common tasks in GSP, such as de-convolution or in-painting.

Proofs

Proof of Proposition 4.

1. We have fk = f k +ξ k , where ξ k = :λ ∈I k ξ( )χ . Random variables ( ξ( )) are all distributed as N (0, σ 2 ) and independent by orthogonality of the eigenbasis (χ ) . In particular for k = k , vectors ξ k and ξ k are independent as expressions involving variables ξ( ) over disjoint subsets I k and I k . Thus the random variables (c k ) 1≤k≤K are also independent.

2. When n k = n k , ξ k and ξ k are identically distributed and the result follows from Equality [START_REF] Candes | Sparsity and incoherence in compressive sampling[END_REF].

When n k = n k , we have E(c k ) = E(c k ) as the following equality holds for all 1 ≤ k ≤ K:

E(c k ) = f k 2 2 n k + σ 2 .
3. Since ( ξ( )) are independent normal variables N (0, σ 2 ), the statement is clear from the expression

c k = 1 n k :λ ∈I k | ξ( )| 2 .
The following lemma is useful for the proof of Proposition 5. Proof. A simple consequence of [START_REF] Chernoff | A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations[END_REF]Theorem 1] implies that for all n ≥ 1 and all a ≥ p P(Z ≥ na) ≤ (1 -p) 2. For all k = 1, . . . , K f , we define

γ - k = Φ -1 Γn 0 • Φ Γn k n k σ 2 c k and γ + k = Φ -1 Γn ∞ • Φ Γn k n k σ 2 c k .
As a matter of fact, (γ -) k=1,...,K f and (γ + k ) k=1,...,K f are two sequences of i.i.d. random variables with γ - 1 ∼ χ 2 (n 0 ) and γ

+ 1 ∼ χ 2 (n ∞ ) such that ∀k = 1, . . . , K f , γ - k ≤ n k σ 2 c k ≤ γ + k almost surely.
Then, for all t > 0,

P σ 2 med ≥ β -1 σ 2 + 2σ 2 β -1 t = P   K f k=1 1 {c k ≥β -1 σ 2 +2σ 2 β -1 t} ≥ K f 2   ≤ P   K f k=1 1 {γ + k ≥n∞+2n∞t} ≥ K f 2   . (14)
Similarly, for all t ∈ (0, 1),

P σ 2 med ≤ βσ 2 -σ 2 βt ≤ P   K f k=1 1 {γ - k ≤n 0 -n 0 t} ≥ K f 2   . (15)
To conclude, apply Lemma 14 to Inequalities ( 14) and ( 15) to obtain our result.

Proof of Proposition 6. The concentration bound of Equation ( 8) implies that

P(b k ≥ b ) = P(n k b k ≥ n k b ) = P σ -2 n k n ξ 2 2 -ξ k 2 2 ≤ σ -2 f k 2 2 + 2 f k , ξ k ≥ α 2 + P σ -2 n k n ξ 2 2 -ξ k 2 2 ≤ σ -2 f k 2 2 + 2t α,σ f k 2 .
Since subsets I k and I are disjoint, random variables ξ k 2 2 and ξ 2 2 are independent. Thus, n k n ξ 2 2ξ k 2 2 is distributed as n k n Γ n -Γ n k where Γ n k and Γ n are independent random variables with Γ n k ∼ χ 2 (n k ) and Γ n ∼ χ 2 (n ). Therefore, the statement of Proposition 6 follows.

Proof of Proposition 7. First, the following equalities hold:

f -f = f -f I + f I -f = (f -f ) I + f I .
As (f -f ) I and f I are orthogonal vectors, it follows that f -f Proof of Lemma 8. By Equation ( 6) and the concentration bound of Equation ( 8), it follows that

p k = P(σ 2 Γ n k > ξ k 2 2 + f k 2 2 + 2 f k , ξ k ) ≤ α 2 + P σ 2 Γ n k > ξ k 2 2 + f k 2 2 -2 f k 2 t α/2,σ = α 2 + P σ 2 (Γ n k -Γ n k ) > f k 2 2 -2 f k 2 t α/2,σ = α 2 + 1 -Φ Γn k -Γ n k (θ(f k , α, σ)),
where θ(f k , α, σ) = σ -2 ( f k 2 -2t α/2,σ ) f k 2 . Consequently, 1 -Φ Γn k -Γ n k (θ(f k , α, σ)) ≤ α/2 and p k ≤ α.

Proof of Lemma 9. Using an estimate on the χ 2 (n k ) tail distribution and independence of Γ n k and Γ n k = σ -2 ξ k 2 2 , it follows

p k ≥ P σ 2 Γ n k > ξ k 2 2 + f k 2 2 + 2 ξ k , f k , ξ k 2 2 ≤ t β,k ≥ P σ 2 Γ n k > ξ k 2 2 + f k 2 2 + 2 ξ k 2 f k 2 , ξ k 2 2 ≤ t β,k = P σ 2 Γ n k > ( f k 2 + t β,k ) 2 , ξ k 2 2 ≤ t β,k = P σ 2 Γ n k > ( f k 2 + t β,k ) 2 , σ 2 Γ n k ≤ t β,k ≥ P σ 2 Γ n k > ( f k 2 + t β,k ) 2 (1 -β) ≥ α 1 -β × (1 -β) = α.
Proof of Proposition 10. Applying Lemma 8 for all indices 1 ≤ k ≤ K satisfying p k > α, one deduce

f k 2 < t α/2,σ + t 2 α/2,σ + σΦ -1 Γn k -Γ n k (1 - α 2 ) 2 .
from which, since n k = n 1 for all k, Inequality (9) follows.

2. Since σ -2 ||ξ k || 2 2 is distributed as a χ 2 (n 1 ) random variable, the second Inequality [START_REF] Chernoff | A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations[END_REF] follows

E f I -f I 2 2 = k:p k ≤α E ξ k 2 2 = |{k, p k ≤ α}|n 1 σ 2 .
Proof of Theorem 11. Since threshold value is t 2 = 0 on I, f = f I . Then, clearly f I (f I -f I ) = 0 almost surely so that

E f -f 2 2 = E f -f I 2 2 = E f -f I + f I -f I 2 2 = E f -f I 2 2 + f I -f I 2 2 .
Applying Theorem 3 from [START_REF] Göbel | Construction of tight frames on graphs and application to denoising[END_REF] to E f I -f I 2 2 yields our statement.

Proof of Proposition 12. Recalling that, for any function g defined on sp(L) and any subset

I ⊂ I L , n | √ g(L I )δ n , f | 2 = √ g(L I )f 2 2 = g(L I )f, f
it follows by Equations ( 11) and [START_REF] Coifman | Diffusion maps[END_REF].

n,k | ϕ n,k , f | 2 + | ψ 1,n,k , f | 2 + | ψ 2,n,k , f | 2 = k ψ 0 (L I k )f, f + ψ k (L I k )f, f + ψ k (L I k+1 )f, f = ψ 0 (L)f, f + k ψ k (L)f, f = f 2 2
Proof of Proposition 13. Remarking that g j (λ) = ψ(s j ω 0 (λ)) with s j = e -jω γ,J,R , Equation [START_REF] Ronald R Coifman | Diffusion wavelets[END_REF] implies that g m,j = l ψ(s j ω 0 (λ l )) δ m (l)χ l .

Setting J j = [C -1 e (j-R)ω γ,J,R , C -1 e jω γ,J,R ] and recalling that supp( g) = [-Rω γ,J,R , 0], it follows that λ ∈ supp( g j ) if and only if ω 0 (λ) ∈ J j if and only if s j ω 0 (λ) ∈ J 0 . Moreover, J 0 = k I k and J j = s -1 j J 0 yield J j = k s -1 j I k with s -1 j I k ∩ s -1 j I k excepted when j = j ad k = k . Consequently, Equation ( 16) can be reformulated as g m,j = 1≤k≤R-1 ∈I k ψ(s j ω 0 (λ )) δ m ( )χ .

Proposition 4 . 2 2

 42 Let (c k ) 1≤k≤K be the sequence of non-negative random variables defined, for all k = 1, . . . , K, by c k = f k /n k . Then, 1. the random variables c 1 , . . . , c K are independent;2. for all k, k such that f k = f k , c k and c k are identically distributed if and only

Algorithm 2 :

 2 LocLets thresholding estimation procedureData: f , α, (I k ) k=1,...,K , estimated n k = |I k ∩ sp(L)|, thresholds t 1 , t 2Result: estimator f of signal f 1 Apply Algorithm 1 with f , α, (I k ) k=1,...K , estimated n k ; it outputs f I and f I ; 2 Apply soft-thresholding with threshold t 1 to W I f and t 2 to W I f ; 3 Apply the inverse LocLet transform to the soft-thresholded coefficients to obtain f I , f I ; 4 Compute the estimator f = f I + f I ;

Algorithm 3 :

 3 LocLets support approximation, and low-rank Parseval Frame thresholding procedureData: f , α, (I k ) k=1,...,K , estimated n k = |I k ∩ sp(L)|, thresholds t 1 , t 2 Result: estimator f of signal f 1 Apply Algorithm 1 with f , α, (I k ) k=1,...K ,estimated n k ; it outputs f I and f I ; 2 Compute Parseval Frame for L I ; 3 Apply Parseval Frame thresholding with threshold t 1 to f I ; it outputs f I ; 4 Apply soft-thresholding with threshold t 2 to W I f ; 5 Apply the inverse LocLet transform to the soft-thresholded coefficients to obtain f I ; 6 Compute the estimator f = f I + f I ;

  k a Lanczos basis (v k m ) m of the subspace spanned by {χ , ∈ I k } is given. Then the size of sequences (v k m ) m and (v k m ) m,k are respectively of order O(|I k ∩ sp(L)|) = O(n k ) and O(n). Thus, with impulse functions (v k m ) n in place of δ m for transform W I k , the storage requirements of localized transform (W I k f ) 1≤k≤K and the original one Wf are of the same order O(Jn).

Figure 1 :

 1 Figure 1: Variations of E N (K) and MRE N (K) with parameter K.

Figure 2 :

 2 Figure 2: Performances of estimators σ mean (left) and σ med (right) for minnesota graph, signal f 1392-1343 and σ = 0.01.

Figure 3 :

 3 Figure 3: Performances of estimators σ r mean (left) and σ r med (right) for net25 graph, signal f 4971-5020 and σ = 0.001.

Figure 4 :

 4 Figure 4: Dependence on parameter r for minnesota graph, signal f 1392-1343 , K = 22 and σ = 0.1 (left), σ = 0.01 (right).

Figure 5 :

 5 Figure 5: SNR performance depending on parameter K for minnesota graph, σ = 0.01, a regular signal f 2593-2642 (left) and a non-regular signal f 1343-1392 (right), over 10 realizations of noise.

Lemma 14 .

 14 Let Z ∼ B(n, p) for some parameters n ≥ 1 and p ≤ 1/2. ThenP(Z ≥ n/2 ) ≤ exp n 2 ln(4p(1 -p)) .

2 .

 2 It remains to notice that E(|| f I || 2 ) = σ 2 |I ∩ sp(L)|.

1 .

 1 To prove Inequality[START_REF] Chen | Multi-scale anomaly detection algorithm based on infrequent pattern of time series[END_REF], first observe that f = k:I k ⊂I f f k so that f -f I = k:I k ⊂I f f kk:p k ≤α f k .The summands which are not present in both terms are exactly those satisfying eitherI k ⊂ I f and p k > α or I k ∩ I f = ∅ and p k ≤ α. Noting that f k = 0 when I k ∩ I f = ∅, it comes f -

Table 1 :

 1 SNR performance for Swissroll (n = 1000, K = 22).

	signal	σ SNR in	M PF M LLet M LLet+PF	µ PF	µ LLet µ LLet+PF
	f 951-1000 0.005 16.195 17.557 20.580	20.528 17.361 20.035	19.974
	f 501-550	0.005 15.859 18.298	8.244	20.821 18.044	8.140	20.245
	f 951-1000	0.01 10.267 12.183 15.564	15.701 10.433 13.652	13.760
	f 501-550	0.01 10.178 13.121	7.879	16.204 11.165	7.646	14.518
	f 951-1000 0.015	6.763	9.430 12.661	13.129	8.961 12.127	12.388
	f 501-550	0.015	6.362	9.898	7.611	14.159	9.540	7.481	13.398

Table 2 :

 2 SNR performances for denoising task.

	matrix	signal	σ SNR in	M PF M LLet+PF	µ PF µ LLet+PF
	Si2	f 720-769 0.005 17.104 22.344	26.973 21.849	25.170
	(n = 762, K = 22)	f 370-419 0.005 16.820 18.034	21.778 17.813	20.673
		f 720-769	0.01 11.408 16.821	22.501 16.572	20.558
		f 370-419	0.01 11.175 12.444	19.740 12.151	17.121
		f 720-769	0.02	4.826 11.476	15.695 11.104	14.711
		f 370-419	0.02	5.047	7.354	13.542	6.925	12.677
	Minnesota	f 2593-2642 0.004 13.599 17.839	20.717 17.672	20.035
	(n = 2642, K = 22) f 1343-1392 0.004 13.741 15.999	20.388 15.822	19.234
		f 2593-2642 0.005 11.681 16.086	19.342 15.830	18.417
		f 1343-1392 0.005 11.916 14.459	18.392 14.298	18.029
		f 2593-2642	0.01	5.911 10.875	14.143 10.605	13.556
		f 1343-1392	0.01	5.843	9.660	11.762	9.409	10.952
	Cage9	f 3485-3534 0.003 15.016 20.477	9.700 20.216	9.664
	(n = 3534, K = 22) f 1785-1834 0.003 15.014 15.876		15.798	16.799
		f 3485-3534 0.005 10.503 17.290	18.410 16.772	18.185
		f 1785-1834 0.005 10.507 12.118	13.032 12.035	12.898
		f 3485-3534 0.009	5.423 13.002	13.264 12.763	12.898
		f 1785-1834 0.009	5.395	8.329	10.468	8.168	9.827
	Saylr4	f 3515-3564 0.003 14.871 23.108	24.516 23.040	24.117
	(n = 3564, K = 22) f 2015-2064 0.003 15.069 21.365	23.903 21.010	23.412
		f 3515-3564 0.005 10.478 19.135	20.966 18.943	20.268
		f 2015-2064 0.005 10.635 17.016	19.610 16.662	18.732
		f 3515-3564 0.009	5.420 15.277	17.070 14.791	16.567
		f 2015-2064 0.009	5.480 12.055	14.802 11.830	14.031
	Net25	f 9471-9520 0.006	4.682	5.171	5.319	5.094	5.205
	(n = 9520, K = 5)	f 4971-5020 0.006	4.577	5.811	6.035	5.714	5.933
		f 9471-9520 0.007	3.282	5.287	5.416	5.127	5.251
		f 4971-5020 0.007	3.406	5.267	5.451	5.104	5.266
		f 9471-9520 0.008	2.208	5.171	5.268	4.928	5.034
		f 4971-5020 0.008	2.153	4.450	4.594	4.319	4.471
	Net25	f 9471-9520 0.006	4.495	5.319	6.004	5.190	5.834
	(n = 9520, K = 25) f 4971-5020 0.006	4.574	5.849	4.752	5.714	4.579
		f 9471-9520 0.007	3.307	5.264	5.765	4.951	5.447
		f 4971-5020 0.007	3.256	5.132	4.182	5.014	4.102
		f 9471-9520 0.008	2.111	4.913	5.249	4.756	5.128
		f 4971-5020 0.008	2.150	4.345	3.670	4.251	3.554

  Proof of Proposition 5.1. For k such thatI k ⊂ I f , we have c k = σ 2 n k Γ n k , which follows the Γ( n k 2 , 2σ 2 n k ) distribution.Then concentration inequalities for σ mean (c) 2 are a direct consequence of Theorem 2.57 in[START_REF] Bercu | Concentration inequalities for sums and martingales[END_REF], applied with a k = n k 2 and b k = 2σ 2 n k .

						1-a 1 -a	1 -a a	p	a n	.
	Now the result follows since na = n/2 implies 1 2 ≤ a ≤ 1 2 + 1 n so that
	(1 -p) 1-a 1 -a	1 -a a	p	a	≤	(1 -a) a-1 a a	p(1 -p) ≤ 4p(1 -p).

) respectively.