Presented by:

Anders Hansen University of Cambridge

Date:

Tuesday 26th November 2019 - 15:05 to 16:05

Venue:

INI Seminar Room 1

Event:

Abstract:

There
are four areas in computational mathematics that have been intensely
investigated over more than half a century: Spectral problems, PDEs,
optimisation and inverse problems. However, despite the matureness of these
fields, the foundations are far from known. Indeed, despite almost 90 years of
quantum mechanics, it is still unknown whether it is possible to compute the
spectrum of a self-adjoint Schrodinger operator with a bounded smooth
potential. Similarly, it is not known which time dependent Schrodinger
equations can be computed (despite well posedness of the equation). Linear
programs (LP) can be solved with rational inputs in polynomial time, but can
LPs be solved with irrational inputs? Problems in signal and image processing
tend to use irrational numbers, so what happens if one plugs in the discrete
cosine transform in one's favourite LP solver? Moreover, can one always compute
the solutions to well-conditioned infinite-dimensional inverse problems, and if
not, which inverse problems can then be solved?
In
this talk we will discuss solutions to many of the questions above, and some of
the results may seem paradoxical. Indeed, despite being an open problem for
more than half a century, computing spectra of Schrodinger operators with
a bounded potential is not harder than computing spectra of infinite diagonal
matrices, the simplest of all infinite-dimensional spectral problems. Moreover,
computing spectra of compact operators, for which the method has been known for
decades, is strictly harder than computing spectra of such Schrodinger
operators. Regarding linear programs (and basis pursuit, semidefinite programs
and LASSO) we have the following. For any integer K > 2 and any norm, there
exists a family of well conditioned inputs containing irrational numbers so
that no algorithm can compute K correct digits of a minimiser, however, there
exists an algorithm that can compute K-1 correct digits. But any algorithm
producing K-1 correct digits will need arbitrarily long time. Finally,
computing K-2 correct digits can be done in polynomial time in the number of
variables. As we will see, all of these problems can be solved via the the
Solvability Complexity Index (SCI) hierarchy, which is a theoretical program
for establishing the boundaries of what computers can achieve in the
sciences.

**The video for this talk should appear here if JavaScript is enabled.**

If it doesn't, something may have gone wrong with our embedded player.

We'll get it fixed as soon as possible.

If it doesn't, something may have gone wrong with our embedded player.

We'll get it fixed as soon as possible.