Low rank approximation is the problem of finding two low rank factors W and H such that the rank(WH) << rank(A) and A ≈ WH. These low rank factors W and H can be constrained for meaningful physical interpretation and referred as Constrained Low Rank Approximation (CLRA). Like most of the constrained optimization problem, performing CLRA can be computationally expensive than its unconstrained counterpart. A widely used CLRA is the Non-negative Matrix Factorization (NMF) which enforces non-negativity constraints in each of its low rank factors W and H. In this thesis, I focus on scalable/distributed CLRA algorithms for constraints such as boundedness and non-negativity for large real world matrices that includes text, High Definition (HD) video, social networks and recommender systems. First, I begin with the Bounded Matrix Low Rank Approximation (BMA) which imposes a lower and an upper bound on every element of the lower rank matrix. BMA is more challenging than NMF as it imposes bounds on the product WH rather than on each of the low rank factors W and H. For very large input matrices, we extend our BMA algorithm to Block BMA that can scale to a large number of processors. In applications, such as HD video, where the input matrix to be factored is extremely large, distributed computation is inevitable and the network communication becomes a major performance bottleneck. Towards this end, we propose a novel distributed Communication Avoiding NMF (CANMF) algorithm that communicates only the right low rank factor to its neighboring machine. Finally, a general distributed HPC- NMF framework that uses HPC techniques in communication intensive NMF operations and suitable for broader class of NMF algorithms.

We discuss the numerical solution of large-scale sparse projected discrete-time periodic Lyapunov equations in lifted form which arise in model reduction of periodic descriptor systems. We extend the alternating direction implicit method and the Smith method to such equations. Low-rank versions of these methods are also presented, which can be used to compute low-rank approximations to the solutions of projected periodic Lyapunov equations in lifted form with low-rank right-hand side. Moreover, we consider an application of the Lyapunov solvers to balanced truncation model reduction of periodic discrete-time descriptor systems. Numerical results are given to illustrate the efficiency and accuracy of the proposed methods.

Quantum-mechanical effects play a major role in the performance of modern electronic devices. In order to predict the behavior of novel devices, quantum effects are often included using Non-Equilibrium Green's Function (NEGF) methods in atomistic device representations. These quantum effects may include realistic inelastic scattering caused by device impurities and phonons. With the inclusion of realistic physical phenomena, the computational load of predictive simulations increases greatly, and a manageable basis through low-rank approximations is desired.<br><br>In this work, low-rank approximations are used to reduce the computational load of atomistic simulations. The benefits of basis reductions on simulation time and peak memory are assessed.<br>The low-rank approximation method is then extended to include more realistic physical effects than those modeled today, including exact calculations of scattering phenomena. The inclusion of these exact calculations are then contrasted to current methods and approximations.

<p>Many kernel matrices from differential equations or data science applications possess low or approximately low off-diagonal rank for certain key matrix subblocks; such matrices are referred to as rank-structured. Operations on rank-structured matrices like factorization and linear system solution can be greatly accelerated by converting them into hierarchical matrix forms, such as the hiearchically semiseparable (HSS) matrix form. The dominant cost of this conversion process, called HSS construction, is the low-rank approximation of certain matrix blocks. Low-rank approximation is also a required step in many other contexts throughout numerical linear algebra. In this work, a proxy point low-rank approximation method is detailed for general analytic kernel matrices, in both one and several dimensions. A new accuracy analysis for this approximation is also provided, as well as numerical evidence of its accuracy. The extension of this method to kernels in several dimensions is novel, and its new accuracy analysis makes it a convenient choice to use over existing proxy point methods. Finally, a new HSS construction algorithm using this method for certain Cauchy and Toeplitz matrices is given, which is asymptotically faster than existing methods. Numerical evidence for the accuracy and efficacy of the new construction algorithm is also provided.</p>

Generative models for creating realistic synthetic graphs constitute a research area that is increasing in popularity, especially as the use of graph data is becoming increasingly common. Generating realistic synthetic graphs enables sharing of the information embedded in graphs without directly sharing the original graphs themselves. This can in turn contribute to an increase of knowledge within several domains where access to data is normally restricted, including the financial system and social networks. In this study, it is examined how existing generative models can be extended to be compatible with directed and weighted graphs, without limiting the models to generating graphs of a specific domain. Several models are evaluated, and all use low-rank approximations to learn structural properties of directed graphs. Additionally, it is evaluated how node embeddings can be used with a regression model to add realistic edge weights to directed graphs. The results show that the evaluated methods are capable of reproducing global statistics from the original directed graphs to a promising degree, without having more than 52% overlap in terms of edges. The results also indicate that realistic directed and weighted graphs can be generated from directed graphs by predicting edge weights using pairs of node embeddings. However, the results vary depending on which node embedding technique is used.

We study numerical methods for time-dependent partial differential equations describing wave propagation, primarily applied to problems in quantum dynamics governed by the time-dependent Schrödinger equation (TDSE). We consider both methods for spatial approximation and for time stepping. In most settings, numerical solution of the TDSE is more challenging than solving a hyperbolic wave equation. This is mainly because the dispersion relation of the TDSE makes it very sensitive to dispersion error, and infers a stringent time step restriction for standard explicit time stepping schemes. The TDSE is also often posed in high dimensions, where standard methods are intractable. The sensitivity to dispersion error makes spectral methods advantageous for the TDSE. We use spectral or pseudospectral methods in all except one of the included papers. In Paper III we improve and analyse the accuracy of the Fourier pseudospectral method applied to a problem with limited regularity, and in Paper V we construct a matrix-free spectral method for problems with non-trivial boundary conditions. Due to its stiffness, the TDSE is most often solved using exponential time integration. In this thesis we use exponential operator splitting and Krylov subspace methods. We rigorously prove convergence for force-gradient operator splitting methods in Paper IV. One way of making high-dimensional problems computationally tractable is low-rank approximation. In Paper VI we prove that a splitting method for dynamical low-rank approximation is robust to singular values in the approximation approaching zero, a situation which is difficult to handle since it implies strong curvature of the approximation space. / eSSENCE

No description available.

This thesis focuses on two topics, computational methods for large spatial datasets and functional data ranking. Both are tackling the challenges of big and high-dimensional data. The first topic is motivated by the prohibitive computational burden in fitting Gaussian process models to large and irregularly spaced spatial datasets. Various approximation methods have been introduced to reduce the computational cost, but many rely on unrealistic assumptions about the process and retaining statistical efficiency remains an issue. We propose a new scheme to approximate the maximum likelihood estimator and the kriging predictor when the exact computation is infeasible. The proposed method provides different types of hierarchical low-rank approximations that are both computationally and statistically efficient. We explore the improvement of the approximation theoretically and investigate the performance by simulations. For real applications, we analyze a soil moisture dataset with 2 million measurements with the hierarchical low-rank approximation and apply the proposed fast kriging to fill gaps for satellite images. The second topic is motivated by rank-based outlier detection methods for functional data. Compared to magnitude outliers, it is more challenging to detect shape outliers as they are often masked among samples. We develop a new notion of functional data depth by taking the integration of a univariate depth function. Having a form of the integrated depth, it shares many desirable features. Furthermore, the novel formation leads to a useful decomposition for detecting both shape and magnitude outliers. Our simulation studies show the proposed outlier detection procedure outperforms competitors in various outlier models. We also illustrate our methodology using real datasets of curves, images, and video frames. Finally, we introduce the functional data ranking technique to spatio-temporal statistics for visualizing and assessing covariance properties, such as separability and full symmetry. We formulate test functions as functions of temporal lags for each pair of spatial locations and develop a rank-based testing procedure induced by functional data depth for assessing these properties. The method is illustrated using simulated data from widely used spatio-temporal covariance models, as well as real datasets from weather stations and climate model outputs.

We discuss the numerical solution of large-scale sparse projected discrete-time periodic Lyapunov equations in lifted form which arise in model reduction of periodic descriptor systems. We extend the alternating direction implicit method and the Smith method to such equations. Low-rank versions of these methods are also presented, which can be used to compute low-rank approximations to the solutions of projected periodic Lyapunov equations in lifted form with low-rank right-hand side. Moreover, we consider an application of the Lyapunov solvers to balanced truncation model reduction of periodic discrete-time descriptor systems. Numerical results are given to illustrate the efficiency and accuracy of the proposed methods.:1 Introduction 2 Periodic descriptor systems 3 ADI method for causal lifted Lyapunov equations 4 Smith method for noncausal lifted Lyapunov equations 5 Application to model order reduction 6 Numerical results 7 Conclusions

Modern big data often emerge as tensors. Standard statistical methods are inadequate to deal with datasets of large volume, high dimensionality, and complex structure. Therefore, it is important to develop algorithms such as low-rank tensor decomposition for data compression, dimensionality reduction, and approximation. With the advancement in technology, high-dimensional images are becoming ubiquitous in the medical field. In lung radiation therapy, the respiratory motion of the lung introduces variabilities during treatment as the tumor inside the lung is moving, which brings challenges to the precise delivery of radiation to the tumor. Several approaches to quantifying this uncertainty propose using a model to formulate the motion through a mathematical function over time. [Li et al., 2011] uses principal component analysis (PCA) to propose one such model using each image as a long vector. However, the images come in a multidimensional arrays, and vectorization breaks the spatial structure. Driven by the needs to develop low-rank tensor decomposition and provided the 4DCT and Displacement Vector Field (DVF), we introduce two tensor decompositions, Population Value Decomposition (PVD) and Population Tucker Decomposition (PTD), to estimate the respiratory lung motion with high levels of accuracy and data compression. The first algorithm is a generalization of PVD [Crainiceanu et al., 2011] to higher order tensor. The second algorithm generalizes the concept of PVD using Tucker decomposition. Both algorithms are tested on clinical and phantom DVFs. New metrics for measuring the model performance are developed in our research. Results of the two new algorithms are compared to the result of the PCA algorithm.