Near optimal recovery of arbitrary signals from uncomplete measurements
given at strobl07 (19.06.07 11:00)
Compressed sensing is a recent concept in signal and image processing where one seeks to minimize the number of measurements to be taken from signals or images while still retaining the information necessary to approximate them well. The ideas have their origins in certain abstract results from
functional analysis and approximation theory but were recently brought into the forefront by the work of Candes-Romberg-Tao, and Donoho who constructed concrete algorithms and showed their promise in application.
There remain several fundamental questions on both the theoretical and practical side of compressed sensing. This talk is primarily concerned about one of these issues revolving around just how well compressed sensing can approximate a given signal from a given budget of fixed linear measurements, as compared to adaptive linear measurements.
More precisely, we consider discrete N-dimensional signals x with N>>1, allocate n<