A remark on compressed sensing (Q941909)

A classical problem in signal processing is the recovery problem: One is interested in reconstructing a vector \(u \in \mathbb R^m\) from given linear functionals \((u, \phi_j)\), \(j = 1, 2, \ldots, n\), with some known values \(\phi_1, \ldots, \phi_n \in \mathbb R^m\). In most typical applications, \(n\) is substantially smaller than \(m\). In order to obtain an efficient algorithm it is particularly important to choose the \(\phi_j\) carefully. The main goal of this paper is to present a precise mathematical formulation of this problem and to show which performance one may expect from a good algorithm. The main tool of the authors is a result that relates the problem at hand to the concepts of Kolmogorov widths and Gelfand widths which are well known in approximation theory.