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
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Faculty Research and Publications /
- Signal reconstruction from incomplete and misplaced...
Open Collections
UBC Faculty Research and Publications
Signal reconstruction from incomplete and misplaced measurements Sastry, Challa; Hennenfent, Gilles; Herrmann, Felix J. 2007-03-10
pdf
Page Metadata
Item Metadata
Title | Signal reconstruction from incomplete and misplaced measurements |
Creator |
Sastry, Challa Hennenfent, Gilles Herrmann, Felix J. |
Contributor | University of British Columbia. Seismic Laboratory for Imaging and Modeling |
Publisher | European Association of Geoscientists & Engineers |
Date Issued | 2007 |
Description | 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 procedures 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 perturbation 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. |
Extent | 185559 bytes |
Subject |
signal reconstruction Fourier domain greedy algorithm binning Stagewise Orthogonal Matching Pursuit basis pursuit matching pursuit signal recovery Fourier reconstruction |
Genre |
Conference Paper |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2008-03-10 |
Provider | Vancouver : University of British Columbia Library |
DOI | 10.14288/1.0107396 |
URI | http://hdl.handle.net/2429/550 |
Affiliation |
Science, Faculty of Earth and Ocean Sciences, Department of |
Citation | Sastry, Challa, Hennenfent, Gilles, Herrmann, Felix J. 2007. Signal reconstruction from incomplete and misplaced measurements. EAGE 69th Conference & Exhibition. |
Peer Review Status | Unreviewed |
Scholarly Level | Graduate Faculty |
Copyright Holder | Herrmann, Felix J. |
Aggregated Source Repository | DSpace |
Download
- Media
- 52383-sastry07.pdf [ 181.21kB ]
- Metadata
- 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
- 52383-1.0107396-fulltext.txt
- Citation
- 52383-1.0107396.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
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"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.52383.1-0107396/manifest