Forthcoming events in this series


Tue, 15 Nov 2016
14:30
L5

SNIPE for memory-limited PCA with incomplete data: From failure to success

Armin Eftekhari
(University of Oxford)
Abstract


Consider the problem of identifying an unknown subspace S from data with erasures and with limited memory available. To estimate S, suppose we group the measurements into blocks and iteratively update our estimate of S with each new block.

In the first part of this talk, we will discuss why estimating S by computing the "running average" of span of these blocks fails in general. Based on the lessons learned, we then propose SNIPE for memory-limited PCA with incomplete data, useful also for streaming data applications. SNIPE provably converges (linearly) to the true subspace, in the absence of noise and given sufficient measurements, and shows excellent performance in simulations. This is joint work with Laura Balzano and Mike Wakin.
 

Tue, 08 Nov 2016
14:30
L5

Solving commutators while preserving structure

Pranav Singh
(Mathematical Institute)
Abstract



Nested commutators of differential operators appear frequently in the numerical solution of equations of quantum mechanics. These are expensive to compute with and a significant effort is typically made to avoid such commutators. In the case of Magnus-Lanczos methods, which remain the standard approach for solving Schrödinger equations featuring time-varying potentials, however, it is not possible to avoid the nested commutators appearing in the Magnus expansion.

We show that, when working directly with the undiscretised differential operators, these commutators can be simplified and are fairly benign, cost-wise. The caveat is that this direct approach compromises structure -- we end up with differential operators that are no longer skew-Hermitian under discretisation. This leads to loss of unitarity as well as resulting in numerical instability when moderate to large time steps are involved. Instead, we resort to working with symmetrised differential operators whose discretisation naturally results in preservation of structure, conservation of unitarity and stability
 

Tue, 18 Oct 2016
14:30
L5

Multi-index methods for quadrature

Abdul Haji-Ali
(Mathematical Institute)
Abstract


Multi-index methods are a generalization of multilevel methods in high dimensional problem and are based on taking mixed first-order differences along all dimensions. With these methods, we can accurately and efficiently compute a quadrature or construct an interpolation where the integrand requires some form of high dimensional discretization. Multi-index methods are related to Sparse Grid methods and the Combination Technique and have been applied to multiple sampling methods, i.e., Monte Carlo, Stochastic Collocation and, more recently, Quasi Monte Carlo.

In this talk, we describe and analyse the Multi-Index Monte Carlo (MIMC) and Multi-Index Stochastic Collocation (MISC) methods for computing statistics of the solution of a PDE with random data. Provided sufficient mixed regularity, MIMC and MISC achieve better complexity than their corresponding multilevel methods. We propose optimization procedures to select the most effective mixed differences to include in these multi-index methods. We also observe that in the optimal case, the convergence rate of MIMC and MISC is only dictated by the convergence of the deterministic solver applied to a one-dimensional spatial problem. We finally show the effectiveness of MIMC and MISC in some computational tests, including PDEs with random coefficients and Stochastic Particle Systems.
 

Tue, 18 Oct 2016
14:00
L5

ODE IVPs and BVPs

Nick Trefethen
(Mathematical Institute)
Abstract

I will discuss some of the relationships between ODE IVPs, usually solved by marching, and ODE BVPs, usually solved by global discretizations.

Tue, 17 May 2016
14:30
L5

Cross-diffusion systems for image enhancement and denoising

Silvia Barbeiro
(University of Coimbra and University of Oxford)
Abstract

Diffusion processes are commonly used in image processing. In particular, complex diffusion models have been successfully applied in medical imaging denoising. The interpretation of a complex diffusion equation as a cross-diffusion system motivates the introduction of more general models of this type and their study in the context of image processing. In this talk we will discuss the use of nonlinear cross-diffusion systems to perform image restoration. We will analyse the well-posedness, scale-space properties and
long time behaviour of the models along with their performance to treat image filtering problems. Examples of application will be highlighted.

Tue, 10 May 2016
14:30
L5

Low-rank compression of functions in 2D and 3D

Nick Trefethen
(University of Oxford)
Abstract

Low-rank compression of matrices and tensors is a huge and growing business.  Closely related is low-rank compression of multivariate functions, a technique used in Chebfun2 and Chebfun3.  Not all functions can be compressed, so the question becomes, which ones?  Here we focus on two kinds of functions for which compression is effective: those with some alignment with the coordinate axes, and those dominated by small regions of localized complexity.

 

Tue, 10 May 2016
14:00
L5

Linear convergence rate bounds for operator splitting methods

Goran Banjac
(Department of Engineering Science, University of Oxford)
Abstract

We establish necessary and sufficient conditions for linear convergence of operator splitting methods for a general class of convex optimization problems where the associated fixed-point operator is averaged. We also provide a tight bound on the achievable convergence rate. Most existing results establishing linear convergence in such methods require restrictive assumptions regarding strong convexity and smoothness of the constituent functions in the optimization problem. However, there are several examples in the literature showing that linear convergence is possible even when these properties do not hold. We provide a unifying analysis method for establishing linear convergence based on linear regularity and show that many existing results are special cases of our approach.

Tue, 03 May 2016
14:30
L3

Optimal preconditioners for systems defined by functions of Toeplitz matrices

Sean Hon
(University of Oxford)
Abstract

We propose several optimal preconditioners for systems defined by some functions $g$ of Toeplitz matrices $T_n$. In this paper we are interested in solving $g(T_n)x=b$ by the preconditioned conjugate method or the preconditioned minimal residual method, namely in the cases when $g(T_n)$ are the analytic functions $e^{T_n}$, $\sin{T_n}$ and $\cos{T_n}$. Numerical results are given to show the effectiveness of the proposed preconditioners.

Tue, 03 May 2016
14:00
L3

Modelling weakly coupled nonlinear oscillators: volcanism and glacial cycles

Jonathan Burley
(Department of Earth Science, University of Oxford)
Abstract

This talk will be a geophysicist's view on the emerging properties of a numerical model representing the Earth's climate and volcanic activity over the past million years.

The model contains a 2D ice sheet (Glen's Law solved with a semi-implicit scheme), an energy balance for the atmosphere and planet surface (explicit), and an ODE for the time evolution of CO2 (explicit).

The dependencies between these models generate behaviour similar to weakly coupled nonlinear oscillators.

Tue, 26 Apr 2016
14:30
L3

Applications of minimum rank of matrices described by a graph or sign pattern

Leslie Hogben
(Iowa State University)
Abstract

Low-rank compression of matrices and tensors is a huge and growing business.  Closely related is low-rank compression of multivariate functions, a technique used in Chebfun2 and Chebfun3.  Not all functions can be compressed, so the question becomes, which ones?  Here we focus on two kinds of functions for which compression is effective: those with some alignment with the coordinate axes, and those dominated by small regions of localized complexity.