selected 16 antennas from 36 (f) Initial configuration leading to fully
augmentable array (g) Freely designed array (h) Hybrid designed array (i) Best
performing array configuration (j) Worst performing array configuration

Given $N=36$ perspective sensor locations placed linearly with an inter-
element spacing of $\lambda/2$. Consider selecting $P=16$ sensors among these
locations so as to maximize the SINR. A single source of interest is operating
at $90^{0}$, i.e. array broadside. There are also six jammers, concurrently
active at locations $40^{0}$, $85^{0}$, $95^{0}$, $135^{0}$, $140^{0}$ and
$160^{0}$. The SNR of the desired signal is $0$ dB, whereas each jammer has
the interference to noise ratio (INR) of $20$ dB. The range of binary search
for the sparsity parameter $\mu$ is set from $0.01$ to $5$, $\gamma=10^{-3}$
(sparsity threshold) and $\epsilon=0.05$. The initial $16$-element sparse
array configuration to estimate the data correlation matrix is randomly
chosen, and shown in the Fig. 4.2a. This configuration has missing correlation
lags and is occupying a fraction of the available aperture. The array collects
the data for $T=1000$ snapshots. The full array Toeplitz estimate is recovered
through matrix completion with the regularization parameter $\zeta=0.5$. The
proposed SCA approach employing matrix completion renders an array
configuration with SINR of $11.73$ dB. It is worth noting that, for the
underlying case, the number of possible array configurations is of order
$10^{9}$ which makes the problem infeasible to solve through exhaustive
search. The upper bound of performance, however, is $12$ dB which corresponds
to the case when interferences are completely canceled in the output. In this
regard, the designed array configuration is very close to the performance
upper bound. The optimized array configuration is shown in the Fig. 4.2c. It
is noted that this configuration has also missing few correlation lags.

In order to access the performance of the hybrid design approach, we consider
a randomly selected $16$ element fully augmentable array, which is shown in
Fig. 4.2b. The full data correlation matrix is estimated using the same
$T=1000$ snapshots and averaging is carried over the available correlation
lags to yield a Toepltiz estimate. The SCA approach, in this case, achieves
the array design shown in Fig. 4.2d and has a reasonable SINR performance of
$10.92$ dB. The designed hybrid array is fully augmentable and involves the
prefixed sensor locations which are arranged in the nested array topology
(prefixed configuration shown in red color). The hybrid design is clearly sub
optimal as compared to the array designed freely. It is noted that the number
of possible hybrid sparse array configurations associated with the prefixed
sensors is $53130$. Although, the possible fully augmentable configurations
are significantly less as compared to $10^{9}$ possibilities, the maximum SINR
hybrid design found through enumeration is $11.93$ dB and is close to the
upper performance bound of $12$ dB. The performance of both designs are
compared with the benchmark design initialized with FCS-LSS estimated from
$T=1000$ samples supposedly collected from all $N$ sensors. The benchmark
design yields the freely designed and hybrid sparse configurations with the
SINR of $11.82$ dB and $11.65$ dB respectively. This performance is superior
to the above mentioned designs that employ the Toeplitz estimation in lieu of
the actual full correlation matrix.

It is of interest to analyze the effect of the initial sparse array
configuration on the proposed SCA optimization. This time, the data is
collected through the initial configurations depicted in Figs. 4.2e and 4.2f,
instead of the configurations (Figs. 4.2a and 4.2b) employed for the earlier
example. The underlying operating environment and all other parameters remain
the same as above. As before, the freely designed array is achieved through
matrix completion, whereas the hybrid design involves averaging to estimate
the full data correlation matrix. The free-design and the hybrid design
achieve SINR of $11.82$ dB and $11.65$ dB, respectively. The designed array
configurations are shown in the Figs. 4.2g and 4.2h. These configurations
offer superior performances to those optimized earlier, assuming different
initial configurations. This underscores the dependence of sparse array
beamforming optimization on the array initial conditions. It is noted that for
the same underlying environment and initial configuration, the proposed
solution is still not unique and dependent on the random realizations of the
received data. In order to reliably gauge the performance of the proposed
scheme, we report the average results repeated over $100$ independent trials.
It is found that under the initial configurations shown in Figs. 4.2a and
4.2b, the average SINR performances are $11.79$ dB for freely designed SCA and
$11.18$ dB for the hybrid design. On the other hand, the initial
configurations, shown in Figs. 4.2e and 4.2f, yield the average performances
of $11.6$ dB and $11.54$ dB for the free and hybrid designs, respectively.
These performances are compared with the FCS-LSS benchmark. It is found that
the FCS-LSS offers the same performance as is achieved by SCA under initial
configurations adopted in Figs. 4.2e and 4.2f. We remark that under the
initial array configurations shown in Figs. 4.2a and 4.2b, the SCA-based
matrix completion even surpasses the FCS-LSS benchmark, however, it offers
slightly lower SINR for the hybrid design ($11.18$ dB as compared to $11.54$
dB). The optimum hybrid array configuration found through enumeration is shown
in Fig. 4.2i with an SINR of $11.9$ dB, whereas the worst case hybrid
configuration (shown in Fig. 4.2j) has an associated SINR of $7.5$ dB which is
considerably lower than the above designs.

####  4.5.2 Monte Carlo design for random scenarios

Figure 4.3: Average SINR performance of various sparse topologies against
desired source DOA for $T=100$ snapshots. Figure 4.4: Average SINR performance
of various sparse topologies against desired source DOA for $T=250$ snapshots.

The above examples tie the performance of the proposed algorithm not only to
the location of the sources and their respective powers but also show the
dependence on the initial array configuration, the number of snapshots and the
observed realization of the received data. In order to provide a more
meaningful assessment, the simulation scenarios are designed keeping the
aforementioned variables in perspective. We generate $11$ different scenarios.
For each scenario, the desired source DOA is kept fixed, whereas six jammers
are randomly placed anywhere from $30^{0}$ to $150^{0}$ with the respective
powers uniformly distributed from $5$ to $15$ dB. The experiments are repeated
$3000$ times and the initial array configuration is randomly chosen for each
experiment. For the freely designed array, the initial array configuration is
selected by randomly choosing $16$ sensors from $36$ sensors. However, the
initial configuration for the hybrid design is randomly chosen from all the
possible $16$ sensor fully augmentable array configurations associated with
the prefixed sensors arranged in nested configuration as depicted in Fig. 4.2b
(red color sensors).

Figure 4.3 shows the results for $T=100$. The performance curve of the SCA
algorithm for the freely designed array incorporating matrix completion lies
in between (for most points) the benchmark designs incorporating FCS-USS and
FCS-LSS. That is the matrix completion approach even outperforms the benchmark
design incorporating the FCS-LSS. This performance is explainable because
matrix completion coupled with the apriori knowledge of noise floor renders a
more accurate estimate of the full correlation matrix as compared to FCS-LSS,
without incorporating knowledge of noise floor, which has high noise variance
because of limited snapshots. The performance of the other benchmark
incorporating the exact knowledge of the correlation matrix (FCS-USS) is
clearly superior over matrix completion. The results are fairly similar for
the hybrid design, where the performance curve utilizing the Toeplitz
averaging is sandwiched between the benchmark designs incorporating the exact
correlation matrix (FCS-USS) and the one utilizing the presumably observed
full data correlation matrix (FCS-LSS). The hybrid designed and freely
designed arrays, both demonstrate desirable performances. However, the matrix
completion marginally outperforms the hybrid design with an average
performance gain of $0.2$ dB.

The performance curves are re-evaluated by increasing the snapshots to $T=250$
and $T=1000$, as shown in Figs. 4.4 and 4.5. With such increase, the
performances of the proposed SCA using Toeplitz completion move closer to the
performances of the FCS-USS benchmark. It is also noted that in contrast to
lower snapshots ($T=100$), the FCS-LSS benchmark for higher samples ($T=1000$)
offers superior average performance over SCA designs incorporating Toeplitz
completion. It is of interest to track the average antenna switching involved
per trial for both the free-design and the hybrid design. Fig. 4.6 shows that
freely designed array involves $9$ antenna switching per trial which is more
than twice that of the hybrid design ($4$ antenna switching per trial). It is
also noted that for the hybrid design, the maximum antenna switching is
constrained to $5$ antennas as the rest of $11$ sensors are prefixed. In this
regard, the hybrid design has more efficient switching as it utilizes 80
percent (4/5) of the DOF as compared to the mere 55 percent (9/16) switching
efficiency of freely designed arrays.

Figure 4.5: Average SINR performance of various sparse topologies against
desired source DOA for $T=1000$ snapshots. Figure 4.6: Sensor switching
comparison vs the free-design and the hybrid design.

###  4.6 Conclusion

Sparse array design for maximizing the beamformer output SINR is considered
for a single source in an interference active environment. The chapter
addressed the problem that the optimization of the array configuration
requires full data correlation matrix which is not readily available in
practice. Two different design approaches were considered; one assumes
prefixed position of subset of sensors so as to provide full array
augmentation, referred to as the hybrid-design approach, whereas the other,
which is referred to as free-design approach, has no such restriction, and
freely allocates all degrees of freedom to maximize the objective function. It
was shown that the Toeplitz estimation of the autocorrelation at the missing
spatial lags has a desirable performance. The SCA was proposed for both the
freely designed and hybrid designed arrays to achieve MaxSINR in polynomial
run times with a reasonable trade off in SINR. It was shown that, in contrast
to hybrid design, the matrix completion scheme does not require to pre-
allocate sensor resources and, therefore, offers more design flexibility and
better SINR performance. This performance improvement is, however, at the cost
of increased computational complexity and finer parameter tuning as required
to accomplish Toepltiz matrix completion. The simulation examples showed that
the performance of the proposed SCA algorithm incorporating Toeplitz
completion is agreeable with the established benchmark designs.

## Chapter 5Sparse Array Beamforming Design for Wideband Signal Models

###  5.1 Introduction

Wideband systems can deliver accurate target localization for radar systems
[80], provide diversity, reliability and anti jamming capabilities to the
wireless communication systems and signal enhancement for microphone arrays
[81, 45], whereas the UWB (Ultra-wideband) systems play a major role in high
resolution imagery in medical imaging [82, 83].

Beamforming techniques for wideband signals either involve a fixed design such
as a frequency invariant beamformer or an adaptive design based on the
linearly constrained minimum variance (LCMV) beamformer [84, 85]. Irrespective
of the design criterion, the wideband beamformers are typically implemented
jointly in the spatial and temporal domains, as shown in Fig. 5.1. This
spatio-temporal processing is often realized through two different schemes,
namely, the tapped delay line (TDL) filtering or subband processing like DFT.
For the former, an $L$ TDL filter is assumed for each sensor, and the received
data at each sampling instant is processed for all sensors jointly [86, 87].
In the DFT implementation scheme, the data at each sensor is buffered and
transformed to the frequency domain by $L$-point DFT. Once expressed in terms
of narrowband signals, optimal beamforming is performed in each DFT bin. The
DFT implementation is computationally more viable [88, 89, 90]. However, the
TDL implementation scheme has an added advantage since buffering is not
required and the spatio-temporal weight vector can be updated at each sampling
instant. The TDL and DFT beamformers would render identical output signal if
the corresponding beamformer weights are related through a DFT transformation.
However, carrying the beamformer design, separately in each domain, doesn’t
warrant the beamformer weights forming strictly a DFT pair. Resultantly, the
output could differ slightly for each implementation. To circumvent the
computationally expensive TDL beamformer design, a DFT beamformer is rather
optimized and the DFT transformation is subsequently used to obtain the TDL
beamformer. This dual domain TDL implementation designed primarily in the DFT
domain can yield adequate output performance in practice [91].

Sparse array design strives to optimally deploy sensors, essentially achieving
desirable beamforming characteristics, lowering the system hardware costs and
reducing the computational complexity. Sparse array design is known to yield
considerable performance advantages under different design criteria for
narrowband signal models. These criteria can largely be segregated into
environment-independent and environment-dependent designs. The minimum
redundancy arrays (MRA) and the structured sparse array configurations are
cases of the former design. They seek to optimize the environment-blind design
criterion to enable the DOA estimation of more sources than physical sensors
[9, 10, 8, 31]. More recently, the switched antenna and beam technologies have
motivated the design for environment adaptive sparse arrays. The available
sensors are switched according to changing environmental conditions, enabling
optimum use of expensive transceiver chains [92, 93, 94, 95]. Sparse array
design based on Cramer-Rao lower bound (CRLB) minimization criterion was shown
effective for DOA estimation schemes [96]. On the other hand, beamforming
approaches typically implements MaxSINR criterion, yielding efficient adaptive
performance that is dependent on the underlying operating environment [11, 12,
20, 97, 2, 13, 15].

Designing sparse arrays has proved to be particularly advantageous for
wideband signal models, as it circumvents the contradicting design
requirements posed by the frequency spread of the signal. On the one hand, the
lower frequency end of the spectrum puts a minimum aperture constraint on the
array to achieve certain resolution. On the other hand, the higher end of the
spectrum dictates the minimum separation between consecutive sensor locations
so as to avoid spatial aliasing, consequently, resulting in the oversampling
of the lower frequency content. For a limited number of available sensors,
wideband sparse array design can, in essence, yield improved performance in
many design applications by offering more control over beampattern
characteristics for all frequencies of interest [98, 99, 100, 101]. Many
different metrics, such as frequency invariant beampattern synthesis, robust
beampattern design and side-lobe level control have been proposed for optimal
wideband sparse array beamforming [102, 103, 100, 104, 105]. For instance,
simulated annealing has been applied in [104] to achieve the desired peak
sidelobe levels, while jointly optimizing the beamformer weights and sensor
locations. Frequency invariant beampattern optimization for wideband sparse
array design employing compressive sensing (CS) technique has been implemented
in [44]. The authors therein, invoked sparsity in the temporal and spatial
domains, simultaneously, in an attempt to decrease the overall processing
complexity.

In this chapter, we examine the Capon based MaxSINR sparse array design from
both the DFT and TDL filtering realization perspectives. We consider a
switched array adaptive beamformer design which is fundamentally different as
compared to the aforementioned wideband performance metrics that optimize a
prefixed receive beampattern for certain sector/frequencies of interest,
independent of the received data statistics. We examine environment-dependent
sparse arrays that maximize the SINR for frequency spread source operating in
wideband jamming environments. The objective of the populated and the sparse
wideband beamformers is fundamentally the same; minimization of noise and
interference signals at the array output while simultaneously maintaining a
desired response in the direction of interest. We adopt a Capon based
methodology for enhancing the signal power for the desired source operating in
an interference active environment. Capon method is a well known linear
constraint beamforming approach that rejects the interference and maximizes
the output SINR [106]. It provides superior estimation accuracy but assumes
the exact knowledge or estimated version of the received data correlation
matrix across the entire array aperture. The latter is the case in many key
applications in radar signal processing and medical imaging [46, 47, 68, 71,
107, 69]. This assumption, however, cannot be readily made for sparse array
configurations.

Figure 5.1: Block Diagram of sparse array wideband processing.

We pose the design problem as optimally selecting $P$ sensors out of $N$
possible equally spaced locations. For the scope of this chapter, we ignore
any mutual coupling or sensor failure possibilities that could arise due to
the closely spaced perspective locations on the grid. Each sensor has an
associated $L$ TDL or $L$ point DFT filtering to jointly process the signal in
the temporal and spatial domains. Our approach is a natural extension of Capon
beamforming at the receiver and amounts to maximizing the SINR over all
possible sparse array configurations. In the case of the TDL realization, we
select those sensors that maximize the principal eigenvalue of the product of
the inverse of received data correlation matrix and the desired source
correlation matrix [25]. For the DFT implementation scheme, the maximization
is performed over all DFT bins. In either case, it is an NP hard optimization
problem. In order to realize convex relaxation and avoid the computational
burden of applying the singular value decomposition (SVD) for each possible
configuration, we solve the underlying problem using constrained minimization
based approach. We consider two different optimization approaches, namely, the
semidefinite relaxation (SDR) and successive convex approximation (SCA). For
SDR-based approach, we pose the problem as quadratically constraint quadratic
program (QCQP) with weighted $l_{1-\infty}$-norm squared to promote group
sparsity. An eigenvector based iterative methodology is adopted to promote
group sparsity and ensure that only $P$ sensors are finally selected. It is
noted that the re-weighted $l_{1-\infty}$-norm squared relaxation is shown to
be effective for reducing the number of sensors in multicast transmit
beamforming [2]. However, owing to the computational complexity associated
with the SDR approach, we alternatively pose the problem as successive convex
relaxation (SCA) that approximates the problem iteratively by first order
gradient approximation [74]. The proposed algorithms are suitable for
moderate-size antenna systems to enable real time applications wherein the
environment largely stays stationary relative to the time required for sparse
configurability.

In order to enable a data-dependent design for sparse array wideband
beamforming, we require knowledge of the received data correlation matrix
corresponding to the full array aperture. With only few active sensors at any
time instant, it is infeasible to assume such knowledge due to missing
correlation entries. We circumvent this problem by employing a low rank block
Toeplitz matrix completion scheme to interpolate the missing correlation
entries. Subsequently, the interpolated data correlation matrix is input to
the proposed sparse optimization algorithms. We demonstrate the offerings of
the proposed sparse array design utilizing matrix completion under limited
data snapshots by comparing its performance with that achieved through
enumeration.

The rest of the chapter is organized as follows: In the next section, we state
the problem formulation for maximizing the output SINR under wideband source
signal model by elucidating the TDL and DFT signal model. Section 5.3 deals
with the optimum sparse array design by semidefinite relaxation as well as
successive convex relaxation to obtain the optimum $P$ sparse array geometry.
Section 5.4 discusses the block Toeplitz matrix completion approach for a
conceivable sparse array design from an implementation perspective. Design
examples and conclusion follow at the end.

###  5.2 Problem Formulation

Consider a single desired source and $Q$ interfering source signals impinging
on a linear array with $N$ uniformly placed sensors. The Nyquist sampled
received baseband signal $\mathbf{x}(n)\in\mathbb{C}^{N}$ at time instant $n$
is, therefore, given by,

$\mathbf{x}(n)=\mathbf{s}(n)+\sum_{k=1}^{Q}\mathbf{i}_{k}(n)+\mathbf{v}(n),$
(5.1)

where $\mathbf{s}(n)\in\mathbb{C}^{N}$ is the contribution from the desired
signal located at $\theta_{s}$, $\mathbf{i}_{k}(n)$ is the $k$th interfering
signal vectors corresponding to the respective direction of arrival,
$\theta_{k}$, and $\mathbf{v}(n)$ is the spatially uncorrelated sensor array
output noise.

Figure 5.2: TDL realization of wideband beamforming.

####  5.2.1 TDL Implementation scheme

We assume a TDL of length $L$ associated with each sensor, as shown in Fig.
5.2. The symbol z-1 denotes the time delay and w${}_{k}(m)$ is the beamforming
weight for the k$th$ sensor at m$th$ sampling instant. We define a stacked
vector
$\mathbf{X}=[\mathbf{x}^{T}(n),\mathbf{x}^{T}(n-1),...,\mathbf{x}^{T}(n-L+1)]^{T}\in\mathbb{C}^{NL}$
containing the array data collected over $L$ sampling instances ((.)T denotes
the transpose). Rewriting (5.1) in a compact way in terms of stacked vectors,
we obtain,

$\mathbf{X}=\mathbf{S}+\sum_{k=1}^{Q}\mathbf{I}_{k}+\mathbf{V}$ (5.2)

Here,
$\mathbf{S}=[\mathbf{s}^{T}(n),\mathbf{s}^{T}(n-1),...,\mathbf{s}^{T}(n-L+1)]^{T}$
and similarly $\mathbf{I}_{k}$ and $\mathbf{V}$ are defined, respectively, as
interference and noise stacked vectors. The received signal $\mathbf{X}$ is
then combined linearly to maximize the output SINR. The output signal $y(n)$
of the optimum beamformer for maximum SINR is given by [25],

$y(n)=\mathbf{w}_{o}^{H}\mathbf{X},$ (5.3)

where $\mathbf{w}_{o}$ is the solution of the following optimization problem,

$\displaystyle\underset{\mathbf{w}\in\mathbb{C}^{NL}}{\text{minimize}}$
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R}_{n}\mathbf{w}$ (5.4) s.t.
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R}_{s}\mathbf{w}=1$

The w${}_{k}(m)$ beamforming weight (shown in Fig. 2) maps to the $(N(m)+k)$th
element of the stacked beamformer $\mathbf{w}$ ($m\in 0,1,...,L-1$, $k\in
1,2,...,N$). Here, (.)H denotes Hermitian transpose,
$\mathbf{R}_{s}=E\mathbf{(SS}^{H})\in\mathbb{C}^{NL\times NL}$ is the desired
signal correlation matrix. Likewise, $\mathbf{R}_{n}$ is the correlation
matrix associated with interference and noise stacked vectors. In the case of
spatial spread or wideband source signal, the correlation matrix is given by
[86],

$\mathbf{R}_{s}=\int_{B_{s}}\int_{\Theta_{s}}\sigma^{2}_{\theta_{s}}(\omega)\mathbf{a}(\theta_{s},\omega)\mathbf{a}^{H}(\theta_{s},\omega)d\theta_{s}d\omega$
(5.5)

Here, $\sigma^{2}_{\theta_{s}}(\omega)$ is the signal power as a function of
$\theta_{s}$ and $\omega$, $\Theta_{s}$ and $B_{s}$ are the spatial and
spectral supports of the desired source signal. We only consider point sources
with no significant spatial extent, hence rewriting (5.5) as follows,

$\mathbf{R}_{s}=\int_{B_{s}}\sigma^{2}_{\theta_{s}}(\omega)\mathbf{a}(\theta_{s},\omega)\mathbf{a}^{H}(\theta_{s},\omega)d\omega$
(5.6)

The space-time steering vector
$\mathbf{a}(\theta_{s},\omega)\in\mathbb{C}^{NL}$, corresponding to the source
signal, can be represented as a Kronecker product ($\otimes$),

$\mathbf{a(\theta_{s},\omega)}=\boldsymbol{\phi}_{\omega}\otimes\mathbf{a}_{\theta_{s}}(\omega),$
(5.7)

with,

$\boldsymbol{\phi}_{\omega}=[1\,\,\,e^{j(\pi\omega/\omega_{max})}\,.\,.\,.\,e^{j(\pi\omega/\omega_{max})(L-1)}]^{T},$
(5.8) $\displaystyle\mathbf{a}_{\theta_{s}}(w)$
$\displaystyle=[1\,\,\,e^{j(2\pi/\lambda_{\omega})dcos(\theta_{s})}\,.\,.\,.\,e^{j(2\pi/\lambda_{\omega})d(N-1)cos(\theta_{s})}]^{T}$
(5.9)
$\displaystyle=[1\,\,\,e^{j\pi(\frac{\omega_{c}+\omega}{\Omega_{max}})cos(\theta_{s})}\,.\,.\,.\,e^{j\pi(\frac{\omega_{c}+\omega}{\Omega_{max}})(N-1)cos(\theta_{s})}]^{T},$

where $\lambda_{\omega}$ is the wavelength corresponding to
$\omega_{c}+\omega$, $\omega$ and $\omega_{c}$ represent the baseband source
angular frequency and the carrier angular frequency respectively, and
$\omega_{max}$ is the maximum source baseband angular frequency. The data is
sampled temporally at the Nyquist rate for a given signal bandwidth.
Similarly, we set the inter-element spacing $d=\lambda_{min}/2$ to avoid
spatial aliasing corresponding to the highest spatial angular frequency
$\Omega_{max}=\omega_{c}+\omega_{max}$, where $\lambda_{min}$ is the
wavelength corresponding to $\Omega_{max}$. The correlation matrix
$\mathbf{R}_{k}\in\mathbb{C}^{NL\times NL}$ for the interferer
$\mathbf{i}_{k}$ is defined according to (5.6) with respective to $\theta_{k}$
and $B_{k}$. The sensor noise correlation matrix,
$\mathbf{R}_{v}=\sigma_{v}^{2}\mathbf{I}\in\mathbb{C}^{NL\times NL}$ assumes
spatially and temporally uncorrelated noise $\mathbf{v}(n)$ with variance
$\sigma_{v}^{2}$. The problem in (5.4) can be written equivalently by
replacing $\mathbf{R}_{n}=\sum_{k=1}^{Q}\mathbf{R}_{k}+\mathbf{R}_{v}$ with
$\mathbf{R}=\mathbf{R}_{s}+\mathbf{R}_{n}$ as follows [25],

Figure 5.3: DFT implementation of wideband beamforming.

$\displaystyle\underset{\mathbf{w}\in\mathbb{C}^{NL}}{\text{minimize}}$
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R}\mathbf{w}$ (5.10) s.t.
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R}_{s}\mathbf{w}\geq 1$

The equality constraint is relaxed in (5.10) due to the inclusion of the
constraint autocorrelation matrix as part of the objective function, thereby
the optimal solution always converges at the equality constraint. The
analytical solution of the above optimization problem exists and is given by
$\mathbf{w}_{o}=\mathscr{P}\\{\mathbf{R}_{n}^{-1}\mathbf{R}_{s}\\}=\mathscr{P}\\{\mathbf{R}^{-1}\mathbf{R}_{s}\\}$.
The operator $\mathscr{P}\\{.\\}$ computes the principal eigenvector of it’s
argument. Substituting
$\mathbf{w}_{o}=\mathscr{P}\\{\mathbf{R}_{n}^{-1}\mathbf{R}_{s}\\}$ into the
SINR formula yields the corresponding optimum output $SINR_{o}$
($\Lambda_{max}$ denotes the maximum eigenvalue of the matrix);

$SINR_{o}=\frac{\mathbf{w}_{o}^{H}\mathbf{R}_{s}\mathbf{w}_{o}}{\mathbf{w}_{o}^{H}\mathbf{R}_{n}\mathbf{w}_{o}}=\Lambda_{max}\\{\mathbf{R}_{n}^{-1}\mathbf{R}_{s}\\},$
(5.11)

which shows that the optimum beamformer for maximizing SINR is directly
related to the desired and interference plus noise correlation matrices.

####  5.2.2 DFT Implementation scheme

Figure 5.3 shows the DFT implementation scheme of wideband array processing.
The received signal $\mathbf{x}(n)$ is processed in the spectral domain by
taking an $L$ point DFT for the data received by $k$th sensor ${x_{k}}(n)$,

${X}_{k}^{(l)}=\sum_{p=0}^{L-1}x_{k}(n-p)(e^{-j\frac{2\pi}{L}})^{lp},\,\,\,\,\,\,l\in\\{0,1,...,\,L-1\\}$
(5.12)

Define a vector ${\mathbf{X}}^{(l)}\in\mathbb{C}^{N}$, containing the $l$th
DFT bin data corresponding to each sensor (superscript (l) denotes the $l$th
DFT bin),

${\mathbf{X}}^{(l)}=[{X}_{1}^{(l)},{X}_{2}^{(l)},...,{X}_{N}^{(l)}]^{T}$
(5.13)

These samples are then combined linearly by the weight vector
$\mathbf{w}^{(l)}\in\mathbb{C}^{N}$ such that,

${y}^{(l)}={\mathbf{w}^{(l)}}^{H}\mathbf{X}^{(l)},\,\,\,\,\,\,l\in\\{0,1,...,\,L-1\\}$
(5.14)

Subsequently, the overall beamformer output $y$ is generated by taking the
inverse DFT of $y^{(l)}$ across the $L$ beamformers. The DFT implementation
scheme seeks to maximum the output SINR for each frequency bin, yielding the
optimum beamforming weight vector $\mathbf{w}_{o}^{(l)}$ as the solution of
the following optimization problem,

$\displaystyle\underset{\mathbf{w}^{(l)}\in\mathbb{C}^{N}}{\text{minimize}}$
$\displaystyle\quad\sum_{l=0}^{L-1}{\mathbf{w}^{(l)}}^{H}\mathbf{R}^{(l)}\mathbf{w}^{(l)}$
(5.15) s.t.
$\displaystyle\quad{\mathbf{w}^{(l)}}^{H}\mathbf{R}_{s}^{(l)}\mathbf{w}^{(l)}\geq
1.\quad l\in\\{0,1,...,\,L-1\\}$

The correlation matrix
$\mathbf{R}^{(l)}=\mathbf{X}^{(l)}{\mathbf{X}^{(l)}}^{H}$ is the received
correlation matrix for the $l$th processing bin. Similarly, the source
correlation matrix $\mathbf{R}_{s}^{(l)}$ for the desired source impinging
from direction of arrival $\theta_{s}$ is given by,

$\mathbf{R}_{s}^{(l)}=\mathbf{S}^{(l)}{\mathbf{S}^{(l)}}^{H}={\sigma_{s}^{(l)}}^{2}\mathbf{a}_{\theta_{s}}^{(l)}{\mathbf{a}_{\theta_{s}}^{(l)}}^{H}$
(5.16)

Here, $\mathbf{S}^{(l)}$ is the received data vector representing the desired
source and ${\sigma_{s}^{(l)}}^{2}$ denotes the power of this source in the
$l$th bin, $\mathbf{a}_{\theta_{s}}^{(l)}$ is the corresponding steering
vector for the source (DOA $\theta_{s}$) and is defined as follows,

$\displaystyle\mathbf{a}_{\theta_{s}}^{(l)}={}$
$\displaystyle[1\,\,\,e^{j\pi(\frac{\Omega_{min}+l\Delta_{\omega}}{\Omega_{max}})cos(\theta_{s})}{}$
(5.17)
$\displaystyle\,.\,.\,.\,\,\,\,\,\,\,e^{j\pi(\frac{\Omega_{min}+l\Delta_{\omega}}{\Omega_{max}})(N-1)cos(\theta_{s})}]^{T}$

Eq. (5.17) models the steering vector for the $l$th DFT bin, where
$\Omega_{min}$ is the lower edge of the passband and
$\Delta_{\omega}=\frac{2w_{max}}{L}$ is the spectral resolution. The overall
output SINR is given by averaging the SINR over all DFT bins. Similar to the
TDL, the DFT implementation scheme determines the optimum sparse array
geometry for enhanced MaxSINR performance as explained in the following
section.

###  5.3 Optimum sparse array design

The problem of maximizing the principal eigenvalue for the $P$ sensor
selection is a combinatorial optimization problem. In this section, we assume
that the full array data correlation matrix is known. However, Section 5.4
explains the means to avoid this assumption through fully augmentable sparse
array design or utilizing the matrix completion approach [108, 109, 72]. We
first formulate the sparse array design for maximizing SINR in the case of
wideband beamforming as an SDR. Owing to the high computational complexity of
SDR, the problem is solved by SCA, for both the TDL and DFT implementation
schemes.

####  5.3.1 Semidefinite relaxation (SDR) for sparse solution

##### TDL Implementation scheme

We assume that the sensor configuration remains the same within the
observation time. In radar, this assumption amounts to selecting the same $P$
sensors over the coherent processing interval (CPI). Therefore, the task is to
select $P$ entries from the first $N$ elements of $\mathbf{w}$, and the same
$P$ entries from each subsequent block of $N$ elements (there are $L$ such
blocks). Define
$\mathbf{w}_{k}=[\mathbf{w}(k),\mathbf{w}(k+N),\cdot\cdot\cdot,\mathbf{w}(k+N(L-1))]\in\mathbb{C}^{L}$
$(k\in\\{1,...,\,N\\})$ as the weights corresponding to TDL of $k$th sensor.
Then, in seeking sparse solution, the problem in (5.10) can be reformulated as
follows,

$\displaystyle\underset{\mathbf{w\in\mathbb{C}}^{NL}}{\text{minimize}}$
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R}\mathbf{w}+\bar{\mu}(\sum_{k=1}^{N}||\mathbf{w}_{k}||_{q})$
(5.18) s.t. $\displaystyle\quad\mathbf{w}^{H}\mathbf{R}_{s}\mathbf{w}\geq 1$

Here, $||.||_{q}$ denotes the $q$-norm of the vector, $\bar{\mu}$ is the
sparsity regularization parameter. The mixed $l_{1-q}$ norm regularization is
known to thrive the group sparsity in the solution. In so doing, the above
formulation enables the decision making on whether to collectively select or
discard all the $L$ sampling instances associated with the $k$th sensor.
Therefore, structured group sparsity is essential for wideband beamformer,
since the final sparse solution has to ensure that only $PL$ out of $NL$
spatio-temporal possible sampling instances are chosen through only $P$
physical sensors. The relaxed problem expressed in the above equation induces
group sparsity in the optimal weight vector without placing a hard constraint
on the desired cardinality. The constrained minimization in $(\ref{a2_ch5})$
can be penalized instead by the weighted $l_{1}$-norm function to further
promote sparse solutions [41, 42, 58],

$\displaystyle\underset{\mathbf{w\in\mathbb{C}}^{NL}}{\text{minimize}}$
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R}\mathbf{w}+\bar{\mu}(\sum_{k=1}^{N}\mathbf{u}^{i}(k)||\mathbf{w}_{k}||_{q})$
(5.19) s.t. $\displaystyle\quad\mathbf{w}^{H}\mathbf{R}_{s}\mathbf{w}\geq 1,$

where, $\mathbf{u}^{i}(k)$ is the $k$th element of re-weighting vector
$\mathbf{u}^{i}$ at the $i$th iteration. We choose the $\infty$-norm for the
$q$-norm and replace the weighted $l_{1}$-norm function in $(\ref{b2_ch5})$ by
the $l_{1}$-norm squared function with a modified regularization parameter
($\mu$ instead of $\bar{\mu}$). This change does not affect the regularization
property of the $l_{1}$-norm [2]. The result is,

$\displaystyle\underset{\mathbf{w\in\mathbb{C}}^{NL}}{\text{minimize}}$
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R}\mathbf{w}+\mu(\sum_{k=1}^{N}\mathbf{u}^{i}(k)||\mathbf{w}_{k}||_{\infty})^{2}$
(5.20) s.t. $\displaystyle\quad\mathbf{w}^{H}\mathbf{R}_{s}\mathbf{w}\geq 1$

The SDR of the above problem is realized by substituting
$\mathbf{W}=\mathbf{w}\mathbf{w}^{H}$. The quadratic function,
$\mathbf{w}^{H}\mathbf{R}\mathbf{w}=$
Tr$(\mathbf{w}^{H}\mathbf{R}\mathbf{w})=$Tr$(\mathbf{R}\mathbf{w}\mathbf{w}^{H})=$
Tr$(\mathbf{R}\mathbf{W})$, where Tr(.) is the trace of the matrix. Similarly,
we replace the regularization term in (5.20) by
Tr$(\mathbf{U}^{i}\mathbf{\tilde{W}})$, with
$\mathbf{U}^{i}=\mathbf{u}^{i}(\mathbf{u}^{i})^{T}$ and $\mathbf{\tilde{W}}$
being the auxiliary matrix implementing $\infty-$norm as follows [59, 61, 2],

$\displaystyle\underset{\mathbf{W\in\mathbb{C}}^{NL\times
NL},\mathbf{\tilde{W}\in\mathbb{R}}^{N\times N}}{\text{minimize}}$
$\displaystyle\quad\text{Tr}(\mathbf{R}\mathbf{W})+\mu\text{Tr}(\mathbf{U}^{i}\mathbf{\tilde{W}})$
(5.21) s.t. $\displaystyle\quad\text{Tr}(\mathbf{R}_{s}\mathbf{W})\geq 1,$
$\displaystyle\quad\mathbf{\tilde{W}}\geq|\mathbf{W}_{ll}|,\quad
l\in\\{0,...,\,L-1\\},$ $\displaystyle\quad\mathbf{W}\succeq
0,\,\text{Rank}(\mathbf{W})=1$

Table 5.1: SDR for the sparse wideband beamformer

0: Sparse correlation matrices $\overset{\circ}{\mathbf{R}}$ for TDL-SDR
($\overset{\circ}{\mathbf{R}}{{}^{(l)}}$ for DFT-SDR), $N$, $P$, $L$,
${\mathbf{R}_{s}}$ for TDL-SDR (${\mathbf{R}_{s}^{(l)}}$ for DFT-SDR).

0: MaxSINR beamformer against $P$ active sensors. Matrix Completion: Procedure
in Section 5.4 is adopted to recover the estimated full data received
correlation matrix $\mathbf{\hat{R}}$ for TDL-SDR ($\mathbf{\hat{R}}^{(l)}$
for DFT-SDR).Initialization: Initialize $\epsilon$, $\mu_{max}$ (upper limit
of binary search), $\mu_{min}$ (lower limit of binary search), $\mathbf{U}=$
all ones matrix. Appropriate value of $\mu$ is selected through the binary
search to ensure $P$ sensor selection.

while (Beamforming weight vector is not $P$ sparse) do

Select $\mu=\frac{1}{2}(\mu_{max}+\mu_{min})$ (Binary search).

Run the SDR of (5.3.1) for TDL-SDR or (5.3.1) for DFT-SDR (Use either
$\mathbf{\hat{R}}$,$\mathbf{\hat{R}}^{(l)}$ in-lieu of
$\mathbf{{R}}$,$\mathbf{{R}}^{(l)}$).

Update $\mathbf{U}^{i}$ according to (5.25). Update $\mu_{max}/\mu_{min}$
according to the binary search.

end while

After achieving the desired cardinality, run SDR for reduced size correlation
matrix corresponding to nonzero values of $\mathbf{\tilde{W}}$ and $\mu=0$,
yielding, $\mathbf{w}_{o}=\mathscr{P}\\{\mathbf{W}\\}$ for TDL-SDR
($\mathbf{w}_{o}^{(l)}=\mathscr{P}\\{\mathbf{W}^{(l)}\\}$ for DFT-SDR).

return Optimal Beamformer $\mathbf{w}_{o}$-TDL-SDR
($\mathbf{w}_{o}^{(l)}$-DFT-SDR)

The operator ‘$|.|$’ returns the element wise absolute values of the entries
of the matrix, ‘$\geq$’ is the element wise comparison and ‘$\succeq$’
represents the generalized matrix inequality, implementing the positive
semidefinite constraint, $\mathbf{W}_{ll}\in\mathbb{C}^{N\times N}$ is the
$l$th diagonal block matrix of $\mathbf{W}$. We note that the solution matrix
$\mathbf{W}$ is Hermitian and therefore, it is sufficient to constrain the
upper or lower triangular entries of $\mathbf{W}_{ll}$ while forcing
$\mathbf{\tilde{W}}$ to be symmetric matrix. In so doing, we reduce the
inequality constraints and decrease the run time substantially. In addition,
we drop rank constraint in (5.21) which is non convex, resulting in the
following SDR,

$\displaystyle\underset{\mathbf{W\in\mathbb{C}}^{NL\times
NL},\mathbf{\tilde{W}\in\mathbb{R}}^{N\times N}}{\text{minimize}}$
$\displaystyle\quad\text{Tr}(\mathbf{R}\mathbf{W})+\mu\text{Tr}(\mathbf{U}^{i}\mathbf{\tilde{W}}),$
s.t. $\displaystyle\quad\text{Tr}(\mathbf{R}_{s}\mathbf{W})\geq 1,$
$\displaystyle\quad\overset{\bigtriangleup}{\mathbf{\tilde{W}}}\geq|\overset{\bigtriangleup}{\mathbf{W}}_{ll}|,\quad
l\in\\{0,1,...,\,L-1\\},$
$\displaystyle\quad\mathbf{\tilde{W}}=\mathbf{\tilde{W}}^{T},\quad\mathbf{W}\succeq
0.$ (5.22)

Here, △ represents the upper or lower triangular entries of the matrix.

##### DFT Implementation scheme

The DFT implementation scheme for sparse array design is achieved by starting
from (5.15) and following similar steps of the TDL. The group sparsity is
invoked as the data in each DFT bin requires the underlying array
configuration to remain the same for processing over all DFT bins. The SDR is
finally realized as follows,

$\displaystyle\underset{\mathbf{W}^{(l)}\mathbf{\in\mathbb{C}}^{N\times
N},\mathbf{\tilde{W}\in\mathbb{R}}^{N\times N}}{\text{minimize}}$
$\displaystyle\sum_{l=0}^{L-1}\text{Tr}(\mathbf{R}^{(l)}\mathbf{W}^{(l)})+\mu\text{Tr}(\mathbf{U}^{i}\mathbf{\tilde{W}})$
s.t. $\displaystyle\,\,\text{Tr}(\mathbf{R}_{s}^{(l)}\mathbf{W}^{(l)})\geq
1,\,\,l\in\\{0,1,...,\,L-1\\},$
$\displaystyle\,\,\overset{\bigtriangleup}{\mathbf{\tilde{W}}}{{}^{(l)}}\geq|\overset{\bigtriangleup}{\mathbf{W}}{{}^{(l)}}|,\quad
l\in\\{0,1,...,\,L-1\\},$
$\displaystyle\,\,\mathbf{\tilde{W}}=\mathbf{\tilde{W}}^{T},\quad\mathbf{W}\succeq
0.$ (5.23)

In general, QCQP of order $M$ with $T$ quadratic constraints can be solved to
an arbitrary small accuracy $\zeta$ by employing interior point methods
involving the worst case complexity of
$\mathcal{O}\\{$max$(T,M)^{4}M^{(1/2)}\log(1/\zeta)\\}$ [61]. It is apparent
from (5.3.1) and (5.3.1) that the dimensionality of the TDL implementation
scheme is $NL\times NL$, whereas that for the DFT approach involves $L$
unknown variables of size $N\times N$. Therefore, the computational complexity
for TDL implementation scheme is $\mathcal{O}\\{(NL)^{9}\log(1/\zeta)\\}$, and
is $\mathcal{O}\\{(N^{9}L^{(9/2)})\log(1/\zeta)\\}$ for the DFT implementation
scheme, which renders the DFT implementation scheme computationally more
viable.

##### Unit rank promoting iteration

Promoting sparse solutions iteratively would depend on careful selection of
the regularization weighting matrix at each iteration. As suggested in [58,
2], the weighting matrix $\mathbf{U}^{i}$ in (5.3.1) and (5.3.1) is
initialized unweighted, i.e., a matrix of all ones. Afterwards, this matrix is
iteratively updated in an inverse relationship to $\mathbf{\tilde{W}}$, which
is related to the solution matrix $\mathbf{W}$ from the previous iteration.
This enables the beamforming weights having relatively lower magnitude to be
penalized aggressively, hence encouraging them to go to zero in an iterative
fashion. The parameter $\epsilon$ prevents the unwanted case of division by
zero and also avoids the solution to converge to local minima as follows,

$\mathbf{U}^{i+1}(m,n)=\frac{1}{\mathbf{\tilde{W}}^{i}(m,n)+\epsilon}$ (5.24)

However, the solution matrix $\mathbf{W}$ in the case of the TDL
implementation scheme is not exactly rank one at initial iterations. The
problem aggravates when the weight matrix is updated according to the above
equation, inadvertently pushing the rank of $\mathbf{W}$ to build up with each
iteration. In this respect, updating $\mathbf{U}$ according to (5.24) favors
solutions of higher ranks, and, as such, fails to yield sparse configurations
iteratively. To mitigate this problem, we propose a modified re-weighting
scheme that relies on updating the regularization weighting matrix that
depends on the inverse of a rank $1$ matrix $\mathbf{Y}$ instead of
$\mathbf{\tilde{W}}$ as follows,

$\mathbf{U}^{i+1}(m,n)=\frac{1}{\mathbf{Y}^{i}(m,n)+\epsilon},$ (5.25)

where, $\mathbf{Y}^{i}=\mathbf{y}^{i}(\mathbf{y}^{i})^{T},$ for
$\mathbf{y}^{i}=\frac{1}{L}\sum_{l=1}^{L}(\mathbf{|\mathscr{P}\\{W}_{ll}^{i}\\}|)^{2}$.
Clearly, $\mathbf{Y}^{i}$ is a rank one matrix that is synthesized from the
rank one approximation of each block diagonal matrix $\mathbf{{W}}_{ll}^{i}$.
It is noted that $\mathbf{{W}}_{ll}^{i}$ are the only entries of
$\mathbf{{W}}$ that are constrained by the SDR formulated in (5.3.1). Since
$\mathbf{{W}}_{ll}^{i}$ are the diagonal block matrices of the solution matrix
$\mathbf{{W}}$, then sparsity is implicitly encouraged in $\mathbf{{W}}$ by
unit rank penalization. This modified re-weighting approach given by (5.25)
effectively solves the optimum sparse array selection problem for the wideband
beamforming. It is noted that the arbitrarily chosen sparsity parameter $\mu$
does not ensure the final solution to be exactly $P$ sparse. In order to do
so, the optimization problem should be solved against various values of $\mu$.
This is typically achieved by successively running the optimization and
updating the values of $\mu$ through a binary search over the possible upper
and lower limit of $\mu_{max}/\mu_{min}$, until the solution converges to $P$
sensors [2]. The proposed algorithm for achieving the sparse optimal weight
vector under the TDL and DFT implementation schemes is summarized in Table
5.1.

Table 5.2: SCA for the sparse wideband beamformer

0: Sparse correlation matrices $\overset{\circ}{\mathbf{R}}$ for TDL-SCA
($\overset{\circ}{\mathbf{R}}{{}^{(l)}}$ for DFT-SCA), $N$, $P$, $L$,
${\mathbf{R}_{s}}$ for TDL-SCA (${\mathbf{R}_{s}^{(l)}}$ for DFT-SCA).

0: MaxSINR beamformer against $P$ active sensors. Matrix Completion: Procedure
in Section 5.4 is adopted to recover the estimated full data received
correlation matrix $\mathbf{\hat{R}}$ for TDL-SCA ($\mathbf{\hat{R}}^{(l)}$
for DFT-SCA).Initialization: Initialize the beamforming vectors randomly to
find $\mathbf{m}$ and $b$. Initialize $\epsilon$, $\mu_{max}$ (upper limit of
binary search), $\mu_{min}$ (lower limit of binary search), $\mu=0$.

while (Solution does not converge corresponding to $\mu=0$) do

Run (5.31) for TDL-SCA or (5.32) for DFT-SCA.

end whileInitialize $\mathbf{u}^{i}$= all ones vector.

while (Beamforming weight vector is not $P$ sparse) do

Select $\mu=\frac{1}{2}(\mu_{max}+\mu_{min})$ (Binary search).

Run (5.31) for TDL-SCA or (5.32) for DFT-SCA (Use $\mathbf{\hat{R}}$ or
$\mathbf{\hat{R}}^{(l)}$ in-lieu of $\mathbf{{R}}$,$\mathbf{{R}}^{(l)}$ to
synthesize $\mathbf{\tilde{R}}$, $\mathbf{\tilde{R}}^{(l)}$).(Also use the
optimal non sparse solution from the previous while loop for $\mathbf{m}$ and
$b$).

Update the regularization weighting parameter
$\mathbf{u}^{i+1}(k)=\frac{1}{||\mathbf{\tilde{w}}_{k}^{i}||_{2}+\epsilon}$.Update
$\mu_{max}/\mu_{min}$ according to the binary search.

end while

After achieving the desired cardinality, run (5.31) for TDL-SCA or (5.32) for
DFT-SCA, with reduced dimension corresponding to nonzero values of
$\mathbf{\tilde{w}}$ and $\mu=0$, yielding, optimal weight vector.

return Optimal Beamformer $\mathbf{w}_{o}$-TDL-SCA
($\mathbf{w}_{o}^{(l)}$-DFT-SCA)

####  5.3.2 Successive convex approximation (SCA)

##### TDL Implementation scheme

The problem in (5.10) can equivalently be rewritten by swapping the objective
and constraint functions as follows,

$\displaystyle\underset{\mathbf{w\in\mathbb{C}}^{NL}}{\text{maximize}}$
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R}_{s}\mathbf{w}$ (5.26) s.t.
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R}\mathbf{w}\leq 1$

Although this swapping operation allows the associated constraint to be
convex, however it renders the objective function non convex. We note that the
formulation in (5.26) doesn’t have a trivial solution $\mathbf{w}=0$, as the
objective and constraint are coupled due to $\mathbf{R}_{s}$ being part of
$\mathbf{R}$. The maximization of the convex function is replaced by the
minimization of the concave function. The transformation to the minimization
problem will later enable carrying out the minimization based on $P$ sparse
solution. Rewriting (5.26) by reversing the sign of the desired source
correlation matrix $\bar{\mathbf{R}}_{s}=-\mathbf{R}_{s}$ as follows,

$\displaystyle\underset{\mathbf{w\in\mathbb{C}}^{NL}}{\text{minimize}}$
$\displaystyle\quad\mathbf{w}^{H}\bar{\mathbf{R}}_{s}\mathbf{w}$ (5.27) s.t.
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R}\mathbf{w}\leq 1$

The beamforming weight vectors are generally complexed valued, whereas the
quadratic functions are real. This observation allows expressing the problem
with only real variables and is typically accomplished by replacing the
correlation matrix $\bar{\mathbf{R}}_{s}$ by $\tilde{\mathbf{R}}_{s}$ and
concatenating the beamforming weight vector accordingly [74],

$\quad\quad\quad\quad\quad\tilde{\mathbf{R}}_{s}=\begin{bmatrix}\text{real}(\bar{\mathbf{R}}_{s})&-\text{imag}(\bar{\mathbf{R}}_{s})\\\
\\\ \text{imag}(\bar{\mathbf{R}}_{s})&\text{real}(\bar{\mathbf{R}}_{s})\\\
\end{bmatrix},\quad\quad\quad\quad\quad\quad\tilde{\mathbf{w}}=\begin{bmatrix}\text{real}({\mathbf{w}})\\\
\\\ \text{imag}({\mathbf{w}})\\\ \end{bmatrix}$ (5.28)

Similarly, the received data correlation matrix $\mathbf{R}$ is replaced by
$\tilde{\mathbf{R}}$. The problem in (5.27) then becomes,

$\displaystyle\underset{\mathbf{\tilde{w}\in\mathbb{R}}^{2NL}}{\text{minimize}}$
$\displaystyle\quad\mathbf{\tilde{w}}^{T}\tilde{\mathbf{R}}_{s}\mathbf{\tilde{w}}$
(5.29) s.t.
$\displaystyle\quad\mathbf{\tilde{w}}^{T}\mathbf{\tilde{R}}\mathbf{\tilde{w}}\leq
1$

We can then proceed to convexify the objective function by utilizing the first
order approximation iteratively,

$\displaystyle\underset{\mathbf{\tilde{w}\in\mathbb{R}}^{2NL}}{\text{minimize}}$
$\displaystyle\quad{\mathbf{m}^{i}}^{T}\mathbf{\tilde{w}}+b^{i}$ (5.30) s.t.
$\displaystyle\quad\mathbf{\tilde{w}}^{T}\mathbf{\tilde{R}}\mathbf{\tilde{w}}\leq
1,$

The linearization coefficients $\mathbf{m}^{i}$ and ${b^{i}}$ are updated as,
$\mathbf{m}^{i+1}=2\tilde{\mathbf{R}}_{s}\mathbf{\tilde{w}}^{i}$, and
$b^{i+1}=-{{\mathbf{\tilde{w}}^{i}}}^{T}\tilde{\mathbf{R}}_{s}\mathbf{\tilde{w}}^{i}$
(superscript i denotes the iteration number). Finally, to invoke sparsity in
the beamforming weight vector, the re-weighted mixed $l_{1-2}$ norm is adopted
primarily for promoting group sparsity,

$\displaystyle\underset{\mathbf{\tilde{w}\in\mathbb{R}}^{2NL}}{\text{minimize}}$
$\displaystyle\quad{\mathbf{m}^{i}}^{T}\mathbf{\tilde{w}}+b^{i}+\mu(\sum_{k=1}^{N}\mathbf{u}^{i}(k)||\mathbf{\tilde{w}}_{k}||_{2})$
(5.31) s.t.
$\displaystyle\quad\mathbf{\tilde{w}}^{T}\mathbf{\tilde{R}}\mathbf{\tilde{w}}\leq
1$

Here, $\mathbf{\tilde{w}}_{k}\in\mathbb{R}^{2L}$ are the beamforming weights
corresponding to TDL of $k$th sensor. Discouraging a sensor ($||.||_{2}$
denotes the $l_{2}$ norm) implies a simultaneous removal of both the real and
corresponding imaginary entries of all beamforming weights associated with the
removed sensor [74].

##### DFT implementation scheme

The above formulation can be extended for the DFT implementation scheme as
follows:

$\displaystyle\underset{\mathbf{\tilde{w}}^{(l)}\mathbf{\in\mathbb{R}}^{2N}}{\text{minimize}}$
$\displaystyle\sum_{l=0}^{L-1}({{\\{\mathbf{m}^{(l)}}\\}^{i}}^{T}\mathbf{\tilde{w}}^{(l)}+\\{b^{(l)}\\}^{i})+\mu(\sum_{k=1}^{N}\mathbf{u}^{i}(k)||\mathbf{\tilde{w}}_{k}||_{2})$
(5.32) s.t.
$\displaystyle\quad{\mathbf{\tilde{w}}^{(l)}}^{T}\mathbf{\tilde{R}}^{(l)}\mathbf{\tilde{w}}^{(l)}\leq
1,\quad l\in\,\,\\{0,1,...L-1\\},$

where $\mathbf{\tilde{w}}_{k}\in R^{2L}$ contains the $L$ DFT bins data for
the $k$th sensor, $\\{{\mathbf{m}^{(l)}}\\}{{}^{i}}$ and
$\\{{b^{(l)}\\}{{}^{i}}}$ are the approximation coefficients at the $i$th
iteration for the desired source correlation matrix in the $l$th bin, with
$\\{{\mathbf{m}^{(l)}}\\}{{}^{i}}=2\tilde{\mathbf{R}}_{s}^{(l)}\\{{\mathbf{\tilde{w}}^{(l)}}\\}{{}^{i}},\\{{b^{(l)}\\}{{}^{i}}}=-{\\{\mathbf{\tilde{w}}^{(l)}\\}^{i}}^{T}\tilde{\mathbf{R}}_{s}^{(l)}\\{\mathbf{\tilde{w}}^{(l)}\\}^{i}$.
The initial estimates $\\{{\mathbf{m}^{(l)}}\\}{{}^{i}}$ and
$\\{{b^{(l)}\\}{{}^{i}}}$ are calculated for the optimal non sparse solution.
These parameters can be found by setting the sparsity parameter $\mu$ to zero.
In so doing, the solution and the corresponding parameters
$\\{{\mathbf{m}^{(l)}}\\}{{}^{i}}$ and $\\{{b^{(l)}\\}{{}^{i}}}$ converge to
the optimal value against the full array elements. Using these values as
initial conditions has proven appropriate in our design for recovering
effective sparse solutions. The sparsity parameter $\mu$ is chosen according
to the binary search over the possible range of $\mu$ to warrant the desired
cardinality of the beamforming weight vector as explained before in section
5.3.1. The $k$th entry of re-weighting vector $\mathbf{u}^{i}(k)$ is updated
according to
$\mathbf{u}^{i+1}(k)=\frac{1}{||\mathbf{\tilde{w}}_{k}^{i}||_{2}+\epsilon}$.
The computational complexity involving SCA is considerably lower as compared
to the SDR formulation, as the latter intrinsically squares the number of
variables involved, essentially exacerbating the runtime [74]. The SCA for
sparse array design for wideband beamforming is summarized in Table 5.2.

###  5.4 Sparse matrix completion of block Toeplitz matrices

The aforementioned sparse array design formulations require the received data
correlation matrix corresponding to the full array aperture. This is a rather
stringent requirement in an adaptive switching environment where the data is
fetched from only $P$ active sensor locations over a given observation period.
The received data correlation matrix for the sparse array design using TDL
implementation scheme has $L^{2}$($N^{2}-P^{2}$) missing correlation entries,
whereas there are $L$($N^{2}-P^{2}$) missing correlation values for the DFT
implementation scheme. Clearly, for the large values of $L$, the TDL
implementation scheme has significantly higher number of missing correlation
entries as compared to the DFT implementation scheme.

Recently, the hybrid sparse design for the narrowband beamforming was
introduced to alleviate the issue of missing correlation lags in the received
data correlation matrix [71]. This is primarily achieved by pre-allocating few
sensors to guarantee a fully augmentable sparse array, while engaging the
remaining degrees of freedom (DOF) to maximize the SINR. However, locking in
few DOFs to ensure the array full augmentability can lead to suboptimal sparse
beamformers. Alternatively, the matrix completion approach can be used to
provide the missing lags [50, 49, 78]. We propose, herein, sparse matrix
completion to efficiently exploit the structure of the data correlation matrix
to recover the missing correlation values. The received data correlation
matrix for the TDL implementation scheme is a Hermitian positive definite
matrix but it also follows a block Toeplitz formation, as shown below,

$\quad\quad\quad\quad\quad\quad\mathbf{R}=\begin{bmatrix}\mathbb{T}_{0}&{\mathbb{T}}_{1}&{\mathbb{T}}_{2}&\ldots&{\mathbb{T}}_{L-1}\\\
\\\
\mathbb{T}_{-1}&{\mathbb{T}}_{0}&{\mathbb{T}}_{1}&\ldots&{\mathbb{T}}_{L-2}\\\
\\\
{\mathbb{T}}_{-2}&{\mathbb{T}}_{-1}&{\mathbb{T}}_{0}&\ldots&{\mathbb{T}}_{L-3}\\\
\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\ \\\
{\mathbb{T}}_{-(L-1)}&{\mathbb{T}}_{-(L-2)}&{\mathbb{T}}_{-(L-3)}&\ldots&{\mathbb{T}}_{0}\\\
\end{bmatrix}\quad\quad\quad\quad\quad\quad$ (5.33)

By definition, block Toeplitz matrices doesn’t necessitate each comprising
block to be Toeplitz within itself. Therefore, matrix $\mathbf{R}$ in (5.33)
represents a special case of block Toeplitz matrices, where the Toeplitz
structure is also preserved for each constituent block
$\mathbb{T}_{k}\in\mathbb{C}^{N\times N}$. Because of the matrix Hermitian
symmetry, we also have
$\mathbb{T}_{k}^{H}=\mathbb{T}_{-k}(\text{for}\,\,\,k\neq 0$). Instead of
recovering $\mathbf{R}$ as a single unit, we focus on completing the
constituent blocks and then synthesizing the full correlation matrix
$\mathbf{R}$. This approach potentially caps the computational expenses
considerably but also efficiently exploits the formation of $\mathbf{R}$.

There is an important distinction between the constituent blocks
$\mathbb{T}_{0}$ and $\mathbb{T}_{k}\,\,\,(\text{for}\,\,\,k\neq 0$). It is
noted that $\mathbb{T}_{0}$ is positive definite Hermitian Toeplitz matrix,
whereas $\mathbb{T}_{k}$ $\,\,\,(\text{for}\,\,\,k\neq 0$) are indefinite
Toeplitz matrices which are not necessarily Hermitian. Therefore, we resort to
two different ways with regards to our treatment of $\mathbb{T}_{0}$ and
$\mathbb{T}_{k}$ while adopting a Toepltiz matrix completion scheme under the
low rank assumption. It is known that the correlation matrix $\mathbf{R}$ for
the wideband far field sources impinging on the ULA resultantly follows the
structure in (5.33) and can be represented effectively with a relatively low
rank approximation depending on the observed source time-bandwidth product
[90]. The trace heuristic is a well known approach which is adopted generally
as a convex surrogate in recovering low rank matrices. This approach has been
successfully used in many areas of control systems and array processing to
recover simpler and low rank data models [62, 63, 61]. Moreover, it has been
shown that the trace heuristic is equivalent to the nuclear norm minimization
in recovering positive semidefinite correlation matrices[75, 77, 78, 79]. The
low rank positive semidefinite Toeplitz matrix completion problem has been
proposed in [76] for interpolating missing correlation lags in coprime array
configuration and can be adopted to interpolate $\mathbb{T}_{0}$ as follows,

$\displaystyle\underset{l\in\mathbb{C}^{N}}{\text{minimize}}$
$\displaystyle\quad||\mathcal{T}(l)\odot\mathbf{Z}-\overset{\circ}{\mathbb{T}}_{0}||_{F}^{2}+\zeta\text{Tr}(\mathcal{T}(l))$
(5.34) s.t. $\displaystyle\quad\mathcal{T}(l)\succeq 0$

Here, the unknown Hermitian Toeplitz matrix $\mathcal{T}(l)$, can uniquely be
defined by a single vector $l$ representing the first row of $\mathcal{T}(l)$,
and $l^{H}$ denoting the matrix first column. Matrix
$\overset{\circ}{\mathbb{T}}_{0}$ is the received data correlation matrix with
the missing correlation values set equal to zero. The element wise product is
denoted by symbol ‘$\odot$’ and ‘$\succeq$’ implements the positive
semidefinite constraint. The objective function attempts to minimize the error
between the observed correlation values and the corresponding entries of
$\mathcal{T}(l)$ implemented through the Frobenius norm of the error matrix
(The function ‘$||.||_{F}^{2}$’, represents the square of the Frobenius norm
of matrix which returns the sum of square of it’s entries). The parameter
‘$\zeta$’ pursues the trade off between the denoising term and the trace
heuristic to recover a simpler low rank model. The nominal value of the
parameter ‘$\zeta$’ is challenging to locate and is typically gleaned from the
numerical experience. In order to do away with the nuisance parameter
‘$\zeta$’, we adopt a fusion based approach more suited to our application. We
note that the non zero elements in $\overset{\circ}{\mathbb{T}}_{0}$ can be
segregated into two classes. With regards to the sparse entries in
$\overset{\circ}{\mathbb{T}}_{0}$, either we have the whole sub-diagonal
entries missing in $\overset{\circ}{\mathbb{T}}_{0}$ or the sub-diagonals are
sparse. The former situation arises if there is missing correlation lag in
$\overset{\circ}{\mathbb{T}}_{0}$, whereas the latter arises when the
corresponding correlation lag is present but lacking the intrinsic redundancy
corresponding to the compact sensor grid. The observed correlation lags are
averaged across the sub diagonal to filter the sensor noise as follows,

$\hat{\vphantom{\rule{1.0pt}{5.71527pt}}\smash{\hat{l}}}^{i}(k)=(\frac{1}{c_{k}})\sum_{\forall\,m-n=k}\overset{\circ}{\mathbb{T}}^{i}_{0}(m,n)$
(5.35)

Here, $\overset{\circ}{\mathbb{T}}^{i}_{0}$ is the $\mathbf{R}(i,i)$ entry in
(5.33) denoting the estimate of $\overset{\circ}{\mathbb{T}}^{i}_{0}$ at $i$th
sampling instance, $k\in 0,1,\cdots,N-1$ represents the respective lag or the
sub diagonal of $\overset{\circ}{\mathbb{T}}^{i}_{0}$ and $c_{k}$ is the
observed redundancy of the $k$th lag. As evident in (5.33), there are $L$
copies of $\overset{\circ}{\mathbb{T}}_{0}$ corresponding to $L$ sampling
instances. Hence,
$\hat{\vphantom{\rule{1.0pt}{5.71527pt}}\smash{\hat{l}}}^{i}(k)$ is averaged
over $L$ blocks to yield an estimate of the given lag
$\hat{l}(k)=\frac{1}{L}\sum_{i=0}^{L-1}\hat{\vphantom{\rule{1.0pt}{5.71527pt}}\smash{\hat{l}}}^{i}(k)$.
The fused matrix completion formulation, therefore, substitutes the sparse
sub-diagonals with the estimated average value $\hat{l}(k)$, whereas the
completely missing sub-diagonals are interpolated as follows,

$\displaystyle\underset{l\in\mathbb{C}^{N}}{\text{minimize}}$
$\displaystyle\quad\text{Tr}(\mathcal{T}(l))$ (5.36) s.t. $\displaystyle\quad
l(\text{lag present})=\hat{l}(k),$ $\displaystyle\quad\mathcal{T}(l)\succeq 0$

The above formulation relies on fairly accurate estimate of the observed
correlation lag which not only involves averaging over the corresponding sub
diagonal but also across $L$ sampling instances. Such accuracy can become
challenging to meet the semidefinite constraint if the available degrees of
freedom are few. To circumvent this problem, the $0$ lag is removed from the
constraint which gives the additional degree of freedom to the algorithm to
set aside an appropriate loading factor to make the problem feasible. It is
noted that the formulation in (5.36) would choose the minimum possible
diagonal loading as it requires to minimize the trace heuristic and hence
strives to maximize the sparse eigenvalues.

The trace heuristic can also be extended for indefinite matrices to recover
sparse models [110]. We couple this observation along with the above
discussion to perform low rank matrix completion for
$\mathbb{T}_{k}\,\,\,(\text{for}\,\,\,k\neq 0$) as follows,

$\displaystyle\underset{l_{r},l_{c}\in\mathbb{C}^{N}}{\text{minimize}}$
$\displaystyle\quad\text{Tr}(\mathbf{W}_{1})+\text{Tr}(\mathbf{W}_{2})$ (5.37)
s.t. $\displaystyle\quad l_{r}(\text{lag present})=\hat{l_{r}}(k),$ s.t.
$\displaystyle\quad l_{c}(\text{lag present})=\hat{l_{c}}(k),$
$\displaystyle\quad\begin{bmatrix}\mathbf{W}_{1}&\mathcal{T}(l_{r},l_{c})\\\
\mathcal{T}(l_{r},l_{c})&\mathbf{W}_{2}\end{bmatrix}\succeq 0$

Here, $\mathbf{W}_{1}$ and $\mathbf{W}_{2}$ are auxiliary matrices
implementing trace heuristic to recover low rank indefinite matrices. The
function $Toeplitz(l_{r},l_{c})$ returns the Toeplitz matrix with $l_{r}$ and
$l_{c}$ being the first row and the first column, respectively. This
distinction is important as in general
$\mathbb{T}_{k}\,\,\,(\text{for}\,\,\,k\neq 0$) is not a Hermitian Toeplitz
matrix. The formulation in (5.37) is repeated to yield an estimate for all
constituent Toeplitz blocks.

Upon performing matrix completion for each constituent Toeplitz block, the
individual Toeplitz blocks can be plugged back into (5.33) to yield an
estimate $\mathbf{\hat{\vphantom{\rule{1.0pt}{5.71527pt}}\smash{\hat{{R}}}}}$.
We can improve the estimate
$\mathbf{\hat{\vphantom{\rule{1.0pt}{5.71527pt}}\smash{\hat{{R}}}}}$ by
incorporating the noise variance which is generally known or estimated
apriori. This is achieved through the maximum likelihood estimate (MLE)
approach where the eigenvalues corresponding to the eigenvectors of the noise
subspace are set equal to the noise floor while the remaining eigenvalues are
kept the same. The MLE of
$\mathbf{\hat{\vphantom{\rule{1.0pt}{5.71527pt}}\smash{\hat{{R}}}}}$ is
donated by $\mathbf{\hat{R}}$ and is given by the outer product of the
original eigenvectors of
$\mathbf{\hat{\vphantom{\rule{1.0pt}{5.71527pt}}\smash{\hat{{R}}}}}$
reweighted by the modified eigenvalues. However, it is noted that in practice
the number of eigenvectors associated with the noise floor are not exactly
known. Nevertheless, we only reset those eigenvalues which are less than the
noise floor. Finally, the maximum likelihood estimate $\mathbf{\hat{R}}$, is
used in lieu of
$\mathbf{\hat{\vphantom{\rule{1.0pt}{5.71527pt}}\smash{\hat{{R}}}}}$, to carry
out the data dependent optimization for MaxSINR. It is also noted that unlike
$\mathbf{\hat{\vphantom{\rule{1.0pt}{5.71527pt}}\smash{\hat{{R}}}}}$, the
matrix $\mathbf{\hat{R}}$ is no longer block Toeplitz but is now guaranteed to
be positive definite as is strictly required to implement the proposed sparse
optimization algorithms. The formulation in (5.36) is sufficient for the DFT
implementation scheme which only involves $L$ received data matrices
corresponding to the $L$ DFT bins.

###  5.5 Simulations

The effectiveness of the sparse array design for MaxSINR beamforming is
demonstrated by design examples considering a wideband source operating in the
presence of a mix of narrowband and wideband jammers. The MATLAB-based CVX
modeling tool is used for convex optimization. The importance of sparse array
design for MaxSINR is further emphasized by comparing the optimum design with
the sub optimum array configurations under the TDL and DFT implementation
schemes. The simulation results are presented for perspective linear sensor
locations, nevertheless, the proposed algorithms are applicable to rectangular
grid points or arbitrary placed sensors on 3D surfaces.

####  5.5.1 Example 1

The task is to select $P=14$ sensors from $N=20$ possible equally spaced
locations with inter-element spacing of $\lambda_{min}/2$. We consider an $8$
delay line filter taps associated with each selected sensor ($8$ DFT bins for
DFT implementation scheme) implying $L=8$. A wideband desired point source
impinges on a linear array from DOA $40^{0}$. Five strong wideband jammers
with uniform PSDs (power spectral density) are located at angles $30^{0}$,
$45^{0}$, $50^{0}$, $140^{0}$ and $150^{0}$. The PSD of all frequency spread
sources are uniform with the fractional bandwidth of $0.22$. A narrowband
jammer locked onto the source carrier frequency is active at $130^{0}$. The
SNR of the desired signal is $0$ dB, and the INR of each interfering signals
is set to $30$ dB. Thereby, the input SINR is $-37$ dB.

Figure 5.4: Frequency dependent beampattern for the array configuration
recovered through convex relaxation.

Figure 5.4 shows the frequency dependent beampattern for the array
configuration recovered through TDL-SDR. It is evident from the beampattern
that a high gain is maintained throughout the band of interest for the desired
source signal while alleviating the interferers from respective DOAs and
frequency bands. These beampattern characteristics translate to an output SINR
of $7.05$ dB. The TDL-SDR performs close to the optimum array found by
enumeration which has an output SINR of $7.83$ dB. The corresponding sparse
array configurations obtained by enumeration and TDL-SDR are shown in the Fig.
5.6a and 5.6b, respectively (the green color denotes corresponding sensor
location selected, whereas the gray color shows the sensor location not
selected). It is important to mention that the optimum array found by
enumeration requires a search over $38760$ possible sparse array
configurations, which has a prohibitive computational cost attributed to
expensive singular value decomposition (SVD) for each enumeration. The optimum
sparse array design achieved through TDL-SCA is shown in Fig. 5.6c. This array
configuration is capable of delivering output SINR of $7.7$ dB with the use of
optimal beamforming weights. It performs very close to the optimum sparse
array found through enumeration with the performance degradation of around
$0.1$ dB. This performance is superior to that of the sparse array found
through TDL-SDR by around $0.65$ dB with less computational complexity.

In general, for any given array configuration, the TDL implementation scheme
yields marginally higher SINR as compared to the DFT implementation scheme.
Owing to the reduced computational cost of the DFT sparse design, and
relatively better performance of the TDL sparse design, one can entwine TDL
and DFT beamformers to capitalize on both merits. That is, we proceed to find
the optimum TDL beamformer weights based on the sensor array configuration
that results from the optimum DFT-based implementation scheme. This way,
optimum sparse array design would involve both implementation schemes. This is
referred as the dual-domain design implementation scheme since it considers
both time and frequency domains in generating the optimum receiver design.
This design has slightly elevated computational expense over the DFT design,
as it involves calculating the optimum TDL beamformer weights corresponding to
the DFT optimized configuration. For the underlying problem, the dual-domain
design, through either the DFT-SDR or DFT-SCA gives an output SINR of $7.76$
dB which is close to the maximum possible SINR of $7.83$ dB. The DFT-SDR and
DFT-SCA both render an identical sparse configurations, which is shown in Fig.
5.6d. Therefore, we remark that for the example considered, the dual domain
design underlying the DFT implementation scheme, performs slightly better than
the design carried out exclusively by the TDL implementation scheme.

Figure 5.5: Frequecy dependent beampattern for the compact ULA (Fig. 5.6e).

(a)

(b)

(c)

(d)

(e)

Figure 5.6: Example 1 - (a) Optimum array TDL implementation scheme
(Enumeration) (b) TDL-SDR (c) TDL-SCA (d) DFT-SDR, DFT-SCA (e) $14$ sensor
compact ULA

(a)

(b)

(c)

(d)

(e)

(f)

Figure 5.7: Example 2 - (a) Optimum array TDL implementation scheme
(Enumeration) (b) TDL-SCA (c) TDL-SDR (d) DFT-SCA (e) DFT-SDR (f) Worst case
array (TDL, DFT)

Fig. 5.5 shows the beampattern for the sparse array design resulting in the
worst case output SINR. In this case, the worst array configuration turns out
to be the compact ULA (Fig. 5.6e). This configuration could not deliver the
resolution required to mitigate the closely located jammers. It can be
observed from the beampattern that the compact ULA, in an effort to remove the
strong interfering signals, failed to provide maximum gain towards the source
of interest. This results in a considerable low output SINR that is equal to
$-4.5$ dB. Therefore, a sparse array design which optimally and efficiently
utilizes the array aperture and the additional degrees of freedom made
available by the switching transceiver chains yields an SINR improvement of
more than $12$ dB.

####  5.5.2 Example 2

Consider a wideband source of interest at $45^{0}$ and the wideband jammers
located at $35^{0}$, $55^{0}$, $60^{0}$, $145^{0}$ and $155^{0}$. A narrowband
jammer is located at $135^{0}$ at an operating frequency of $f_{c}$, all other
parameters are the same as in Example $1$. The SINR of the optimum array for
the TDL implementation scheme (Fig. 5.7a) is $11.32$ dB (found through
enumeration). Optimization performed using SCA yields the array in Fig. 5.7b,
with respective SINR of $11.2$ dB, whereas that performed by SDR yields the
array shown in Fig. 5.7c and corresponding SINR of $10.9$ dB. For the dual
domain design, the optimum sparse arrays found through DFT-SCA (Fig. 5.7d) and
through the DFT-SDR algorithm (Fig. 5.7e) deliver an approximately similar
output SINR, around $11.02$ dB. This is inferior to the exclusive TDL design.
It is important to note that the array configuration resulting in the worst
case performance, shown in Fig. 5.7f, spans the full aperture as the optimum
array, yet it offers an output SINR of only $7.35$ dB, underscoring the
importance of carefully performing sensor selection for the sparse array
design.

####  5.5.3 Comparison of SDR and SCA under both models

The design examples discussed thus far show amicable performance of the
proposed algorithms under the assumption of the knowledge of full data
correlation matrix. The results clearly tie the performance to the location of
the sources and their respective powers. However, evaluating the performance
under matrix completion involves analysis for additional variables, namely,
the initial sparse array configuration prior to optimization and the number of
snapshots. The performance is, therefore, dependent on the observed
realization of the received data. In order to have a holistic assessment of
the proposed algorithms, Monte Carlo simulations are generated. We select
$P=8$ locations out of $N=16$ available locations. For specified DOA of the
desired source, trials are generated involving six jammers occupying random
locations from $30^{0}$ to $150^{0}$. The SNR of the desired source is $0$ dB,
while the powers of the jammers are uniformly distributed from $10$ to $20$
dB. The simulation is repeated at $11$ different desired source DOAs, and the
average SINR computed. In total, $1500$ experiments are conducted. For each
trial, a random $P$-sparse array topology serves as an initial array
configuration. This configuration could be an optimized configuration from the
preceding operating conditions. The sparse data correlation matrix is
estimated based on sensor locations in the initial configuration before
performing matrix completion and subsequent optimization process. The binary
search for the sparsity parameter $\mu$ ranges from $0.01$ to $3$, sparsity
threshold $\gamma=10^{-3}$ and $\epsilon=0.05$, relative signal bandwidths and
other parameters are the same as given in Example 1.

Three benchmarks are established to access the performance of the proposed
algorithm under limited snapshots and lack of knowledge of the full data
correlation matrix. The first benchmark applies the enumeration technique for
MaxSINR design under the assumption that the data from all the perspective
sensor locations is available and accurate knowledge of the data correlation
matrix, i.e., assuming unlimited number of snapshots. This benchmark is
referred as “Knowledge of Full Correlation Matrix-Unlimited Snapshots (KFM-
USS)”. Other benchmarks utilize matrix completion to recover the missing lags
(corresponding to $N-P$ missing sensors). We refer to these benchmarks as
"Matrix Completion-Unlimited Snapshots (MC-USS)" and "Matrix Completion-
Limited Snap Shots (MC-LSS)," depending on whether the correlation values are
accurately known through unlimited snapshots or estimated from the limited
snapshots. The evaluation under limited snapshots considers $T=500$. The
performance of the SCA algorithm for the DFT implementation scheme is shown in
the Fig. 5.8. The performance upper bound is given by the MaxSINR design
evaluated through enumeration (DFT-Enumeration (KFM-USS)). In this case, the
average performance over all the desired source DOAs is $7.24$ dB. The
proposed DFT-SCA algorithm under the KFM-USS benchmark offers an average SINR
of $6.63$ dB. This performance is also comparable to the one achieved through
the proposed matrix completion, as is evident in Fig. 5.8. However, the DFT-
SCA design incorporating the MC-LSS benchmark ($T=500$) has a slight
performance trade off of $0.14$ dB w.r.t. the DFT-SCA MC-USS design. The
aforementioned robustness of the MaxSINR design under limited snapshots is
partially attributable to a rather accurate full matrix estimate achieved by
incorporating the apriori knowledge of noise floor.

Figure 5.8: Performance comparisons of SCA under DFT model. Figure 5.9:
Performance comparisons of SCA under TDL model.

The performance of the SCA under the TDL model is evaluated based on the
aforementioned benchmarks, as depicted in Fig. 5.9. The performance trends are
similar, however, the average SINR offered by the TDL implementation scheme is
slightly superior to the DFT implementation scheme which is consistent with
the literature on wideband beamforming for compact arrays [91]. Moreover, it
is noted that the DFT-SCA dual domain design achieves comparable performance
to the TDL-SCA under all design benchmarks. This demonstrates the potential of
the dual design in achieving an effective MaxSINR beamformer with reduced
complexity. Figs. 5.10 and 5.11 depict the Monte Carlo performance results
analyzing the proposed SDR. It shows that the SDR offers comparable
performance to the SCA technique, but involves a heavy computational overhead.
It is also clear from the plots that the optimized array configurations offer
a consequential advantage over both the compact ULA and the high resolution
structured arrays, such as coprime and nested arrays [9, 8], and the randomly
selected $P$ sparse array configuration, each employing their respective
optimal beamforming weights. The average worst case SINR is, however, reduced
significantly to only $1.1$ dB. The performance is also re-evaluated at
varying number of snapshots with consistent results. The performances of the
proposed algorithms under MC-LSS inch closer to the MC-USS benchmark with
increased data.

Figure 5.10: Performance comparisons of SDR under DFT model. Figure 5.11:
Performance comparisons of SDR under TDL model. Figure 5.12: Performance
comparisons of the optimum sparse array, the worst performing array and the
compact ULA (TDL implementation scheme).

####  5.5.4 Practical Considerations for sparse array design

To assess the SINR advantage of the optimum sparse array design, we consider
the effect of two important environment dependent parameters, namely, the DOA
of the desired source and the relative locations of the jammers w.r.t. the
desired source. To demonstrate this effect, the desired source DOA in the
above examples is changed in steps of $5^{0}$, with the relative locations of
the jammers remaining the same with respect to the desired source. For
example, when the desired source is at $50^{0}$ instead of $45^{0}$, the
corresponding jammer locations shift by $5^{0}$. Figure 5.12 compares the
performance of the optimal configuration, the worst performing array, and the
compact ULA, with the desired source DOA varying from $30^{0}$ to $60^{0}$
under Example 1 and 2. It is evident from Fig. 5.12 that under all scenarios
generated in Example 1, the compact ULA delivers the worst performance,
irrespective of the desired source DOA. This is because the jammers are
located closer to the source of interest and the compact ULA lacks the
resolution due to it’s limited array aperture. On the other hand, for Example
2, the jammers are comparatively widely spaced and as such, the compact ULA
has a satisfactory performance that is close to the optimum sparse arrays,
especially when the source DOAs are near the array broadside. The performance
degradation of the ULA near end-fire is due to the increasing overlap between
the desired signal subspace and the interference plus noise subspace [111],
therefore lowering SINR performance. In such scenarios, the sparse array
design efficiently utilizes its degrees of freedom to improve SINR by
increasing the separation between the two subspaces. These examples show that
the sparse array design is most critical when the underlying jamming
environment calls for additional degrees of freedom to engage the available
array aperture more efficiently and to fulfill the resolution requirements
posed by the closer proximity of jammers and the desired source DOA.

###  5.6 Conclusion

This chapter considered optimum sparse array design for maximizing the
beamformer output SINR for the case of wideband signal models. Two different
implementations, namely the TDL and the DFT implementation schemes, were
presented for the optimum sparse array design. The DFT implementation scheme
reduces the MaxSINR sparse array design problem to the lower dimensional
space, thereby reducing computational cost. The sparse array configuration
optimized in the DFT domain and later imported to the TDL implementation
scheme is analyzed to alleviate the computational cost of the TDL sparse
implementation. It was shown that the imported design can possibly yield
comparable performance to the design carried out exclusively through the TDL
implementation scheme. For both approaches, we solved the problem using the
iterative unit rank promoting SDR algorithm and a simplified implementation
using SCA. The parameter-free block Toeplitz matrix completion was proposed to
realize the data dependent design. It was shown that the SDR and SCA
formulation perform reasonably close to the optimum sparse array design
achieved through enumeration under limited data snapshots. The MaxSINR optimum
sparse array yielded considerable performance improvement over suboptimal
sparse arrays and compact ULA for the underlying sensing scenarios.

## Chapter 6Sparse Array Design for Transmit Beamforming

###  6.1 Introduction

Low latency sensor selection technology enables cost effective sparse array
design that can be readily configured to meet environment-dependent
performance metrics. In this case, the system cost can be considerably reduced
by multiplexing the expensive transmission chains to serve many more
perspective sensor locations. However, at any given time, only a few sensor
locations are operational which correspond to the active connections to the
transmission chains. This approach is fundamentally different from the
environment-independent sparse array design which seeks to maximize the number
of spatial autocorrelation lags by producing a hole-free coarray aperture for
a given number of sensors. There, the main task is to enhance source
identifiability for DOA estimation and be able to handle more sources than
sensors [7, 8, 108, 10, 67]. This task can also be achieved for wideband or
multiple frequency sources [31]. Similarly, the environment-independent fixed
beamformer design optimizes the receive beampattern characteristics such as
desirable main lobe width and minimum sidelobe levels as well as frequency
invariant beampattern design for wideband sources [98, 99, 100, 101].

Environment-dependent sparse array optimum configuration design has primarily
been considered from the perspective of receive beampattern characteristics.
The optimality criteria such as maximizing the signal-to-interference plus
noise ratio (MaxSINR) at the receiver can potentially harness effective array
configurations for enhancing target parameter estimation accuracy [97, 11, 28,
73, 112, 113]. In this chapter, we consider environment-dependent sparse array
design for transmit beamforming. Transmit bempattern design is critical to
implementing an efficient receiver design for adaptive radar operations [114,
115, 116]. A desirable transmit design focuses the transmitted power towards
the perceived target locations and, as such, suppress the transmission towards
undesired directions. In so doing, it can steer clear of heavy clutter
environment or avoid probing towards an adversary location in covert
situations. Another critical design objective for the transmitter is to
minimize the cross correlation from the returns from different targets to
enable effective adaptive receiver processing, as high target cross
correlation can severely deteriorate performance.

The transmit beamforming design, in essence, is realized by designing the
waveforms launched across all array sensors. This is in contrast to receive
beamforming which optimizes the weights to yield a desirable output of a
linear combiner. The transmit design can be simplified into two steps, one
pertains to designing the correlation matrix of the transmitted waveform and
the other involves synthesizing the actual transmitted sequence from the
optimized correlation matrix [117]. For the scope of this chapter, we consider
the transmit waveform correlation matrix optimization. There are also
additional constraints that arise in transmit waveform design vis-a-vis
receiver design. The former typically requires a total transmit power
constraint as well as a unit modulus or equal power constraint for each sensor
location so as to utilize system resources judiciously.

In this chapter, we propose sparse array design for transmit beamforming which
is formulated as maximizing the transmit signal power at the target locations
w.r.t. to the power transmitted to the undesired locations while minimizing
the cross correlation among the transmitted signals towards target locations.
Our approach extends the sparse array transmit design proposed in [15] which
optimizes the transmit waveform correlation matrix to maximize the power
towards the desired targets for a given total power constraint. The
methodology therein neither incorporates the cross correlation term nor
proposes a method to suppress transmission towards certain unwanted
directions.

We pose the active sensing design problem as optimally selecting $P$ antennas
out of $N$ possible equally spaced locations. The optimum sparse transmit
array beamformer, in this case, is the one that achieves the design objective,
considering all possible sparse array configurations that stem from different
arrangements of the available sensors. It is important to note that for the
compact arrays (ULAs), the transmit beampattern design only involves
optimizing the transmitted waveform sequence [25]. However, for the underlying
problem, sparse array design involves optimization over two sets of variables,
namely, sensor placements and transmitted waveforms. Selecting sensor
positions for transmit beamformer is a combinatorial optimization problem and
is, therefore, NP hard. In order to avoid the extensive computational burden
for enumerating each possible array configuration, we solve the problem by
convex approximation. The design problem at hand is posed as QCQP with
weighted mixed $l_{1-\infty}$-norm penalization. We propose an approach for
transmit beampattern design to handle the cross correlation term rather
implicitly and best suited for the sparse transmitter design. The proposed
formulation involves an $L$ rank waveform correlation matrix design,
synthesized by $L$ unit rank correlation matrices corresponding to each target
location. As a result, the proposed sparse array design promotes group
sparsity harmoniously across $L$ constituent correlation matrices to ensure
that the designed correlation matrix correspond to $P$ sparse solution. The
QCQP is solved by the SDR approach through convex relaxation and, therefore,
can be solved in polynomial time.

The rest of the chapter is organized as follows: In the next section, we state
the problem formulation for transmit beamformer design in case of a pre-
specified array configuration. Section 6.3 elaborates the sparse array design
by semidefinite relaxation to find the optimum $P$ sparse transmit array
geometry. In the subsequent section, simulations are presented to demonstrate
the offerings of the proposed sparse array transmit design, followed by the
concluding remarks.

###  6.2 Problem Formulation

We consider $L$ target locations at $\\{\theta_{l}\\}_{1}^{L}$ and $Q$ known
adversary or undesired locations for transmission specified by
$\\{\theta_{q}\\}_{1}^{Q}$. The received baseband probing signal ${x}_{l}(n)$
at target locations $\theta_{l}$ at time instant $n$ is given by,

${x}_{l}(n)=\mathbf{s}^{H}(n)\mathbf{a}_{l}$ (6.1)

The signal vector $\mathbf{s}(n)$ is launched from a linear array with $N$
uniformly placed sensors with an inter-element spacing of $d$. Assuming a
narrowband signal model with targets at far field, the steering vector
$\mathbf{a}_{l}\in\mathbb{C}^{N}$ is given by,

$\mathbf{a}_{l}=[1\,\,\,e^{j(2\pi/\lambda)dcos(\theta_{l})}\,.\,.\,.\,e^{j(2\pi/\lambda)d(N-1)cos(\theta_{l})}]^{T}$
(6.2)

Likewise, the baseband signal ${x_{q}}(n)\in\mathbb{C}$ at locations
$\theta_{q}$ is defined. The expression of the signal power at locations
$\theta_{l}$ is given as follows,

$P_{l}=\mathbf{a}^{H}_{l}\mathbf{R}\mathbf{a}_{l}$ (6.3)

The matrix $\mathbf{R}=E(\mathbf{s}(n)\mathbf{s}(n)^{H})$ is the transmitted
waveform correlation matrix. The symbol $E$ denotes the expectation operator.
The problem of maximizing the signal power at the target locations w.r.t. the
unwanted locations can then be formulated as seeking to maximize the directed
power for each target location, yielding the following optimization problem,

$\displaystyle\underset{\mathbf{R}}{\text{minimize}}$
$\displaystyle\quad\sum_{q=1}^{Q}w_{q}(\mathbf{a}_{q}^{H}\mathbf{R}\mathbf{a}_{q})$
(6.4) s.t.
$\displaystyle\quad\mathbf{a}_{l}^{H}\mathbf{R}\mathbf{a}_{l}=1,\quad
l\in\,\,\\{1,...L\\}$

The weighting coefficients $w_{q}$ determines the relative preference of
minimizing one signal over another. We incorporate the cross-correlations of
any two target signals located at $\theta_{l^{{}^{\prime}}}$ and $\theta_{l}$,
which is given by,

$P_{l,{l^{{}^{\prime}}}}=|\mathbf{a}_{l}^{H}\mathbf{R}\mathbf{a}_{l^{{}^{\prime}}}|,$
(6.5)

where ‘$|.|$’ is the modulus operator. The objective function in (6.4) can
then be rewritten as follows [117],

$\displaystyle\underset{\mathbf{R}}{\text{minimize}}$
$\displaystyle\quad\sum_{q=1}^{Q}w_{q}(\mathbf{a}_{q}^{H}\mathbf{R}\mathbf{a}_{q})+\sum_{l=1}^{L}\sum_{{l^{{}^{\prime}}}=l+1}^{L}w_{ll^{{}^{\prime}}}|\mathbf{a}_{l}^{H}\mathbf{R}\mathbf{a}_{l^{{}^{\prime}}}|$
s.t. $\displaystyle\quad\mathbf{a}_{l}^{H}\mathbf{R}\mathbf{a}_{l}=1,\quad
l\in\,\,\\{1,...L\\}$ (6.6)

The weighting coefficients $w_{ll^{{}^{\prime}}}$ determines the relative
trade off in minimizing the cross correlation terms. We adopt a method to
handle the cross correlation term in a more implicit way. Consider the
correlation matrix $\mathbf{R}$ decomposed into $L$ matrices such that
$\mathbf{R}=\sum_{l=1}^{L}\mathbf{R}_{l}$. Matrix $\mathbf{R}_{l}$ is chosen
such that the associated cross correlation term is zero, i.e.,
$\mathbf{a}_{l}^{H}\mathbf{R}_{l}\mathbf{a}_{l^{{}^{\prime}}}=0$ for $l\neq
l^{{}^{\prime}}$. This is possible, for instance, if
$\mathbf{a}_{l^{{}^{\prime}}}\in\mathcal{N}(\mathbf{R}_{l})\,\,\,\forall\,\,l\neq
l^{{}^{\prime}}$. The symbol $\mathcal{N}$ denotes the null space of the input
matrix. Assuming the aforementioned conditions are satisfied, then (6.2) can
be rewritten as,

$\displaystyle\underset{\mathbf{R}_{1},\mathbf{R}_{2},...,\mathbf{R}_{L}}{\text{minimize}}$
$\displaystyle\quad\sum_{l=1}^{L}\sum_{q=1}^{Q}w_{q}(\mathbf{a}_{q}^{H}\mathbf{R}_{l}\mathbf{a}_{q})$
(6.7) s.t.
$\displaystyle\quad\sum_{l=1}^{L}\mathbf{a}_{l^{{}^{\prime}}}^{H}\mathbf{R}_{l}\mathbf{a}_{l^{{}^{\prime}}}=1,\quad{l^{{}^{\prime}}}\in\,\,\\{1,...L\\}$

It is noted that the constraints in the above equation can also be simplified
owing to the aforementioned assumptions on
$\mathbf{a}_{l^{{}^{\prime}}}\in\mathcal{N}(\mathbf{R}_{l})\,\,\,\forall\,\,l\neq
l^{{}^{\prime}}$. We rewrite (6.7) as,

$\displaystyle\underset{\mathbf{R}_{1},\mathbf{R}_{2},...,\mathbf{R}_{L}}{\text{minimize}}$
$\displaystyle\quad\sum_{l=1}^{L}\sum_{q=1}^{Q}w_{q}(\mathbf{a}_{q}^{H}\mathbf{R}_{l}\mathbf{a}_{q})$
(6.8) s.t.
$\displaystyle\quad\mathbf{a}_{l}^{H}\mathbf{R}_{l}\mathbf{a}_{l}=1,\quad
l\in\,\,\\{1,...L\\}$

The zero cross-correlation conditions can be achieved approximately by
introducing additional terms as part of the objective function, that is,

$\displaystyle\underset{\mathbf{R}_{1},\mathbf{R}_{2},...,\mathbf{R}_{L}}{\text{minimize}}$
$\displaystyle\quad\sum_{l=1}^{L}\sum_{q=1}^{Q}w_{q}(\mathbf{a}_{q}^{H}\mathbf{R}_{l}\mathbf{a}_{q})+\sum_{l=1}^{L}\sum_{l^{{}^{\prime}}\neq
l}w_{l^{{}^{\prime}}}(\mathbf{a}_{l^{{}^{\prime}}}^{H}\mathbf{R}_{l}\mathbf{a}_{l^{{}^{\prime}}})$
(6.9) s.t.
$\displaystyle\quad\mathbf{a}_{l}^{H}\mathbf{R}_{l}\mathbf{a}_{l}=1,\quad
l\in\,\,\\{1,...L\\}$

Here, we have utilized the fact that since
$\mathbf{a}_{l^{{}^{\prime}}}^{H}\mathbf{R}_{l}\mathbf{a}_{l^{{}^{\prime}}}$
bounds the cross-term
$|\mathbf{a}_{l}^{H}\mathbf{R}_{l}\mathbf{a}_{l^{{}^{\prime}}}|$, therefore
minimizing the terms
$\mathbf{a}_{l^{{}^{\prime}}}^{H}\mathbf{R}_{l}\mathbf{a}_{l^{{}^{\prime}}}$
for all $l\neq l^{{}^{\prime}}$ also minimizes the cross terms
$|\mathbf{a}_{l}^{H}\mathbf{R}_{l}\mathbf{a}_{l^{{}^{\prime}}}|$ for all
$l\neq l^{{}^{\prime}}$. The weighting coefficients $w_{l^{{}^{\prime}}}$
controls the the relative cross correlations among the target locations.
Therefore, instead of enforcing exact zero value for the cross-terms, we
resort to minimizing the augmented term in (6.9), leading to,

$\displaystyle\underset{\mathbf{R}_{1},\mathbf{R}_{2},...,\mathbf{R}_{L}}{\text{minimize}}$
$\displaystyle\quad\sum_{l=1}^{L}(\sum_{q=1}^{Q}w_{q}(\mathbf{a}_{q}^{H}\mathbf{R}_{l}\mathbf{a}_{q})+\sum_{l^{{}^{\prime}}\neq
l}w_{l^{{}^{\prime}}}(\mathbf{a}_{l^{{}^{\prime}}}^{H}\mathbf{R}_{l}\mathbf{a}_{l^{{}^{\prime}}}))$
s.t. $\displaystyle\quad\mathbf{a}_{l}^{H}\mathbf{R}_{l}\mathbf{a}_{l}=1,\quad
l\in\,\,\\{1,...L\\}$ (6.10)

In essence, the proposed formulation in (6.2) limits the cross-terms
inherently by treating the $Q$ unwanted signals somewhat similarly to the
other target locations except the $l$th target. We define the manifold matrix
corresponding to the unwanted locations $\theta_{q}$,
$\mathbf{V}=[\mathbf{a}_{1},\mathbf{a}_{2},...,\mathbf{a}_{Q}]$. Let
$\mathbf{S}_{l}=[\mathbf{a}_{1},\mathbf{a}_{2},...,\mathbf{a}_{L-1}]$
incorporate all target steering vectors except the $l$th target. Define
$\mathbf{B}_{l}=[\mathbf{V}\,\,\,\,\mathbf{S}_{l}]$. Lumping the weighting
coefficients in a diagonal matrix $\mathbf{W}_{l}$ other than the $l$th target
allows rewriting (6.2) in a compact manner as,

$\displaystyle\underset{\mathbf{R}_{1},\mathbf{R}_{2},...,\mathbf{R}_{L}}{\text{minimize}}$
$\displaystyle\quad\sum_{l=1}^{L}(\mathbf{W}_{l}\mathbf{B}_{l}^{H}\mathbf{R}_{l}\mathbf{B}_{l}+\rho_{l}\text{Tr}(\mathbf{R}_{l}))$
(6.11) s.t.
$\displaystyle\quad\mathbf{a}_{l}^{H}\mathbf{R}_{l}\mathbf{a}_{l}=1,\quad
l\in\,\,\\{1,...L\\}$

The additional term involving Tr($\mathbf{R}_{l}$) is introduced in (6.11),
where the symbol ‘Tr(.)’ represents the trace of the matrix and its
minimization limits the norm of $\mathbf{R}_{l}$. This additional
regularization term ($\rho_{l}$ is the regularization parameter) can also help
to alleviate high sidelobe levels in the transmit beampattern [47]. The above
quadratic formulation requires the information of the target locations as well
as the undesired locations, but it holds true irrespective of the array
configuration and is equally valid for compact arrays as well as sparse
arrays. The sparse optimization of the above formulation is explained in the
next section.

###  6.3 Sparse array design

The above quadratic problem for $P$ antenna selection is a combinatorial
optimization problem and can’t be solved in polynomial times. We formulate the
sparse array design as a rank relaxed semidefinite program (SDR) with the
mixed norm regularization to recover group sparse solutions.

####  6.3.1 Sparse solution through SDR

Invoking sparsity in the designed correlation matrix $\mathbf{R}_{l}$ of the
transmitted waveform essentially implies that a missing sensor translates to
the sparsity in the corresponding row and column of $\mathbf{R}_{l}$.
Furthermore, $\mathbf{R}=\sum_{l=1}^{L}\mathbf{R}_{l}$ implies that the sparse
rows and columns should be consistent across all $L$ correlation matrices. In
order to do so, and invoke sparsity in a systematic manner, the positive
semidefinite correlation matrices $\mathbf{R}_{l}^{\prime}s$ are assumed to be
unit rank and expressed as an outer product,
$\mathbf{R}_{l}=\mathbf{r}_{l}\mathbf{r}_{l}^{H}$. Define
$\mathbf{r}^{(k)}=[\mathbf{r}_{1}(k),\mathbf{r}_{2}(k),...,\mathbf{r}_{L}(k)]\in\mathbb{C}^{L}$
as the $k$th entry for all the $L$ vectors $\mathbf{r}_{l}$’s which is
associated with the $k$th transmitter. The problem formulated in (6.11) can be
rewritten with an additional regularization term as,

$\displaystyle\underset{\mathbf{R}_{l}\mathbf{\in\mathbb{C}}^{N}}{\text{minimize}}$
$\displaystyle\quad\sum_{l=1}^{L}(\mathbf{W}_{l}\mathbf{B}_{l}^{H}\mathbf{R}_{l}\mathbf{B}_{l}+\rho_{l}\text{Tr}(\mathbf{R}_{l}))+\mu(\sum_{k=1}^{N}||\mathbf{r}^{(k)}||_{q})$
s.t. $\displaystyle\quad\mathbf{a}_{l}^{H}\mathbf{R}_{l}\mathbf{a}_{l}=1,\quad
l\in\,\,\\{1,...L\\}$ (6.12)

Here, $||.||_{q}$ denotes the $q$-norm of the vector. The mixed $l_{1-q}$ norm
regularization is known to thrive the group sparsity in the solution. This
ensures that the identical $P$ transmitters are selected for each constituent
correlation matrix $\mathbf{R}_{l}$, and without specifying the cardinality of
active transmitters. For the underlying design problem, the re-weighted
$l_{1}$-norm is adopted which is a well known regularizer for promoting sparse
solutions iteratively [58],

$\displaystyle\underset{\mathbf{R}_{l}\mathbf{\in\mathbb{C}}^{N}}{\text{minimize}}$
$\displaystyle\quad\sum_{l=1}^{L}(\mathbf{W}_{l}\mathbf{B}_{l}^{H}\mathbf{R}_{l}\mathbf{B}_{l}+\rho_{l}\text{Tr}(\mathbf{R}_{l}))$
$\displaystyle\quad\quad\quad\quad\qquad\qquad\qquad\qquad\qquad\qquad+\mu(\sum_{k=1}^{N}\mathbf{u}^{i}(k)||\mathbf{r}^{(k)}||_{q})$
s.t.
$\displaystyle\quad\sum_{l=1}^{L}\mathbf{a}_{l}^{H}\mathbf{R}_{l}\mathbf{a}_{l}=1,\quad
l\in\,\,\\{1,...L\\}$ (6.13)

The choice of the $k$th element of the re-weighting vector $\mathbf{u}^{i}(k)$
at the $i$th iteration is later discussed. Implementing the group sparsity
through the $\infty$-norm and choosing $l_{1}$-norm squared function instead
of the $l_{1}$-norm can facilitate the semidefinite realization [2],

$\displaystyle\underset{\mathbf{R}_{l}\mathbf{\in\mathbb{C}}^{N}}{\text{minimize}}$
$\displaystyle\quad\sum_{l=1}^{L}(\mathbf{W}_{l}\mathbf{B}_{l}^{H}\mathbf{R}_{l}\mathbf{B}_{l}+\rho_{l}\text{Tr}(\mathbf{R}_{l}))$
$\displaystyle\quad\quad\quad\quad\quad\qquad\qquad\qquad\qquad\qquad+\mu(\sum_{k=1}^{N}\mathbf{u}^{i}(k)||\mathbf{r}^{(k)}||_{\infty})^{2}$
s.t.
$\displaystyle\quad\sum_{l=1}^{L}\mathbf{a}_{l}^{H}\mathbf{R}_{sl}\mathbf{a}_{l}=1,\quad
l\in\,\,\\{1,...L\\}$ (6.14)

The above problem can then be posed as semidefinite programming by
equivalently expressing the quadratic functions,
$\mathbf{W}_{l}\mathbf{B}_{l}^{H}\mathbf{R}_{l}\mathbf{B}_{l}=$
Tr$(\mathbf{W}_{l}\mathbf{B}_{l}^{H}\mathbf{R}_{l}\mathbf{B}_{l})=$Tr$(\mathbf{R}_{l}\mathbf{W}_{l}\mathbf{B}_{l}\mathbf{B}_{l}^{H})=$
Tr$(\mathbf{R}_{l}\mathbf{\bar{B}}_{l})$. Here,
$\mathbf{\bar{B}}_{l}=\mathbf{W}_{l}\mathbf{B}_{l}\mathbf{B}_{l}^{H}$ and
similarly $\mathbf{{A}}_{l}=\mathbf{a}_{l}\mathbf{a}_{l}^{H}$ is the outer
product of $l$th target steering vector. The formulation in (6.14) takes the
following form [59, 61, 72, 60, 2],

$\displaystyle\underset{\mathbf{R}_{l}\mathbf{\in\mathbb{C}}^{N.N},\mathbf{\tilde{R}\in\mathbb{R}}^{N.N}}{\text{minimize}}$
$\displaystyle\quad\sum_{l=1}^{L}\text{Tr}(\mathbf{R}_{l}(\mathbf{\bar{B}}_{l}+\rho_{l}\mathbf{I}))+\mu\text{Tr}(\mathbf{U}^{i}\mathbf{\tilde{R}})$
s.t. $\displaystyle\quad\text{Tr}(\mathbf{R}_{l}\mathbf{A}_{l})\geq 1,\quad
l\in\,\,\\{1,...L\\},$
$\displaystyle\quad\mathbf{\tilde{R}}\geq|\mathbf{R}_{l}|\quad
l\in\,\,\\{1,...L\\},$ $\displaystyle\quad\mathbf{R}_{l}\succeq
0,\,\text{Rank}(\mathbf{R}_{l})=1$ (6.15)

Here ‘$\geq$’ is the element wise comparison and ‘$\succeq$’ denotes the
positive semidefinite constraint, and
$\mathbf{U}^{i}=\mathbf{u}^{i}(\mathbf{u}^{i})^{T}$ ((.)T denotes the
transpose). The SDR realization of the problem in (6.3.1) is pursued by
dropping the non-convex rank limiting constraint,

$\displaystyle\underset{\mathbf{R}_{l}\mathbf{\in\mathbb{C}}^{N.N},\mathbf{\tilde{R}\in\mathbb{R}}^{N.N}}{\text{minimize}}$
$\displaystyle\quad\sum_{l=1}^{L}\text{Tr}(\mathbf{R}_{l}(\mathbf{\bar{B}}_{l}+\rho_{l}\mathbf{I}))+\mu\text{Tr}(\mathbf{U}^{i}\mathbf{\tilde{R}})$
s.t. $\displaystyle\quad\text{Tr}(\mathbf{R}_{l}\mathbf{A}_{l})\geq 1,\quad
l\in\,\,\\{1,...L\\},$
$\displaystyle\quad\mathbf{\tilde{R}}\geq|\mathbf{R}_{l}|\quad
l\in\,\,\\{1,...L\\},$ $\displaystyle\quad\mathbf{R}_{l}\succeq 0,\quad
l\in\,\,\\{1,...L\\}$ (6.16)

Although the formulation in (6.3.1) doesn’t enforce the rank constraint, it
has been observed, through extensive numerical simulations, that it usually
renders rank 1 solutions and, therefore, approximates the original problem
fairly accurately.

Table 6.1: SDR-Transmit Beamformer Design

0: $N$, $P$, $L$, Look directions $\theta_{q}$ and $\theta_{l}$.

0: $\mathbf{R}=\sum_{l=1}^{L}\mathbf{R}_{l}$ transmit waveform correlation
matrix. Initialization: Initialize $\gamma$, $\epsilon$, $\mathbf{W}_{l}$,
$\rho_{l}$, $\mathbf{U}$ as all ones matrix. Bisection search for desired
cardinality $P$$l=\mu_{lower}$, $u=\mu_{upper}$ (Initializing lower and upper
limits of sparsity parameter range)

while (Cardinality of $\mathbf{r}_{l}\text{'s}$ $\neq$ $P$) do

$\mu=[(l+u)/2]$

Run the SDR of Eq. (16).

Update $\mathbf{U}$ according to Eq. (17).

Update $\mu$ through bisection method.

end while

After achieving the desired cardinality, run SDR for reduced size correlation
matrix corresponding to nonzero values of $\mathbf{\tilde{R}}$ and $\mu=0$,
yielding, $\mathbf{R}=\sum_{l=1}^{L}\mathbf{R}_{l}$.

return $\mathbf{R}$

####  6.3.2 Reweighting sparsity

The reweighting matrix $\mathbf{U}^{i}$ is typically initialized unweighted
with an all ones matrix. It is subsequently updated with an inverse function
of the absolute values of the entries of the correlation matrix as follows
[58],

$\mathbf{U}_{m,n}^{i+1}=\frac{1}{\mathbf{\tilde{R}}^{i}(m,n)+\epsilon}$ (6.17)

The $m,n$th entry of $\mathbf{\tilde{R}}$ is given by
$\mathbf{\tilde{R}}^{i}(m,n)$. The parameter $\epsilon$ prevents the solution
to converge to local minima and avoids the unwanted case of division by zero.
Choosing the randomly selected sparsity parameter $\mu$ does not exactly
correspond to $P$ sparse solution. In order to trace $\mu$ corresponding to
$P$ sparse solution, the optimization problem is typically solved for
different values of $\mu$ found through a bisection search, until the solution
converges to $P$ sensors [2]. The proposed algorithm for controlling the
sparsity of the transmitted waveform correlation matrix is elaborated further
in Table 6.1.

####  6.3.3 Transmit power constraint

It is noted that the formulation adopted so far doesn’t explicitly account for
the total transmit power constraint which is critical for a pragmatic design.
However, the proposed approach can inherently accommodate this constraint as
it is primarily based on relative target power maximization w.r.t. the
undesired locations. This renders the design invariant to the scaling factor.
Therefore, for a given transit power of $P_{t}$ and the designed transmit
correlation matrix $\mathbf{R}$, the total transmit power constraint is
realized by a scaling factor $\alpha$ such that
$\alpha$Tr$(\mathbf{R})=P_{t}$. For the scope this chapter, we don’t consider
the uniform elemental power constraint.

###  6.4 Simulations

In this section, we demonstrate the effectiveness of the active sparse array
design from the perspective of the transmit beampattern. The performance of
sparse array design is compared with the compact ULA and the structured sparse
array design.

(a)

(b)

(c)

(d)

Figure 6.1: Various array configurations

####  6.4.1 Example

We consider $N=18$ equally spaced locations are potentially available for
sensor selection. The minimum spacing among the sensors is $d=\lambda/2$, and
$P=10$ sensor locations can be chosen concurrently. The three targets
locations, $L=3$, namely Targets 1, 2 and 3 are perceived at $40^{0}$,
$50^{0}$ and $65^{0}$, respectively. Four unwanted directions are located at
$25^{0}$, $60^{0}$, $110^{0}$ and $120^{0}$. All the weighting coefficients
corresponding to the targets and unwanted locations are set to one
($\rho_{l}=1)$. The sparsity parameter $\mu$ is found through bisection search
ranging from $0.01$ to $3$, the sensor locations corresponding to the
correlation values of less than the sparsity threshold $\gamma=10^{-5}$ are
declared sparse and $\epsilon=0.05$ is chosen for the underlying problem.

Figure (6.1a) shows the sparse array found through enumeration that optimizes
the formulated objective function over all possible configurations. This
sparse array configuration has a performance that is comparable to that of the
array optimized through the proposed SDR algorithm. The SDR-optimized topology
is shown in (6.1b), and has the performance trade off less than 0.23 dB as
compared to the enumerated design. The transmit beampattern of the optimized
topology is depicted in Fig. (6.2). It is observed form the normalized
beampattern that the designed configuration fairly attempts to maximize the
transmitted power towards the target locations while mitigating the power
towards the unwanted directions. In so doing, the average directed gain
towards the target locations is less than 0.5 dB down as compared to the
maximum gain. On the other hand, the nested array configuration and the
compact ULA offers an average gain towards the targets which is $2.1$ dB and
$2.45$ dB down, respectively, as compared to the corresponding locations with
the maximum transmitted power. The nested array and the compact ULA are shown
on Figs. (6.1c) and (6.1d), with the respective beampatterns depicted in Figs.
(6.3) and (6.4) , respectively.

Figure 6.2: Transmit beampattern for the SDR-optimized configuration. Figure
6.3: Transmit beampattern for the nested array configuration.

It is noted from the depicted beampatterns that the proposed methodology, in
an attempt to minimize the cross correlation among the target signals, renders
a synthesized beampattern whose maxima are precisely towards the target
locations. This is also evident from the beampattern of the SDR-optimized
array as shown in Fig. (6.2), where the maxima is slightly skewed from the
target locations. This effect can be explained from the transmit beampatterns
of the constituent correlation matrices shown in Fig. (6.5). It is clear that
the individual constituent beampatterns have the maxima at the respective
target locations. However, since the transmit beampattern is a cumulative
pattern found by the superposition of constituent beampatterns, the overall
maxima can drift from the proximity of the target locations. This effect
doesn’t pose a major drawback to the proposed design as it is evident from the
beampattern of Fig. (6.2), where the beampattern maxima is located somewhere
in the middle of the closely located targets at $40^{0}$, $50^{0}$ and is
merely $0.5$ dB strong as compared to the target gains. In this case, still
significantly higher power is directed to the target locations relative to the
total average transmitted power.

Figure 6.4: Transmit beampattern for the compact ULA. Figure 6.5: Constituent
transmit beampatterns for the SDR-optimized configuration.

To analyze the cross correlation term, we plotted the following normalized
cross-term $\hat{P}_{l,{l^{{}^{\prime}}}}$ for each target location,

$P_{l,{l^{{}^{\prime}}}}=\frac{|\mathbf{a}^{H}(\theta_{l})\mathbf{R}\mathbf{a}(\theta_{l^{{}^{\prime}}})|}{(\mathbf{a}^{H}(\theta_{l})\mathbf{R}\mathbf{a}(\theta_{l}))^{\frac{1}{2}}(\mathbf{a}^{H}(\theta_{l^{{}^{\prime}}})\mathbf{R}\mathbf{a}(\theta_{l^{{}^{\prime}}}))^{\frac{1}{2}}}$

Fig. (6.6) shows the cross-correlation pattern w.r.t. to the Target 1. It is
clear that the cross-correlation contributions of the Target 1 to the target
locations 2 and 3 are negligible and are less than $20$ dB. In contrast, the
cross correlation coefficients of the Target 1 to Target 2, in case of the
nested array and the compact ULA are $0.46$ and $0.53$ which are significantly
higher. However, the cross correlations of the Target 1 to Target 3 are
substantially lower for the nested array and the compact ULA as Target 3 is
sufficiently farther away from Target 1 location. This also holds true for the
cross correlations of the Target 2 to Target 3 owing to the spacing of both
target locations as shown in Fig. (6.7).

###  6.5 Conclusion

This chapter considered active sensing using sparse array configuration. It
sought optimum transmit beamforming for radar applications. The problem was
formulated as optimizing the transmit waveform correlation matrix and solved
through convex relaxation with low computational complexity. It was shown that
the active sparse array design can achieve desirable beampattern
characteristics such as directing a high proportion of the transmitted power
towards the perspective target locations with minimal cross-correlation among
target signals. We showed the effectiveness of the proposed approach by
comparing its performance with that of compact ULA, a structured array, and
the design achieved through enumeration.

Figure 6.6: Cross-correlation pattern against the Target 1 for various sparse
configurations. Figure 6.7: Cross-correlation pattern against the Target 2 for
various sparse configurations.

## Chapter 7Sparse Array Capon Beamformer Design Availing Deep Learning
Approach

###  7.1 Introduction

Sparse array design reduces system transceiver costs by reducing the hardware
and processing complexity through sensor selection. It is useful in multitude
of sensor signal processing tasks for MIMO communications, radar/sonar,
satellite navigation, radio telescopes, speech enhancement and medical imaging
applications [1, 2, 3, 4, 5, 6]. The performance gains in using sparse arrays
stem from their inherent ability of tending the additional degrees of freedom
to accomplish certain pre-defined performance metrics. Several different
performance metrics have been proposed in the literature, and can generally be
categorized into environment-independent or environment-dependent design. In
the latter case, the receiver performance then largely depends on the
operating environment, which may change according to the source and
interference signals and locations, implemented via reconfigurable sensor
arrays. This is in contrast to environment-independent sparse arrays whose
configurations follow certain formulas and seek to attain structured sparse
configurations with extended aperture co-arrays. The driving objective, in
this case, is to enable direction of arrival (DOA) estimation of more sources
than the available physical sensors. Common examples of structured sparse
arrays are the nested and coprime arrays [7, 8, 10].

Reliably extracting a desired signal waveform by enhancing SINR has a direct
bearing on improving target detection and localization for radar signal
processing, increasing throughput or channel capacity for MIMO wireless
communication systems, and enhancing resolution capability in medical imaging
[45, 46, 47]. Maximizing signal to noise ratio (MaxSNR) and MaxSINR criteria
have been shown to yield significantly efficient beamforming performance and
interference mitigation. For sparse array design, the MaxSINR beamforming
performance depends mainly on the selected positions of the sensors as well as
the locations of sources in the field of view (FOV) [11, 13, 14, 12, 20, 71].
It is noted that with sparse arrays, the commonly used Capon beamforming must
not only find the optimum weights but also the optimum array configuration.
This is clearly an entwined optimization problem and requires attaining
maximum SINR over all possible sparse array configurations.

Sparse array design typically involves the selection of a subset of uniform
grid points for sensor placements. For a given number of sensors, it is
assumed that the number of perspective grid points, spaced by half wavelength,
is limited due to a size constraint on the physical aperture. For environment-
dependent sparse arrays, the antenna positions are selected from uniformly
spaced locations that are served by a limited number of transceiver chains.
The environment-sensitive array design objectives have recently become more
realizable due to advances in efficient sensor switching technologies that
readily activates a subset of sensors on a predefined grid points resulting in
rapid array reconfigurability. Thereby, the system cost can significantly be
reduced by limiting the number of expensive transceivers chains as shown in
Fig. 7.1 [92, 95, 94, 93].

Environment-dependent sparse array design algorithms generally follow two
different approaches. The designs based on prior knowledge of interfernce
parameters, essentially require that the real time interference parameters
such as DOAs and respective SINRs are either known or are estimated apriori in
real time. The other approach doesn’t explicitly require the information of
interfering environment which is the case in the Capon beamforming
formulation. In both cases, several iterative algorithms have been proposed to
optimize the sparse array beamformer design. Although, convex based
optimization algorithms, such as semidefinite relaxation (SDR) and successive
convex approximation (SCA) have been developed to yield sparse configurations
with superior beamforming performances [20, 71], the real time implementation
of these algorithms remains limited due to the relatively high computation
cost. The latter is undesirable in rapidly changing environments stemming from
temporal and spatial nonstationary behaviors of the sources in the field of
view.

In this chapter, we propose a sparse beamformer methodology implementing data-
driven array design by training the DNN to learn and mimic the sparse
beamforming design algorithms [118, 119]. Towards this goal, the training
scenarios are simulated in two different ways. In the first approach, we use
enumeration technique to generate the training labels for any given received
sensor correlation function. This is achieved by finding the MaxSINR
configuration by sifting through all possible sparse configurations and
choosing the best performing topology. Although in practice, the training data
is generated offline, it becomes infeasible to obtain optimum configuration
even for a moderate size arrays due to the enormous sensor permutations. In
order to circumvent this problem, we propose a new technique to expedite the
generation of large number to training data labels to input the DNN. For a
given environment in the training set, this technique considers the array
spatial spectrum and incorporates the lag redundancy in determining desired
array structures. Aside from efficient generation of DNN training data, the
same technique can be used as a stand alone method to determine the best array
configuration if prior information of the interference parameter is provided.
The DNN approximates the unknown mapping from the input correlation matrix to
the output of sensor placements (Fig. 7.2). It is shown that DNN effectively
learns the optimum array structure. This makes DNN suitable for real-time
implementation as DNN output prediction only requires a fewer number of
trivial operations.

Figure 7.1: Block diagram of adaptive switched sensor beamformer

Prior work: DNNs have shown great potential due to its automatic feature
selection with demonstrated ability of effective feature learning in many
applications including computer vision, speech recognition, and natural
language processing. Recently, ’learn to optimize’ approaches has been
proposed to improve and automate the implementation of DNNs iteslf, which
largely require the laborious task of designing the learning algorithms
alongside model and hyperparameter selection that needs to be manually
tailored from task to task. In these methods, an additional DNN is trained
(called the meta-DNN) to ensure better optimization of the original DNN
(called the base-DNN) and generalize over many tasks, hence avoiding to
redesign algorithm for closely related tasks [120, 121, 122].

Depending on the task at hand, the DNN employed to learn can either be trained
by reinforcement learning or supervised learning. It has been shown that the
reinforcement learning is a reliable approach, in case, the training examples
are not independent and identically distributed (i.i.d.). This is precisely
the case in optimizer learning because the step vector towards the optimizer,
for any given iteration, affects the gradients at all subsequent iterations.
On the other hand, the DNN designs based on standard supervised learning
approach has been shown to realize computationally efficient implementation of
iterative signal processing algorithms [123, 124]. These computationally
intensive algorithms, take a given set of design parameters and produce the
“optimized” solutions as their outputs. The DNN learns from the training
examples that are generated by running these algorithms offline. Also, the
parameters of the network are learned entirely offline, whereas efficient
online implementation is realized by passing the input through this pre-
trained DNN which requires a small number of simple operations to yield the
optimized output.

In this chapter, we develop sparse array beamformer design implementation
using supervised training. Learning sparse optimization techniques has been
studied before in the contest of developing sparse representations and seeking
simpler models [125]. Unlike, sparse representation approaches the sparse
beamformer optimization refers to ’sparsity in the sensing’ rather than
’sparsity in the sensed’ and has important distinctions. Learning sparse
algorithms, thus far, are mainly focused on iterative “unfolding” concept
implemented by a single layer of the network [126, 127, 128, 129, 125]. The
proposed approach approximate rather simple algorithms implemented through
iterative soft-thresholding such as ISTA algorithm for sparse optimization.
The sparse beamformer design, on the other hand, involves intricate operations
such as singular value decomposition and matrix inversion. Also, the sparse
beamfomer designs mainly implemented through convex relaxation are based on
SDR and SCA algorithms involving sparsity promoting regularizers and are very
expensive to implement in real time.

Main Contributions: The main contributions of this chapter can be summarized
as follows,

1) Sparse beamformer spectral analysis (SBSA) algorithm is proposed which
provides an insightful perspective for MaxSINR beamformer design with reduced
computational complexity and superior performance. The design elucidates the
concept of ’inherently amenable’ sparse configurations for interference
mitigation.

2) The DNN based approach is developed, for the first time, to configure a
Capon based data driven sparse beamfomer by learning the enumerated algorithm
as well as SBSA design. The design is achieved through a direct mapping of the
received correlation matrix to the optimum sparse configuration for a given
‘look direction’. The proposed methodology combines the merits of the data
dependent designs and the designs assuming prior information of the
interfering environment.

3) The proposed design is shown to be robust in the case of limited data
snapshots and can easily be extended to robust adaptive beamforming to cater
the uncertainty regarding the look direction DOA as well as array calibration
errors.

The rest of the chapter is organized as follows: In the next section, we state
the problem formulation for maximizing the output SINR. Section 7.3 deals with
the optimum sparse array design by SBSA algorithm and DNN based Capon
implementation. In section 7.4, with the aid of number of design examples, we
demonstrate the usefulness of proposed algorithms in achieving MaxSINR sparse
array design. Concluding remarks follow at the end.

Figure 7.2: Architecture of Deep Neural Network (DNN)

###  7.2 Problem Formulation

Consider a desired source and $L$ independent interfering source signals
impinging on a linear array with $N$ uniformly placed sensors. The baseband
signal received at the array at time instant $t$ is then given by;

$\mathbf{x}(t)=(\alpha(t))\mathbf{s}(\theta)+\sum_{l=1}^{L}(\beta_{l}(t))\mathbf{v}(\theta_{l})+\mathbf{n}(t),$
(7.1)

where, $\mathbf{s}({\theta_{k}})$ and $\mathbf{v}({\theta_{l}})$
$\in\mathbb{C}^{N}$ are the steering vectors corresponding to the direction of
arrival, $\theta$ or $\theta_{l}$, and are defined as follows;

$\mathbf{s}({\theta})=[1\,\,\,e^{j(2\pi/\lambda)dcos(\theta)}\,.\,.\,.\,e^{j(2\pi/\lambda)d(N-1)cos(\theta)}]^{T}.$
(7.2)

where $d$ is the inter-element spacing and ($\alpha(t)$, $\beta_{l}(t))$
$\in\mathbb{C}$ are the complex amplitudes of the incoming baseband signals
[54]. The additive Gaussian noise $\mathbf{n}(t)$ $\in\mathbb{C}^{N}$ is of
variance of $\sigma_{n}^{2}$. The received signal vector $\mathbf{x}(t)$ is
combined linearly by the $N$-sensor beamformer that strives to maximize the
output SINR. The output signal $y(t)$ of the optimum beamformer for maximum
SINR is given by [25],

$y(t)=\mathbf{w}_{o}^{H}\mathbf{x}(t),$ (7.3)

where $\mathbf{w}_{o}$ is the solution of the optimization problem given by,

$\displaystyle\underset{\mathbf{w}\in\mathbb{C}^{N}}{\text{minimize}}$
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R}_{s^{{}^{\prime}}}\mathbf{w},$
(7.4) s.t. $\displaystyle\quad\mathbf{w}^{H}\mathbf{R}_{s}\mathbf{w}=1.$

For statistically independent signals, the desired source correlation matrix
is $\mathbf{R}_{s}=\sigma^{2}\mathbf{s}(\theta)\mathbf{s}^{H}(\theta)$, where
$\sigma^{2}=E\\{\alpha(t)\alpha^{H}(t)\\}$. Likewise, the interference and
noise correlation matrix,
$\mathbf{R}_{s^{{}^{\prime}}}=\sum_{l=1}^{L}(\sigma^{2}_{l}\mathbf{v}(\theta_{l})\mathbf{v}^{H}(\theta_{l})$)
+ $\sigma_{n}^{2}\mathbf{I}_{N\times N}$, with
$\sigma^{2}_{l}=E\\{\beta_{l}(t)\beta_{l}^{H}(t)\\}$ being the power of the
$l$th interfering source. The problem in (7.4) can be written equivalently by
replacing $\mathbf{R}_{s^{{}^{\prime}}}$ with the received data covariance
matrix, $\mathbf{R_{xx}}=\mathbf{R}_{s}+\mathbf{R}_{s^{{}^{\prime}}}$ as
follows [25],

$\displaystyle\underset{\mathbf{w}\in\mathbb{C}^{N}}{\text{minimize}}$
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R_{xx}}\mathbf{w},$ (7.5) s.t.
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R}_{s}\mathbf{w}\geq 1.$

Figure 7.3: Overview of the proposed approach using Deep Neural Network (DNN)

It is noted that the equality constraint in (7.4) is relaxed in (7.5) due to
the inclusion of the constraint as part of the objective function, and as
such, (7.5) converges to the equality constraint. Additionally, the optimal
solution in (7.5) is invariant up to uncertainty in the absolute power of the
source of interest. However, in practice, these assumptions can deviate from
the actual received data statistics and hence the discrepancy is typically
mitigated, to an extent, by preprocessing the received data correlation matrix
through diagonal loading or tapering the correlation matrix [47].

The closed form solution of the above optimization problem exists and is given
by
$\mathbf{w}_{o}=\mathscr{P}\\{\mathbf{R}_{s^{{}^{\prime}}}^{-1}\mathbf{R}_{s}\\}=\mathscr{P}\\{\mathbf{R_{xx}}^{-1}\mathbf{R}_{s}\\}$.
The operator $\mathscr{P}\\{.\\}$ computes the principal eigenvector of the
input matrix. Substituting $\mathbf{w}_{o}$ into (7.3) yields the
corresponding optimum output SINRo;

$\text{SINR}_{o}=\frac{\mathbf{w}_{o}^{H}\mathbf{R}_{s}\mathbf{w}_{o}}{\mathbf{w}_{o}^{H}\mathbf{R}_{s^{{}^{\prime}}}\mathbf{w}_{o}}=\Lambda_{max}\\{\mathbf{R}^{-1}_{s^{{}^{\prime}}}\mathbf{R}_{s}\\}.$
(7.6)

This shows that the optimum output SINRo is given by the maximum eigenvalue
($\Lambda_{max}$) associated with the product of the inverse of interference
plus noise correlation matrix and the desired source correlation matrix.
Therefore, the performance of the optimum beamformer for maximizing the output
SINR is directly related to the desired and interference plus noise
correlation matrices.

###  7.3 Optimum sparse array design

The constraint optimization (7.5) can be re-formulated for optimum sparse
array design by incorporating an additional constraint on the cardinality of
the weight vector;

$\displaystyle\underset{\mathbf{w\in\mathbb{C}}^{N}}{\text{minimize}}$
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R_{xx}}\mathbf{w},$ (7.7) s.t.
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R}_{s}\mathbf{w}\geq 1,$
$\displaystyle\quad||\mathbf{w}||_{0}=P.$

Here, $||.||_{0}$ determines the cardinality of the weight vector
$\mathbf{w}$. This is a combinatorial optimization problem and can be solved
optimally by enumerating over all possible locations. Several different
approaches have been developed to mitigate the computational expense of the
combinatorial search either by exploiting the information of the interference
parameters or employing data-dependent approaches realized through the SDR and
SCA algorithms. These algorithms have high computational costs, impeding real
time implementations, especially in applications involving rapidly changing
environments. In the context of designing sparse arrays using machine
learning, the optimum sparse arrays for different operating environments
constitute labels for the network training data. These labels can be generated
off-line through enumerations. Although, this procedure is off line,
accounting for all possible source and interference scenarios leads to a
formidable computational problem rendering solutions for large arrays and a
large number of training samples infeasible. In order to simplify the problem,
we propose a sparse beamformer spectral analysis (SBSA) design technique to
efficiently train the DNN. This technique is detailed below, and has improved
performance and yields lower computational complexity as compared to the
state-of-the-art. The subsequent subsection presents the implementation of the
SBSA and enumerated design algorithms using the DNN approach, this further
reduces the implementation time and also paves the way to data dependent
design (refer to Fig. 7.3 for an overview).

####  7.3.1 Sparse beamformer spectral analysis (SBSA) design

Figure 7.4: Eight element sparse array configuration Figure 7.5: Lag
Redundancy of the sparse array shown in Fig. 7.4 Figure 7.6: DFT of the lag
redundancy  Figure 7.7: Power spectrum of the desired signal Figure 7.8:
Explanation of the proposed objective criterion for the optimum array
configuration shown in Fig. 7.4 Figure 7.9:  Explanation of the proposed
objective criterion for the worst possible array configuration Figure 7.10:
Plot of the proposed objective criterion in ascending order

As shown in Eq. 7.6, the sparse array configuration for MaxSINR design depends
on the beamforming weights and also on the sparse array configuration.
Therefore, the problem of interference mitigation is not a cascade design but
is an entwined task, calling for the simultaneous optimization for the
beamforming weights and the sparse array configuration. We adopt a frequency
domain approach offering a unique insight to the problem and addressing the
suitability of a given sparse configuration, irrespective of the beamforming
weights, in canceling the interfering signals.

The problem formulation developed in the previous section is valid
irrespective of the array configuration and holds true for the compact ULA or
any generic sparse configuration. The beamformer output signal,
$y(t)={\mathbf{w}}^{H}\mathbf{x}$, for a sparse beamfromer can be rewritten as
$\overset{\circ}{y}(t)=\overset{\circ}{\mathbf{w}}^{H}\mathbf{x}$. The typeset
‘${{\circ}}$’ indicates that the corresponding vector is sparse with few zero
entries. The sparse beamformer $\overset{\circ}{y}(t)$ can also be rewritten,
equivalently, as
$\overset{\circ}{y}(t)=\overset{\circ}{\mathbf{w}}^{H}\\{\overset{\circ}{\mathbf{z}}\odot\mathbf{x}\\}$.
Here, the point-wise multiplication ($\odot$) of the received vector
$\mathbf{x}$ with a sparse selection vector $\overset{\circ}{\mathbf{z}}$ sets
the entries of the received signal to zero which corresponds to the zero
beamforming weights of $\overset{\circ}{\mathbf{w}}$. The entries of
$\overset{\circ}{\mathbf{z}}\in\mathbb{R}^{N}$ are either 1’s or 0’s depending
on whether the corresponding sensor location is active or inactive
respectively.

The above formulation shows that the sparse beamforming filter
$\overset{\circ}{\mathbf{w}}$ can also be viewed as pre-processing the
received signal by point-wise multiplication, prior to applying the
beamforming filter. We analyze how the point-wise multiplication of received
signal with the selection vector can either help or hinder the performance of
the subsequent beamforming filter $\overset{\circ}{\mathbf{w}}$. Denote the
DFT of the input data as $\mathbf{X}=\mathscr{F}(\mathbf{x})$ and
$\mathbf{Z}=\mathscr{F}(\overset{\circ}{\mathbf{z}})$, respectively. Then, the
DFT of the pointwise multiplication of these two vectors is given by the
circular convolution of the correspond DFTs,
$\mathscr{F}(\overset{\circ}{\mathbf{z}}\odot\mathbf{x})=\mathbf{X}\circledast\mathbf{Z}$,
where $\circledast$ denotes the circular convolution. Furthermore, because the
received data vector can be written as
$\mathbf{x}=\alpha\mathbf{s}(\theta_{k})+\sum_{l=1}^{L}\beta_{l}\mathbf{v}(\theta_{l})+\mathbf{n}$,
then by invoking the linearity of the DFT transform, we obtain
$\mathscr{F}(\overset{\circ}{\mathbf{z}}\odot\mathbf{x})=\alpha\mathbf{S}\circledast\mathbf{Z}+\sum_{l=1}^{L}\beta_{l}\mathbf{V}_{l}\circledast\mathbf{Z}+\mathbf{N}.\circledast\mathbf{Z}$.
For an effective sparse beamformer, it is desirable to minimize the
overlapping of the spatial spectrum of the desired source and the spectra of
interfering signals. This action is poised to aid the subsequent beamformer
filtering to effectively suppress the unwanted signals. We propose a design
metric $\Omega(\mathbf{Z})$ based on weighted sum of the spatial spectrum of
the individual interfering signals scaled by the desired signal spatial
spectrum as follows,

$\Omega(\mathbf{Z})=\sum_{l=1}^{L}\\{\alpha^{2}|\mathbf{S}|^{2}\circledast|\mathbf{Z}|^{2}\\}\odot\\{\beta_{l}^{2}|\mathbf{V}_{l}|^{2}\circledast|\mathbf{Z}|^{2}\\}$
(7.8)

It is clear that Eq. 7.8 performs element wise scaling of the interfering
powers in the DFT domain. Therefore, if the interfering signal power, after
convolution through the selection filter, is concentrated in the DFT bins
different from those occupied primarily by the desired signal, then the