Matrices de code sous-échantillonnées

Bibliothèques numériques

L’une des premières collections de logiciels de haute qualité a été une série d’algorithmes écrit en Algol 60 paru en 1971. Il comprenait onze sous-programmes pour les systèmes linéaires, les moindres carrés linéaires et la programmation linéaire ainsi que dix-huit routines pour le calcul des valeurs propres algébrique. En 1974, EISPACK est apparu comme une collection de sous-routines écrites en language Fortran IV contenant le calcul des valeurs propres et les vecteurs propres des matrices. EISPACK était basé principalement sur les procédures d’Algol. LINPACK, réalisé en 1979, est une collection de sous-routines écrites en Fortran pour résoudre les systèmes d’équations linéaires ainsi que le problème des moindres carrés linéaire. L’une des caractéristiques les plus importantes de LINPACK est que les sous-routines effectuent autant de calculs que possible par des appels aux sous-programmes d’algèbre linéaire de base (BLAS).

BLAS, connu sous le nom de niveau 1 BLAS, a été introduit en 1979 par Lawson. BLAS est un ensemble de fonctions standardisés réalisant des opérations de base d’algèbre linéaire comme des additions de vecteurs, des produits scalaires ou des multiplications de matrices. Le niveau 2 BLAS sont des opérations impliquant une matrice et un ou plusieurs vecteurs, alors que le niveau 3 de BLAS, introduit en 1990, a été dérivé du niveau 2 BLAS en remplaçant les vecteurs par des matrices. Ils permettent d’atteindre des performances proches de l’optimum sur une grande variété d’architectures. La routine de multiplication matrice-matrice (GEMM) est le noyau du niveau 3 de BLAS qui se rapproche le plus des performances de pointe. La collection LAPACK de sous-programmes a été publiée en 1992 et est conçue pour remplacer et intégrer les algorithmes dans LINPACK et EISPACK. LAPACK est une bibliothèque écrite en fortran dédié à l’algèbre linéaire numérique, elle est développé par l’université du Tennessee. Un certain nombre d’algorithmiques avancées qui ont été faites après LINPACK et EISPACK ont été écrits et incorporés. Les sous-programmes sont restructurés pour atteindre une efficacité beaucoup plus grande sur les ordinateurs haute performance modernes. La bibliothèque LAPACK a énormément simplifié les calculs matriciels. Plusieurs formes spéciales de matrices sont supportées par LAPACK. ScaLAPACK est une extension de la bibliothèque logicielle LAPACK conçu pour être efficace. Les sous programmes de ScaLAPACK ressemble beaucoup à ceux de LAPACK. LAPACK95 est une interface Fortran 95 de la bibliothèque LAPACK écrite en Fortran 77. Il améliore l’interface utilisateur originale du paquet LAPACK, en profitant des simplifications considérables que Fortran-95 permet.

Matrices aléatoires

Dans cette partie, on se concentrera sur les matrices d’échantillonnage aléatoires et les matrices de projection aléatoire afin de résoudre le problème linéaire d’approximation des moindres carrés. Étant donnée une n×d matrice A, avec n _ d, et un vecteur b, le problème d’approximation des moindres carrés se base sur la recherche du vecteur xopt = minx k Ax − b k2 Les méthodes classiques, y compris la décomposition de Cholesky, les factorisation QR, et la décomposition en valeurs singulières, calcule la solution en temps O(nd2). Les Méthodes aléatoires résolvent ce problème en multipliant la matrice A par une matrice aléatoire. Les matrices d’échantillonnage consistent à travailler avec un petit nombre échantillonnées et remis à l’échelle de la matrice A (ainsi que les éléments de b), tandis que pour les méthodes de projection aléatoire utilise un nombre de combinaisons linéaires des lignes de A et des éléments de b. Si on résout le sous système induit, alors les approximations des erreurs relatives trés fines à la solution du problème original sont obtenues.

En plus, on peut utiliser les matrices aléatoires pour calculer un préconditionneur du problème original afin d’obtenir une très haute précision des approximations. Ces implémentations numériques s’exécutent en O(nd2) temps, elles sont plus rapides que les méthodes numériques déterministes existantes. On peut représenter l’échantillonnage aléatoire avec une matrice d’échantillonnage aléatoire S, si l’échantillonnage aléatoire est implémenté en choisissant des colonnes c, alors la matrice S de n × c a des entrées Sij = 1 p cpi Alternativement, étant donné une matrice A 2 Rn×d, on peut s’intéresser à une projection aléatoire en multipliant A par une matrice de projection aléatoire n × l , ainsi sélectionnant l combinaisons linéaires des colonnes de A. Il y a plusieurs façons de construire une telle matrice. Johnson et Lindenstrauss [25] considèrent une projection orthogonale sur un espace de dimension aléatoire, où l = O(logm)

Résolution des problèmes larges des moindres carrés

Dans ce chapitre, nous allons travailler sur trois méthodes aléatoires. Trois algorithmes différents afin de trouver la solution la plus approximée au problème des moindres carrés dont les matrices inclues sont de grandes tailles. Comme première partie du travail nous devons effectuer un échantillonnage aléatoire moyen d’une projection afin de respecter la moyenne statistique et par la suite, accélérer le calcul de la solution des moindres carrés. Afin de résoudre le problème des moindres carrés avec précision, nous proposons une approche basée sur un préconditionneur aléatoire, puis nous itérons avec une méthode d’itération. Pour trouver la matrice de préconditionnement, nous calculons la factorisation QR de A, malheureusement cette étape est coûteuse. Dans ce cas, Woodruff [42] a proposé l’utilisation des méthodes aléatoires pour trouver R approximativement. Soit S une matrice aléatoire, nous formons L = StA = QR telle que QR est la décomposition de L. Ensuite, nous choisissons R−1 comme matrice de préconditionnement de A [30]. Par la suite, nous appelons une méthode d’itération avec R−1 comme préconditionneur. Finalement, nous déterminons ˜x tel que R˜x = y. Le choix approprié du préconditionneur est pris en compte car le conditionnement de la matrice AR−1 est petit. Par la suite, l’utilisation d’une méthode itérative tel que le gradient conjugué nécessite quelques itérations pour obtenir y.

Conclusion et perspectives

Les moindres carrés linéaires est un problème de calcul très importants, qui est originaire de la nécessité d’ajuster un modèle mathématique linéaire à des observations données. Ils sont appliqués dans plusieurs domaines notamment en ingénierie tels que les statistiques, la géodésie, la photogrammétrie, le traitement du signal et le contrôle. Nous avons montré dans cette thèse comment les calculs d’algèbre linéaire peuvent être accélérés en utilisant des techniques statistiques dans le cas d’un système linéaire. Nous avons étudié des transformations aléatoires de A qui nous permettent d’éviter de pivoter et par la suite réduire le volume des matrices. Ces transformations s’effectuent à un coût calculatoire très abordable tout en donnant une précision satisfaisante lorsqu’on les compare avec le pivotage. L’utilisation des méthodes aléatoires pour l’analyse des données volumineuse sont très utilisées à cause de la rapidité du calcul en plus de sa simplicité à mettre en oeuvre que les méthodes traditionnelles. Le but de ce travail est de démontrer que les méthodes aléatoires représentent un outil puissant pour la résolution des problèmes des moindres carrés larges. Le choix entre les différentes matrices aléatoires afin d’obtenir la solution du problème des moindres carrés dépend de la recherche d’une solution avec une probabilité élevée. Dans cette thèse, nous avons analysé les différents types de matrices aléatoires. A noter que nous pouvons utiliser les matrices aléatoires sur des matrices relativement denses ou creuses.

Dans cette thèse, parmi les trois algorithmes définis dans le chapitre 4, nous déduisons que la combinaison utilisé dans le premier algorithme est la meilleure puisqu’elle tient compte d’une méthode aléatoire et qu’elle s’intéresse à l’aspect statistique. Dans cet algorithme nous échantillonnons uniformément et rééchelonnons la projection d’Hadamard de la matrice A, dont le but est d’accélérer le calcul de la solution avec précision. Nous remarquons que l’algorithme 1 fonctionne mieux que les autres modèles. Le conditionnement des moindres carrés est considéré comme une étape fondamental pour l’analyse de la sensibilité des solutions. Il a été appliqué à de nombreux problèmes d’algèbre linéaire tels que les systèmes linèaires, les moindres carrés linéaires …Il mesure l’effet sur la solution des petits changements des données. Cette quantité dépend des normes choisies. Dans ce travail, l’estimation statistique du conditionnement a été obtenue via la dérivée de Fréchet et avec la méthode appelée des petits échantillons. Dans les perspectives, nous s’intéresserons à l’application des méthodes aléatoires sur les systèmes linéaires dans le cas où le rang de la matrice est incomplet ainsi qu’aux problèmes des moindres carrés non linéaires. Par la suite appliqué cette théorie dans le domaine de détermination des orbites des satellites.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport gratuit propose le téléchargement des modèles gratuits de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

I Propriétés statistiques du problème des moindres carrés
1 Introduction
2 Notions de Statistique
2.1 indépendance des variables aléatoires
2.2 Espérance d’une variable aléatoire
2.3 Propriétés de l’espérance mathématique
2.4 Variance et covariance d’une variable aléatoire
2.5 Propriété de la variance
2.6 Inégalité de Markov
3 Méthodes numériques
4 Bibliothèques numériques
4.1 Produit de Kronecker
5 Résolution des problèmes des moindres carrés
5.1 Sketching matrice
5.2 Approximation des moindres carrés
II Matrices aléatoires
1 Introduction
2 Préliminaires
3 Produit matriciel aléatoire
4 Matrices aléatoires
4.1 Projection Gaussienne
4.2 Transformé d’Hadamard aléatoire
4.3 Transformée de Fourier randomisée sous-échantillonnée
4.4 Leverage score échantillonné
4.5 Count-sketch
4.6 Matrices de code sous-échantillonnées
4.7 Comparaison entre les différentes matrices aléatoires
5 Approximation des moindres carrés
6 Conclusion
III Conditionnement des problèmes des moindres carrés
1 Introduction
2 Formule explicite du conditionnement des moindres carrés
3 Estimation statistique du conditionnement
IV Résolution des problèmes larges des moindres carrés
1 Introduction
2 Résolution des problèmes des moindres carrés
2.1 Description d’algorithme 1
2.2 Description d’algorithme 2
2.3 Description d’algorithme 3
3 Application numérique
Conclusion et perspectives
Annexe 1