IEEE Signal Processing - March 2018 - 64

X n - x l = d l n is sufficiently smaller than Dx (see Figure 1).
We write (2) as a Taylor series around a closer point x l of the
regular grid
1
M

d ^X nh .

stand for samples d (X n), the small circles are points x l of a regular grid,
and the small vertical bars are bin delimiters.

The general setup of the problem
The problem of finding the Fourier spectra of an irregular set
of samples usually does not exhibit properties like uniqueness
and may not even have a solution. Defining the minimum and
maximum frequencies, whether a constant or a variable frequency interval should be used to get an optimal set of sinusoidal functions, is neither practical nor easy. As a result, the
general problem is commonly formulated as that of finding the
least square solution
-1

(1)

whatever the set of frequencies/wavenumbers eventually chosen to characterize the problem. Here, the upper index H
stands for the Hermitian, and K is a diagonal matrix used both
for regularization and/or conveying desired physical or statistical properties to the solution.
The use of an embedded, regular DFT restricts the set of
basic sinusoidal functions to a regularly spaced one in the frequency/wavenumber domain. Only the Nyquist frequency, and
consequently the embedded grid sampling rate, remains to be
chosen. In a highly irregular survey there may be a tradeoff
between a higher sampling rate, where all grid point displacements are small, and a smaller sampling rate, where there are
no empty bins. The former choice guarantees fast convergence
and reduced computational cost. On the other hand, as it is
going to be shown, the latter choice guarantees uniqueness and
stability in the spectrum estimate. In any case, (1) will be the
reference for building an approximate inverse for the irregular
Fourier transform.

The one-dimensional formulation
of the approximation
A unidimensional set of N measurements d (X n) can be written as a linear combination of M Fourier components if
d (X n) = 1
M

M-1

/

D m e -2irk m X n .

D m e -2irk m x l

m=0

/

j=0

(- 2irk m d l n) j
.
j!

(3)

(2)

d ( X n) .

/

j=0

(- 2ird l n) j
j!

1
M

M-1

/

(k m) j D m e -2irk m x l .

(4)

m=0

Considering that approximations of this type can be made to
every measurement point and denoting the regular DFT in (3)
as F, one can write an approximation to (1) as
d . " F + dFk + d 2 Fk 2 + ... , D,
which allows us to write the irregular unidimensional Fourier
transform in a series form as
F=

3

/

j=0

1 d j Fk j ,
j!

(5)

with k a diagonal matrix made up of different wavenumbers
times - 2ir for simplicity.
An underlying assumption of one measurement point X n
to every regular grid point x l in (5) makes it not general. The
definition of an embedded grid in a set of irregular measurements d may lead to accumulation points (more than one X
for a given x as in Figure 1) as well as grid points that have
no measured point around. To extend (5), so as to account for
accumulation and empty bins, let us introduce an extended
identity matrix I e and simply rewrite (5) as
F = Ie F +

3

/

j=1

1 d j Fk j,
j!

(6)

bearing in mind that there can be more than one n in d ln
associated with one single grid point x l . The matrix k is still
diagonal since it is desirable to keep F a regular DFT. Matrices
I e and d map a regular set of the data space into the measured
data space and, since, in general, it is neither regular nor complete, they have to carry these irregularities inside. Note that
terms like d j are not real matrix products. By construction,
they are matrices of the same shape as I e but made up of jth
powers in d ln . The general aspect of I e (and d) is that of an
identity matrix with repeated rows everywhere more than one
measured point surrounds one single grid point. Empty bins
are accounted for in I e by dropping or zeroing out corresponding rows.

m=0

with D m the discrete Fourier spectra that honor all measurements d (X n) for a given discrete set of k m . Equation (2) explicitly presents the Fourier operator F defined in (1).
Let x l, 0 1 l 1 M - 1, x l - x l - 1 = Dx 6 l be a regular
set of points defining an embedded grid where for all existing measurement point X n there is a grid point x l such that
64

/

Now, the summation over m is already a regular DFT. Rearranging, one can write

Figure 1. The unidimensional space sampled irregularly. The arrows

F -1 & 6F H F + K@ F H,

M-1

The F H F matrix

The F H F matrix is fundamental for working out an estimate
for the inverse F -1 . Given the expression for F in (6), one
can write
F H F = F H I Te I e F + 6F H I Te dFk + k ) F H d T I e F@ + ... (7)

IEEE Signal Processing Magazine

|

March 2018

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