Soutenance de thèse d’Elie Chedemail

Elie Chedemail soutiendra sa thèse de doctorat « Débruitage de signaux définis sur des graphes de grande taille avec application à la confidentialité différentielle » le jeudi 21 décembre 2023 à 14 h, à l’ENSAI.

Ecole Doctorale : Mathématiques, Télécommunications, Informatique, Signal, Systèmes, Electronique (Matisse)

Unité de recherche : CREST (UMR 9194)

Directeur de thèse : Fabien NAVARRO, Maître de Conférences, Université Paris 1 Panthéon-Sorbonne

Composition du jury

NomQualitéEtablissementRôle
BORGNAT PierreDirecteur de RechercheENS Lyon (69)Examinateur
DE LOYNES BasileEnseignant-ChercheurENSAI (35)Co-encadrant
EL KOLEI SalimaEnseignant-ChercheurENSAI (35)Examinateur
FADILI JalalProfesseurENSICAEN (14)Examinateur
LE PENNEC ErwanProfesseurEcole Polytechnique (91)Examinateur
NAVARRO FabienMaître de ConférencesUniversité Paris 1 Panthéon-Sorbonne (75)Directeur de thèse
OLIVIER BaptisteIngénieur rechercheIBM (Amsterdam)Co-encadrant
SHUMAN DavidProfesseurFranklin W. Olin College of Engineering (USA)Examinateur

Mots-clés

Ondelettes sur graphe, réduction du bruit, confidentialité différentielle

Débruitage de signaux définis sur des graphes de grande taille avec application à la confidentialité différentielle

Résumé : Au cours de la dernière décennie, le traitement du signal sur graphe est devenu un domaine de recherche très actif. Plus précisément, le nombre d’applications utilisant des repères construits à partir de graphes, tels que les ondelettes sur graphe, a augmenté de manière significative. Nous considérons en particulier le débruitage de signaux sur graphes au moyen d’une décomposition dans un repère ajusté d’ondelettes. Cette approche est basée sur le seuillage des coefficients d’ondelettes à l’aide de l’estimateur sans biais du risque de Stein (SURE). Nous étendons cette méthodologie aux graphes de grande taille en utilisant l’approximation par polynômes de Chebyshev qui permet d’éviter la décomposition de la matrice laplacienne du graphe. La principale difficulté est le calcul de poids dans l’expression du SURE faisant apparaître un terme de covariance en raison de la nature surcomplète du repère d’ondelettes. Le calcul et le stockage de celui-ci est donc nécessaire et rédhibitoire à grande échelle. Pour estimer cette covariance, nous développons et analysons un estimateur de Monte-Carlo reposant sur la transformation rapide de signaux aléatoires. Cette nouvelle méthode de débruitage trouve une application naturelle en confidentialité différentielle dont l’objectif est de protéger les données sensibles utilisées par les algorithmes. Une évaluation expérimentale de ses performances est réalisée sur des graphes de taille variable à partir de données réelles et simulées.

Abstract: Over the last decade, signal processing on graphs has become a very active area of research. Specifically, the number of applications using frames built from graphs, such as wavelets on graphs, has increased significantly. We consider in particular signal denoising on graphs via a wavelet tight frame decomposition. This approach is based on the thresholding of the wavelet coefficients using Stein’s unbiased risk estimate (SURE). We extend this methodology to large graphs using Chebyshev polynomial approximation, which avoids the decomposition of the graph Laplacian matrix. The main limitation is the computation of weights in the SURE expression, which includes a covariance term due to the overcomplete nature of the wavelet frame. The computation and storage of the latter is therefore necessary and impractical for large graphs. To estimate such covariance, we develop and analyze a Monte Carlo estimator based on the fast transform of random signals. This new denoising methodology finds a natural application in differential privacy whose purpose is to protect sensitive data used by algorithms. An experimental evaluation of its performance is carried out on graphs of varying size, using real and simulated data.