Randomness: A Computational Resource for Large Scale Inverse Problems

Applications are invited for a postgraduate research position leading to a PhD degree in Electrical Engineering in the Institute for Digital Communications within the School of Engineering at the University of Edinburgh.

Recent advances in big data analytics have brought about various randomisation algorithms in the aim of exploring massive data sets and performing linear algebra operations with matrices and vectors at extreme dimensions, e.g. O(1012). Among the most prominent examples of this innovation is the randomised singular value decomposition, as well as the randomised linear algebra algorithms for matrix multiplication and least-squares regression. In principle, this new framework aims to replace high-dimensional deterministic computation with low-sample statistical estimation in the context of sample-based average approximation, where one selects only a few elements, rows, or columns of the matrices involved to approximate the result of the operation. The key concept of this process is the choice of the sampling distribution so that the result is obtained with minimal statistical error (variance) measured in the appropriate metric. For rank deficient model matrices, such as those encountered in some ill-posed inverse problems, randomisation methods tend to be very efficient, in terms of convergence, as well memory usage and accuracy of the result. This research is aimed at developing randomised algorithms for high-dimensional inverse problems associated with partial differential equations. The focus will be on the design of efficient, low-variance sampling distributions based on importance sampling principles. The research will benefit from the collaboration with data scientists and geophysicists.

Further Information: 

The project is aimed at extending some initial work on sample-average approximations for large-scale linear inverse problems associated with integral operators into more general partial differential equations based engineering problems in imaging. Applications include geophysical imaging and non-destructing testing.

  1. N. Polydorides, M. Wang, and D. P. Bertsekas, A quasi Monte Carlo method for large scale inverse problems, Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, Springer-Verlag, 2012.
  2. M. Wang, N. Polydorides, and D. P. Bertsekas, Approximate simulation-based solution of large-scale least squares problems, Lab. for Information and Decision Systems Report LIDS-P-2819, MIT, September 2009.
  3. N. Polydorides, M. Wang, and D. P. Bertsekas, Approximate solution of large-scale linear inverse problems with Monte Carlo simulation, Lab. for Information and Decision Systems Report LIDS-P-2822, MIT, November 2009.
  4. M. W. Mahoney, Lecture Notes on Randomized Linear Algebra, UC Berkeley, 2013.

Closing Date: 

Sunday, December 31, 2017
Figure: Randomised importance sampling distributions on smooth toy matrices [3]
Figure: Randomised importance sampling distributions on smooth toy matrices [3]

Principal Supervisor: 

Eligibility: 

A first class Honours degree (or International equivalent) in engineering, physics, informatics or applied mathematics, ideally supplemented by an MSc Degree. 

Further information on English language requirements for EU/Overseas applicants.

Funding: 

Competitive funding subject to availability.

Further information and other funding options.

Informal Enquiries: 

Nick Polydorides, Agile Tomography Group Leader, n.polydorides@ed.ac.uk