Consider the problem of solving a large system of linear algebraic equations, using the Krylov subspace methods. In order to find the solution efficiently, the system often needs to be preconditioned, i.e., transformed prior to the iterative scheme. A feature of the system that often enables fast solution with efficient preconditioners is the structural sparsity of the corresponding matrix. A recent development brought another and a slightly different phe- nomenon called the data sparsity. In contrast to the classical (structural) sparsity, the data sparsity refers to an uneven distribution of extractable information inside the matrix. In practice, the data sparsity of a matrix ty- pically means that its blocks can be successfully approximated by matrices of low rank. Naturally, this may significantly change the character of the numerical computations involving the matrix. The thesis focuses on finding ways to construct Cholesky-based preconditioners for the conjugate gradi- ent method to solve systems with symmetric and positive definite matrices, exploiting a combination of the data and structural sparsity. Methods to exploit the data sparsity are evolving very fast, influencing not only iterative solvers but direct solvers as well. Hierarchical schemes based on the data sparsity concepts can be derived...

On étudie la décomposition de matrice de Hankel comme une somme des matrices de Hankel de rang faible en corrélation avec la décomposition de son symbole σ comme une somme des séries exponentielles polynomiales. On présente un nouvel algorithme qui calcule la décomposition d’un opérateur de Hankel de petit rang et sa décomposition de son symbole en exploitant les propriétés de l’algèbre quotient de Gorenstein . La base de est calculée à partir la décomposition en valeurs singuliers d’une sous-matrice de matrice de Hankel . Les fréquences et les poids se déduisent des vecteurs propres généralisés des sous matrices de Hankel déplacés de . On présente une formule pour calculer les poids en fonction des vecteurs propres généralisés au lieu de résoudre un système de Vandermonde. Cette nouvelle méthode est une généralisation de Pencil méthode déjà utilisée pour résoudre un problème de décomposition de type de Prony. On analyse son comportement numérique en présence des moments contaminés et on décrit une technique de redimensionnement qui améliore la qualité numérique des fréquences d’une grande amplitude. On présente une nouvelle technique de Newton qui converge localement vers la matrice de Hankel de rang faible la plus proche au matrice initiale et on montre son effet à corriger les erreurs sur les moments. On étudie la décomposition d’un tenseur multi-symétrique T comme une somme des puissances de produit des formes linéaires en corrélation avec la décomposition de son dual comme une somme pondérée des évaluations. On utilise les propriétés de l’algèbre de Gorenstein associée pour calculer la décomposition de son dual qui est définie à partir d’une série formelle τ. On utilise la décomposition d’un opérateur de Hankel de rang faible associé au symbole τ comme une somme des opérateurs indécomposables de rang faible. La base d’ est choisie de façon que la multiplication par certains variables soit possible. On calcule les coordonnées des points et leurs poids correspondants à partir la structure propre des matrices de multiplication. Ce nouvel algorithme qu’on propose marche bien pour les matrices de Hankel de rang faible. On propose une approche théorique de la méthode dans un espace de dimension n. On donne un exemple numérique de la décomposition d’un tenseur multilinéaire de rang 3 en dimension 3 et un autre exemple de la décomposition d’un tenseur multi-symétrique de rang 3 en dimension 3. On étudie le problème de complétion de matrice de Hankel comme un problème de minimisation. On utilise la relaxation du problème basé sur la minimisation de la norme nucléaire de la matrice de Hankel. On adapte le SVT algorithme pour le cas d’une matrice de Hankel et on calcule l’opérateur linéaire qui décrit les contraintes du problème de minimisation de norme nucléaire. On montre l’utilité du problème de décomposition à dissocier un modèle statistique ou biologique. / We study the decomposition of a multivariate Hankel matrix as a sum of Hankel matrices of small rank in correlation with the decomposition of its symbol σ as a sum of polynomialexponential series. We present a new algorithm to compute the low rank decomposition of the Hankel operator and the decomposition of its symbol exploiting the properties of the associated Artinian Gorenstein quotient algebra . A basis of is computed from the Singular Value Decomposition of a sub-matrix of the Hankel matrix . The frequencies and the weights are deduced from the generalized eigenvectors of pencils of shifted sub-matrices of Explicit formula for the weights in terms of the eigenvectors avoid us to solve a Vandermonde system. This new method is a multivariate generalization of the so-called Pencil method for solving Pronytype decomposition problems. We analyse its numerical behaviour in the presence of noisy input moments, and describe a rescaling technique which improves the numerical quality of the reconstruction for frequencies of high amplitudes. We also present a new Newton iteration, which converges locally to the closest multivariate Hankel matrix of low rank and show its impact for correcting errors on input moments. We study the decomposition of a multi-symmetric tensor T as a sum of powers of product of linear forms in correlation with the decomposition of its dual as a weighted sum of evaluations. We use the properties of the associated Artinian Gorenstein Algebra to compute the decomposition of its dual which is defined via a formal power series τ. We use the low rank decomposition of the Hankel operator associated to the symbol τ into a sum of indecomposable operators of low rank. A basis of is chosen such that the multiplication by some variables is possible. We compute the sub-coordinates of the evaluation points and their weights using the eigen-structure of multiplication matrices. The new algorithm that we propose works for small rank. We give a theoretical generalized approach of the method in n dimensional space. We show a numerical example of the decomposition of a multi-linear tensor of rank 3 in 3 dimensional space. We show a numerical example of the decomposition of a multi-symmetric tensor of rank 3 in 3 dimensional space. We study the completion problem of the low rank Hankel matrix as a minimization problem. We use the relaxation of it as a minimization problem of the nuclear norm of Hankel matrix. We adapt the SVT algorithm to the case of Hankel matrix and we compute the linear operator which describes the constraints of the problem and its adjoint. We try to show the utility of the decomposition algorithm in some applications such that the LDA model and the ODF model.

This thesis deals with the nuclear magnetic resonance field, especially spectroscopy and spectroscopy imaging, sparse signal representation and low-rank approximation approaches. Spectroscopy imaging methods are becoming very popular in clinical praxis, however, long measurement times and low resolution prevent them from their spreading. The goal of this thesis is to improve state of the art methods by using sparse signal representation and low-rank approximation approaches. The compressed sensing technique is demonstrated on the examples of magnetic resonance imaging speedup and hyperspectral imaging data saving. Then, a new spectroscopy imaging scheme based on compressed sensing is proposed. The thesis deals also with the in vivo spectrum quantitation problem by designing the MRSMP algorithm specifically for this purpose.

Tato práce se zabývá doplňováním chybějících dat do audio signálů a algoritmy řešícími problém založenými na řídké reprezentaci audio signálu. Práce se zaměřuje na některé algoritmy, které řeší doplňování chybějících dat do audio signálů pomocí řídké reprezentace signálů. Součástí práce je také návrh algoritmu, který používá řídkou reprezentaci signálu a také nízkou hodnost signálu ve spektrogramu audio signálu. Dále práce uvádí implementaci tohoto algoritmu v programu Matlab a jeho vyhodnocení.

Magnetic resonance perfusion imaging is a today's very promising method for medicine diagnosis. This thesis deals with a sparse representation of signals, low-rank matrix recovery and compressed sensing, which allows overcoming present physical limitations of magnetic resonance perfusion imaging. Several models for reconstruction of measured perfusion data is introduced and numerical methods for their software implementation, which is an important part of the thesis, is mentioned. Proposed models are verified on simulated and real perfusion data from magnetic resonance.

Une des finalités du traitement d’antenne est la détection et la localisation de cibles en milieu bruité. Dans la plupart des cas pratiques, comme par exemple le RADAR ou le SONAR actif, il faut estimer dans un premier temps les propriétés statistiques du bruit, et plus précisément sa matrice de covariance ; on dispose à cette fin de données secondaires supposées identiquement distribuées. Dans ce contexte, les hypothèses suivantes sont généralement formulées : bruit gaussien, données secondaires ne contenant que du bruit, et bien sûr matériels fonctionnant parfaitement. Il est toutefois connu aujourd’hui que le bruit en RADAR est de nature impulsive et que l’hypothèse Gaussienne est parfois mal adaptée. C’est pourquoi, depuis quelques années, le bruit et en particulier le fouillis de sol est modélisé par des processus elliptiques, et principalement des Spherically Invariant Random Vectors (SIRV). Dans ce nouveau cadre, la Sample Covariance Matrix (SCM) estimant classiquement la matrice de covariance du bruit entraîne des pertes de performances très importantes des détecteurs / estimateurs. Dans ce contexte non-gaussien, d’autres estimateurs de la matrice de covariance mieux adaptés à cette statistique du bruit ont été développés : la Matrice du Point Fixe (MPF) et les M-estimateurs.Parallèlement, dans un cadre où le bruit se décompose sous la forme d’une somme d’un fouillis rang faible et d’un bruit blanc, la matrice de covariance totale est structurée sous la forme rang faible plus identité. Cette information peut être utilisée dans le processus d'estimation afin de réduire le nombre de données nécessaires. De plus, il aussi est possible d'utiliser le projecteur orthogonal au sous espace fouillis à la place de la matrice de covariance ce qui nécessite moins de données secondaires et d’être aussi plus robuste aux données aberrantes. On calcule classiquement ce projecteur à partir d'un estimateur de la matrice de covariance. Néanmoins l'état de l'art ne présente pas d'estimateurs à la fois être robustes aux distributions hétérogènes, et rendant compte de la structure rang faible des données. C'est pourquoi ces travaux se focalisent sur le développement de nouveaux estimateurs (de covariance et de sous espace), directement adaptés au contexte considéré. Les contributions de cette thèse s'orientent donc autour de trois axes :- Nous présenterons tout d'abord un modèle statistique précis : celui de sources hétérogènes ayant une covariance rang faible noyées dans un bruit blanc gaussien. Ce modèle et est, par exemple, fortement justifié pour des applications de type radar. Il à cependant peu été étudié pour la problématique d'estimation de matrice de covariance. Nous dériverons donc l'expression du maximum de vraisemblance de la matrice de covariance pour ce contexte. Cette expression n'étant pas une forme close, nous développerons différents algorithmes pour tenter de l'atteindre efficacement.- Nous développons de nouveaux estimateurs directs de projecteur sur le sous espace fouillis, ne nécessitant pas un estimé de la matrice de covariance intermédiaire, adaptés au contexte considéré.- Nous étudierons les performances des estimateurs proposés et de l'état de l'art sur une application de Space Time Adaptative Processing (STAP) pour radar aéroporté, au travers de simulations et de données réelles. / One purpose of array processing is the detection and location of a target in a noisy environment. In most cases (as RADAR or active SONAR), statistical properties of the noise, especially its covariance matrix, have to be estimated using i.i.d. samples. Within this context, several hypotheses are usually made: Gaussian distribution, training data containing only noise, perfect hardware. Nevertheless, it is well known that a Gaussian distribution doesn’t provide a good empirical fit to RADAR clutter data. That’s why noise is now modeled by elliptical process, mainly Spherically Invariant Random Vectors (SIRV). In this new context, the use of the SCM (Sample Covariance Matrix), a classical estimate of the covariance matrix, leads to a loss of performances of detectors/estimators. More efficient estimators have been developed, such as the Fixed Point Estimator and M-estimators.If the noise is modeled as a low-rank clutter plus white Gaussian noise, the total covariance matrix is structured as low rank plus identity. This information can be used in the estimation process to reduce the number of samples required to reach acceptable performance. Moreover, it is possible to estimate the basis vectors of the clutter-plus-noise orthogonal subspace rather than the total covariance matrix of the clutter, which requires less data and is more robust to outliers. The orthogonal projection to the clutter plus noise subspace is usually calculated from an estimatd of the covariance matrix. Nevertheless, the state of art does not provide estimators that are both robust to various distributions and low rank structured.In this Thesis, we therefore develop new estimators that are fitting the considered context, to fill this gap. The contributions are following three axes :- We present a precise statistical model : low rank heterogeneous sources embedded in a white Gaussian noise.We express the maximum likelihood estimator for this context.Since this estimator has no closed form, we develop several algorithms to reach it effitiently.- For the considered context, we develop direct clutter subspace estimators that are not requiring an intermediate Covariance Matrix estimate.- We study the performances of the proposed methods on a Space Time Adaptive Processing for airborne radar application. Tests are performed on both synthetic and real data.

Multivariate linear regression methods are widely used statistical tools in data analysis, and were developed when some response variables are studied simultaneously, in which our aim is to study the relationship between predictor variables and response variables through the regression coefficient matrix. The rapid improvements of information technology have brought us a large number of large-scale data, but also brought us great challenges in data processing. When dealing with high dimensional data, the classical least squares estimation is not applicable in multivariate linear regression analysis. In recent years, some approaches have been developed to deal with high-dimensional data problems, among which dimension reduction is one of the main approaches. In some literature, random projection methods were used to reduce dimension in large datasets. In Chapter 2, a new random projection method, with low-rank matrix approximation, is proposed to reduce the dimension of the parameter space in high-dimensional multivariate linear regression model. Some statistical properties of the proposed method are studied and explicit expressions are then derived for the accuracy loss of the method with Gaussian random projection and orthogonal random projection. These expressions are precise rather than being bounds up to constants. In multivariate regression analysis, reduced rank regression is also a dimension reduction method, which has become an important tool for achieving dimension reduction goals due to its simplicity, computational efficiency and good predictive performance. In practical situations, however, the performance of the reduced rank estimator is not satisfactory when the predictor variables are highly correlated or the ratio of signal to noise is small. To overcome this problem, in Chapter 3, we incorporate matrix projections into reduced rank regression method, and then develop reduced rank regression estimators based on random projection and orthogonal projection in high-dimensional multivariate linear regression models. We also propose a consistent estimator of the rank of the coefficient matrix and achieve prediction performance bounds for the proposed estimators based on mean squared errors. Envelope technology is also a popular method in recent years to reduce estimative and predictive variations in multivariate regression, including a class of methods to improve the efficiency without changing the traditional objectives. Variable selection is the process of selecting a subset of relevant features variables for use in model construction. The purpose of using this technology is to avoid the curse of dimensionality, simplify models to make them easier to interpret, shorten training time and reduce overfitting. In Chapter 4, we combine envelope models and a group variable selection method to propose an envelope-based sparse reduced rank regression estimator in high-dimensional multivariate linear regression models, and then establish its consistency, asymptotic normality and oracle property. Tensor data are in frequent use today in a variety of fields in science and engineering. Processing tensor data is a practical but challenging problem. Recently, the prevalence of tensor data has resulted in several envelope tensor versions. In Chapter 5, we incorporate envelope technique into tensor regression analysis and propose a partial tensor envelope model, which leads to a parsimonious version for tensor response regression when some predictors are of special interest, and then consistency and asymptotic normality of the coefficient estimators are proved. The proposed method achieves significant gains in efficiency compared to the standard tensor response regression model in terms of the estimation of the coefficients for the selected predictors. Finally, in Chapter 6, we summarize the work carried out in the thesis, and then suggest some problems of further research interest. / Dissertation / Doctor of Philosophy (PhD)

To leverage the extreme parallelism of emerging architectures, so that scientific applications can fulfill their high fidelity and multi-physics potential while sustaining high efficiency relative to the limiting resource, numerical algorithms must be redesigned. Algorithmic redesign is capable of shifting the limiting resource, for example from memory or communication to arithmetic capacity. The benefit of algorithmic redesign expands greatly when introducing a tunable tradeoff between accuracy and resources. Scientific applications from diverse sources rely on dense matrix operations. These operations arise in: Schur complements, integral equations, covariances in spatial statistics, ridge regression, radial basis functions from unstructured meshes, and kernel matrices from machine learning, among others. This thesis demonstrates how to extend the problem sizes that may be treated and to reduce their execution time. Two “universes” of algorithmic innovations have emerged to improve computations by orders of magnitude in capacity and runtime. Each introduces a hierarchy, of rank or precision. Tile Low-Rank approximation replaces blocks of dense operator with those of low rank. Mixed precision approximation, increasingly well supported by contemporary hardware, replaces blocks of high with low precision. Herein, we design new high-performance direct solvers based on the synergism of TLR and mixed precision. Since adapting to data sparsity leads to heterogeneous workloads, we rely on task-based runtime systems to orchestrate the scheduling of fine-grained kernels onto computational resources. We first demonstrate how TLR permits to accelerate acoustic scattering and mesh deformation simulations. Our solvers outperform the state-of-art libraries by up to an order of magnitude. Then, we demonstrate the impact of enabling mixed precision in bioinformatics context. Mixed precision enhances the performance up to three-fold speedup. To facilitate the adoption of task-based runtime systems, we introduce the AL4SAN library to provide a common API for the expression and queueing of tasks across multiple dynamic runtime systems. This library handles a variety of workloads at a low overhead, while increasing user productivity. AL4SAN enables interoperability by switching runtimes at runtime, which permits to achieve a twofold speedup on a task-based generalized symmetric eigenvalue solver.

<p dir="ltr">We propose a fully online procedure to conduct statistical inference with adaptively collected data. The low-rank structure of the model parameter and the adaptivity nature of the data collection process make this task challenging: standard low-rank estimators are biased and cannot be obtained in a sequential manner while existing inference approaches in sequential decision-making algorithms fail to account for the low-rankness and are also biased. To tackle the challenges previously outlined, we first develop an online low-rank estimation process employing Stochastic Gradient Descent with noisy observations. Subsequently, to facilitate statistical inference using the online low-rank estimator, we introduced a novel online debiasing technique designed to address both sources of bias simultaneously. This method yields an unbiased estimator suitable for parameter inference. Finally, we developed an inferential framework capable of establishing an online estimator for performing inference on the optimal policy value. In theory, we establish the asymptotic normality of the proposed online debiased estimators and prove the validity of the constructed confidence intervals for both inference tasks. Our inference results are built upon a newly developed low-rank stochastic gradient descent estimator and its non-asymptotic convergence result, which is also of independent interest.</p>

Les dernières décennies ont donné lieux à d'énormes progrès dans la simulation numérique des phénomènes physiques. D'une part grâce au raffinement des méthodes de discrétisation des équations aux dérivées partielles. Et d'autre part grâce à l'explosion de la puissance de calcul disponible. Pourtant, de nombreux problèmes soulevés en ingénierie tels que les simulations multi-physiques, les problèmes d'optimisation et de contrôle restent souvent hors de portée. Le dénominateur commun de ces problèmes est le fléau des dimensions. Un simple problème tridimensionnel requiert des centaines de millions de points de discrétisation auxquels il faut souvent ajouter des milliers de pas de temps pour capturer des dynamiques complexes. L'avènement des supercalculateurs permet de générer des simulations de plus en plus fines au prix de données gigantesques qui sont régulièrement de l'ordre du pétaoctet. Malgré tout, cela n'autorise pas une résolution ``exacte'' des problèmes requérant l'utilisation de plusieurs paramètres. L'une des voies envisagées pour résoudre ces difficultés est de proposer des représentations ne souffrant plus du fléau de la dimension. Ces représentations que l'on appelle séparées sont en fait un changement de paradigme. Elles vont convertir des objets tensoriels dont la croissance est exponentielle $n^d$ en fonction du nombre de dimensions $d$ en une représentation approchée dont la taille est linéaire en $d$. Pour le traitement des données tensorielles, une vaste littérature a émergé ces dernières années dans le domaine des mathématiques appliquées.Afin de faciliter leurs utilisations dans la communauté des mécaniciens et en particulier pour la simulation en mécanique des fluides, ce manuscrit présente dans un vocabulaire rigoureux mais accessible les formats de représentation des tenseurs et propose une étude détaillée des algorithmes de décomposition de données qui y sont associées. L'accent est porté sur l'utilisation de ces méthodes, aussi la bibliothèque de calcul texttt{pydecomp} développée est utilisée pour comparer l'efficacité de ces méthodes sur un ensemble de cas qui se veut représentatif. La seconde partie de ce manuscrit met en avant l'étude de l'écoulement dans une cavité entraînée à haut nombre de Reynolds. Cet écoulement propose une physique très riche (séquence de bifurcation de Hopf) qui doit être étudiée en amont de la construction de modèle réduit. Cette étude est enrichie par l'utilisation de la décomposition orthogonale aux valeurs propres (POD). Enfin une approche de construction ``physique'', qui diffère notablement des développements récents pour les modèles d'ordre réduit, est proposée. La connaissance détaillée de l'écoulement permet de construire un modèle réduit simple basé sur la mise à l'échelle des fréquences d'oscillation (time-scaling) et des techniques d'interpolation classiques (Lagrange,..). / Numerical simulation has experienced tremendous improvements in the last decadesdriven by massive growth of computing power. Exascale computing has beenachieved this year and will allow solving ever more complex problems. But suchlarge systems produce colossal amounts of data which leads to its own difficulties.Moreover, many engineering problems such as multiphysics or optimisation andcontrol, require far more power that any computer architecture could achievewithin the current scientific computing paradigm. In this thesis, we proposeto shift the paradigm in order to break the curse of dimensionality byintroducing decomposition and building reduced order models (ROM) for complexfluid flows.This manuscript is organized into two parts. The first one proposes an extendedreview of data reduction techniques and intends to bridge between appliedmathematics community and the computational mechanics one. Thus, foundingbivariate separation is studied, including discussions on the equivalence ofproper orthogonal decomposition (POD, continuous framework) and singular valuedecomposition (SVD, discrete matrices). Then a wide review of tensor formats andtheir approximation is proposed. Such work has already been provided in theliterature but either on separate papers or into a purely applied mathematicsframework. Here, we offer to the data enthusiast scientist a comparison ofCanonical, Tucker, Hierarchical and Tensor train formats including theirapproximation algorithms. Their relative benefits are studied both theoreticallyand numerically thanks to the python library texttt{pydecomp} that wasdeveloped during this thesis. A careful analysis of the link between continuousand discrete methods is performed. Finally, we conclude that for mostapplications ST-HOSVD is best when the number of dimensions $d$ lower than fourand TT-SVD (or their POD equivalent) when $d$ grows larger.The second part is centered on a complex fluid dynamics flow, in particular thesingular lid driven cavity at high Reynolds number. This flow exhibits a seriesof Hopf bifurcation which are known to be hard to capture accurately which iswhy a detailed analysis was performed both with classical tools and POD. Oncethis flow has been characterized, emph{time-scaling}, a new ``physics based''interpolation ROM is presented on internal and external flows. This methodsgives encouraging results while excluding recent advanced developments in thearea such as EIM or Grassmann manifold interpolation.