Compressed sensing and best 𝑘-term approximation

Compressed sensing is a new concept in signal processing where one seeks to minimize the number of measurements to be taken from signals 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 by Kashin but were recently brought into the forefront by the work of Candès, Romberg, and Tao and of Donoho who constructed concrete algorithms and showed their promise in application. There remain several fundamental questions on both the theoretical and practical sides of compressed sensing. This paper is primarily concerned with one of these theoretical 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 signals <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="x element-of double-struck upper R Superscript upper N"> <mml:semantics> <mml:mrow> <mml:mi>x</mml:mi> <mml:mo>∈</mml:mo> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="double-struck">R</mml:mi> </mml:mrow> <mml:mi>N</mml:mi> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">x\in \mathbb {R}^N</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, allocate <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n greater-than upper N"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>&gt;</mml:mo> <mml:mi>N</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">n&gt;N</mml:annotation> </mml:semantics> </mml:math> </inline-formula> linear measurements of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="x"> <mml:semantics> <mml:mi>x</mml:mi> <mml:annotation encoding="application/x-tex">x</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, and we describe the range of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for which these measurements encode enough information to recover <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="x"> <mml:semantics> <mml:mi>x</mml:mi> <mml:annotation encoding="application/x-tex">x</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in the sense of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script l Subscript p"> <mml:semantics> <mml:msub> <mml:mi>ℓ</mml:mi> <mml:mi>p</mml:mi> </mml:msub> <mml:annotation encoding="application/x-tex">\ell _p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> to the accuracy of best <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-term approximation. We also consider the problem of having such accuracy only with high probability.