Plusieurs problèmes en mathématiques appliquées requièrent la résolution de systèmes linéaires de très grandes tailles, et parfois ces systèmes doivent être résolus de multiples fois. Dans de tels cas, les algorithmes standards basés sur l'élimination de Gauss demandent O(n^3) opérations arithmétiques pour résoudre un système de taille n, et ce sera un handicap pour le calcul. C'est pour cela qu'on cherche à utiliser la structure pour réduire le temps de calcul.<br /><br /> La structure de Toeplitz, de Hankel, de Cauchy, de Vandermonde et d'autre structure plus générales sont bien exploitées pour réduire la complexité de résolution d'un système linéaire à O(n log^2 n) opérations arithmétiques.<br /><br /> Les matrices structurées en deux niveaux et surtout les matrices de Toeplitz par blocs de Toeplitz (TBT) apparaissent dans beaucoup des applications. Le but de ce travail est de trouver des algorithmes de résolution rapide pour des systèmes TBT de grande taille.<br /><br /> Dans cette thèse, on décrit les difficultés de ce problème. On donne trois algorithmes rapide, en O(n^3/2) opérations, de résolution pour les systèmes de Toeplitz bande par blocs Toeplitz bande. On donne aussi une nouvelle méthode de résolution des systèmes de Toeplitz scalaires en donnant une relation entre la solution d'un système de Toeplitz scalaires et les syzygies des polynômes en une seule variable. On généralise cette méthode pour les matrices TBT et on donne une relation entre la solution d'un tel système linéaire et les syzygies des polynômes en deux variables.

Dans la première partie de cette thèse, on formule deux méthodes pour le calcul d'une décomposition polyadique canonique avec facteurs matriciels linéairement structurés (tels que des facteurs de Toeplitz ou en bande): un algorithme de moindres carrés alternés contraint (CALS) et une solution algébrique dans le cas où tous les facteurs sont circulants. Des versions exacte et approchée de la première méthode sont étudiées. La deuxième méthode fait appel à la transformée de Fourier multidimensionnelle du tenseur considéré, ce qui conduit à la résolution d'un système d'équations monomiales homogènes. Nos simulations montrent que la combinaison de ces approches fournit un estimateur statistiquement efficace, ce qui reste vrai pour d'autres combinaisons de CALS dans des scénarios impliquant des facteurs non-circulants. La seconde partie de la thèse porte sur la récupération de tenseurs de rang faible et, en particulier, sur le problème de reconstruction tensorielle (TC). On propose un algorithme efficace, noté SeMPIHT, qui emploie des projections séquentiellement optimales par mode comme opérateur de seuillage dur. Une borne de performance est dérivée sous des conditions d'isométrie restreinte habituelles, ce qui fournit des bornes d'échantillonnage sous-optimales. Cependant, nos simulations suggèrent que SeMPIHT obéit à des bornes optimales pour des mesures Gaussiennes. Des heuristiques de sélection du pas et d'augmentation graduelle du rang sont aussi élaborées dans le but d'améliorer sa performance. On propose aussi un schéma d'imputation pour TC basé sur un seuillage doux du coeur du modèle de Tucker et son utilité est illustrée avec des données réelles de trafic routier / In the first part of this thesis, we formulate two methods for computing a canonical polyadic decomposition having linearly structured matrix factors (such as, e.g., Toeplitz or banded factors): a general constrained alternating least squares (CALS) algorithm and an algebraic solution for the case where all factors are circulant. Exact and approximate versions of the former method are studied. The latter method relies on a multidimensional discrete-time Fourier transform of the target tensor, which leads to a system of homogeneous monomial equations whose resolution provides the desired circulant factors. Our simulations show that combining these approaches yields a statistically efficient estimator, which is also true for other combinations of CALS in scenarios involving non-circulant factors. The second part of the thesis concerns low-rank tensor recovery (LRTR) and, in particular, the tensor completion (TC) problem. We propose an efficient algorithm, called SeMPIHT, employing sequentially optimal modal projections as its hard thresholding operator. Then, a performance bound is derived under usual restricted isometry conditions, which however yield suboptimal sampling bounds. Yet, our simulations suggest SeMPIHT obeys optimal sampling bounds for Gaussian measurements. Step size selection and gradual rank increase heuristics are also elaborated in order to improve performance. We also devise an imputation scheme for TC based on soft thresholding of a Tucker model core and illustrate its utility in completing real-world road traffic data acquired by an intelligent transportation