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.