IEEE Signal Processing - March 2018 - 63

Despite the wide use of FFTs to estimate the Fourier spectra of continuous functions given a limited set of their samples,
these estimates are, in general, not accurate if one of the following two requirements are not fulfilled:
1) The bandwidth of the function must be contained in the
interval [0, (aDx) -1], Dx is the sampling interval and a is
a constant that depends on how the function is sampled
(primitive, derivatives, etc).
2) All of the functions' support must be sampled.
There are many proved sampling theorems establishing how
to reconstruct continuous band-limited functions after infinitely and regularly measuring the functions itself and/or their
derivatives [12], [13], provided a required minimal sampling
rate is achieved. However, if one counts only with a limited
set of samples over just a fraction of a band-limited function's
support, it is likely that the estimated discrete spectrum will
be an aliased version of the one if all of the functions' support
has been sampled. This will be the case if the resulting discrete
function has discontinuities. It implies lack of fidelity and/or
uniqueness on the reconstruction of the original continuous
function using just this limited set of samples.
Most papers on Fourier interpolation deal essentially with
the idea of computing a set of weights for sinusoidal functions
so as to honor a discrete set of samples via a linear combination of these basic trigonometric functions. The weights are
the estimated Fourier spectrum for the set of measurements.
Trigonometric interpolation is what is generally meant by Fourier interpolation of discrete functions.
The situation is the same if the sampling process is irregular
[4]-[8]. Provided that all of the function's support is covered,
the fidelity in the reconstruction of the function will depend
only on the available sampling density.
One usually relies on a limited set of measurements instead.
Thus, the success in the reconstruction or interpolation processes will depend on the range of the functions' support effectively sampled. In the general case, a finite and discrete set
D m, m = 1, M, components of the DFT of an also finite set
of samples d n, n = 1, N, is used to estimate the corresponding
continuous function d (x) as the sum
dr(x) = 1
M

M

/

Dm e

-2irxm
MDx

.

do field conditions and/or limited budgets allow for a painstaking, relatively long, geophysical survey design and deployment.
Then, many authors have addressed the problem of estimating
the Fourier spectrum given an irregular set of measurements.
Most papers on this field address aspects of the problem like
underdetermination, numerical instabilities [4], [6]-[8], noise,
as well as numerical performance. At this point, most expectations are that higher-dimensional problems should deserve
alternative approaches to the common Fourier interpolation.
In the general case, given a set of irregular measurements of
a continuous function, an associated Fourier spectrum estimate
is made with either of two approaches: 1) the data d is interpolated for a regular grid and then current FFT algorithms are
applied or 2) the Fourier spectrum D is estimated as the solution to an inverse problem D = F -1 d. The first approach is
not guaranteed to reproduce original measurements as a linear
combination of Fourier basis. The second approach is usually
preferred since it is expected to honor original measurements
without any additional constraints to the nature of the data but
the very Fourier composition itself. This approach is currently
used, but it generally implies inverting matrices in a problem of
numerical complexity O (N 3), prohibitive for larger N.
The objective here is essentially to present an affordable
alternative technique to compute F -1 for bigger problems.
Emphasis is on the algorithm and its numerical performance.
The irregular Fourier transform is written as a correction for
an embedded regular Fourier transform that is defined for an
embedded regular grid chosen so as to hopefully estimate the
Fourier spectrum for the data as accurately as possible.
This work was initially motivated by the relative success
achieved in Liu and Sacchi [7] and Naghizadeh and Sacchi [8].
The authors neglected small measuring point departures from
a regular grid to use current FFTs in seismic data regularization. It can be said that the work by Naghizadeh and Sacchi
used a zero-order approximation for the irregular DFT. One
could argue: What if higher-order approximations for small
deviations of a regular grid were considered?
The order of approximation required to achieve higher
accuracy in the Fourier spectrum determination depends on
how much the argument of Fourier transform kernels deviates from

m=0

The reconstructed function dr(x), ideally, honors the original samples d n when x = X n, the sampling positions, for all
0 1 n 1 N - 1. This reconstruction is said to be a trigonometric interpolation of the original, generally unknown, function d (x).
To estimate the spectra of nonregular data efficiently, especial discretizations of the Fourier space would be required to
maximize the number of redundant computations or, at least,
to assure orthogonality for the irregular DFT. This is not a
practical goal to achieve. The interest in nonregular data is
great however, since practical limitations and/or theoretical
reasons may demand irregular measurement designs. This is
particularly true in geophysical data acquisition, where rarely

2r k n Dx ,
where 0 1 n 1 N - 1 and N is the number of grid points. As
regular DFTs have k max # (2Dx) -1, the maximum deviation
will be given by
2r k max max (d x) .
Thus, keeping the maximum deviation under the limit
max ^ d x h % D x
r

would guarantee a rapid convergence of an approximation for
the irregular DFT.

IEEE SIgnal ProcESSIng MagazInE

|

March 2018

|

63



Table of Contents for the Digital Edition of IEEE Signal Processing - March 2018

Contents
IEEE Signal Processing - March 2018 - Cover1
IEEE Signal Processing - March 2018 - Cover2
IEEE Signal Processing - March 2018 - Contents
IEEE Signal Processing - March 2018 - 2
IEEE Signal Processing - March 2018 - 3
IEEE Signal Processing - March 2018 - 4
IEEE Signal Processing - March 2018 - 5
IEEE Signal Processing - March 2018 - 6
IEEE Signal Processing - March 2018 - 7
IEEE Signal Processing - March 2018 - 8
IEEE Signal Processing - March 2018 - 9
IEEE Signal Processing - March 2018 - 10
IEEE Signal Processing - March 2018 - 11
IEEE Signal Processing - March 2018 - 12
IEEE Signal Processing - March 2018 - 13
IEEE Signal Processing - March 2018 - 14
IEEE Signal Processing - March 2018 - 15
IEEE Signal Processing - March 2018 - 16
IEEE Signal Processing - March 2018 - 17
IEEE Signal Processing - March 2018 - 18
IEEE Signal Processing - March 2018 - 19
IEEE Signal Processing - March 2018 - 20
IEEE Signal Processing - March 2018 - 21
IEEE Signal Processing - March 2018 - 22
IEEE Signal Processing - March 2018 - 23
IEEE Signal Processing - March 2018 - 24
IEEE Signal Processing - March 2018 - 25
IEEE Signal Processing - March 2018 - 26
IEEE Signal Processing - March 2018 - 27
IEEE Signal Processing - March 2018 - 28
IEEE Signal Processing - March 2018 - 29
IEEE Signal Processing - March 2018 - 30
IEEE Signal Processing - March 2018 - 31
IEEE Signal Processing - March 2018 - 32
IEEE Signal Processing - March 2018 - 33
IEEE Signal Processing - March 2018 - 34
IEEE Signal Processing - March 2018 - 35
IEEE Signal Processing - March 2018 - 36
IEEE Signal Processing - March 2018 - 37
IEEE Signal Processing - March 2018 - 38
IEEE Signal Processing - March 2018 - 39
IEEE Signal Processing - March 2018 - 40
IEEE Signal Processing - March 2018 - 41
IEEE Signal Processing - March 2018 - 42
IEEE Signal Processing - March 2018 - 43
IEEE Signal Processing - March 2018 - 44
IEEE Signal Processing - March 2018 - 45
IEEE Signal Processing - March 2018 - 46
IEEE Signal Processing - March 2018 - 47
IEEE Signal Processing - March 2018 - 48
IEEE Signal Processing - March 2018 - 49
IEEE Signal Processing - March 2018 - 50
IEEE Signal Processing - March 2018 - 51
IEEE Signal Processing - March 2018 - 52
IEEE Signal Processing - March 2018 - 53
IEEE Signal Processing - March 2018 - 54
IEEE Signal Processing - March 2018 - 55
IEEE Signal Processing - March 2018 - 56
IEEE Signal Processing - March 2018 - 57
IEEE Signal Processing - March 2018 - 58
IEEE Signal Processing - March 2018 - 59
IEEE Signal Processing - March 2018 - 60
IEEE Signal Processing - March 2018 - 61
IEEE Signal Processing - March 2018 - 62
IEEE Signal Processing - March 2018 - 63
IEEE Signal Processing - March 2018 - 64
IEEE Signal Processing - March 2018 - 65
IEEE Signal Processing - March 2018 - 66
IEEE Signal Processing - March 2018 - 67
IEEE Signal Processing - March 2018 - 68
IEEE Signal Processing - March 2018 - 69
IEEE Signal Processing - March 2018 - 70
IEEE Signal Processing - March 2018 - 71
IEEE Signal Processing - March 2018 - 72
IEEE Signal Processing - March 2018 - 73
IEEE Signal Processing - March 2018 - 74
IEEE Signal Processing - March 2018 - 75
IEEE Signal Processing - March 2018 - 76
IEEE Signal Processing - March 2018 - 77
IEEE Signal Processing - March 2018 - 78
IEEE Signal Processing - March 2018 - 79
IEEE Signal Processing - March 2018 - 80
IEEE Signal Processing - March 2018 - 81
IEEE Signal Processing - March 2018 - 82
IEEE Signal Processing - March 2018 - 83
IEEE Signal Processing - March 2018 - 84
IEEE Signal Processing - March 2018 - 85
IEEE Signal Processing - March 2018 - 86
IEEE Signal Processing - March 2018 - 87
IEEE Signal Processing - March 2018 - 88
IEEE Signal Processing - March 2018 - 89
IEEE Signal Processing - March 2018 - 90
IEEE Signal Processing - March 2018 - 91
IEEE Signal Processing - March 2018 - 92
IEEE Signal Processing - March 2018 - 93
IEEE Signal Processing - March 2018 - 94
IEEE Signal Processing - March 2018 - 95
IEEE Signal Processing - March 2018 - 96
IEEE Signal Processing - March 2018 - 97
IEEE Signal Processing - March 2018 - 98
IEEE Signal Processing - March 2018 - 99
IEEE Signal Processing - March 2018 - 100
IEEE Signal Processing - March 2018 - 101
IEEE Signal Processing - March 2018 - 102
IEEE Signal Processing - March 2018 - 103
IEEE Signal Processing - March 2018 - 104
IEEE Signal Processing - March 2018 - 105
IEEE Signal Processing - March 2018 - 106
IEEE Signal Processing - March 2018 - 107
IEEE Signal Processing - March 2018 - 108
IEEE Signal Processing - March 2018 - 109
IEEE Signal Processing - March 2018 - 110
IEEE Signal Processing - March 2018 - 111
IEEE Signal Processing - March 2018 - 112
IEEE Signal Processing - March 2018 - 113
IEEE Signal Processing - March 2018 - 114
IEEE Signal Processing - March 2018 - 115
IEEE Signal Processing - March 2018 - 116
IEEE Signal Processing - March 2018 - 117
IEEE Signal Processing - March 2018 - 118
IEEE Signal Processing - March 2018 - 119
IEEE Signal Processing - March 2018 - 120
IEEE Signal Processing - March 2018 - 121
IEEE Signal Processing - March 2018 - 122
IEEE Signal Processing - March 2018 - 123
IEEE Signal Processing - March 2018 - 124
IEEE Signal Processing - March 2018 - 125
IEEE Signal Processing - March 2018 - 126
IEEE Signal Processing - March 2018 - 127
IEEE Signal Processing - March 2018 - 128
IEEE Signal Processing - March 2018 - 129
IEEE Signal Processing - March 2018 - 130
IEEE Signal Processing - March 2018 - 131
IEEE Signal Processing - March 2018 - 132
IEEE Signal Processing - March 2018 - 133
IEEE Signal Processing - March 2018 - 134
IEEE Signal Processing - March 2018 - 135
IEEE Signal Processing - March 2018 - 136
IEEE Signal Processing - March 2018 - 137
IEEE Signal Processing - March 2018 - 138
IEEE Signal Processing - March 2018 - 139
IEEE Signal Processing - March 2018 - 140
IEEE Signal Processing - March 2018 - 141
IEEE Signal Processing - March 2018 - 142
IEEE Signal Processing - March 2018 - 143
IEEE Signal Processing - March 2018 - 144
IEEE Signal Processing - March 2018 - 145
IEEE Signal Processing - March 2018 - 146
IEEE Signal Processing - March 2018 - 147
IEEE Signal Processing - March 2018 - 148
IEEE Signal Processing - March 2018 - 149
IEEE Signal Processing - March 2018 - 150
IEEE Signal Processing - March 2018 - 151
IEEE Signal Processing - March 2018 - 152
IEEE Signal Processing - March 2018 - 153
IEEE Signal Processing - March 2018 - 154
IEEE Signal Processing - March 2018 - 155
IEEE Signal Processing - March 2018 - 156
IEEE Signal Processing - March 2018 - 157
IEEE Signal Processing - March 2018 - 158
IEEE Signal Processing - March 2018 - 159
IEEE Signal Processing - March 2018 - 160
IEEE Signal Processing - March 2018 - 161
IEEE Signal Processing - March 2018 - 162
IEEE Signal Processing - March 2018 - 163
IEEE Signal Processing - March 2018 - 164
IEEE Signal Processing - March 2018 - 165
IEEE Signal Processing - March 2018 - 166
IEEE Signal Processing - March 2018 - 167
IEEE Signal Processing - March 2018 - 168
IEEE Signal Processing - March 2018 - 169
IEEE Signal Processing - March 2018 - 170
IEEE Signal Processing - March 2018 - 171
IEEE Signal Processing - March 2018 - 172
IEEE Signal Processing - March 2018 - 173
IEEE Signal Processing - March 2018 - 174
IEEE Signal Processing - March 2018 - 175
IEEE Signal Processing - March 2018 - 176
IEEE Signal Processing - March 2018 - Cover3
IEEE Signal Processing - March 2018 - Cover4
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201809
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201807
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201805
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201803
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_201801
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0917
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0717
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0517
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0317
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0117
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0916
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0716
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0516
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0316
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0116
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0915
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0715
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0515
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0315
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0115
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0914
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0714
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0514
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0314
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0114
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0913
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0713
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0513
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0313
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0113
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0912
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0712
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0512
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0312
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0112
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0911
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0711
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0511
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0311
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0111
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0910
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0710
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0510
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0310
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0110
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0909
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0709
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0509
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0309
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0109
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_1108
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0908
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0708
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0508
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0308
https://www.nxtbook.com/nxtbooks/ieee/signalprocessing_0108
https://www.nxtbookmedia.com