Controlled recovery experiments for different sampling schemes

Next: Application to seismic data Up: Theory Previous: Jittered undersampling ( ):

Controlled recovery experiments for different sampling schemes

With the favorable sampling schemes identified, it remains to be shown that these samplings lead to an improved recovery compared to the unfavorable regular undersampling. In particular, we want to experimentally confirm that jittered undersampling behaves similarly as random undersampling according to a discrete uniform distribution.

For this purpose, we define the sparsifying transform $\tensor{S}$ as the Fourier transform $\tensor{F}$ , i.e., $\tensor{S}\; {\buildrel\rm def\over=}\; \tensor{F}$ , and generate a vector $\ensuremath{\mathbf{x}}_0$ with nonzero entries and of length . The nonzero entries of $\ensuremath{\mathbf{x}}_0$ are distributed at random with random signs and amplitudes. The to-be-recovered signal $\ensuremath{\mathbf{f}}_0$ is given by $\ensuremath{\mathbf{f}}_0=\tensor{S}^H\ensuremath{\mathbf{x}}_0$ and the observations $\ensuremath{\mathbf{y}}$ are obtained by undersampling $\ensuremath{\mathbf{f}}_0$ regularly, randomly according to a discrete uniform distribution, or optimally-jittered, i.e., $\xi =\gamma$ . Finally, the estimated spectrum $\tilde{\ensuremath{\mathbf{x}}}$ of $\ensuremath{\mathbf{f}}_0$ is obtained by solving equation 3 with the Spectral Projected Gradient for $\ell_1$ solver (SPGL1 - van den Berg and Friedlander, 2007). Keep in mind that the number of nonzero entries of $\ensuremath{\mathbf{x}}_0$ is not known a priori. Each experiment is repeated 100 times for the different undersampling schemes and for varying undersampling factors $\gamma$ , ranging from 2 to 6. The reconstruction error is the number of entries at which the estimated representation $\tilde{\ensuremath{\mathbf{x}}}$ and the true representation $\ensuremath{\mathbf{x}}_0$ of $\ensuremath{\mathbf{f}}_0$ in the Fourier domain disagree by more than $10^{-4}$ . This error accounts for both false positives and false negatives. The averaged results for the different experiments are summarized in Figures 6(a), 6(b), and 6(c), which correspond to regular, random, and optimally-jittered undersampling, respectively. The horizontal axes in these plots represent the relative underdeterminedness of the system, i.e., the ratio of the number of nonzero entries in $\ensuremath{\mathbf{x}}_0$ to the number of acquired data points. The vertical axes represent the average reconstruction error. The different curves represents the different undersampling factors. In each plot, the curves from top to bottom correspond to $\gamma = 2,\ldots, 6$ .

Figure 6(a) shows that, regardless of the undersampling factor, there is no range of relative underdeterminedness for which $\ensuremath{\mathbf{x}}_0$ can accurately be recovered from a regular undersampling of $\ensuremath{\mathbf{f}}_0$ . Sparsity is not enough to discriminate the signal components from the spectral leakage. The situation is completely different in Figures 6(b) and 6(c) for the random and optimally-jittered sampling. In this case, one can observed that exact recovery is possible for $0<k/n\lesssim 1/4$ . The main purpose of these plots is to qualitatively show the transition from successful to failed recovery. The quantitative interpretation for these diagrams to the right of the transition is less well understood but also observed in phase diagrams published in the literature (Donoho et al., 2006). A possible explanation for the observed behavior of the error lies in the nonlinear behavior of the solvers and on an error not measured in the $\ell_2$ sense.

The key observations from these experiments are threefold. First, it is possible, under specific conditions, to exactly recover by sparsity-promoting inversion the original spectrum $\ensuremath{\mathbf{x}}_0$ of $\ensuremath{\mathbf{f}}_0$ from (very) few data points. Secondly, optimally-jittered undersampling behaves like random undersampling according to a discrete uniform distribution. For practical purposes, the former can thus be seen as equivalent to the latter. Thirdly, not all undersampling schemes for a given undersampling factor are comparable from a CS perspective. Regular undersampling is the most challenging. Random and optimally-jittered undersamplings according to a discrete uniform distribution are among the most favorable. In particular, if the signal is sufficiently sparse, these schemes lead to a reconstruction as good as dense regular sampling. Translated to the reconstruction of seismic wavefields, these results hint at a new nonlinear sampling theory based on a sparsifying transform for complex seismic data, e.g., the curvelet transform, and a coarse random sampling scheme that creates favorable recovery conditions for that transform, e.g., optimally-jittered undersampling.


phasediagREG,phasediagIRREG,phasediagJIT1 Figure 6. Averaged recovery errors for a -sparse Fourier vector reconstructed from time samples taken (a) regularly, (b) randomly, and (c) optimally jittered from the model. In each plot, the curves from top to bottom correspond to an undersampling factor ranging from two to six, i.e., $\gamma = 2, \dots , 6$ .

Next: Application to seismic data Up: Theory Previous: Jittered undersampling ( ):

2007-11-27