UBC Faculty Research and Publications

Signal reconstruction from incomplete and misplaced measurements Sastry, Challa; Hennenfent, Gilles; Herrmann, Felix J. 2007-03-10

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

Item Metadata


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

Full Text

SIGNAL RECONSTRUCTION FROM INCOMPLETE AND MIS-PLACED MEASUREMENTSABSTRACTConstrained by practical and economical considerations, one often uses seismic datawith missing traces. The use of such data results in image artifacts and poor spatialresolution. Sometimes due to practical limitations, measurements may be available ona 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 ontoregular grid via the Fourier domain, using a recently developed greedy algorithm. Thebasic 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 gridto be considered as on the designated grid for faithful recovery. Our experimental workshows that for compressible signals, a uniformly distributed perturbation can be offsetwith slightly more number of measurements.EAGE 69th Conference & Exhibition ? London, UK, 11 - 14 June 2007IntroductionThe seismic source generates a wavefield. During data acquisition, this wavefield issampled at discrete locations and at discrete times over a large area. Due to the trade offbetween geophysical and economical constraints, sampling is rarely regular and com-plete, which results in artifacts in seismic images when the measurements are processedwith simple binning techniques (see e.g. Hennenfent and Herrmann, 2006; Herrmannand Hennenfent, 2007). These artifacts can be minimized by improving upon binningusing other techniques. One of these is based on Fourier reconstruction, which is atransform based method.The recently proposed optimization techniques via Basis Pursuit (BP) and MatchingPursuit (MP) have promising applications (see e.g. Candes et al., 2006; Hennenfentand Herrmann, 2006; Herrmann and Hennenfent, 2007) for the interpolation of missingdata in otherwise regularly sampled grid. The Stagewise Orthogonal Matching Pur-suit (StOMP) (see Donoho et al., 2006) assumes easily verifiable recovery conditionsand provides a faster algorithm for solving underdetermined system of equations In thepresent paper, we apply StOMP to the data interpolation problem through a Fourierbased 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 matrixequation asf[x] = F[x]?. (1)The notation f[x], F[x] is used to emphasize the dependence of f, F on the data gridx. Given measurements fj = f(xj) for xj element [-12, 12) with xj distributed according tosome random distribution, our concern is the evaluation of Fourier coefficients ?k from(1). The system (1) represents an underdetermined system for an incomplete set ofmeasurements. In the following section, we describe the signal reconstruction methodsproposed in the recent literature (see e.g. Candes et al., 2006; Chen at al., 2001; Donohoet al., 2006) for solving underdetermined systems. After describing the recent recoveryalgorithms, we present our problem in some detail and analyze our experimental work.Signal recovery from incomplete measurementsSuppose the vector y element I n of measurements yi satisfiesy = Phix for Phi element I n?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? = PhiT(PhiPhiT)-1y, called the pseudo inverse of Phi. Another way of computing a so-lution of (2) involves taking ?shortest? vector. That is, bardblxbardbl0 := |#{i : xi negationslash= 0}| < N.In this case, Basis pursuit (BP) (see e.g. Chen et. al., 2001), a convex programmingapproach, proposes the solution via l1 minimization asminalpha bardblalphabardbl1 subject to Phialpha = y. (3)One of the important results, for exact recovery from incomplete samples, states thatexact recovery is possible as long as the synthesis matrix Phi obeys what is called a re-stricted isometry (see e.g. Candes et al., 2006; Chen et. al., 2001) and certain conditionsin terms of the so-called coherence parameter (?), which is the maximum off-diagonalentry in PhiTPhi (see e.g. Candes et al., 2006; Chen et. al., 2001). An important resultEAGE 69th Conference & Exhibition ? London, UK, 11 - 14 June 2007by (see e.g. Candes et al.). states that exact recovery of the k nonzero entries in x0 ispossible as long as the number of measurements is roughly proportional to the numberof nonzeros, that is, n proportional ?2k.Stagewise Orthogonal Matching Pursuit (StOMP)The stronger recovery results for arbitrary systems stated in the above section are verypowerful. They, however, tend to be pessimistic requiring many measurements or highersparsity for the solution vector. Additionally, it is difficult to verify the stronger recov-ery conditions in general. Nevertheless, there are certain weaker recovery conditionsassumed by StOMP, proposed recently by ( Donoho et al., 2006). The conditionsinvolve 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), whenthe columns of Phi are Gaussian random variables with unit norm.Starting with an initial residual r0 = y, at sth stage, StOMP forms the matched fil-ter PhiTrs-1 and identifies all coordinates with amplitude exceeding a specially chosenthreshold. 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 fixednumber of steps. In order to design the threshold parameters, StOMP assumes the Gaus-sian behaviour of the (residual) vector: z = ? -x0 = (PhiTPhi-I)x0. The performanceof StOMP is studied in terms of a phase diagram, which provides the information onthe reconstruction error in terms of the number of measurements and sparsity of recon-struction vector. Though StOMP is primarily designed for certain matrices of Gaussianrandom variables, (Donoho et al., 2006) have found that the method applies to partialFourier ensemble as well. Hence the application of StOMP to the present interpolationproblem is justified.Present workThe optimization techniques described in the previous section are shown to be usefulby Hennenfent and Herrmann, 2006; Herrmann and Hennenfent, 2007 for seismic in-terpolation. As our measurements are missing on otherwise regularly sampled grid, wemodel them as random variables having uniform distribution in the discrete sense. Inseismology, 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 resultin some artifacts. In this article, we empirically study the behaviour of reconstructionerror 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 ? of uniformly distributed measurement coordinate set r be definedas? = r + lambdap, (4)where p is the perturbation vector having some random distribution and lambda is controlparameter. Let y and x (also their ?tilde? counterparts) stand for the signal and itsFourier coefficients such that y := y[r] = F[r]x and ? := y[?] = F[?]x. When wetreat ? 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 behaviourof the solution of ? = F[r]x1 in terms of the error bardblx-x1bardbl2bardblxbardbl2 . Besides the measurementsEAGE 69th Conference & Exhibition ? London, UK, 11 - 14 June 2007being noisy, naturally occurring signals typically are not sparse in strict sense, but ratherdecay by some power law when sorted in decreasing order of magnitude. Such signalsare called compressible signals. That is, for some positive numbers r and Cr, the sortedelements of {x}ielementI satisfy|xielementI| <=< Cri-r. (5)Simulation workThroughout our simulation work, we have taken N, the actual size of the signal, tobe 800. In generating the pixel values in the phase diagrams, we have taken averagesover 25 iterations. Motivated by the Gaussianity assumption used in StOMP, we havetaken the optimum tolerance in StOMP as radicalbigvar(? -y)(n + sqrt(2n)) for each n. Tobegin 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 aboutthe behaviour of error as a function of decay of compression rate (r) and the numberof measurements (n). The bright region in Figure 2(a) corresponds to parameter com-binations that favour accurate recovery. As expected, the recovery error decays withboth n and r. The transition implies that a small number of measurements are neededfor highly compressible signals. In an another experiment, we have implemented thealgorithm taking p in (4) to be (continuously) uniformly distributed in [- 12N , 12N ] andlambda element [0.05,1]. The compressible signal used in generating Figure 2(b) is shown in Figure1. 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 maynote that for the signal of unit compression rate (that is, |xielementI| <=< 1.1i ) in its frequencydomain, the number of random measurements needed for its reliable recovery can be assmall as 20-30 % of its length, and in the presence of perturbation as described above,not so many more measurements are needed for different lambda, which is demonstrated byFigure 2(b).Figure 1: Randomly permuted compressible signal xi = 1iConclusionIn the present article, applying StOMP to the Fourier-based interpolation problem, wehave demonstrated that the recovery of compressible signals can be made from a smallnumber 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. Intypical seismic imaging applications, the seismic traces are neither sparse nor com-pressible in strict sense, but rather have compressible nature in the transformed domainEAGE 69th Conference & Exhibition ? London, UK, 11 - 14 June 2007Figure 2: (a). Recovery diagram of compressible signals for different compressionrates (y-axis) and nN (x-axis). This figure depicts that a small number of measurementsare needed for the reconstruction of highly compressible signals. (b). Phase diagram ofcompressible signal of unit compression rate for different sizes of perturbations (y-axis)and nN (x-axis). This figure illustrates that with slightly more measurements, the effectof 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 carriedout as part of the project with support, secured through ITF, from the following organi-zations: BG Group, BP, Chevron, ExxonMobil and Shell.ReferencesE. J. Candes, J. Romberg and T. Tao (2006),?Stable Signal Recovery from Incompleteand Inaccurate Measurements,? Comm. Pure Appl. Math., 59, 1207-1223.S.S. Chen, D. L. Donoho, M. A. Saunders (2001), ?Atomic decomposition by basispursuit,?, SIAM Review, Vol. 43, No.1 pp: 129-159.D. L. Donoho, Y. Tsaig, I. Drori, J. L. Starck, ?Sparse solution of underdeterminedlinear 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 curveletframes,? Submitted, 2006.EAGE 69th Conference & Exhibition ? London, UK, 11 - 14 June 2007


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items