Applied Functional Analysis | Faculty of Mathematics | TU Chemnitz
CMS
Computational Complexity and Compressed Sensing
Anders Christian Hansen
Let A be an n by n matrix. Questions on computing the
spectrum of A, finding eigenvectors, solving inverse problems etc.
have been essential in applied mathematics for decades and
tackled with great success.
What if A is replaced by an infinite matrix or rather an operator
on a separable Hilbert space? We meet these operators in all kinds
of mathematical physics and applied mathematics from quantum mechanics
to medical imaging. The same computational questions may be asked,
however, much less is known. Consider for example the following question:
Can we compute the spectrum of an arbitrary linear operator,
and if so, how "difficult" or "complex" may such a computation be?
I will discuss this general question and introduce a new tool for
classifying computational spectral problems, namely the Complexity Index.
A new tool for solving inverse problems in finite dimensions called
Compressed Sensing has recently been developed and showed to have
great impact.
I will discuss how some of the ideas developed by Emmanuel Candes and
Terence Tao can be extended to infinite dimensional inverse problems.
This allows for complete recovery of more general object such as
analog signals and infinite resolution images.
