Université de Rennes E︠́chantillonnage de données : acquisition comprimée et réduction de graphe Data sampling : database compression, graph reduction, and compressed sensing; three aspects of dimensionality reduction réduction de dimensionsparsification de grapheéchantillonnageacquisition comprimée dimensionnality reductiongraph sparsificationsamplingcompressive sensing Échantillonnage (statistique) Données -- Compression (informatique) Dans cette thèse, nous étudions trois aspects du problème de réduction de la dimension. Le premier concerne la compression de base de données. Nous proposons plusieurs algorithmes d’échantillonnage préservant l’information contenue dans les données, ainsi que deux applications au conditionnement de matrices et à l’acquisition comprimée. Ces algorithmes sont déterministes et leur faible complexité en font une alternative intéressante aux meilleurs algorithmes connus. Le second aspect abordé concerne la sparsification de graphe. Nous proposons de réduire le nombre d’arêtes d’un graphe tout en préservant sa connectivité. Nous élaborons deux algorithmes itératifs, déterministes et de faible complexité, permettant d’approcher la solution de ce problème NP-difficile. Nous présentons également une application possible à la simplification du graphe sous-jacent à un réseau neuronal sur graphe. La troisième partie de la thèse traite d’acquisition comprimée et propose une analyse statistique d’un algorithme de reconstruction de signaux parcimonieux. Dans le cadre d’un modèle asymptotique où la matrice de mesure et le signal sont aléatoires et pour lequel les paramètres de taille tendent vers l’infini à la même vitesse, nous montrons que la probabilité de succès à une itération donnée tend vers 1. In this thesis, we study three aspects of the dimensionality reduction problem. The first concerns database compression. We propose several sampling algorithms that preserve the information contained in the data, along with two applications in matrix conditioning and compressive sensing. These algorithms are deterministic, and their low complexity makes them an interesting alternative to the state-of-the-art algorithms. The second aspect addressed is graph reduction. We aim to reduce the number of edges, while attempting to preserve the graph’s connectivity. We develop two iterative, deterministic, and low-complexity algorithms that approximate the solution to this NP-hard problem. We also present a possible application in simplifying the underlying graph of a Graph Neural Network. The third part of the thesis deals with compressive sensing and provides a statistical analysis of a reconstruction algorithm for sparse signals. In the context of an asymptotic model where both the measurement matrix and the sparse signal are random, and the size parameters tend to infinity at the same rate, we show that the probability of success at a given iteration tends to 1. Electronic Thesis or DissertationText en application/pdf1 : 6503 Kohttps://ged.univ-rennes1.fr/nuxeo/site/esupversions/f896c37b-5980-457b-aa0a-7bc88ea9442e Petit Claude 1969-01-24 FR 282516158 claude.petit@cpmath.fr 2024URENS049 http://www.theses.fr/2024URENS049 2024-11-26 Signal, image, vision Université de Rennesthesis.degree.grantor_1 26693823X Doctorat non ouiRoumyAlineintervenant_1150161522MaurelPierreintervenant_213063185XSaumardAdrienintervenant_5148321933DuprezElsaintervenant_3176646671SoussenCharlesintervenant_4164038469 MATISSEecoleDoctorale_1 267602553 INRIA-RENNES partenaireRecherche_1 133175863 ddc:004 RoumyAlineMaurelPierreDuprezElsaSoussenCharlesSaumardAdrienUniversité de RennesMATISSE INRIA-RENNES ASCII PDF 6658884