Scientist’s Documentation¶

This pages describes the motivation and the approach behind the sensor placement algorithm. More details are found in the original publication:

Stefano Maranò, Donat Fäh, and Yue M. Lu, “Sensor Placement for the Analysis of Seismic Surface Waves: Sources of Error, Design Criterion and Array Design Algorithms”, Geophys. J. Int. (2014) 197 (3): 1566–1581. Free access online, doi:10.1093/gji/ggt489.

The proposed sensor placement algorithm was developed to design planar arrays in seismology. Other possible domains of application include acoustic and radar. The most important assumption behind this work is that the wave should cross the array with a pklane wavefront.

Motivation
Important quantities
Relationship with likelihood function
Proposed cost function
Discretization and relaxation
How to choose the parameters?
Stretching
Bibliography

Motivation ¶

The presence of outliers can severely downgrade the estimation performance. Outliers are related to the presence of sidelobes in the array response.

In the image below, we evaluate the performance of a maximum likelihood estimator at three different signal-to-noise ratio (SNR) levels. The wavevector of a wave with plane wavefront is estimated using the WaveDec software. The red cross pinpoint the location of the true wavevector. The black crosses pinpoint the estimated wavevector for different noise realizations.

At low SNR, the wavenumber estimates appears to be distributed randomly. The signal is dominated by the strong noise and the estimates carry no information about the true wavevector.

At intermediate SNR, many estimates cluster near the true wavevector. Many other estimates are clustered away from the true wavevector. They are clustered near the sidelobe of the expected loglikelihood function (shown in the background). This large errors are called gross errors or outliers.

At high SNR, all the estimates are clustered near the true wavevector. Their variance is well described by the Cramér–Rao bound.

Wavenumber estimate at low signal-to-noise ratio (SNR), at intermediate SNR and at high SNR.¶

Important quantities ¶

Given $N_s$ sensor positions $\mathbf{p}_n\in\mathbb{R}^2$ we define the sampilng pattern as the sum of $N_s$ Dirac delta centered at the sensor positions

(1)¶ $\begin{eqnarray*} h(\mathbf{p})=\sum_{n=1}^{N_s}\delta(\mathbf{p}-\mathbf{p}_{n})\,. \end{eqnarray*}$

Then we consider the two-dimensional Fourier transform of the sampling pattern. Let $\boldsymbol{\kappa}=\left(\kappa_x,\kappa_y\right)^T$ denote the wavevector (spatial frequency). The Fourier transform is

(2)¶ $\begin{eqnarray*} H(\boldsymbol{\kappa}) & = & \mathcal{F}\left\{ h(\mathbf{p}))\right\} \\ & = & \int_{\mathbb{R}^2} \sum_{n=1}^{N_s}\delta(\mathbf{p}-\mathbf{p}_{n}) \textrm{exp}\left(-i \boldsymbol{\kappa}^T \mathbf{p} \right) \,\textrm{d}\mathbf{p} \\ & = & \sum_{n=1}^{N_s} \textrm{exp}\left( -i \boldsymbol{\kappa}^T \mathbf{p}_n \right)\,. \end{eqnarray*}$

The squared complex modulus of the Fourier transform, $\left|H(\boldsymbol{\kappa})\right|^{2}$ , is known as array response.

Sampling pattern $h(\mathbf{p})$ of a 5 sensor array.¶

The array response $\left|H(\boldsymbol{\kappa})\right|^{2}$ .¶

Relationship with likelihood function ¶

Love and Rayleigh likelihood functions are related to the array response. It can be shown that the likelihood function of a Love wave $\ln(p_{\mathbf{Y}}(\mathbf{y}|\boldsymbol{\kappa}))$ is realted to the array response as

(3)¶ $\begin{eqnarray*} \mathop{\mathbb{E}} \left\{ \ln\left(p_{\mathbf{Y}}\left(\mathbf{y}|\boldsymbol{\kappa}\right)\right)\right\} \propto f_{\textrm{L}}(\psi,\breve{\psi})\left|H(\boldsymbol{\kappa}-\breve{\boldsymbol{\kappa}})\right|^{2}\,, \end{eqnarray*}$

where $\mathop{\mathbb{E}}$ denotes the expectation operator, $p_{\mathbf{Y}}\left(\mathbf{y}|\boldsymbol{\kappa}\right)$ is the likelihood function. True wave parameters are detoted with the superscript $\breve{}$ .

Similarly, for Rayleigh waves, it can be shown that

(4)¶ $\begin{eqnarray*} \mathop{\mathbb{E}} \left\{ \ln\left(p_{\mathbf{Y}}\left(\mathbf{y} |\boldsymbol{\kappa},\xi\right)\right)\right\} \propto f_{\textrm{R}}(\psi,\breve{\psi},\xi,\breve{\xi})\left|H(\boldsymbol{\kappa}-\breve{\boldsymbol{\kappa}})\right|^{2}\,. \end{eqnarray*}$

The functions $f_{\textrm{L}}$ and $f_{\textrm{L}}$ multiply the array response changing its shape. They reflect the contribution to the likelihood function of the three-component sensors. It is important to stress that these two functions do not depend on the sensor positions. For an acoustic wave measured at a microphone array (scalar sensor), these factor would disappear.

The following pictures show graphically the relationship between likelihood function and array response. Observe the shift corresponding to the true wavevector $\breve{\boldsymbol{\kappa}}$ and compare with the array response depicted in the previous section.

Likelihood function for a Love wave. The true wavenumber is $\breve{\boldsymbol{\kappa}}$ .¶

Likelihood function of a Rayleigh wave.¶

More details concerning the relationship between likelihood function and array response are given in [Maranò_et_al_2014b].

Proposed cost function ¶

The region $\mathcal{K}$ on the wavenumber (spatial frequency) plane is defined by $\kappa_{\textrm{min}}$ and $\kappa_{\textrm{max}}$ .¶

Our aim is to reduce the sidelobes of the array response in a certain spatial badwidth of interest. The region of interest is the annulus $\mathcal{K}$ defined by a minimum and maximum wavenumber, $\kappa_{\textrm{min}}$ and $\kappa_{\textrm{max}}$ , respectively.

We formulate the following optimization problem, minimizing the largest sidelobe in the region $\mathcal{K}$ :

(5)¶ $\begin{eqnarray*} \min_{\mathbf{p}_{1},\mathbf{p}_{2},\ldots,\mathbf{p}_{N_s}} \max_{\boldsymbol{\kappa}\in\mathcal{K}}\left|H(\boldsymbol{\kappa},\mathbf{p}_{1},\mathbf{p}_{2},\ldots,\mathbf{p}_{N_s})\right| \\ \mathcal{K}=\{\boldsymbol{\kappa}:\kappa_{\textrm{min}}\leq\left\Vert \boldsymbol{\kappa}\right\Vert _{2}\leq2\kappa_{\textrm{max}}\}\,. \end{eqnarray*}$

This problem is very difficult to optimize. In fact, the minimization variables $\mathbf{p}_{1},\mathbf{p}_{2},\ldots,\mathbf{p}_{N_s}$ appear in the argument of complex exponentials, cf. Eq. (2).

Warning

The values $\kappa_{\textrm{min}}$ and $\kappa_{\textrm{max}}$ define region $\mathcal{K}$ where the sidelobes are minimized. They should not be confused with the smallest and largest resolvable wavenumber by the optimized array (i.e., array resolution limits).

The array resolution limits are clearly related with the extent of the region $\mathcal{K}$ . The smallest resolvable wavenumber is typically slightly smaller than $\kappa_{\textrm{min}}$ . The largest resolvable wavenumber is typically $\kappa_{\textrm{max}}/2$ .

Discretization and relaxation ¶

Instead of dealing with the optimization problem of Eq. (5) directly, we restrict the possible sensor position to arbitrary discrete locations. We introduce the vector $\mathbf{x}\in\{0,1\}^N$ to represent the presence or absence of a sensor at discrete locations.

The discretized problem is

(6)¶ $\begin{eqnarray*} \min_{\mathbf{x}} \left\Vert \mathbf{F}\mathbf{x}\right\Vert _{\infty} \\ \mathbf{A}\mathbf{x} = \mathbf{b} \\ \mathbf{x} \in \{0,1\}^{N} \end{eqnarray*}$

where $\mathbf{F}:\mathbb{R}^{N}\to\mathbb{C}^{M}$ is a linear operator computing the array response $H$ at $M$ spatial-frequency points. The infinity norm returns the largest complex modulus of the array response, $\left\Vert \mathbf{x}\right\Vert _{\infty}=\max\{|x_{1}|,|x_{2}|,\ldots\}$ .

Let $\boldsymbol{\kappa}_m$ be the $m$ -th spatial frequency and let $\mathbf{p}_n$ be the position of the $n$ -th possible sensor location. The element $m,n$ of $\mathbf{F}$ is

(7)¶ $\begin{eqnarray*} \left[\mathbf{F}\right]_{m,n} & = & \textrm{exp} \left( -i \boldsymbol{\kappa}^T_m \mathbf{p}_n\right)\,. \end{eqnarray*}$

A linear constraint specifying the number of sensors $\sum_{n=1}^{N} x_n = N_s$ is enforced within $\mathbf{A}\mathbf{x} = \mathbf{b}$ .

The ojective function in (6) is convex, a major improvement from (5)! The problem is still very hard because of the binary constraint on the vector $\mathbf{x}$ .

As a last step, we relax the problem. Instead of considering the largest sidelobe in terms of complex modulus ( $\left| \mathbf{F}\mathbf{x}\right|$ ), we consider the absolute value of the real and imaginary parts ( $\left|\textrm{Re}\left(\mathbf{F}\mathbf{x}\right)\right|$ and $\left|\textrm{Im}\left(\mathbf{F}\mathbf{x}\right)\right|$ ). With this relaxation, the objective function becomes linear.

The relaxed problem, after introducing the dummy variable $y\in\mathbb{R}$ is

(8)¶ $\begin{eqnarray*} \min_{y}\, y \\ \left(\begin{array}{c} \textrm{Re}\left(\mathbf{F}\right)\\ \textrm{Im}\left(\mathbf{F}\right)\\ -\textrm{Re}\left(\mathbf{F}\right)\\ -\textrm{Im}\left(\mathbf{F}\right) \end{array}\right) \mathbf{x} \preceq y\mathbf{1} \\ \mathbf{A}\mathbf{x} =\mathbf{b} \\ y\in\mathbb{R} ,\,\mathbf{x}\in\{0,1\}^{N} \\ \end{eqnarray*}$

where $\mathbf{1}$ is a vector of $1$ s of length $4M$ .

The optimization problem of Eq. (8) is addressed numerically as a mixed integer program (MIP).

Maranò_et_al_2014b: Stefano Maranò, Donat Fäh, and Yue M. Lu, “Sensor Placement for the Analysis of Seismic Surface Waves: Sources of Error, Design Criterion and Array Design Algorithms”, Geophys. J. Int. (2014) 197 (3): 1566–1581. Free access online.

Scientist’s Documentation¶

Motivation ¶

Important quantities ¶

Relationship with likelihood function ¶

Proposed cost function ¶

Discretization and relaxation ¶

How to choose the parameters?¶

Stretching ¶

Bibliography ¶

Table of Contents

Previous topic

Next topic