Past Numerical Analysis Group Internal Seminar

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.

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.

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.

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.

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.

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.

An important observation in compressed sensing is the exact recovery of an l0 minimiser to an underdetermined linear system via the l1 minimiser, given the knowledge that a sparse solution vector exists. Here, we develop a continuous analogue of this observation and show that the best L1 and L0 polynomial approximants of a corrupted function (continuous analogue of sparse vectors) are equivalent. We use this to construct best L1 polynomial approximants of corrupted functions via linear programming. We also present a numerical algorithm for computing best L1 polynomial approximants to general continuous functions, and observe that compared with best L-infinity and L2 polynomial approximants, the best L1 approximants tend to have error functions that are more localized.

Joint work with Alex Townsend (MIT).

The Faraday cage effect is the phenomenon whereby electrostatic and electromagnetic fields are shielded by a wire mesh "cage". Nick Trefethen, Jon Chapman and I recently carried out a mathematical analysis of the two-dimensional electrostatic problem with thin circular wires, demonstrating that the shielding effect is not as strong as one might infer from the physics literature. In this talk I will present new results generalising the previous analysis to the electromagnetic case, and to wires of arbitrary shape. The main analytical tool is the asymptotic method of multiple scales, which is used to derive continuum models for the shielding, involving homogenized boundary conditions on an effective cage boundary. In the electromagnetic case one observes interesting resonance effects, whereby at frequencies close to the natural frequencies of the equivalent solid shell, the presence of the cage actually amplifies the incident field, rather than shielding it. We discuss applications to radiation containment in microwave ovens and acoustic scattering by perforated shells. This is joint work with Ian Hewitt.

Kerdock matrices are an attractive choice as deterministic measurement matrices for compressive sensing. I'll explain how Kerdock matrices are constructed, and then show how they can be adapted to one particular  strategy for quantizing measurements, in which measurements exceeding the desired dynamic range are rejected.

At the heart of the interior point method in optimization is a linear system solve, but how accurate must this solve be?  The behaviour of such methods is well-understood when a direct solver is used, but the scale of problems being tackled today means that users increasingly turn to iterative methods to approximate its solution.  Current suggestions of the accuracy required can be seen to be too stringent, leading to inefficiency.

In this talk I will give conditions on the accuracy of the solution in order to guarantee the inexact interior point method converges at the same rate as if there was an exact solve.  These conditions can be shown numerically to be tight, in that performance degrades rapidly if a weaker condition is used.  Finally, I will describe how the norms that appear in these condition are related to the natural norms that are minimized in several popular Krylov subspace methods. This, in turn, could help in the development of new preconditioners in this important field.

Operators, functions, and functionals are combined in many problems of computational science in a fashion that has the same logical structure as is familiar for block matrices and vectors.  It is proposed that the explicit consideration of such block structures at the continuous as opposed to discrete level can be a useful tool.  In particular, block operator diagrams provide templates for spectral discretization by the rectangular differentiation, integration, and identity matrices introduced by Driscoll and Hale.  The notion of the rectangular shape of a linear operator can be made rigorous by the theory of Fredholm operators and their indices, and the block operator formulations apply to nonlinear problems too, where the convention is proposed of representing nonlinear blocks as shaded.  At each step of a Newton iteration, the structure is linearized and the blocks become unshaded, representing Fréchet derivative operators, square or rectangular.  The use of block operator diagrams makes it possible to precisely specify discretizations of even rather complicated problems with just a few lines of pseudocode.

[Joint work with Nick Trefethen]

Adaptive cubic regularization methods have recently emerged as a credible alternative to line search and trust-region for smooth nonconvex optimization, with optimal complexity amongst second-order methods. Here we consider a general class of adaptive regularization methods, that use first- or higher-order local Taylor models of the objective regularized by a(ny) power of the step size. We investigate the worst-case complexity/global rate of convergence of these algorithms, in the presence of varying (unknown) smoothness of the objective. We find that some methods automatically adapt their complexity to the degree of smoothness of the objective; while others take advantage of the power of the regularization step to satisfy increasingly better bounds with the order of the models. This work is joint with Nick Gould (RAL) and Philippe Toint (Namur).