"Although it is convenient for conceptual and theoretical purposes to think of signals as general functions of time. In practice they are usually acquired, processed, stored and transmitted as discrete and finite time samples. We need to study this sampling process carefully to determine to what extent a sampling or discretization allows us to reconstruct the original information in the signal. Furthermore, real signals such as speech or images are not arbitrary functions. Depending on the type of signal, they have special structure. No one would confuse the output of a random number generator with human speech. It is also important to understand the extent to which we can compress the basic information in the signal to minimize storage space and maximize transmission time. Shannon sampling is one approach to these issues. In this approach we model real signals as functions $f(t)$ in $L_2(-\infty,\infty)$ that are bandlimited. Thus if the frequency support of ${\hat f}(\omega)$ is contained in the interval $[-\Omega,\Omega]$ and we sample the signal at discrete time intervals with equal spacing less than $1/2\pi\Omega$, i.e., faster than the Nyquist rate, we can reconstruct the original signal exactly from the discrete samples. This method will work provided hardware exists to sample the signal at the required rate. Increasingly this is a problem because modern technologies can generate signals of higher bandwidth than existing hardware can sample.

There are other models for signals that exploit different properties of real signals and can be used as alternatives to Shannon sampling. In this chapter we introduce an alternative model that is based on the sparsity of many real signals. Intuitively we think of a signal as sparse if its expression with respect to some chosen basis has coefficients that are mostly zero (or very small). The content of the signal is in the location and values of the spikes, the nonzero terms. For example the return from a radar signal at an airport is typically null, except for a few spikes locating the positions and velocities of nearby aircraft. A time trace of the sound from a musical instrument might not be sparse, whereas the Fourier transform of the the same signal would be sparse. This approach to the modeling, processing and storage of real signals is called compressive sampling. In what follows, we present (1) The Algebraic Theory, (2) The Analytic Theory, (3) RIP (Restricted Isometry Property), Concentration of measure and Ranom Matrices, (4) Practical Implementation."