Computer Science - Numerical Analysis Publications (50)


Computer Science - Numerical Analysis Publications

The widespread use of multisensor technology and the emergence of big data sets have created the necessity to develop more versatile tools to represent large and multimodal data such as higher-order tensors. Tensor decomposition based methods have been shown to be flexible in the choice of the constraints and to extract more general latent components in such data compared to matrix-based methods. For these reasons, tensor decompositions have found applications in many different signal processing problems including dimensionality reduction, signal separation, linear regression, feature extraction, and classification. Read More

Optimal transportation provides a means of lifting distances between points on a geometric domain to distances between signals over the domain, expressed as probability distributions. On a graph, transportation problems can be used to express challenging tasks involving matching supply to demand with minimal shipment expense; in discrete language, these become minimum-cost network flow problems. Regularization typically is needed to ensure uniqueness for the linear ground distance case and to improve optimization convergence; state-of-the-art techniques employ entropic regularization on the transportation matrix. Read More

This paper proposes the use of the Spectral method to simulate diffusive moisture transfer through porous materials, which can be strongly nonlinear and can significantly affect sensible and latent heat transfer. An alternative way for computing solutions by considering a separated representation is presented, which can be applied to both linear and nonlinear diffusive problems, considering highly moisture-dependent properties. The Spectral method is compared with the classical implicit Euler and Crank-Nicolson schemes. Read More

The scalable calculation of matrix determinants has been a bottleneck to the widespread application of many machine learning methods such as determinantal point processes, Gaussian processes, generalised Markov random fields, graph models and many others. In this work, we estimate log determinants under the framework of maximum entropy, given information in the form of moment constraints from stochastic trace estimation. The estimates demonstrate a significant improvement on state-of-the-art alternative methods, as shown on a wide variety of UFL sparse matrices. Read More

Matrix completion models are among the most common formulations of recommender systems. Recent works have showed a boost of performance of these techniques when introducing the pairwise relationships between users/items in the form of graphs, and imposing smoothness priors on these graphs. However, such techniques do not fully exploit the local stationarity structures of user/item graphs, and the number of parameters to learn is linear w. Read More

We consider a symmetric matrix, the entries of which depend linearly on some parameters. The domains of the parameters are compact real intervals. We investigate the problem of checking whether for each (or some) setting of the parameters, the matrix is positive definite (or positive semidefinite). Read More

This paper studies different signaling techniques on the continuous spectrum (CS) of nonlinear optical fiber defined by nonlinear Fourier transform. Three different signaling techniques are proposed and analyzed based on the statistics of the noise added to CS after propagation along the nonlinear optical fiber. The proposed methods are compared in terms of error performance, distance reach, and complexity. Read More

In this paper, we present a fast implementation of the Singular Value Thresholding (SVT) algorithm for matrix completion. A rank-revealing randomized singular value decomposition (R3SVD) algorithm is used to adaptively carry out partial singular value decomposition (SVD) to fast approximate the SVT operator given a desired, fixed precision. We extend the R3SVD algorithm to a recycling rank revealing randomized singular value decomposition (R4SVD) algorithm by reusing the left singular vectors obtained from the previous iteration as the approximate basis in the current iteration, where the computational cost for partial SVD at each SVT iteration is significantly reduced. Read More

An unsteady problem is considered for a space-fractional equation in a bounded domain. A first-order evolutionary equation involves a fractional power of an elliptic operator of second order. Finite element approximation in space is employed. Read More

In this short note, we present a novel method for computing exact lower and upper bounds of a symmetric tridiagonal interval matrix. Compared to the known methods, our approach is fast, simple to present and to implement, and avoids any assumptions Our construction explicitly yields those matrices for which particular lower and upper bounds are attained. Read More

Rational filter functions improve convergence of contour-based eigensolvers, a popular algorithm family for the solution of the interior eigenvalue problem. We present an optimization method of these rational filters in the Least-Squares sense. Our filters out-perform existing filters on a large and representative problem set, which we show on the example of FEAST. Read More

Affiliations: 1ENS Paris-Saclay, 2ENS Paris-Saclay, 3ENS Paris-Saclay, 4ENS Paris-Saclay, CNRS, INRIA

In this paper, we propose a symbolic control synthesis method for nonlinear sampled switched systems whose vector fields are one-sided Lipschitz. The main idea is to use an approximate model obtained from the forward Euler method to build a guaranteed control. The benefit of this method is that the error introduced by symbolic modeling is bounded by choosing suitable time and space discretizations. Read More

The solution of inverse problems in a variational setting finds best estimates of the model parameters by minimizing a cost function that penalizes the mismatch between model outputs and observations. The gradients required by the numerical optimization process are computed using adjoint models. Exponential integrators are a promising family of time discretizations for evolutionary partial differential equations. Read More

Hybrid systems are complex dynamical systems that combine discrete and continuous components. Reachability questions, regarding whether a system can run into a certain subset of its state space, stand at the core of verification and synthesis problems for hybrid systems. This volume contains papers describing new developments in this area, which were presented at the 3rd International Workshop on Symbolic and Numerical Methods for Reachability Analysis. Read More

In this paper, we propose a novel unfitted finite element method for the simulation of multiple body contact. The computational mesh is generated independently of the geometry of the interacting solids, which can be arbitrarily complex. The key novelty of the approach is the combination of elements of the CutFEM technology, namely the enrichment of the solution field via the definition of overlapping fictitious domains with a dedicated penalty-type regularisation of discrete operators, and the LaTIn hybrid-mixed formulation of complex interface conditions. Read More

Convolution with Green's function of a differential operator appears in a lot of applications e.g. Lippmann-Schwinger integral equation. Read More

The log-determinant of a kernel matrix appears in a variety of machine learning problems, ranging from determinantal point processes and generalized Markov random fields, through to the training of Gaussian processes. Exact calculation of this term is often intractable when the size of the kernel matrix exceeds a few thousand. In the spirit of probabilistic numerics, we reinterpret the problem of computing the log-determinant as a Bayesian inference problem. Read More

This work investigates the geometry of a nonconvex reformulation of minimizing a general convex loss function $f(X)$ regularized by the matrix nuclear norm $\|X\|_*$. Nuclear-norm regularized matrix inverse problems are at the heart of many applications in machine learning, signal processing, and control. The statistical performance of nuclear norm regularization has been studied extensively in literature using convex analysis techniques. Read More

This paper introduces a parametric level-set method for tomographic reconstruction of partially discrete images. Such images consist of a continuously varying background and an anomaly with a constant (known) grey-value. We represent the geometry of the anomaly using a level-set function, which we represent using radial basis functions. Read More

The purpose of this manuscript is to derive new convergence results for several subgradient methods for minimizing nonsmooth convex functions with H\"olderian growth. The growth condition is satisfied in many applications and includes functions with quadratic growth and functions with weakly sharp minima as special cases. To this end there are four main contributions. Read More

We consider the problem of low canonical polyadic (CP) rank tensor completion. A completion is a tensor whose entries agree with the observed entries and its rank matches the given CP rank. We analyze the manifold structure corresponding to the tensors with the given rank and define a set of polynomials based on the sampling pattern and CP decomposition. Read More

We introduce the concept of numerical Gaussian processes, which we define as Gaussian processes with covariance functions resulting from temporal discretization of time-dependent partial differential equations. Numerical Gaussian processes, by construction, are designed to deal with cases where: (1) all we observe are noisy data on black-box initial conditions, and (2) we are interested in quantifying the uncertainty associated with such noisy data in our solutions to time-dependent partial differential equations. Our method circumvents the need for spatial discretization of the differential operators by proper placement of Gaussian process priors. Read More

Symmetric Positive Definite (SPD) matrices have been widely used as feature descriptors in image recognition. However, the dimension of an SPD matrix built by image feature descriptors is usually high. So SPD matrices oriented dimensionality reduction techniques are needed. Read More

Large scale parameter estimation problems are among some of the most computationally demanding problems in numerical analysis. An academic researcher's domain-specific knowledge often precludes that of software design, which results in inversion frameworks that are technically correct, but not scalable to realistically-sized problems. On the other hand, the computational demands for realistic problems result in industrial codebases that are geared solely for high performance, rather than comprehensibility or flexibility. Read More

The CANDECOMP/PARAFAC (CP) tensor decomposition is a popular dimensionality-reduction method for multiway data. Dimensionality reduction is often sought since many high-dimensional tensors have low intrinsic rank relative to the dimension of the ambient measurement space. However, the emergence of `big data' poses significant computational challenges for computing this fundamental tensor decomposition. Read More

In this paper we consider a distributed optimization scenario in which the aggregate objective function to minimize is partitioned, big-data and possibly non-convex. Specifically, we focus on a set-up in which the dimension of the decision variable depends on the network size as well as the number of local functions, but each local function handled by a node depends only on a (small) portion of the entire optimization variable. This problem set-up has been shown to appear in many interesting network application scenarios. Read More

Motivated by economic dispatch and linearly-constrained resource allocation problems, this paper proposes a novel Distributed Approx-Newton algorithm that approximates the standard Newton optimization method. A main property of this distributed algorithm is that it only requires agents to exchange constant-size communication messages. The convergence of this algorithm is discussed and rigorously analyzed. Read More

In this work, we propose a subspace-based algorithm for direction-of-arrival (DOA) estimation, referred to as two-step knowledge-aided iterative estimation of signal parameters via rotational invariance techniques (ESPRIT) method (Two-Step KAI-ESPRIT), which achieves more accurate estimates than those of prior art. The proposed Two-Step KAI-ESPRIT improves the estimation of the covariance matrix of the input data by incorporating prior knowledge of signals and by exploiting knowledge of the structure of the covariance matrix and its perturbation terms. Simulation results illustrate the improvement achieved by the proposed method. Read More

We study the effect of adaptive mesh refinement on a parallel domain decomposition solver of a linear system of algebraic equations. These concepts need to be combined within a parallel adaptive finite element software. A prototype implementation is presented for this purpose. Read More

Kernel quadratures and other kernel-based approximation methods typically suffer from prohibitive cubic time and quadratic space complexity in the number of function evaluations. The problem arises because a system of linear equations needs to be solved. In this article we show that the weights of a kernel quadrature rule can be computed efficiently and exactly for up to tens of millions of nodes if the kernel, integration domain, and measure are fully symmetric and the node set is a union of fully symmetric sets. Read More

Singular values of a data in a matrix form provide insights on the structure of the data, the effective dimensionality, and the choice of hyper-parameters on higher-level data analysis tools. However, in many practical applications such as collaborative filtering and network analysis, we only get a partial observation. Under such scenarios, we consider the fundamental problem of recovering spectral properties of the underlying matrix from a sampling of its entries. Read More

A novel and scalable geometric multi-level algorithm is presented for the numerical solution of elliptic partial differential equations, specially designed to run with high occupancy of streaming processors inside Graphics Processing Units(GPUs). The algorithm consists of iterative, superposed operations on a single grid, and it is composed of two simple full-grid routines: a restriction and a coarsened interpolation-relaxation. The restriction is used to collect sources using recursive coarsened averages, and the interpolation-relaxation simultaneously applies coarsened finite-difference operators and interpolations. Read More

Matrix and tensor completion aim to recover a low-rank matrix / tensor from limited observations and have been commonly used in applications such as recommender systems and multi-relational data mining. A state-of-the-art matrix completion algorithm is Soft-Impute, which exploits the special "sparse plus low-rank" structure of the matrix iterates to allow efficient SVD in each iteration. Though Soft-Impute is a proximal algorithm, it is generally believed that acceleration destroys the special structure and is thus not useful. Read More

Stochastic variance reduction algorithms have recently become popular for minimizing the average of a large, but finite number of loss functions. The present paper proposes a Riemannian stochastic quasi-Newton algorithm with variance reduction (R-SQN-VR). The key challenges of averaging, adding, and subtracting multiple gradients are addressed with notions of retraction and vector transport. Read More

This work proposes a space-time least-squares Petrov-Galerkin (ST-LSPG) projection method for model reduction of nonlinear dynamical systems. In contrast to typical nonlinear model-reduction methods that first apply (Petrov-)Galerkin projection in the spatial dimension and subsequently apply time integration to numerically resolve the resulting low-dimensional dynamical system, the proposed method applies projection in space and time simultaneously. To accomplish this, the method first introduces a low-dimensional space-time trial subspace, which can be obtained by computing tensor decompositions of state-snapshot data. Read More

In exploratory tensor mining, a common problem is how to analyze a set of variables across a set of subjects whose observations do not align naturally. For example, when modeling medical features across a set of patients, the number and duration of treatments may vary widely in time, meaning there is no meaningful way to align their clinical records across time points for analysis purposes. To handle such data, the state-of-the-art tensor model is the so-called PARAFAC2, which yields interpretable and robust output and can naturally handle sparse data. Read More

In this letter, we propose an algorithm for recovery of sparse and low rank components of matrices using an iterative method with adaptive thresholding. In each iteration, the low rank and sparse components are obtained using a thresholding operator. This algorithm is fast and can be implemented easily. Read More

Approximate computing has shown to provide new ways to improve performance and power consumption of error-resilient applications. While many of these applications can be found in image processing, data classification or machine learning, we demonstrate its suitability to a problem from scientific computing. Utilizing the self-correcting behavior of iterative algorithms, we show that approximate computing can be applied to the calculation of inverse matrix p-th roots which are required in many applications in scientific computing. Read More

This research investigates the implementation mechanism of block-wise ILU(k) preconditioner on GPU. The block-wise ILU(k) algorithm requires both the level k and the block size to be designed as variables. A decoupled ILU(k) algorithm consists of a symbolic phase and a factorization phase. Read More

In this paper, we present a parallel numerical algorithm for solving the phase field crystal equation. In the algorithm, a semi-implicit finite difference scheme is derived based on the discrete variational derivative method. Theoretical analysis is provided to show that the scheme is unconditionally energy stable and can achieve second-order accuracy in both space and time. Read More

Bayesian matrix factorization (BMF) is a powerful tool for producing low-rank representations of matrices, and giving principled predictions of missing values. However, scaling up MCMC samplers to large matrices has proven to be difficult with parallel algorithms that require communication between MCMC iterations. On the other hand, designing communication-free algorithms is challenging due to the inherent unidentifiability of BMF solutions. Read More

In this paper, we introduce and provide a short overview of nonnegative matrix factorization (NMF). Several aspects of NMF are discussed, namely, the application in hyperspectral imaging, geometry and uniqueness of NMF solutions, complexity, algorithms, and its link with extended formulations of polyhedra. In order to put NMF into perspective, the more general problem class of constrained low-rank matrix approximation problems is first briefly introduced. Read More

The FLAME methodology makes it possible to derive provably correct algorithms from a formal description of a linear algebra problem. So far, the methodology has been successfully used to automate the derivation of direct algorithms such as the Cholesky decomposition and the solution of Sylvester equations. In this thesis, we present an extension of the FLAME methodology to tackle iterative methods such as Conjugate Gradient. Read More

We solve tensor balancing, rescaling an Nth order nonnegative tensor by multiplying (N - 1)th order N tensors so that every fiber sums to one. This generalizes a fundamental process of matrix balancing used to compare matrices in a wide range of applications from biology to economics. We present an efficient balancing algorithm with quadratic convergence using Newton's method and show in numerical experiments that the proposed algorithm is several orders of magnitude faster than existing ones. Read More

Many machine learning models are reformulated as optimization problems. Thus, it is important to solve a large-scale optimization problem in big data applications. Recently, subsampled Newton methods have emerged to attract much attention for optimization due to their efficiency at each iteration, rectified a weakness in the ordinary Newton method of suffering a high cost in each iteration while commanding a high convergence rate. Read More

We develop and analyze efficient "coordinate-wise" methods for finding the leading eigenvector, where each step involves only a vector-vector product. We establish global convergence with overall runtime guarantees that are at least as good as Lanczos's method and dominate it for slowly decaying spectrum. Our methods are based on combining a shift-and-invert approach with coordinate-wise algorithms for linear regression. Read More

We describe stochastic Newton and stochastic quasi-Newton approaches to efficiently solve large linear least-squares problems where the very large data sets present a significant computational burden (e.g., the size may exceed computer memory or data are collected in real-time). Read More

A new simple convergence acceleration method is proposed for a certain wide range class of convergent alternating series. The method has some common features with Smith's and Ford's modification of Levin's and Weniger's sequence transformations, but it is computationally less expensive. The similarities and differences between all three methods are analyzed and some common theoretical results are given. Read More

In an effort to increase the versatility of finite element codes, we explore the possibility of automatically creating the Jacobian matrix necessary for the gradient-based solution of nonlinear systems of equations. Particularly, we aim to assess the feasibility of employing the automatic differentiation tool TAPENADE for this purpose on a large Fortran codebase that is the result of many years of continuous development. As a starting point we will describe the special structure of finite element codes and the implications that this code design carries for an efficient calculation of the Jacobian matrix. Read More

Boolean matrix factorisation aims to decompose a binary data matrix into an approximate Boolean product of two low rank, binary matrices: one containing meaningful patterns, the other quantifying how the observations can be expressed as a combination of these patterns. We introduce the OrMachine, a probabilistic generative model for Boolean matrix factorisation and derive a Metropolised Gibbs sampler that facilitates efficient parallel posterior inference. On real world and simulated data, our method outperforms all currently existing approaches for Boolean matrix factorisation and completion. Read More