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.