Is compressive sensing a type of interpolation?

Question

In what ways is compressive sensing different from traditional numerical interpolation of sampled points from a given signal?

Answer 1

The "traditional" compressive sensing (CS) considers the problem of recovering exactly an unknown vector $\mathbf{x} \in \mathbb{R}^N$ from $m<N$ linear observations, i.e., from a vector $\mathbf{y} = \mathbf{A} \mathbf{x}$, where $\mathbf{A} \in \mathbb{R}^{m\times N}$ is a, so called, sensing matrix (which is known). As the resulting system of linear equations is underdetermined, CS makes the additional assumption that $\mathbf{x}$ has only $s \ll N$ non-zero elements when expressed with respect to a certain (known) basis, i.e., $\mathbf{x}$ is sparse. CS theory investigates what properties $\mathbf{A}$ should have in order to recover $\mathbf{x}$ with the smallest possible number of observations $m$, as well as designing practical (numerical) algorithms to do that.

Interpolation is usually considered as the problem of recovering an unknown vector $\mathbf{x} \in \mathbb{R}^N$ by directly observing only $m<N$ of its elements. Since, as stated, this problem is ill posed, common interpolation methods such as linear, cubic or spline make the additional assumption that the values of consecutive elements of $\mathbf{x}$ are not significantly different, i.e., $\mathbf{x}$ is "smooth". In general, conventional interpolation does not guarantee exact recovery of the unknown vector. A notable exception are bandlimited signals, which can indeed be recovered exactly under a sampling scheme with periodic samples, taken with sufficiently large (Nyquist) frequency.

Therefore, the major differneces of CS and conventional interpolation are

1. Observation model: CS considers a more general observation model than conventional interpolation
2. Unknown vector assumptions: CS considers the recovery of sparse vectors (w.r.t. some basis) whereas interpolation considers "smooth"/"bandlimited" vectors. Note that, in general, a sparse vector is not "smooth"/"bandlimited" and vice versa.
3. Theoretical analysis: CS provides rigorous guarantees for the exact recovery of sparse vectors, whereas few things can be said on the exact recovery of signals by numerical interpolation.