UBC Faculty Research and Publications

Signal reconstruction from incomplete and misplaced measurements Sastry, Challa 2008

You don't seem to have a PDF reader installed, try download the pdf

Item Metadata


sastry07.pdf [ 181.21kB ]
JSON: 1.0107396.json
JSON-LD: 1.0107396+ld.json
RDF/XML (Pretty): 1.0107396.xml
RDF/JSON: 1.0107396+rdf.json
Turtle: 1.0107396+rdf-turtle.txt
N-Triples: 1.0107396+rdf-ntriples.txt

Full Text

SIGNAL RECONSTRUCTION FROM INCOMPLETE AND MIS- PLACED MEASUREMENTS ABSTRACT Constrained by practical and economical considerations, one often uses seismic data with missing traces. The use of such data results in image artifacts and poor spatial resolution. Sometimes due to practical limitations, measurements may be available on a perturbed grid, instead of on the designated grid. Due to algorithmic requirements, when such measurements are viewed as those on the designated grid, the recovery pro- cedures may result in additional artifacts. This paper interpolates incomplete data onto regular grid via the Fourier domain, using a recently developed greedy algorithm. The basic objective is to study experimentally as to what could be the size of the perturba- tion in measurement coordinates that allows for the measurements on the perturbed grid to be considered as on the designated grid for faithful recovery. Our experimental work shows that for compressible signals, a uniformly distributed perturbation can be offset with slightly more number of measurements. EAGE 69th Conference & Exhibition — London, UK, 11 - 14 June 2007 Introduction The seismic source generates a wavefield. During data acquisition, this wavefield is sampled at discrete locations and at discrete times over a large area. Due to the trade off between geophysical and economical constraints, sampling is rarely regular and com- plete, which results in artifacts in seismic images when the measurements are processed with simple binning techniques (see e.g. Hennenfent and Herrmann, 2006; Herrmann and Hennenfent, 2007). These artifacts can be minimized by improving upon binning using other techniques. One of these is based on Fourier reconstruction, which is a transform based method. The recently proposed optimization techniques via Basis Pursuit (BP) and Matching Pursuit (MP) have promising applications (see e.g. Candes et al., 2006; Hennenfent and Herrmann, 2006; Herrmann and Hennenfent, 2007) for the interpolation of missing data in otherwise regularly sampled grid. The Stagewise Orthogonal Matching Pur- suit (StOMP) (see Donoho et al., 2006) assumes easily verifiable recovery conditions and provides a faster algorithm for solving underdetermined system of equations In the present paper, we apply StOMP to the data interpolation problem through a Fourier based technique for naturally occurring compressible signals. It aims primarily at al- lowing certain misplacement in measurement coordinates. The discrete Fourier reconstruction of a 1-D (discrete) signal f can be written in a matrix equation as f [x] = F[x]̂f . (1) The notation f [x], F[x] is used to emphasize the dependence of f , F on the data grid x. Given measurements fj = f(xj) for xj ∈ [−12 , 12) with xj distributed according to some random distribution, our concern is the evaluation of Fourier coefficients f̂k from (1). The system (1) represents an underdetermined system for an incomplete set of measurements. In the following section, we describe the signal reconstruction methods proposed in the recent literature (see e.g. Candes et al., 2006; Chen at al., 2001; Donoho et al., 2006) for solving underdetermined systems. After describing the recent recovery algorithms, we present our problem in some detail and analyze our experimental work. Signal recovery from incomplete measurements Suppose the vector y ∈ IRn of measurements yi satisfies y = Φx for Φ ∈ IRn×N ; for n << N, (2) which admits infinitely many solutions. One way of choosing a solution for (2) in- volves taking the solution that is ‘smallest,’ (in the l2 sense), which corresponds to x̃ = ΦT(ΦΦT)−1y, called the pseudo inverse of Φ. Another way of computing a so- lution of (2) involves taking ‘shortest’ vector. That is, ‖x‖0 := |#{i : xi 6= 0}| < N. In this case, Basis pursuit (BP) (see e.g. Chen et. al., 2001), a convex programming approach, proposes the solution via l1 minimization as min α ‖α‖1 subject to Φα = y. (3) One of the important results, for exact recovery from incomplete samples, states that exact recovery is possible as long as the synthesis matrix Φ obeys what is called a re- stricted isometry (see e.g. Candes et al., 2006; Chen et. al., 2001) and certain conditions in terms of the so-called coherence parameter (µ), which is the maximum off-diagonal entry in ΦTΦ (see e.g. Candes et al., 2006; Chen et. al., 2001). An important result EAGE 69th Conference & Exhibition — London, UK, 11 - 14 June 2007 by (see e.g. Candes et al.). states that exact recovery of the k nonzero entries in x0 is possible as long as the number of measurements is roughly proportional to the number of nonzeros, that is, n ∝ µ2k. Stagewise Orthogonal Matching Pursuit (StOMP) The stronger recovery results for arbitrary systems stated in the above section are very powerful. They, however, tend to be pessimistic requiring manymeasurements or higher sparsity for the solution vector. Additionally, it is difficult to verify the stronger recov- ery conditions in general. Nevertheless, there are certain weaker recovery conditions assumed by StOMP, proposed recently by ( Donoho et al., 2006). The conditions involve randomness in measurements and Gaussian behaviour of the residual vector, which is defined in the next paragraph. These conditions are relatively easily verifiable. Hence StOMP is attractive for large scale problems such as those in seismic imaging. Suggesting the slogan that “noiseless underdetermined problems behave like noisy well- determined problems,” StOMP aims at achieving an approximate solution of (2), when the columns of Φ are Gaussian random variables with unit norm. Starting with an initial residual r0 = y, at sth stage, StOMP forms the matched fil- ter ΦTrs−1 and identifies all coordinates with amplitude exceeding a specially chosen threshold. It then solves a least-squares problem using the selected coordinates and sub- tracts the least squares fit, which results in a new residual. The method stops after a fixed number of steps. In order to design the threshold parameters, StOMP assumes the Gaus- sian behaviour of the (residual) vector: z = x̃− x0 = (ΦTΦ− I)x0. The performance of StOMP is studied in terms of a phase diagram, which provides the information on the reconstruction error in terms of the number of measurements and sparsity of recon- struction vector. Though StOMP is primarily designed for certain matrices of Gaussian random variables, (Donoho et al., 2006) have found that the method applies to partial Fourier ensemble as well. Hence the application of StOMP to the present interpolation problem is justified. Present work The optimization techniques described in the previous section are shown to be useful by Hennenfent and Herrmann, 2006; Herrmann and Hennenfent, 2007 for seismic in- terpolation. As our measurements are missing on otherwise regularly sampled grid, we model them as random variables having uniform distribution in the discrete sense. In seismology, quite often the measurements may not be acquired on the uniformly dis- tributed grid, but instead on some perturbation. Due to the algorithmic requirements, when we use them as on uniformly distributed grid, the recovery algorithms may result in some artifacts. In this article, we empirically study the behaviour of reconstruction error by means of recovery diagram as a function of the number of measurements (n) and the size of perturbation. Mathematically our problem may be described as follows: let the perturbation r̃ of uniformly distributed measurement coordinate set r be defined as r̃ = r+ λp, (4) where p is the perturbation vector having some random distribution and λ is control parameter. Let y and x (also their ’tilde’ counterparts) stand for the signal and its Fourier coefficients such that y := y[r] = F[r]x and ỹ := y[̃r] = F[̃r]x. When we treat ỹ to be the measurements over r and try to recover the underlying signal from ỹ = F[r]x, we get an inaccurate solution (x1). We study numerically the behaviour of the solution of ỹ = F[r]x1 in terms of the error ‖x−x1‖2 ‖x‖2 . Besides the measurements EAGE 69th Conference & Exhibition — London, UK, 11 - 14 June 2007 being noisy, naturally occurring signals typically are not sparse in strict sense, but rather decay by some power law when sorted in decreasing order of magnitude. Such signals are called compressible signals. That is, for some positive numbers r and Cr, the sorted elements of {x}i∈I satisfy |xi∈I | ≤ Cri−r. (5) Simulation work Throughout our simulation work, we have taken N , the actual size of the signal, to be 800. In generating the pixel values in the phase diagrams, we have taken averages over 25 iterations. Motivated by the Gaussianity assumption used in StOMP, we have taken the optimum tolerance in StOMP as √ var(ỹ − y)(n+ sqrt(2n)) for each n. To begin with, we have generated the recovery diagram in Figure 2(a) for the compress- ible signals with different compression rates . It provides some useful insights about the behaviour of error as a function of decay of compression rate (r) and the number of measurements (n). The bright region in Figure 2(a) corresponds to parameter com- binations that favour accurate recovery. As expected, the recovery error decays with both n and r. The transition implies that a small number of measurements are needed for highly compressible signals. In an another experiment, we have implemented the algorithm taking p in (4) to be (continuously) uniformly distributed in [− 1 2N , 1 2N ] and λ ∈ [0.05, 1]. The compressible signal used in generating Figure 2(b) is shown in Figure 1. The phase transition in Figure 2(b) illustrates that with slightly more number of mea- surements, the effect of perturbation error can be minimized. In Figure 2(a), one may note that for the signal of unit compression rate (that is, |xi∈I | ≤ 1.1i ) in its frequency domain, the number of random measurements needed for its reliable recovery can be as small as 20-30 % of its length, and in the presence of perturbation as described above, not so many more measurements are needed for different λ, which is demonstrated by Figure 2(b). 0 50 100 150 200 250 300 350 400 −0.2 0 0.2 0.4 0.6 0.8 1 Figure 1: Randomly permuted compressible signal xi = 1i Conclusion In the present article, applying StOMP to the Fourier-based interpolation problem, we have demonstrated that the recovery of compressible signals can be made from a small number of its random measurements. Further we have empirically shown that the re- covery of compressible signals can be made reliably in spite of error arising in mea- surements due to moderate amounts of misplacement in measurement coordinates. In typical seismic imaging applications, the seismic traces are neither sparse nor com- pressible in strict sense, but rather have compressible nature in the transformed domain EAGE 69th Conference & Exhibition — London, UK, 11 - 14 June 2007 Figure 2: (a). Recovery diagram of compressible signals for different compression rates (y-axis) and n N (x-axis). This figure depicts that a small number of measurements are needed for the reconstruction of highly compressible signals. (b). Phase diagram of compressible signal of unit compression rate for different sizes of perturbations (y-axis) and n N (x-axis). This figure illustrates that with slightly more measurements, the effect of perturbation error can be mitigated. provided by redundant frames such as curvelets . As curvelet transform is Fourier based, the observations made herein are directly relevant for seismic imaging. Acknowledgments: This work was in part financially supported by the NSERC Dis- covery Grant 22R81254 and CRD Grant 334810-05 of F.J. Herrmann and was carried out as part of the project with support, secured through ITF, from the following organi- zations: BG Group, BP, Chevron, ExxonMobil and Shell. References E. J. Candes, J. Romberg and T. Tao (2006),“Stable Signal Recovery from Incomplete and Inaccurate Measurements,” Comm. Pure Appl. Math., 59, 1207-1223. S.S. Chen, D. L. Donoho, M. A. Saunders (2001), “Atomic decomposition by basis pursuit,”, SIAM Review, Vol. 43, No.1 pp: 129-159. D. L. Donoho, Y. Tsaig, I. Drori, J. L. Starck, “Sparse solution of underdetermined linear equations by stagewise orthogonal matching pursuit,” Submitted, 2006. G. Hennenfent, F.J. Herrmann, “Seismic denoising with non-uniformly sampled curvelets,” Computing in science and engineering, pp: 50-59, May/June 2006. F.J. Herrmann and G. Hennenfent, “Non-parametric seismic data recovery with curvelet frames,” Submitted, 2006. EAGE 69th Conference & Exhibition — London, UK, 11 - 14 June 2007


Citation Scheme:


Usage Statistics

Country Views Downloads
China 9 30
Japan 4 0
City Views Downloads
Beijing 9 0
Tokyo 4 0

{[{ mDataHeader[type] }]} {[{ month[type] }]} {[{ tData[type] }]}


Share to:


Related Items