Attenuating random and coherent noise is an important part of seismic data processing. Successful removal results in an enhanced image of the subsurface geology, which facilitate economical decisions in hydrocarbon exploration. This motivates the search for new and more efficient techniques for noise removal. The main goal of this thesis is to present an overview of the Singular Spectrum Analysis (SSA) technique, studying its potential application to seismic data processing. An overview of the application of SSA for time series analysis is presented. Subsequently, its applications for random and coherent noise attenuation, expansion to multiple dimensions, and for the recovery of unrecorded seismograms are described. To improve the performance of SSA, a faster implementation via a randomized singular value decomposition is proposed. Results obtained in this work show that SSA is a versatile method for both random and coherent noise attenuation, as well as for the recovery of missing traces. / Geophysics

No description available.

Quantum chemistry is plagued by the presence of high-rank quantities, stemming from the N-body nature of the electronic Schrödinger equation. These high-rank quantities present a significant mathematical and computational barrier to the computation of chemical observables, and also drastically complicate the pedagogical understanding of important interactions between particles in a molecular system. The application of physically-motivated rank reduction approaches can help address these to problems. This thesis details recent efforts to apply rank reduction techniques in both of these arenas. With regards to computational tractability, the representation of the 1/r Coulomb repulsion between electrons is a critical stage in the solution of the electronic Schrödinger equation. Typically, this interaction is encapsulated via the order-4 electron repulsion integral (ERI) tensor, which is a major bottleneck in terms of generation, manipulation, and storage. Many rank reduction techniques for the ERI tensor have been proposed to ameliorate this bottleneck, most notably including the order-3 density fitting (DF) and pseudospectral (PS) representations. Here we detail a new and uniquely powerful factorization - tensor hypercontraction (THC). THC decomposes the ERI tensor as a product of five order-2 matrices (the first wholly order-2 compression proposed for the ERI) and offers great flexibility for low-scaling algorithms for the manipulations of the ERI tensor underlying electronic structure theory. THC is shown to be physically-motivated, markedly accurate, and uniquely efficient for some of the most difficult operations encountered in modern quantum chemistry. On the front of chemical understanding of electronic structure theory, we present our recent work in developing robust two-body partitions for ab initio computations of intermolecular interactions. Noncovalent interactions are the critical and delicate forces which govern such important processes as drug-protein docking, enzyme function, crystal packing, and zeolite adsorption. These forces arise as weak residual interactions leftover after the binding of electrons and nuclei into molecule, and, as such, are extremely difficult to accurately quantify or systematically understand. Symmetry-adapted perturbation theory (SAPT) provides an excellent approach to rigorously compute the interaction energy in terms of the physically-motivated components of electrostatics, exchange, induction, and dispersion. For small intermolecular dimers, this breakdown provides great insight into the nature of noncovalent interactions. However, SAPT abstracts away considerable details about the N-body interactions between particles on the two monomers which give rise to the interaction energy components. In the work presented herein, we step back slightly and extract an effective 2-body interaction for each of the N-body SAPT terms, rather than immediately tracing all the way down to the order-0 interaction energy. This effective order-2 representation of the order-N SAPT interaction allows for the robust assignment of interaction energy contributions to pairs of atoms or functional groups (the A-SAPT or F-SAPT partitions), allowing one to discuss the interaction in terms of atom- or functional-group-pairwise interactions. These A-SAPT and F-SAPT partitions can provide deep insight into the origins of complicated noncovalent interactions, e.g., by clearly shedding light on the long-contested question of the nature of the substituent effect in substituted sandwich benzene dimers.

Efficient receiver designs for cooperative communication networks are becoming increasingly important. In previous work, cooperative networks communicated with the use of L relays. As the receiver is constrained, channel shortening and reduced-rank techniques were employed to design the preprocessing matrix that reduces the length of the received vector from L to U. In the first part of the work, a receiver structure is proposed which combines our proposed threshold selection criteria with the joint iterative optimization (JIO) algorithm that is based on the mean square error (MSE). Our receiver assists in determining the optimal U. Furthermore, this receiver provides the freedom to choose U for each frame depending on the tolerable difference allowed for MSE. Our study and simulation results show that by choosing an appropriate threshold, it is possible to gain in terms of complexity savings while having no or minimal effect on the BER performance of the system. Furthermore, the effect of channel estimation on the performance of the cooperative system is investigated. In the second part of the work, a joint preprocessor-based detector for cooperative communication networks is proposed for one-way and two-way relaying. This joint preprocessor-based detector operates on the principles of minimizing the symbol error rate (SER) instead of minimizing MSE. For a realistic assessment, pilot symbols are used to estimate the channel. From our simulations, it can be observed that our proposed detector achieves the same SER performance as that of the maximum likelihood (ML) detector with all participating relays. Additionally, our detector outperforms selection combining (SC), channel shortening (CS) scheme and reduced-rank techniques when using the same U. Finally, our proposed scheme has the lowest computational complexity.

No description available.

Dans cette thèse, nous nous sommes intéressés à l'analyse locale de systèmes différentiels linéaires singulièrement perturbés et de systèmes de Pfaff complètement intégrables et multivariés à croisements normaux. De tels systèmes ont une vaste littérature et se retrouvent dans de nombreuses applications. Cependant, leur résolution symbolique est toujours à l'étude. Nos approches reposent sur l'état de l'art de la réduction formelle des systèmes linéaires singuliers d'équations différentielles ordinaires univariées (ODS). Dans le cas des systèmes différentiels linéaires singulièrement perturbés, les complications surviennent essentiellement à cause du phénomène des points tournants. Nous généralisons les notions et les algorithmes introduits pour le traitement des ODS afin de construire des solutions formelles. Les algorithmes sous-jacents sont également autonomes (par exemple la réduction de rang, la classification de la singularité, le calcul de l'indice de restriction). Dans le cas des systèmes de Pfaff, les complications proviennent de l'interdépendance des multiples sous-systèmes et de leur nature multivariée. Néanmoins, nous montrons que les invariants formels de ces systèmes peuvent être récupérés à partir d'un ODS associé, ce qui limite donc le calcul à des corps univariés. De plus, nous donnons un algorithme de réduction de rang et nous discutons des obstacles rencontrés. Outre ces deux systèmes, nous parlons des singularités apparentes des systèmes différentiels univariés dont les coefficients sont des fonctions rationnelles et du problème des valeurs propres perturbées. Les techniques développées au sein de cette thèse facilitent les généralisations d'autres algorithmes disponibles pour les systèmes différentiels univariés aux cas des systèmes bivariés ou multivariés, et aussi aux systèmes d''equations fonctionnelles. / In this thesis, we are interested in the local analysis of singularly-perturbed linear differential systems and completely integrable Pfaffian systems in several variables. Such systems have a vast literature and arise profoundly in applications. However, their symbolic resolution is still open to investigation. Our approaches rely on the state of art of formal reduction of singular linear systems of ordinary differential equations (ODS) over univariate fields. In the case of singularly-perturbed linear differential systems, the complications arise mainly from the phenomenon of turning points. We extend notions introduced for the treatment of ODS to such systems and generalize corresponding algorithms to construct formal solutions in a neighborhood of a singularity. The underlying components of the formal reduction proposed are stand-alone algorithms as well and serve different purposes (e.g. rank reduction, classification of singularities, computing restraining index). In the case of Pfaffian systems, the complications arise from the interdependence of the multiple components which constitute the former and the multivariate nature of the field within which reduction occurs. However, we show that the formal invariants of such systems can be retrieved from an associated ODS, which limits computations to univariate fields. Furthermore, we complement our work with a rank reduction algorithm and discuss the obstacles encountered. The techniques developed herein paves the way for further generalizations of algorithms available for univariate differential systems to bivariate and multivariate ones, for different types of systems of functional equations.

Cette thèse est consacrée aux méthodes symboliques de résolution locale des systèmes différentiels linéaires à coefficients dans K = C((x)), le corps des séries de Laurent, sur un corps effectif C. Plus précisément, nous nous intéressons aux algorithmes effectifs de réduction formelle. Au cours de la réduction, nous sommes amenés à introduire des extensions algébriques du corps de coefficients K (extensions algébriques de C, ramifications de la variable x) afin d’obtenir une structure plus fine. Du point de vue algorithmique, il est préférable de retarder autant que possible l’introduction de ces extensions. Dans ce but, nous développons un nouvel algorithme de réduction formelle qui utilise l’anneau des endomorphismes du système, appelé « eigenring », afin de se ramener au cas d’un système indécomposable sur K. En utilisant la classification formelle donnée par Balser-Jurkat-Lutz, nous déduisons la structure de l’eigenring d’un système indécomposable. Ces résultats théoriques nous permettent de construire une décomposition sur le corps de base K qui sépare les différentes parties exponentielles du système et permet ainsi d’isoler dans des sous-systèmes, indécomposables sur K, les différentes extensions de corps qui peuvent apparaître afin de les traiter séparément. Dans une deuxième partie, nous nous intéressons à l’algorithme de Miyake pour la réduction formelle. Celle-ci est basée sur le calcul du poids et d’une suite de Volevic de la matrice de valuation du système. Nous donnons des interprétations en théorie de graphe et en algèbre tropicale du poids et suites de Volevic, et obtenons ainsi des méthodes de calculs efficaces sur le plan pratique, à l’aide de la programmation linéaire. Ceci complète une étape fondamentale dans l’algorithme de réduction de Miyake. Ces différents algorithmes sont implémentés sous forme de librairies pour le logiciel de calcul formel Maple. Enfin, nous présentons une discussion sur la performance de l’algorithme de réduction avec l’eigenring ainsi qu’une comparaison en terme de temps de calcul entre notre implémentation de l’algorithme de réduction de Miyake par la programmation linéaire et ceux de Barkatou et Pflügel. / This thesis is devoted to symbolic methods for local resolution of linear differential systems with coefficients in K = C((x)), the field of Laurent series, on an effective field C. More specifically, we are interested in effective algorithms for formal reduction. During the reduction, we are led to introduce algebraic extensions of the field of coefficients K (algebraic extensions of C, ramification of the variable x) in order to obtain a finer structure. From an algorithmic point of view, it is preferable to delay as much as possible the introduction of these extensions. To this end, we developed a new algorithm for formal reduction that uses the ring of endomorphisms of the system, called "eigenring". Using the formal classification given by Balser-Jurkat-Lutz, we deduce the structure of the eigenring of an indecomposable system. These theoretical results allow us to construct a decomposition on the base field K that separates the different exponential parts of the system and thus allows us to isolate, in indecomposable subsystems in K, the different algebraic extensions that can appear in order to treat them separately. In a second part, we are interested in Miyake’s algorithm for formal reduction. This algorithm is based on the computation of the Volevic weight and numbers of the valuation matrix of the system. We provide interpretations in graph theory and tropical algebra of the Volevic weight and numbers, and thus obtain practically efficient methods using linear programming. This completes a fundamental step in the Miyake reduction algorithm. These different algorithms are implemented as libraries for the computer algebra software Maple. Finally, we present a discussion on the performance of the reduction algorithm using the eigenring as well as a comparison in terms of timing between our implementation of Miyake’s reduction algorithm by linear programming and the algorithms of Barkatou and Pflügel.

In many fields of science, engineering, and economics large amounts of data are stored and there is a need to analyze these data in order to extract information for various purposes. Data mining is a general concept involving different tools for performing this kind of analysis. The development of mathematical models and efficient algorithms is of key importance. In this thesis we discuss algorithms for the reduced rank regression problem and algorithms for the computation of the best multilinear rank approximation of tensors. The first two papers deal with the reduced rank regression problem, which is encountered in the field of state-space subspace system identification. More specifically the problem is \[ \min_{\rank(X) = k} \det (B - X A)(B - X A)\tp, \] where $A$ and $B$ are given matrices and we want to find $X$ under a certain rank condition that minimizes the determinant. This problem is not properly stated since it involves implicit assumptions on $A$ and $B$ so that $(B - X A)(B - X A)\tp$ is never singular. This deficiency of the determinant criterion is fixed by generalizing the minimization criterion to rank reduction and volume minimization of the objective matrix. The volume of a matrix is defined as the product of its nonzero singular values. We give an algorithm that solves the generalized problem and identify properties of the input and output signals causing a singular objective matrix. Classification problems occur in many applications. The task is to determine the label or class of an unknown object. The third paper concerns with classification of handwritten digits in the context of tensors or multidimensional data arrays. Tensor and multilinear algebra is an area that attracts more and more attention because of the multidimensional structure of the collected data in various applications. Two classification algorithms are given based on the higher order singular value decomposition (HOSVD). The main algorithm makes a data reduction using HOSVD of 98--99 \% prior the construction of the class models. The models are computed as a set of orthonormal bases spanning the dominant subspaces for the different classes. An unknown digit is expressed as a linear combination of the basis vectors. The resulting algorithm achieves 5\% in classification error with fairly low amount of computations. The remaining two papers discuss computational methods for the best multilinear rank approximation problem \[ \min_{\cB} \| \cA - \cB\| \] where $\cA$ is a given tensor and we seek the best low multilinear rank approximation tensor $\cB$. This is a generalization of the best low rank matrix approximation problem. It is well known that for matrices the solution is given by truncating the singular values in the singular value decomposition (SVD) of the matrix. But for tensors in general the truncated HOSVD does not give an optimal approximation. For example, a third order tensor $\cB \in \RR^{I \x J \x K}$ with rank$(\cB) = (r_1,r_2,r_3)$ can be written as the product \[ \cB = \tml{X,Y,Z}{\cC}, \qquad b_{ijk}=\sum_{\lambda,\mu,\nu} x_{i\lambda} y_{j\mu} z_{k\nu} c_{\lambda\mu\nu}, \] where $\cC \in \RR^{r_1 \x r_2 \x r_3}$ and $X \in \RR^{I \times r_1}$, $Y \in \RR^{J \times r_2}$, and $Z \in \RR^{K \times r_3}$ are matrices of full column rank. Since it is no restriction to assume that $X$, $Y$, and $Z$ have orthonormal columns and due to these constraints, the approximation problem can be considered as a nonlinear optimization problem defined on a product of Grassmann manifolds. We introduce novel techniques for multilinear algebraic manipulations enabling means for theoretical analysis and algorithmic implementation. These techniques are used to solve the approximation problem using Newton and Quasi-Newton methods specifically adapted to operate on products of Grassmann manifolds. The presented algorithms are suited for small, large and sparse problems and, when applied on difficult problems, they clearly outperform alternating least squares methods, which are standard in the field.