Rutherford Appleton Laboratory, nr Didcot

Because of atmospheric turbulence, images of objects in outer space acquired via ground-based telescopes are usually blurry.  One way to estimate the blurring kernel or point spread function (PSF) is to make use of the aberration of wavefront received at the telescope, i.e., the phase. However only the low-resolution wavefront gradients can be collected by wavefront sensors. In this talk, I will discuss how to use regularization methods to reconstruct high-resolution phase gradients and then use them to recover the phase and the PSF in high accuracy. I will end by relating the problem to high-resolution image reconstruction and methods for solving it.
Joint work with Rui Zhao and research supported by HKRGC.

Adjoint derivatives reveal the sensitivity of a computer program's output to changes in its inputs. These derivatives are useful as a building block for optimisation, uncertainty quantification, noise estimation, inverse design, etc., in many industrial and scientific applications that use PDE solvers or other codes.
Algorithmic differentiation (AD) is an established method to transform a given computation into its corresponding adjoint computation. One of the key challenges in this process is the efficiency of the resulting adjoint computation. This becomes especially pressing with the increasing use of shared-memory parallelism on multi- and many-core architectures, for which AD support is currently insufficient.
In this talk, I will present an overview of challenges and solutions for the differentiation of shared-memory-parallel code, using two examples: an unstructured-mesh CFD solver, and a structured-mesh stencil kernel, both parallelised with OpenMP. I will show how AD can be used to generate adjoint solvers that scale as well as their underlying original solvers on CPUs and a KNC XeonPhi. The talk will conclude with some recent efforts in using AD and formal verification tools to check the correctness of manually optimised adjoint solvers.
 

Structural optimization can be interpreted as the attempt to find the best mechanical structure to support specific load cases respecting some possible constraints. Within this context, topology optimization aims to obtain the connectivity, shape and location of voids inside a prescribed structural design domain. The methods for the design of stiff lightweight structures are well established and can already be used in a specific range of industries where such structures are important, e.g., in aerospace and automobile industries.

In this seminar, we will go through the basic engineering concepts used to quantify and analyze the computational models of mechanical structures. After presenting the motivation, the methods and mathematical tools used in structural topology optimization will be discussed. In our method, an implicit level set function is used to describe the structural boundaries. The optimization problem is approximated by linearization of the objective and constraint equations via Taylor’s expansion. Shape sensitivities are used to evaluate the change in the structural performance due to a shape movement and to feed the mathematical optimiser in an iterative procedure. Recent developments comprising multiscale and Multiphysics problems will be presented and a specific application proposal including acoustic-structure interaction will be discussed.

In variational imaging and other inverse problem modeling, regularisation plays a major role. In recent years, high order regularizers such as the total generalised variation, the mean curvature and the Gaussian curvature are increasingly studied and applied, and many improved results over the widely-used total variation model are reported.
Here we first introduce the fractional order derivatives and the total fractional-order variation which provides an alternative  regularizer and is not yet formally analysed. We demonstrate that existence and uniqueness properties of the new model can be analysed in a fractional BV space, and, equally, the new model performs as well as the high order regularizers (which do not yet have much theory). 
In the usual framework, the algorithms of a fractional order model are not fast due to dense matrices involved. Moreover, written in a Bregman framework, the resulting Sylvester equation with Toeplitz coefficients can be solved efficiently by a preconditioned solver. Further ideas based on adaptive integration can also improve the computational efficiency in a dramatic way.
 Numerical experiments will be given to illustrate the advantages of the new regulariser for both restoration and registration problems.
 

Work with Jemima Tabeart, Sarah Dance, Nancy Nichols, Joanne Waller (University of Reading) and Stefano Migliorini, Fiona Smith (Met Office). 
In environmental prediction variational data assimilation (DA) is a method for using observational data to estimate the current state of the system. The DA problem is usually solved as a very large nonlinear least squares problem, in which the fit to the measurements is balanced against the fit to a previous model forecast. These two terms are weighted by matrices describing the correlations of the errors in the forecast and in the observations. Until recently most operational weather and ocean forecasting systems assumed that the errors in the observations are uncorrelated. However, as we move to higher resolution observations then it is becoming more important to specify observation error correlations. In this work we look at the effect this has on the conditioning of the optimization problem. In the context of a linear system we develop bounds on the condition number of the problem in the presence of correlated observation errors. We show that the condition number is very dependent on the minimum eigenvalue of the observation error correlation matrix. We then present results using the Met Office data assimilation system, in which different methods for reconditioning the correlation matrix are tested. We investigate the effect of these different methods on the conditioning and the final solution of the problem.
 

I will present a broad family of stochastic algorithms for inverting a matrix, including specialized variants which maintain symmetry or positive definiteness of the iterates. All methods in the family converge globally and linearly, with explicit rates. In special cases, the methods obtained are stochastic block variants of several quasi-Newton updates, including bad Broyden (BB), good Broyden (GB), Powell-symmetric-Broyden (PSB), Davidon-Fletcher-Powell (DFP) and Broyden-Fletcher-Goldfarb-Shanno (BFGS). After a pause for questions, I will then present a block stochastic BFGS method based on the stochastic method for inverting positive definite matrices. In this method, the estimate of the inverse Hessian matrix that is maintained by it, is updated at each iteration using a sketch of the Hessian, i.e., a randomly generated compressed form of the Hessian. I will propose several sketching strategies, present a new quasi-Newton method that uses stochastic block BFGS updates combined with the variance reduction approach SVRG to compute batch stochastic gradients, and prove linear convergence of the resulting method. Numerical tests on large-scale logistic regression problems reveal that our method is more robust and substantially outperforms current state-of-the-art methods.

We consider the problem of computing a nonnegative low rank factorization to a given nonnegative input matrix under the so-called "separabilty condition".  This assumption makes this otherwise NP hard problem polynomial time solvable, and we will use first order optimization techniques to compute such a factorization. The optimization model use is based on sparse regression with a self-dictionary, in which the low rank constraint is relaxed to the minimization of an l1-norm objective function.  We apply these techniques to endmember detection and classification in hyperspecral imaging data.

To predict the behaviour of a dynamical system using a mathematical model, an accurate estimate of the current state of the system is needed in order to initialize the model. Complete information on the current state is, however, seldom available. The aim of optimal state estimation, known in the geophysical sciences as ‘data assimilation’, is to determine a best estimate of the current state using measured observations of the real system over time, together with the model equations. The problem is commonly formulated in variational terms as a very large nonlinear least-squares optimization problem. The lack of complete data, coupled with errors in the observations and in the model, leads to a highly ill-conditioned inverse problem that is difficult to solve.

To understand the nature of the inverse problem, we examine how different components of the assimilation system influence the conditioning of the optimization problem. First we consider the case where the dynamical equations are assumed to model the real system exactly. We show, against intuition, that with increasingly dense and precise observations, the problem becomes harder to solve accurately. We then extend these results to a 'weak-constraint' form of the problem, where the model equations are assumed not to be exact, but to contain random errors. Two different, but mathematically equivalent, forms of the problem are derived. We investigate the conditioning of these two forms and find, surprisingly, that these have quite different behaviour.

In many applications we need to find or estimate the $p \ge 1$ largest elements of a matrix, along with their locations. This is required for recommender systems used by Amazon and Netflix, link prediction in graphs, and in finding the most important links in a complex network, for example. 

Our algorithm uses only matrix vector products and is based upon a power method for mixed subordinate norms. We have obtained theoretical results on the convergence of this algorithm via a comparison with rook pivoting for the LU  decomposition. We have also improved the practicality of the algorithm by producing a blocked version iterating on $n \times t$ matrices, as opposed to vectors, where $t$ is a tunable parameter. For $p > 1$ we show how deflation can be used to improve the convergence of the algorithm. 

Finally, numerical experiments on both randomly generated matrices and real-life datasets (the latter for $A^TA$ and $e^A$) show how our algorithms can reliably estimate the largest elements of a matrix whilst obtaining considerable speedups when compared to forming the matrix explicitly: over 1000x in some cases.

We will review the basic building blocks of iterative solvers, i.e. sparse matrix-vector multiplication, in the context of GPU devices such 
as the cards by NVIDIA; we will then discuss some techniques in preconditioning by approximate inverses, and we will conclude with an 
application to an image processing problem from the biomedical field.