University of Oxford

Hessians of functionals of PDE solutions have important applications in PDE-constrained optimisation (Newton methods) and uncertainty quantification (for accelerating high-dimensional Bayesian inference).  With current techniques, a typical cost for one Hessian-vector product is 4-11 times the cost of the forward PDE solve: such high costs generally make their use in large-scale computations infeasible, as a Hessian solve or eigendecomposition would have costs of hundreds of PDE solves.

In this talk, we demonstrate that it is possible to exploit the common structure of the adjoint, tangent linear and second-order adjoint equations to greatly accelerate the computation of Hessian-vector products, by trading a large amount of computation for a large amount of storage. In some cases of practical interest, the cost of a Hessian-
vector product is reduced to a small fraction of the forward solve, making it feasible to employ sophisticated algorithms which depend on them.

Finding a sparse signal solution of an underdetermined linear system of measurements is commonly solved in compressed sensing by convexly relaxing the sparsity requirement with the help of the l1 norm. Here, we tackle instead the original nonsmooth nonconvex l0-problem formulation using projected gradient methods. Our interest is motivated by a recent surprising numerical find that despite the perceived global optimization challenge of the l0-formulation, these simple local methods when applied to it can be as effective as first-order methods for the convex l1-problem in terms of the degree of sparsity they can recover from similar levels of undersampled measurements. We attempt here to give an analytical justification in the language of asymptotic phase transitions for this observed behaviour when Gaussian measurement matrices are employed. Our approach involves novel convergence techniques that analyse the fixed points of the algorithm and an asymptotic probabilistic analysis of the convergence conditions that derives asymptotic bounds on the extreme singular values of combinatorially many submatrices of the Gaussian measurement matrix under matrix-signal independence assumptions.

This work is joint with Andrew Thompson (Duke University, USA).

The Ramsey number $R(K_s, Q_n)$ is the smallest integer $N$ such that every red-blue colouring of the edges of the complete graph $K_N$ contains either a red $n$-dimensional hypercube, or a blue clique on $s$ vertices. Note that $N=(s-1)(2^n -1)$ is not large enough, since we may colour in red $(s-1)$ disjoint cliques of cardinality $2^N -1$ and colour the remaining edges blue. In 1983, Burr and Erdos conjectured that this example was the best possible, i.e., that $R(K_s, Q_n) = (s-1)(2^n -1) + 1$ for every positive integer $s$ and sufficiently large $n$. In a recent breakthrough, Conlon, Fox, Lee and Sudakov proved the conjecture up to a multiplicative constant for each $s$. In this talk we shall sketch the proof of the conjecture and discuss some related problems.

(Based on joint work with Gonzalo Fiz Pontiveros, Robert Morris, David Saxton and Jozef Skokan)

Perfect matchings are fundamental objects of study in graph theory. There is a substantial classical theory, which cannot be directly generalised to hypergraphs unless P=NP, as it is NP-complete to determine whether a hypergraph has a perfect matching. On the other hand, the generalisation to hypergraphs is well-motivated, as many important problems can be recast in this framework, such as Ryser's conjecture on transversals in latin squares and the Erdos-Hanani conjecture on the existence of designs. We will discuss a characterisation of the perfect matching problem for uniform hypergraphs that satisfy certain density conditions (joint work with Richard Mycroft), and a polynomial time algorithm for determining whether such hypergraphs have a perfect matching (joint work with Fiachra Knox and Richard Mycroft).

Clouds play a key role in the climate system. Driven by radiation, clouds power the hydrological cycle and global atmospheric dynamics. In addition, clouds fundamentally affect the global radiation balance by reflecting solar radiation back to space and trapping longwave radiation. The response of clouds to global warming remains poorly understood and is strongly regime dependent. In addition, anthropogenic aerosols influence clouds, altering cloud microphysics, dynamics and radiative properties. In this presentation I will review progress and limitations of our current understanding of the role of clouds in climate change and discuss the state of the art of the representation of clouds and aerosol-cloud interactions in global climate models, from (slightly) better constrained stratiform clouds to new frontiers: the investigation of anthropogenic effects on convective clouds.

Market events such as order placement and order cancellation are examples of the complex and substantial flow of data that surrounds a modern financial engineer. New mathematical techniques, developed to describe the interactions of complex oscillatory systems (known as the theory of rough paths) provides new tools for analysing and describing these data streams and extracting the vital information. In this paper we illustrate how a very small number of coefficients obtained from the signature of financial data can be sufficient to classify this data for subtle underlying features and make useful predictions.

This paper presents financial examples in which we learn from data and then proceed to classify fresh streams. The classification is based on features of streams that are specified through the coordinates of the signature of the path. At a mathematical level the signature is a faithful transform of a multidimensional time series. (Ben Hambly and Terry Lyons \cite{uniqueSig}), Hao Ni and Terry Lyons \cite{NiLyons} introduced the possibility of its use to understand financial data and pointed to the potential this approach has for machine learning and prediction.

We evaluate and refine these theoretical suggestions against practical examples of interest and present a few motivating experiments which demonstrate information the signature can easily capture in a non-parametric way avoiding traditional statistical modelling of the data. In the first experiment we identify atypical market behaviour across standard 30-minute time buckets sampled from the WTI crude oil future market (NYMEX). The second and third experiments aim to characterise the market "impact" of and distinguish between parent orders generated by two different trade execution algorithms on the FTSE 100 Index futures market listed on NYSE Liffe.

Abstract: The expected signature is often viewed as a direct analogue of the Laplace transform, and as such it has been asked whether, under certain conditions, it may determine the law of a random signature. In this talk we first introduce a meaningful topology on the space of (geometric) rough paths which allows us to study it as a well-defined probability space. With the help of compact symplectic Lie groups, we then define a set of characteristic functions and show that two random variables in this space are equal in law if and only if they agree on each characteristic function. We finally show that under very general boundedness conditions, the value of each characteristic function is completely determined by the expected signature, giving an affirmative answer to the aforementioned question in many cases. In particular, we demonstrate that the Stratonovich signature is completely determined in law by its expected signature, and show how a similar technique can be used to demonstrate convergence in law of random signatures.

Background material: http://arxiv.org/abs/1307.3580

''Regression analysis aims to use observational data from multiple observations to develop a functional relationship relating explanatory variables to response variables, which is important for much of modern statistics, and econometrics, and also the field of machine learning. In this paper, we consider the special case where the explanatory variable is a stream of information, and the response is also potentially a stream. We provide an approach based on identifying carefully chosen features of the stream which allows linear regression to be used to characterise the functional relationship between explanatory variables and the conditional distribution of the response; the methods used to develop and justify this approach, such as the signature of a stream and the shue product of tensors, are standard tools in the theory of rough paths and seem appropriate in this context of regression as well and provide a surprisingly unified and non-parametric approach.''