Imaging using compressive sensing

Compressive sensing

Compressive sensing is a statistical technique whose start is usually traced back to Donoho (2006), but whose start could be placed as early as the basic pursuit work of Mallat and Zhang (1993). A compressive sensing problem at its heart is a special case of a missing data problem. In geophysics, we often think of a missing data problem as solving for a model $\bf m$ given some data $\bf d$ which exist in the same vector space. We have a masking operator $\bf M$ (1 where the data is known, 0 elsewhere). We add in some knowledge of the covariance of the model through a regularization operator $\bf A$ . We then estimate the best model from the following system of equations in a $\ell_2$ sense,

$$\bf0 \approx \bf r_d = \ell_2(\bf d - \bf M \bf m)$$

$$\bf0 \approx \bf r_m = \ell_2(\bf A \bf m ),$$ (1)

where $\bf r_d$ and $\bf r_m$ are the result of taking the $\ell_2$ norm of the first and second equations. The success of this approach relies on the accuracy of $\bf A$ to describe the covariance of the model.

Compressive sensing approaches the problem from a different perspective. It starts from the notion that there exists a basis function that $\bf d$ can be transformed into through the linear operator $\bf L'$ in which very few non-zero elements are needed to represent the signal. The compressive sensing approach is then to set up the missing data problem in two phases. First, estimate the elements of the sparse basis function $\bf m$ through,

$$\bf0 \approx \bf r = \ell_1(\bf d- \bf M \bf L \bf m),$$ (2)

where we are now estimating $\bf m$ in the $\bf\ell_1$ sense. We can then apply $\bf L$ to recover the full model. Compressive sensing makes the claim that if the signal can be represented in this basis function by $n$ points, if you collect $b m$ randomly sampled points, where $b$ is typically 4-5, significantly less than what the Nyquist-Shannon criteria would suggest.

Figure 1 shows an example of this technique applied to a 2-D missing data problem. In this case, we are trying to recover the image seen in Figure 1(a). We start from the data points seen in Figure 1(b), and recover the image seen in Figure 1(c). In this case, the image was subsampled by a factor of 8 and nearly perfect recovery was achieved.

before,random,after
Figure 1. The original image (a), the image sub-sampled by a factor of 8 (b), and the reconstructed image (c) using compressive sensing. Baraniuk et al. (2008).

Reconstruction using compressive sensing techniques is expensive. $\ell_1$ solvers are significantly more expensive than their $\ell_2$ counterparts, which in themselves can represent a significant cost. As a result, only certain classes of problems benefit from compressive sensing techniques. For compressive sensing to be useful, the cost of acquiring the full dataset must be significant. In addition, the signal must be highly compressible. The following two sections address both criterion.

Imaging using compressive sensing