The purpose of this thesis is to study how to overcome difficulties one typically encounters when solving non-negative inverse problems by standard Krylov subspace methods. We first give a theoretical background to the non-negative inverse problems. Then we concentrate on selected modifications of Krylov subspace methods known to improve the solution significantly. We describe their properties, provide their implementation and propose an improvement for one of them. After that, numerical experiments are presented giving a comparison of the methods and analyzing the influence of the present parameters on the behavior of the solvers. It is clearly demonstrated, that the methods imposing nonnegativity perform better than the unconstrained methods. Moreover, our improvement leads in some cases to a certain reduction of the number of iterations and consequently to savings of the computational time while preserving a good quality of the approximation.

No description available.

The theoretical problem of finding the solution to an underdeterminedset of linear equations has for several years attracted considerable attentionin the literature. This problem has many practical applications.One example of such an application is compressed sensing (cs), whichhas the potential to revolutionize how we acquire and process signals. Ina general cs setup, few measurement coefficients are available and thetask is to reconstruct a larger, sparse signal.In this thesis we focus on algorithm design and selected applicationsfor cs. The contributions of the thesis appear in the following order:(1) We study an application where cs can be used to relax the necessityof fast sampling for power spectral density estimation problems. Inthis application we show by experimental evaluation that we can gainan order of magnitude in reduced sampling frequency. (2) In order toimprove cs recovery performance, we extend simple well-known recoveryalgorithms by introducing a look-ahead concept. From simulations it isobserved that the additional complexity results in significant improvementsin recovery performance. (3) For sensor networks, we extend thecurrent framework of cs by introducing a new general network modelwhich is suitable for modeling several cs sensor nodes with correlatedmeasurements. Using this signal model we then develop several centralizedand distributed cs recovery algorithms. We find that both thecentralized and distributed algorithms achieve a significant gain in recoveryperformance compared to the standard, disconnected, algorithms.For the distributed case, we also see that as the network connectivity increases,the performance rapidly converges to the performance of thecentralized solution. / <p>QC 20120229</p>

En esta tesis profundizamos en el estudio de los códigos flag. Un flag es una sucesión de subespacios encajados de un espacio vectorial finitodimensional sobre un cuerpo también finito y un código flag es una colección no vacía de flags. Estos códigos fueron introducidos en 2018 por Liebhold et al. como una generalización de los códigos de subespacio, ampliamente estudiados en la última década. Cada código flag define de forma natural una familia de códigos de subespacio: sus códigos proyectados. A lo largo de esta tesis, investigamos la relación existente entre los códigos flag y sus respectivos códigos proyectados, a través de problemas de diferente naturaleza y utilizando herramientas provenientes de distintas áreas de las matemáticas. A continuación, exponemos brevemente el contenido de cada uno de los nueve capítulos que constituyen esta tesis. En primer lugar, abordamos el estudio de los códigos flag de distancia óptima. Estos códigos presentan gran interés puesto que detectan y corrigen el máximo número de errores y/o borrados posibles. En el Capítulo 1 caracterizamos estos códigos en términos de sus códigos proyectados. Además, bajo ciertas condiciones, concluimos que los códigos flag de distancia óptima alcanzan también el máximo cardinal posible cuando uno de sus códigos proyectados es un código spread. Los Capítulos 1 y 2 están dedicados al estudio y la construcción sistemática de esta familia especial de códigos flag (los de distancia óptima con un spread como proyectado) para cualquier elección de los parámetros. Por otra parte, en los Capítulos 3 y 6 utilizamos la acción transitiva del grupo general lineal sobre la variedad de flags y determinamos subgrupos adecuados para obtener construcciones, ahora orbitales, de códigos flag de distancia óptima con un spread entre sus proyectados. El Capítulo 4, por su parte, es un estudio general de propiedades de códigos flag orbitales bajo la acción natural del grupo multiplicativo de un cuerpo finito: los códigos flag cíclicos. Para ello, resulta crucial conocer el llamado mejor amigo del flag generador. En el mismo trabajo, estudiamos los “códigos flag de Galois”, en los que el flag generador está dado por una torre de subcuerpos encajados. En este caso, obtenemos construcciones orbitales cíclicas con spreads en todos los códigos proyectados. Además, probamos que las posibilidades para la distancia de un código flag de Galois son muy reducidas y determinamos qué subgrupos permiten alcanzar cada una de ellas. Este estudio continúa en el Capítulo 7, donde consideramos los llamados códigos flag de Galois generalizados: aquellos en los que el flag generador contiene cuerpos encajados, pero no todos sus subespacios son cuerpos. En este caso, mostramos que la presencia de cuerpos en el flag generador tampoco es compatible con todos los valores de la distancia de los códigos orbitales que este genera. Sin embargo, presentamos construcciones de estos códigos que nos permiten afirmar que, al contrario de lo que ocurre con los códigos de Galois, no todas las distancias compatibles con la estructura de cuerpos son realmente alcanzables. En el Capítulo 5 hacemos un estudio pormenorizado de los códigos flag consistentes: una familia de códigos flag cuyos parámetros quedan perfectamente determinados por los de sus códigos proyectados. Además, probamos que, bajo la condición de consistencia, ciertas propiedades estructurales de un código flag son equivalentes a las análogas para sus códigos proyectados y presentamos varias familias de ejemplos. Por último, la condición de consistencia también resulta ser de gran utilidad a la hora de decodificar códigos flag y proporcionamos un algoritmo de decodificación en el canal de borrado. Los Capítulos 8 y 9 están dedicados al estudio del parámetro distancia de los códigos flag. En el primero de ellos, introducimos el concepto de vector distancia y determinamos los valores de la distancia entre flags que pueden ser obtenidos a través de vectores distancia satisfaciendo determinadas condiciones. Este estudio se relaciona, a continuación, con el número de subespacios que dos flags distintos pueden compartir sin comprometer el valor de la distancia mínima de un código flag. Como consecuencia, obtenemos nuevas cotas para el cardinal de códigos flag para cualquier elección de los parámetros. Por último, en el Capítulo 9, interpretamos la distancia entre flags a través de estructuras combinatorias que construimos ad hoc para el estudio de nuestro problema. Más concretamente, asociamos un diagrama de Ferrers adecuado a la variedad de flags completos y, a través de él, identificamos condiciones sobre la distancia entre flags con ciertos elementos combinatorios provenientes de la Teoría de Particiones. Este nuevo diccionario nos permite obtener nuevos resultados que relacionan los parámetros de un código flag con los de sus proyectados, así como reinterpretar la caracterización de códigos flag de distancia óptima propuesta en el primer capítulo en términos de objetos combinatorios. / Generalitat Valenciana y Fondo Social Europeo (ACIF/2018/196)

Wastewater treatment plants (WWTPs) face increasingly stringent effluent quality constraints as a result of rising environmental concerns. Efficient operation of the secondary clarification process is essential to be able to meet these strict regulations. Treatment plants can benefit greatly from making better use of available resources through improved automation and implementing more process systems engineering techniques to enhance plant performance. As such, the primary objective of this research is to utilize data-driven modeling techniques to obtain a representative model of a simplified secondary clarification unit in a WWTP. First, a deterministic subspace-based identification approach is used to estimate a linear state-space model of the secondary clarification process that can accurately predict process dynamics, with the ultimate objective of motivating the use of the subspace model in a model predictive control (MPC) framework for closed-loop control of the clarification process. To this end, a low-order subspace model which relates a set of typical measured outputs from a secondary clarifier to a set of typical inputs is identified and subsequently validated on simulated data obtained via Hydromantis's WWTP simulation software, GPS-X. Results illustrate that the subspace model is able to approximate the nonlinear process behaviour well and can effectively predict the dynamic output trajectory for various candidate input profiles, thus establishing its candidacy for use in MPC. Subsequently, a framework for forecasting the occurrence of sludge bulking--and consequently clarification failure--based on an engineered interaction variable that aims to capture the relationship between key input variables is proposed. Partial least squares discriminant analysis (PLS-DA) is used to discriminate between process conditions associated with clarification failure versus effective clarification. Preliminary results show that PLS-DA models augmented with the interaction variable demonstrate improved predictions and higher classification accuracy. / Thesis / Master of Applied Science (MASc)

No description available.

We propose a new framework for understanding block Krylov subspace methods, which hinges on a matrix-valued inner product. We can recast the ``classical" block Krylov methods, such as O'Leary's block conjugate gradients, global methods, and loop-interchange methods, within this framework. Leveraging the generality of the framework, we develop an efficient restart procedure and error bounds for the shifted block full orthogonalization method (Sh-BFOM(m)). Regarding BFOM as the prototypical block Krylov subspace method, we propose another formalism, which we call modified BFOM, and show that block GMRES and the new block Radau-Lanczos method can be regarded as modified BFOM. In analogy to Sh-BFOM(m), we develop an efficient restart procedure for shifted BGMRES with restarts (Sh-BGMRES(m)), as well as error bounds. Using this framework and shifted block Krylov methods with restarts as a foundation, we formulate block Krylov subspace methods with restarts for matrix functions acting on multiple vectors f(A)B. We obtain convergence bounds for \bfomfom (BFOM for Functions Of Matrices) and block harmonic methods (i.e., BGMRES-like methods) for matrix functions. With various numerical examples, we illustrate our theoretical results on Sh-BFOM and Sh-BGMRES. We also analyze the matrix polynomials associated to the residuals of these methods. Through a variety of real-life applications, we demonstrate the robustness and versatility of B(FOM)^2 and block harmonic methods for matrix functions. A particularly interesting example is the tensor t-function, our proposed definition for the function of a tensor in the tensor t-product formalism. Despite the lack of convergence theory, we also show that the block Radau-Lanczos modification can reduce the number of cycles required to converge for both linear systems and matrix functions. / Mathematics

Science and engineering problems frequently require solving a sequence of single linear systems or a sequence of dual linear systems. We develop algorithms that recycle Krylov subspaces and preconditioners from one system (or pair of systems) in the sequence to the next, leading to efficient solutions. Besides the benefit of only having to store few Lanczos vectors, using BiConjugate Gradients (BiCG) to solve dual linear systems may have application-specific advantages. For example, using BiCG to solve the dual linear systems arising in interpolatory model reduction provides a backward error formulation in the model reduction framework. Using BiCG to evaluate bilinear forms -- for example, in the variational Monte Carlo (VMC) algorithm for electronic structure calculations -- leads to a quadratic error bound. Since one of our focus areas is sequences of dual linear systems, we introduce recycling BiCG, a BiCG method that recycles two Krylov subspaces from one pair of dual linear systems to the next pair. The derivation of recycling BiCG also builds the foundation for developing recycling variants of other bi-Lanczos based methods like CGS, BiCGSTAB, BiCGSTAB2, BiCGSTAB(l), QMR, and TFQMR. We develop a generalized bi-Lanczos algorithm, where the two matrices of the bi-Lanczos procedure are not each other's conjugate transpose but satisfy this relation over the generated Krylov subspaces. This is sufficient for a short term recurrence. Next, we derive an augmented bi-Lanczos algorithm with recycling and show that this algorithm is a special case of generalized bi-Lanczos. The Petrov-Galerkin approximation that includes recycling in the iteration leads to modified two-term recurrences for the solution and residual updates. We generalize and extend the framework of our recycling BiCG to CGS, BiCGSTAB and BiCGSTAB2. We perform extensive numerical experiments and analyze the generated recycle space. We test all of our recycling algorithms on a discretized partial differential equation (PDE) of convection-diffusion type. This PDE problem provides well-known test cases that are easy to analyze further. We use recycling BiCG in the Iterative Rational Krylov Algorithm (IRKA) for interpolatory model reduction and in the VMC algorithm. For a model reduction problem, we show up to 70% savings in iterations, and we also demonstrate that solving the problem without recycling leads to (about) a 50% increase in runtime. Experiments with recycling BiCG for VMC gives promising results. We also present an algorithm that recycles preconditioners, leading to a dramatic reduction in the cost of VMC for large(r) systems. The main cost of the VMC method is in constructing a sequence of Slater matrices and computing the ratios of determinants for successive Slater matrices. Recent work has improved the scaling of constructing Slater matrices for insulators, so that the cost of constructing Slater matrices in these systems is now linear in the number of particles. However, the cost of computing determinant ratios remains cubic in the number of particles. With the long term aim of simulating much larger systems, we improve the scaling of computing determinant ratios in the VMC method for simulating insulators by using preconditioned iterative solvers. The main contribution here is the development of a method to efficiently compute for the Slater matrices a sequence of preconditioners that make the iterative solver converge rapidly. This involves cheap preconditioner updates, an effective reordering strategy, and a cheap method to monitor instability of ILUTP preconditioners. Using the resulting preconditioned iterative solvers to compute determinant ratios of consecutive Slater matrices reduces the scaling of the VMC algorithm from O(n^3) per sweep to roughly O(n^2), where n is the number of particles, and a sweep is a sequence of n steps, each attempting to move a distinct particle. We demonstrate experimentally that we can achieve the improved scaling without increasing statistical errors. / Ph. D.

Mean shift (MS) and subspace constrained mean shift (SCMS) algorithms are non-parametric, iterative methods to find a representation of a high dimensional data set on a principal curve or surface embedded in a high dimensional space. The representation of high dimensional data on a principal curve or surface, the class of mean shift type algorithms and their properties, and applications of these algorithms are the main focus of this dissertation. Although MS and SCMS algorithms have been used in many applications, a rigorous study of their convergence is still missing. This dissertation aims to fill some of the gaps between theory and practice by investigating some convergence properties of these algorithms. In particular, we propose a sufficient condition for a kernel density estimate with a Gaussian kernel to have isolated stationary points to guarantee the convergence of the MS algorithm. We also show that the SCMS algorithm inherits some of the important convergence properties of the MS algorithm. In particular, the monotonicity and convergence of the density estimate values along the sequence of output values of the algorithm are shown. We also show that the distance between consecutive points of the output sequence converges to zero, as does the projection of the gradient vector onto the subspace spanned by the D-d eigenvectors corresponding to the D-d largest eigenvalues of the local inverse covariance matrix. Furthermore, three new variations of the SCMS algorithm are proposed and the running times and performance of the resulting algorithms are compared with original SCMS algorithm. We also propose an adaptive version of the SCMS algorithm to consider the effect of new incoming samples without running the algorithm on the whole data set. As well, we develop some new potential applications of the MS and SCMS algorithm. These applications involve finding straight lines in digital images; pre-processing data before applying locally linear embedding (LLE) and ISOMAP for dimensionality reduction; noisy source vector quantization where the clean data need to be estimated before the quanization step; improving the performance of kernel regression in certain situations; and skeletonization of digitally stored handwritten characters. / Thesis (Ph.D, Mathematics & Statistics) -- Queen's University, 2013-09-30 18:01:12.959

Une tâche importante qui a été étudiée dans le contexte de données à forte dimensionnalité est la tâche connue sous le nom de subspace clustering. Le subspace clustering est généralement reconnu comme étant plus compliqué que le clustering standard, étant donné que cette tâche vise à détecter des groupes d’objets similaires entre eux (clusters), et qu’en même temps elle vise à trouver les sous-espaces où apparaissent ces similitudes. Le subspace clustering, ainsi que le clustering traditionnel ont été récemment étendus au traitement de flux de données en mettant à jour les modèles de clustering de façon incrémentale. Les différents algorithmes qui ont été proposés dans la littérature, reposent sur des bases algorithmiques très différentes. Parmi ces approches, les algorithmes évolutifs ont été sous-explorés, même si ces techniques se sont avérées très utiles pour traiter d’autres problèmes NP-difficiles. L’objectif de cette thèse a été de tirer parti des nouvelles connaissances issues de l’évolution afin de concevoir des algorithmes évolutifs qui traitent le problème du subspace clustering sur des jeux de données statiques ainsi que sur des flux de données dynamiques. Chameleoclust, le premier algorithme développé au cours de ce projet, tire partie du grand degré de liberté fourni par des éléments bio-inspirés tels qu’un génome de longueur variable, l’existence d’éléments fonctionnels et non fonctionnels et des opérateurs de mutation incluant des réarrangements chromosomiques. KymeroClust, le deuxième algorithme conçu dans cette thèse, est un algorithme de k-medianes qui repose sur un mécanisme évolutif important: la duplication et la divergence des gènes. SubMorphoStream, le dernier algorithme développé ici, aborde le problème du subspace clustering sur des flux de données dynamiques. Cet algorithme repose sur deux mécanismes qui jouent un rôle clef dans l’adaptation rapide des bactéries à des environnements changeants: l’amplification de gènes et l’absorption de matériel génétique externe. Ces algorithmes ont été comparés aux principales techniques de l’état de l’art, et ont obtenu des résultats compétitifs. En outre, deux applications appelées EvoWave et EvoMove ont été développés pour évaluer la capacité de ces algorithmes à résoudre des problèmes réels. EvoWave est une application d’analyse de signaux Wi-Fi pour détecter des contextes différents. EvoMove est un compagnon musical artificiel qui produit des sons basés sur le clustering des mouvements d’un danseur, décrits par des données provenant de capteurs de déplacements. / An important task that has been investigated in the context of high dimensional data is subspace clustering. This data mining task is recognized as more general and complicated than standard clustering, since it aims to detect groups of similar objects called clusters, and at the same time to find the subspaces where these similarities appear. Furthermore, subspace clustering approaches as well as traditional clustering ones have recently been extended to deal with data streams by updating clustering models in an incremental way. The different algorithms that have been proposed in the literature, rely on very different algorithmic foundations. Among these approaches, evolutionary algorithms have been under-explored, even if these techniques have proven to be valuable addressing other NP-hard problems. The aim of this thesis was to take advantage of new knowledge from evolutionary biology in order to conceive evolutionary subspace clustering algorithms for static datasets and dynamic data streams. Chameleoclust, the first algorithm developed in this work, takes advantage of the large degree of freedom provided by bio-like features such as a variable genome length, the existence of functional and non-functional elements and mutation operators including chromosomal rearrangements. KymeroClust, our second algorithm, is a k-medians based approach that relies on the duplication and the divergence of genes, a cornerstone evolutionary mechanism. SubMorphoStream, the last one, tackles the subspace clustering task over dynamic data streams. It relies on two important mechanisms that favor fast adaptation of bacteria to changing environments, namely gene amplification and foreign genetic material uptake. All these algorithms were compared to the main state-of-the-art techniques, obtaining competitive results. Results suggest that these algorithms are useful complementary tools in the analyst toolbox. In addition, two applications called EvoWave and EvoMove have been developed to assess the capacity of these algorithms to address real world problems. EvoWave is an application that handles the analysis of Wi-Fi signals to detect different contexts. EvoMove, the second one, is a musical companion that produces sounds based on the clustering of dancer moves captured using motion sensors.