# Past Numerical Analysis Group Internal Seminar

Compressed sensing and matrix completion are techniques by which simplicity in data can be exploited for more efficient data acquisition. For instance, if a matrix is known to be (approximately) low rank then it can be recovered from few of its entries. The design and analysis of computationally efficient algorithms for these problems has been extensively studies over the last 8 years. In this talk we present a new algorithm that balances low per iteration complexity with fast asymptotic convergence. This algorithm has been shown to have faster recovery time than any other known algorithm in the area, both for small scale problems and massively parallel GPU implementations. The new algorithm adapts the classical nonlinear conjugate gradient algorithm and shows the efficacy of a linear algebra perspective to compressed sensing and matrix completion.

When applied to an inequality constrained optimization problem, interior point methods generate iterates that belong to the interior of the set determined by the constraints, thus avoiding/ignoring the combinatorial aspect of the solution. This comes at the cost of difficulty in predicting the optimal active constraints that would enable termination. We propose the use of controlled perturbations to address this challenge. Namely, in the context of linear programming with only nonnegativity constraints as the inequality constraints, we consider perturbing the nonnegativity constraints so as to enlarge the feasible set. Theoretically, we show that if the perturbations are chosen appropriately, the solution of the original problem lies on or close to the central path of the perturbed problem and that a primal-dual path-following algorithm applied to the perturbed problem is able to predict the optimal active-set of the original problem when the duality gap (for the perturbed problem) is not too small. Encouraging preliminary numerical experience is obtained when comparing the perturbed and unperturbed interior point algorithms' active-set predictions for the purpose of cross-over to simplex.

Networks arise pervasively in biology, physics, technology, social science, and myriad other areas. An ordinary network consists of a collection of entities (called nodes) that interact via edges. "Multilayer networks" are a more general representation that can be used when nodes are connected to each other via multiple types of edges or a network changes in time. In this talk, I will discuss how to find dense sets of nodes called "communities" in multilayer networks and some applications of community structure to problems in neuroscience and finance.

Sobolev spaces are the standard framework in which to analyse weak (variational) formulations of PDEs or integral equations and their numerical solution (e.g. using the Finite Element Method or the Boundary Element Method). There are many different ways to define Sobolev spaces on a given domain, for example via integrability of weak derivatives, completions of spaces of smooth functions with respect to certain norms, or restriction from spaces defined on a larger domain. For smooth (e.g. Lipschitz) domains things many of these definitions coincide. But on rough (e.g. fractal) domains the picture is much more complicated. In this talk I'll try to give a flavour of the sort of interesting behaviour that can arise, and what implications this behaviour has for a "practical" example, namely acoustic wave scattering by fractal screens.

Quantifying the uncertainty in computational simulations is one of the central challenges confronting the field of computational science and engineering today. The uncertainty quantification of inverse problems is neatly addressed in the Bayesian framework, where instead of seeking one unique minimiser of a regularised misfit functional, the entire posterior probability distribution is to be characterised. In this talk I review the deep connection between deterministic PDE-constrained optimisation techniques and Bayesian inference for inverse problems, discuss some recent advances made in the Bayesian viewpoint by adapting deterministic techniques, and mention directions for future research.

Composite dilation wavelets are affine systems which extend the notion of wavelets by incorporating a second set of dilations. The addition of a second set of dilations allows the composite system to capture directional information in addition to time and frequency information. We classify admissible dilation groups at two extremes: frequency localization through minimally supported frequency composite dilation wavelets and time localization through crystallographic Haar-type composite dilation wavelets.

Convolution is widely-used and fundamental mathematical operation

in signal processing, statistics, and PDE theory.

Unfortunately the CONV() method in Chebfun for convolving two chebfun

objects has long been one of the most disappointingly slow features of

the project. In this talk we will present a new algorithm, which shows

performance gains on the order of a factor 100.

The key components of the new algorithm are:

* a convolution theorem for Legendre polynomials

* recurrence relations satisfied by spherical Bessel functions

* recent developments in fast Chebyshev-Legendre transforms [1]

Time-permitting, we shall end with an application from statistics,

using the fact that the probability distribution of the sum of two

independent random variables is the convolution of their individual

distributions.

[1] N. Hale and A. Townsend, "A fast, simple, and stable Chebyshev-

Legendre transform using an asymptotic formula”, SISC (to appear).

The accurate and efficient solution of linear systems $Ax=b$ is very important in many engineering and technological applications, and systems of this form also arise as subproblems within other algorithms. In particular, this is true for interior point methods (IPM), where the Newton system must be solved to find the search direction at each iteration. Solving this system is a computational bottleneck of an IPM, and in this talk I will explain how preconditioning and deflation techniques can be used, to lessen this computational burden. This work is joint with Jacek Gondzio.