chapter[0pt]Chapter :

Sparse Array Beamformer Design for Active and Passive Sensing
by
Syed Ali Hamza
College of Engineering, Villanova University
DOCTORATE OF PHILOSOPHY
Advisor: Moeness Amin

##

Copyright © 2020, Syed Ali Hamza
All Rights Reserved

## STATEMENT BY AUTHOR

This dissertation has been submitted in partial fulfillment of requirements
for an advanced degree at the Villanova University.

Brief quotations from this dissertation are allowable without special
permission, provided that accurate acknowledgment of source is made. Requests
for permission for extended quotation from or reproduction of this manuscript
in whole or in part may be granted by the head of the major department or the
Associate Dean for Graduate Studies and Research of the College of Engineering
when in his or her judgment the proposed use of the material is in the
interests of scholarship. In all other instances, however, permission must be
obtained from the author.

## ACKNOWLEDGEMENTS

This dissertation is the result of my research at Villanova University. The
project described in this thesis was supported in part by National Science
Foundation and Office of Naval Research. Its contents are solely the
responsibility of the author and do not necessarily represent the official
views of the sponsors.

First and foremost, I would like to thank my family. My parents and my
siblings made everything seem so easy, and generously supported me along the
way. A very special gratitude goes out to my friends who made sure I had a
life outside my research.

Many people who I cannot mention individually deserve thanks and appreciation
for their support in the preparation of my dissertation. I would like to
express my gratitude to my advisor, Prof. Moeness Amin, who provided me an
opportunity to work on timely and exciting topics. It would not have been
possible without his unfettered support, guidance and encouragement. Besides
my advisor, I would like to thank Prof. Aboulnasr Hassanien for sharing his
experiences and providing insightful comments during my research. Special
gratitude goes to the rest of my thesis committee, Prof. Bijan Mobasseri and
Prof. Ahmad Hoorfar, for their invaluable support. Also, I am grateful to
Janice Moughan and to the university staff at the International Student Office
for their help in managing administrative tasks, which are always complicated
for me. I thank my fellow labmates for the stimulating discussions inside and
outside the lab.

Thanks to everyone who supported me.

## DEDICATION

This dissertation is lovingly dedicated to my parents and siblings, Maryam,
Samrat and Usama!

###### TABLE OF CONTENTS
Section Page

  1. STATEMENT BY AUTHOR
  2. ACKNOWLEDGEMENTS
  3. DEDICATION
  4. NOMENCLATURE
  5. ABSTRACT
  6. 1 INTRODUCTION AND MOTIVATION
    1. 1.1 Sparse Arrays
    2. 1.2 Main Contributions and Thesis Organization
    3. 1.3 List of publications
      1. 1.3.1 Journal articles
      2. 1.3.2 Conference papers
  7. 2 Optimum Sparse Array Design for Maximizing Signal-to-Noise Ratio in Presence of Local Scatterings
    1. 2.1 Introduction
    2. 2.2 Problem Formulation
    3. 2.3 Gaussian and circular scattering models
    4. 2.4 Optimum sparse array design
    5. 2.5 Simulations
      1. 2.5.1 Gaussian model
      2. 2.5.2 Circular model
    6. 2.6 Conclusion
    7. 2.7 Appendix
  8. 3 Hybrid Sparse Array Beamforming Design for General Rank Signal Models
    1. 3.1 Introduction
    2. 3.2 Problem Formulation
    3. 3.3 Optimum sparse array design
      1. 3.3.1 Fair gain beamforming
      2. 3.3.2 Modified re-weighting for fully augmentable hybrid array
      3. 3.3.3 Symmetric arrays
    4. 3.4 Simulations
      1. 3.4.1 Single point source
      2. 3.4.2  Multiple point sources
      3. 3.4.3  Fully augmentable linear arrays
      4. 3.4.4  Fully augmentable 2D arrays
    5. 3.5 Conclusion
    6. 3.6 Appendix
      1. 3.6.1 Proof of the Conjugate symmetric property of optimal weight vector
  9. 4 Sparse Array Design for Maximizing the Signal-to-Interference-plus-Noise-Ratio by Matrix Completion
    1. 4.1 Introduction
    2. 4.2 Problem Formulation
    3. 4.3 Sparse array design through SCA algorithm
      1. 4.3.1 Hybrid sparse array design
    4. 4.4 Toeplitz matrix completion and Fully augmentable completion through averaging
    5. 4.5 Simulations
      1. 4.5.1 Example comparing both designs
      2. 4.5.2 Monte Carlo design for random scenarios
    6. 4.6 Conclusion
  10. 5 Sparse Array Beamforming Design for Wideband Signal Models
    1. 5.1 Introduction
    2. 5.2 Problem Formulation
      1. 5.2.1 TDL Implementation scheme
      2. 5.2.2 DFT Implementation scheme
    3. 5.3 Optimum sparse array design
      1. 5.3.1 Semidefinite relaxation (SDR) for sparse solution
      2. 5.3.2 Successive convex approximation (SCA)
    4. 5.4 Sparse matrix completion of block Toeplitz matrices
    5. 5.5 Simulations
      1. 5.5.1 Example 1
      2. 5.5.2 Example 2
      3. 5.5.3 Comparison of SDR and SCA under both models
      4. 5.5.4 Practical Considerations for sparse array design
    6. 5.6 Conclusion
  11. 6 Sparse Array Design for Transmit Beamforming
    1. 6.1 Introduction
    2. 6.2 Problem Formulation
    3. 6.3 Sparse array design
      1. 6.3.1 Sparse solution through SDR
      2. 6.3.2 Reweighting sparsity
      3. 6.3.3 Transmit power constraint
    4. 6.4 Simulations
      1. 6.4.1 Example
    5. 6.5 Conclusion
  12. 7 Sparse Array Capon Beamformer Design Availing Deep Learning Approach
    1. 7.1 Introduction
    2. 7.2 Problem Formulation
    3. 7.3 Optimum sparse array design
      1. 7.3.1 Sparse beamformer spectral analysis (SBSA) design
      2. 7.3.2 DNN based learning of the SBSA and enumerated designs
    4. 7.4 Simulations
      1. 7.4.1 Enumerated design
      2. 7.4.2 DNN based SBSA design
      3. 7.4.3 Robust design
      4. 7.4.4 Performance comparisions with state-of-the-art
    5. 7.5 Conclusion
  13. 8 CONCLUSIONS AND RECOMMENDATIONS

###### LIST OF TABLES

  1. 3.1 Proposed algorithm to achieve desired cardinality of optimal weight vector
  2. 4.1 SCA for sparse array beamforming.
  3. 5.1 SDR for the sparse wideband beamformer
  4. 5.2 SCA for the sparse wideband beamformer
  5. 6.1 SDR-Transmit Beamformer Design
  6. 7.1 SBSA Algorithm

###### LIST OF FIGURES

  1. 1.1 (a) Minimum redundancy array (7 elements); (b) Corresponding coarray
  2. 1.2 (a) Nested array (11 elements); (b) Corresponding coarray
  3. 1.3 Reconfigurable array through sensor switching
  4. 2.1 (a) Circular model; (b) Correlation coefficient as a function of lags
  5. 2.2 Output SNR comparison for various array configurations; (a) Gaussian model; (b) circular model. Beampattern of optimum array; (c) Gaussian model; (d) circular model.
  6. 2.3 (a) Worst sparse array (Gaussian); (b) Second best (Gaussian); (c) Optimum array (circular); (d) Worst sparse array (circular); (e) Nested array; (f) Coprime array
  7. 2.4 Output SNR for different arrays vs centre angle.
  8. 3.1 Block diagram of adaptive switched sensor beamformer
  9. 3.2 Output SINR for different array topologies
  10. 3.3 Average Output SINR for different array topologies over $6000$ Monte Carlo trials
  11. 3.4 Array configurations obtained for the point source at the array broadside (a) Optimum (Enumeration) (b) NFSDR-approach (c) Perturbed-NFSDR (d) Worst performing array configuration
  12. 3.5 (a) Antenna array multiple sources (NFSDR-approach) (b) Fair gain $10$ element antenna array (NFSDR-approach) (c) Hybrid $10$ antenna array for multiple desired sources (FSDR)
  13. 3.6 Beampattern for multiple point sources
  14. 3.7 (a) $14$ element antenna array (NFSDR-approach) (b) Hybrid $14$ antenna sparse array ($8$ prefixed, $6$ selected through FSDR) (c) Hybrid $14$ antenna sparse array ($8$ prefixed, $6$ selected through FSDR)
  15. 3.8 Average Output SINR for different array topologies over $3500$ Monte Carlo trials
  16. 3.9 $24$ element antenna sparse array (NFSDR-approach)
  17. 3.10  $24$ element hybrid antenna sparse array ($19$ prefixed, $5$ selected through FSDR)
  18. 3.11  $24$ element worst performing hybrid antenna sparse array ($19$ prefixed, $5$ selected)
  19. 3.12 Beampattern for the antenna array in Fig. 3.10
  20. 3.13 Beampattern for a $6\times 4$ compact rectangular array
  21. 4.1 Block diagram implementing adaptive beamforming and antenna switching
  22. 4.2 (a) Initial configuration; randomly selected 16 antennas from 36 (b) Initial configuration leading to fully augmentable array (c) Freely designed array (d) Hybrid designed array (e) Initial random configuration; 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
  23. 4.3 Average SINR performance of various sparse topologies against desired source DOA for $T=100$ snapshots.
  24. 4.4 Average SINR performance of various sparse topologies against desired source DOA for $T=250$ snapshots.
  25. 4.5 Average SINR performance of various sparse topologies against desired source DOA for $T=1000$ snapshots.
  26. 4.6 Sensor switching comparison vs the free-design and the hybrid design.
  27. 5.1 Block Diagram of sparse array wideband processing.
  28. 5.2 TDL realization of wideband beamforming.
  29. 5.3 DFT implementation of wideband beamforming.
  30. 5.4 Frequency dependent beampattern for the array configuration recovered through convex relaxation.
  31. 5.5 Frequecy dependent beampattern for the compact ULA (Fig. 5.6e).
  32. 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
  33. 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)
  34. 5.8 Performance comparisons of SCA under DFT model.
  35. 5.9 Performance comparisons of SCA under TDL model.
  36. 5.10 Performance comparisons of SDR under DFT model.
  37. 5.11 Performance comparisons of SDR under TDL model.
  38. 5.12 Performance comparisons of the optimum sparse array, the worst performing array and the compact ULA (TDL implementation scheme).
  39. 6.1 Various array configurations
  40. 6.2 Transmit beampattern for the SDR-optimized configuration.
  41. 6.3 Transmit beampattern for the nested array configuration.
  42. 6.4 Transmit beampattern for the compact ULA.
  43. 6.5 Constituent transmit beampatterns for the SDR-optimized configuration.
  44. 6.6 Cross-correlation pattern against the Target 1 for various sparse configurations.
  45. 6.7 Cross-correlation pattern against the Target 2 for various sparse configurations.
  46. 7.1 Block diagram of adaptive switched sensor beamformer
  47. 7.2 Architecture of Deep Neural Network (DNN)
  48. 7.3 Overview of the proposed approach using Deep Neural Network (DNN)
  49. 7.4 Eight element sparse array configuration
  50. 7.5 Lag Redundancy of the sparse array shown in Fig. 7.4
  51. 7.6 DFT of the lag redundancy
  52. 7.7 Power spectrum of the desired signal
  53. 7.8 Explanation of the proposed objective criterion for the optimum array configuration shown in Fig. 7.4
  54. 7.9  Explanation of the proposed objective criterion for the worst possible array configuration
  55. 7.10 Plot of the proposed objective criterion in ascending order
  56. 7.11 Performance comparison enumerated design under unlimited snapshots
  57. 7.12 Performance comparison SBSA design under unlimited snapshots
  58. 7.13 Performance comparison enumerated design under 1000 snapshots
  59. 7.14 Performance comparison SBSA design under 1000 snapshots
  60. 7.15 Performance comparisons with the state-of-the-art

## NOMENCLATURE

CRB | Cramer Rao bound
---|---
CPI | Coherent processing interval
DFT | Discrete Fourier transform
DNN | Deep Neural Network
DOA | Direction of arrival
FOV | Field of view
MLE | Maximum likelihood estimate
MaxSNR | Maximizing signal to noise ratio
MaxSINR | Maximizing signal to interfernce plus noise ratio
MIMO | Multiple input multiple output
MRA | Minimum redundancy array
QCQP | Quadrtically constraint quadratic program
SDR | Semidefinite relaxation
SCA | Successive convex relaxation
TDL | Time delay line
ULA | Uniform linear array

## ABSTRACT

Sparse array design through sensor selection reduces system transceiver
overhead by lowering the hardware costs and processing complexity. Sparse-
based design can potentially improve active and passive sensing in radar,
communications, and underwater acoustics. Sparse array design approaches
include coarse sampling in time, frequency, and space at both the transmitter
(for active sensing) and the receiver. These approaches present a new paradigm
to, for instance, direction-of-arrival (DOA) or Doppler estimation and allow
dealing with more sources than physical sensors.

Sparse sensor placement, with various design objectives, has successfully been
employed in diverse application areas, particularly for enhanced parameter
estimation and receiver performance. The sparse array design criteria are
generally categorized into environment-independent and environment-dependent
performance metrics. The former are largely benign to the underlying
environment and, in principle, seek to maximize the spatial degrees of freedom
by extending the coarray aperture. This enables high resolution DOA estimation
possibly involving more sources than the available physical sensors.
Environment-dependent objectives, on the other hand, consider the operating
conditions characterized by emitters and targets in the array field of view,
in addition to receiver noise. In this regard, applying such objectives
renders the array configuration as well as the array weights time-varying in
response to dynamic and changing environment.

This work is geared towards designing environment-dependent sparse array
beamformer to improve the output signal-to-interference and noise ratio using
both narrowband and wideband signal platforms. This is achieved through low
latency sensor selection technology that 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 transceiver 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
transceiver chains.

One key challenge in implementing the data-dependent approaches is the lack of
knowledge of exact or estimated values of the data autocorrelation function
across the full sparse array aperture. The sparse array design can only have
few active sensors at a time, in essence making it difficult to furnish the
correlation values corresponding to the inactive sensor locations. At the core
of this work is to address the aforementioned issues by devising innovative
solutions using convex optimization and machine learning tools, structured
sparsity concepts, low rank matrix completion schemes and fusing the
environment-dependent and environment-independent deigns by developing a
hybrid approach. Sparse array design is also proposed using the deep neural
network (DNN). The DNN based design paves the way for a successful real-time
nimble implementation of data driven sparse beamformer that efficiently
overcomes the bottlenecks specific to sparse implementations.

Finally, active sparse array design is considered which is critical to
implementing an efficient receiver design for adaptive radar operations. A
desirable transmit beampattern design is achieved which focuses the
transmitted power towards the perceived target locations and, as such,
suppresses 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. This work also addresses another critical
design objective for the transmitter, i.e., to minimize the cross correlation
of the returns from different targets to enable effective adaptive receiver
processing. High target cross correlation can severely deteriorate performance
and impede the performance of adaptive radar operations. This is achieved by
lending a separate beamformer for each target location, such that all
beamformers share a common sparse configuration.

## Chapter 1INTRODUCTION AND MOTIVATION

###  1.1 Sparse Arrays

Planning sensor locations can potentially economize the receiver cost by
curtailing the valuable hardware and computational resources. Sparse sensor
placement, with various design objectives, has successfully been employed in
diverse application areas, particularly for enhanced parameter estimation and
receiver performance [1, 2, 3, 4, 5, 6]. The sparse array design criteria are
generally categorized into environment-independent and environment-dependent
performance metrics. The former are largely benign to the underlying
environment and, in principle, seek to maximize the spatial degrees of freedom
by extending the coarray aperture.The difference coarray of a given array
configuration demonstrates the unique correlation lags that can be exploited
to maximize the degrees-of-freedom (DOF). This enables high resolution
direction of arrival (DOA) estimation possibly involving more sources than the
available physical sensors. Towards this goal, sparse array is interpreted in
the coarray domain to yield a higher number of degrees-of-freedom (DOFs). For
instance, for a given number of physical sensors, the minimum redundancy array
(MRA [7]) (Fig. 1.1a) maximizes the number of consecutive virtual sensors in
the resulting difference coarray as shown in Fig. 1.1b. However, for an
arbitrary number of sensors, the MRA configurations are hard to optimize since
they don’t follow any general expressions. Alternatively, several structured
array configurations have recently been proposed to maximize the contiguous
difference coarray including the coprime arrays and nested arrays [8, 9, 10].
Nested array is easy to construct configuration obtained by combining two
uniform linear subarrays with different interelement and result in a larger
number of consecutive virtual sensors under the coarray equivalence as shown
in Fig. 1.2.

(a)

(b)

Figure 1.1: (a) Minimum redundancy array (7 elements); (b) Corresponding
coarray

(a)

(b)

Figure 1.2: (a) Nested array (11 elements); (b) Corresponding coarray

Environment dependent objectives, on the other hand, consider the operating
conditions characterized by the underlying constellation of emitters and
targets or interferences in the array field of view, in addition to receiver
noise. In this regard, applying such objectives renders the array
configuration as well as the array weights time-varying in response to dynamic
and changing environment. In this thesis, we focus on environment dependent
optimum sparse array beamformer design that maximizes the signal to-
interference and noise ratio (MaxSINR). 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 grid points, spaced
by half wavelength, is limited due to the constraint on the physical aperture.
In this approach, antenna positions are selected from uniformly spaced
locations that are served by a limited number of transceiver chains. The
environment-sensitive 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
reconfigurable arrays [11] depicted in Fig. 1.3. Thereby, the system cost can
significantly be reduced by limiting the number of expensive transceivers
chains.

###  1.2 Main Contributions and Thesis Organization

The work presented in this thesis is geared towards designing environment-
dependent sparse array beamformer to improve the output signal-to-interference
and noise ratio using both narrowband and wideband signal platforms. It
addresses key challenges in implementing the data-dependent approaches
including the lack of knowledge of exact or estimated values of the data
autocorrelation function across the full sparse array aperture. This is
because the sparse array design can only have few active sensors at a time, in
essence making it difficult to furnish the correlation values corresponding to
the inactive sensor locations. At the core of this work is to address the
aforementioned issues by devising innovative solutions using convex
optimization and machine learning tools, structured sparsity concepts, low
rank matrix completion schemes and fusing the environment-dependent and
environment-independent deigns by developing a hybrid approach.

The main contributions of the thesis are organized as follows. Chapters 2
deals with sparse array design to optimally process the source seen through
the local scatterers. Chapter 3 and 4 focus on the MaxSINR narrowband sparse
receive beamformer through the hybrid and matrix completion approaches.
Chapter 5 develops the design of wideband sparse array design through TDL and
DFT implementations. Sparse array active design is investigated in Chapters 6
and Chapter 7 presents DNN based sparse beamformer design, followed by
conclusion.

Figure 1.3: Reconfigurable array through sensor switching

Chapter 2 examines the MaxSNR problem in presence of local scatterings which
may follow specific deterministic or statistical scattering models. It is
shown that if the scatterers assume a Gaussian distribution centered around
the source angular position, the optimum array configuration for maximizing
the SNR is the commonly used uniform linear array (ULA). If the scatterers
circulate the source, the array design is optimized to harness sparse array
topologies with superior performance over ULAs. Simulation results are
presented to show the effectiveness of array configurability in the case of
both Gaussian and circularly spread sources.

In Chapter 3, we consider sparse array design for receive beamforming
achieving maximum signal-to-interference plus noise ratio (MaxSINR) for both
single point source and multiple point sources, operating in an interference
active environment. Unlike existing sparse design methods which either deal
with structured, environment-independent, or non-structured, environment-
dependent arrays, our method is a hybrid approach and seeks a full
augumentable array that optimizes beamformer performance. Thereby, one can in
essence reap the benefits of structured and non-structured arrays. This
paradigm calls for a new aperture design approach that strives to provide
filled co-arrays and, at the same time, be environment-sensitive. This
approach proves important for limited aperture that constrains the number of
possible uniform grid points for sensor placements. The problem is formulated
as quadratically constraint quadratic program (QCQP), with the cost function
penalized with weighted $l_{1}$-norm squared of the beamformer weight vector.
Performance comparisons among the proposed sparse array, the commonly used
uniform arrays, arrays obtained by other design methods, and arrays designed
without the augmentability constraint are provided.

Chapter 4 address the sparse array optimization design requiring to estimate
the data autocorrelations at all spatial lags across the array aperture.
Towards this end, we adopt low rank matrix completion under the semidefinite
Toeplitz constraint for interpolating those autocorrelation values
corresponding to the missing lags. We compare the performance of matrix
completion approach with that of the fully augmentable sparse array design
acting on the same objective function. The optimization tool employed is the
regularized $l_{1}$-norm successive convex approximation (SCA). Design
examples with simulated data are presented using different operating
scenarios, along with performance comparisons among various configurations.

In Chapter 5, we develop sparse array receive beamformer design methods
achieving maximum signal-to-interference plus noise ratio (MaxSINR) for
wideband sources and jammers. Both tapped delay line (TDL) filtering and the
DFT realizations to wideband array processing are considered. The sparse array
configuration design problem is formulated as a quadratically constraint
quadratic program (QCQP) and solved by using SDR (semidefinite relaxation). A
computationally viable approach through SCA (successive convex relaxation) is
also pursued. It is assumed that the sensor configuration remains the same
within the observation time. In radar, this assumption amounts to configuring
the same sparse configuration over the coherent processing interval (CPI). The
notion of mixed $l_{1-q}$ norm regularization is exploited to thrive the group
sparsity to conceive a wideband sparse beamformer. In order to realize an
implementable design, in presence of missing autocorrelation lags, we propose
parameter-free block Toeplitz matrix completion to estimate the received data
correlation matrix across the entire array aperture.

Chapter 6 examines the sparse array design for transmit beamforming. The main
task is to design the beamformer to direct the bulk of the transmitted power
to target locations. This, in turn, enables improved receiver performance
which strives to maximize the signal-to-interference plus noise ratio
(MaxSINR) of the radar returns. In order to realize an environmental-dependent
adaptive design, it is incumbent that the directed signals towards different
targets are maximally mutually independent. This is achieved by lending a
separate beamformer for each target location, such that all beamformers share
a common sparse configuration. It is shown that the proposed approach can
efficiently utilize the available array aperture to achieve the desired
transmitted beampattern characteristics.

In Chapter 7, we consider sparse array design for receive beamforming
achieving maximum signal-to-interference plus noise ratio (MaxSINR) for a
desired point source, operating in a narrowband interference active
environment. The sparse array design methods developed thus far, are either
data driven or rely entirely on the prior knowledge of the interference DOAs
and respective powers. In this chapter, we develop a sparse beamformer
spectral analysis (SBSA) approach, exploiting the prior information of the
interference parameters for implementing a MaxSINR beamformer with superior
performance and low computational complexity. The data-driven design is
essentially conceived by integrating the proposed SBSA design and the Deep
Neural Network (DNN). Towards this goal, the training scenarios are generated
either through enumeration or simulated more expediently by SBSA methodology
for DNN, to learn an effective representation that can perform well in a
downstream task. The DNN effectively approximates the unknown mapping from the
input received correlation matrix and outputs the sparse configuration with
superior interference mitigation capability. The performance of the DNN is
evaluated by the ability to learn the enumerated and SBSA designs. It is shown
that DNN effectively learns the proposed algorithms and, as such, paves the
way for efficient real-time implementation.

Conclusion and recommendations follow at the end.

###  1.3 List of publications

The following publications are the result of this research.

####  1.3.1 Journal articles

  * •

S. Hamza and M. Amin, “Sparse Array Design for Maximizing the Signal-to-
Interference-plus-Noise-Ratio by Matrix Completion,” Digital Signal
Processing, 2020.

  * •

S. Hamza and M. G. Amin, “Hybrid Sparse Array Beamforming Design for General
Rank Signal Models,” IEEE Transactions on Signal Processing, 2019.

  * •

S. Hamza and M. G. Amin, “Sparse Array Beamforming for Wideband Signal
Models,” IEEE Transactions on Aerospace and Electronic Systems (Under review).

  * •

S. Hamza and M. G. Amin, “Sparse Array Beamformer Design Availing Deep
Learning Approach,” IEEE Transactions on Signal Processing (Ready for
submission).

####  1.3.2 Conference papers

  * •

S. Hamza and M. Amin, “Sparse Array Receiver Beamformer Design for Multi-
Functional Antenna,” submitted to EUSIPCO, 2020.

  * •

S. Hamza and M. G. Amin, “Sparse Array Design for Transmit Beamforming,” IEEE
Radar Conference (RadarConf20), 2020.

  * •

S. Hamza and M. G. Amin, “Planar Sparse Array Design for Transmit
Beamforming,” SPIE Defense and Commercial Sensing, 2020.

  * •

S. Hamza and M. G. Amin, “A Method for Optimum Sparse Array Beamforming
Design,” SPIE Defense and Commercial Sensing, 2020.

  * •

S. Hamza and M. G. Amin “Hybrid Sparse Array Design for Under-determined
Models,” ICASSP 2019 - 2019 IEEE International Conference on Acoustics, Speech
and Signal Processing (ICASSP), Brighton, United Kingdom, 2019.

  * •

S. Hamza and M. G. Amin “Sparse Array Design Utilizing Matix Completion,”
Asilomar Conference on Signals, Systems, and Computers, Pacific Grove, CA,
USA, 2019.

  * •

S. Hamza and M. Amin, “Sparse Array DFT Beamformers for Wideband Sources,”
2019 IEEE Radar Conference (RadarConf19), Boston, MA, USA.

  * •

S. Hamza and M. Amin, “Optimum Sparse Array Beamforming for General Rank
Signal Models,” 2018 IEEE Radar Conference (RadarConf18), Oklahoma City, OK,
2018.

  * •

S. Hamza, M. G. Amin and G. Fabrizio “Optimum Sparse Array Design for
Maximizing Signal- to-Noise Ratio in Presence of Local Scatterings,” 2018 IEEE
International Conference on Acoustics, Speech and Signal Processing (ICASSP),
Calgary, AB, 2018.

  * •

S. Hamza and M. G. Amin “Optimum Sparse Array Receive Beamforming for Wideband
Signal Model,” 2018 Asilomar Conference on Signals, Systems, and Computers,
Pacific Grove, CA, USA, 2018.

  * •

S. Hamza and M. G. Amin “Two Dimensional Sparse Array Design of Wideband
Signals for Data Reduction,” SPIE Defense and Commercial Sensing, 2019

## Chapter 2Optimum Sparse Array Design for Maximizing Signal-to-Noise Ratio
in Presence of Local Scatterings

###  2.1 Introduction

Sparse arrays have recently attracted much attention that is motivated by
switched antenna technologies and advances in constrained minimization and
convex optimization techniques. There are several metrics to design sparse
arrays and decide on optimum array configurations. Among those metrics,
maximum signal-to-noise ratio (MaxSNR), maximum signal-to-interference and
noise ratio (MaxSINR), and reduced Cramer-Rao bound (CRB) for direction-of-
arrival (DOA) estimation, yield improved beamforming and direction finding
performance [2, 11, 12, 13, 14, 15].

Designing optimum sparse arrays for MaxSNR strives to maximize the SNR at the
array output for a given source direction-of-arrival (DOA). Depending on the
number of antennas and permissible antenna locations, it has been shown that a
significant performance improvement can be achieved over other commonly used
sparse arrays, including nested and coprime structured array [8, 9, 10]. In
past contributions, point sources have typically been assumed where each
source is characterized by a steering vector and provides a rank-one spatial
covariance matrix at the array receiver. However, depending on the multipath
environments and source signal bandwidth, these steering vectors, along with
the corresponding covariance matrix rank, can significantly change [16, 17,
18, 19, 20].

In this chapter, the effect of the spatial channel on optimum sparse array
beamforming for MaxSNR is examined for the first time. Two models for local
scatterings, namely, the Gaussian model and circular model, are considered.
These scattering models are most suitable for dense urban environment, in
which the signal encounter rich scattering prior to its arrival at the array
receiver [21, 22, 23, 24]. It is shown that the optimum sparse array always
elects a configuration that seeks the highest spatial correlation values
across the antennas. On the other hand for a spatial correlation that is
monotonically decreasing, the sparse array would assume the minimum possible
antenna separation, so as to collect the highest correlation values. This is
accomplished by configuring a ULA. For those scattering models in which the
correlation rises and falls with increased antenna spacing, the optimum MaxSNR
sparse array configuration deviates from a ULA, and positions the antennas
such that their separations are consistent with the highest sensor correlation
values.

We pose the problem as optimally selecting $K$ antennas out of $N$ possible
equally spaced locations on a uniform grid. The antenna selection problem for
maximizing SNR amounts to maximizing the principal eigenvalue of the source
correlation matrix [25]. In order to realize convex relaxation for this NP
hard optimization problem and avoid computational burden of singular value
decomposition for each possible configuration, we maximize the lower bound of
output SNR instead. The lower bound optimization objective is approximated by
Taylor series and formulated as an iterative linear program.

The rest of the chapter is organized as follows: In section 2.2, we formulate
the problem for maximizing the output SNR. The role of array configurability
for MaxSNR for Gaussian and circular scattering models is explained in section
2.3. Section 2.4 deals with the iterative solution of finding optimum array
design. Simulations and conclusion follows at the end.

###  2.2 Problem Formulation

Consider a spatially spread source with $P$ independently scattered components
impinging on a linear array with $N$ uniformly placed antennas. Then, the
signal received at the array at time instant $t$ is given by:

$\mathbf{x}(t)=\sum_{k=1}^{P}(\alpha_{k}(t))\mathbf{a}(\theta_{k})+\mathbf{n}(t),$
(2.1)

where

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

is the steering vector corresponding to the $k$th scatterer with the
direction-of-arrival $\theta_{k}$, $d$ is the inter-element spacing in terms
of wavelengths $\lambda$, $\alpha_{k}(t)$ $\in\mathbb{C}$ represents the
complex amplitude of $k$th scatterer and $\mathbf{n}(t)$ $\in\mathbb{C}^{N}$
represents the additive Gaussian noise with variance $\sigma_{n}^{2}$ at the
receiver output. The received signal $\mathbf{x}(t)$ is linearly combined by
the $N$-antenna beamformer that strives to maximize the output SNR. The output
signal $y(t)$ of the optimum beamformer for maximum SNR is given by [25],

$y(t)=\mathbf{w_{0}}^{H}\mathbf{x}(t),$ (2.2)

with

$\mathbf{w_{0}}=\mathscr{P}\\{\mathbf{R_{n}}^{-1}\mathbf{R}\\}.$ (2.3)

The operator $\mathscr{P}\\{.\\}$ computes the principal eigenvector,
$\mathbf{R}=\mathbf{UR_{s}U}^{H}$ is the received source correlation matrix
with
$\mathbf{U}=[\mathbf{a}({\theta_{1}})\,.\,.\,.\,\mathbf{a}({\theta_{P}})]$ and
$k$, $l$th entry of
$\mathbf{R_{s}}(k,l)=E\\{\alpha_{k}(t)\alpha_{k}^{H}(t)\\}$ for $k=l$ and zero
otherwise. For spatially uncorrelated noise,
$\mathbf{R_{n}}=\sigma_{n}^{2}\mathbf{I}$, we obtain the corresponding optimum
output $SNR_{o}$ as follows:

$\mathbf{w_{0}}=\mathscr{P}\\{\mathbf{R}\\},$ (2.4)
$SNR_{o}=\frac{\mathbf{w_{0}}^{H}\mathbf{R}\mathbf{w_{0}}}{\mathbf{w_{0}}^{H}\mathbf{R_{n}}\mathbf{w_{0}}}=\frac{||\mathbf{R}||_{2}}{\sigma_{n}^{2}}.$
(2.5)

Here, $||.||_{2}$ denotes the spectral norm or the maximum eigenvalue of the
matrix. Equations (2.4) and (2.5) show that the optimum beamformer for MaxSNR
is directly tied to the eigen-structure of the correlation matrix. As such,
there is a need to analyze the correlation matrix under the scattering models.

###  2.3 Gaussian and circular scattering models

Gaussian model assumes that the directions of arrival of the scatterers are
Gaussianly distributed, $\mathscr{N}(\theta_{0},\sigma_{\theta})$, having mean
direction of arrival $\theta_{0}$ and variance $\sigma_{\theta}$.
Consequently, each element of the steering vector would be jointly Gaussian
with zero mean and covariance matrix given by [21],

$\mathbf{R_{g}}_{(\theta_{0},\sigma_{0})}\approx(\mathbf{a}({\theta_{0}})\mathbf{a}^{H}({\theta_{0}}))\circ\mathbf{B}_{(\theta_{0},\sigma_{0})},$
(2.6)

where ‘$\circ$’ denotes Hadamard product and

$\mathbf{B}_{(\theta_{0},\sigma_{0})}(k,l)=e^{-2(\pi\delta(k-l))^{2}\sigma_{0}^{2}cos^{2}(\theta_{0})}.$
(2.7)

Denote $\mathbf{z}\in\\{0,1\\}^{N}$ a selection vector whose entries $0$’s and
$1$’s represents the presence and absence of corresponding antennas
respectively. The steering vector corresponding to antenna selection vector
$\mathbf{z}$ is given by
$\mathbf{a}_{{\theta_{0}}}(\mathbf{z})=\mathbf{a}{{(\theta_{0})}}\odot\mathbf{z}$.
Here ‘$\odot$’ is the element-wise product operator which allows the selection
of antenna elements according to $\mathbf{z}$. Similarly,
$\mathbf{B}_{(\theta_{0},\sigma_{0})}(\mathbf{z})=\mathbf{B}_{(\theta_{0},\sigma_{0})}\odot\mathbf{Z}$
with $\mathbf{Z}=\mathbf{z}\mathbf{z}^{T}$ being the corresponding antenna
selection matrix. Equation (2.6) with selected antennas can be re-written as
follows:

$\mathbf{R_{g}}_{(\theta_{0},\sigma_{0})}(\mathbf{z})\approx(\mathbf{a}_{{\theta_{0}}}(\mathbf{z})\mathbf{a}^{H}_{{\theta_{0}}}(\mathbf{z}))\circ\mathbf{B}_{(\theta_{0},\sigma_{0})}(\mathbf{z}).$
(2.8)

We note that the trace of
$\mathbf{R_{g}}_{(\theta_{0},\sigma_{0})}(\mathbf{z})$ is constant since the
input source power remains the same irrespective of the array configuration.
Accordingly, the sum of eigenvalues is constant for all possible correlation
matrices associated with the $K$ antenna selection problem. To be more
explicit, the problem formulated in Eq. (2.5) can be expressed as:

$\displaystyle\underset{\mathbf{z}}{\text{max}}$
$\displaystyle\quad\quad{||\mathbf{R_{g}}_{(\theta_{0},\sigma_{0})}(\mathbf{z})||_{2}},$
(2.9) $\displaystyle\text{given};$
$\displaystyle\,\sum_{k=1}^{K}v_{\mathbf{z}}(k)=\mathbf{Tr}\,(\mathbf{R_{g}}_{(\theta_{0},\sigma_{0})}(\mathbf{z}))=K\mathbf{Tr}(\mathbf{R_{s}}),$

where $\mathbf{Tr}$ $(.)$ denotes the trace of the matrix, $v_{\mathbf{z}}(k)$
is the $k$th eigenvalue of correlation matrix
$\mathbf{R_{g}}_{(\theta_{0},\sigma_{0})}(\mathbf{z})$. Equations (2.6) and
(2.7) show that the correlation drops monotonically with increased correlation
lag. As shown below, this property compels the optimum sparse array to assume
a ULA with minimum inter-element spacing; hence, the solution does not require
any iteration-based method or enumeration.

Let $\mathbf{R_{g}}_{(\theta_{0},\sigma_{0})}(\mathbf{u})$ be the correlation
matrix for ULA ‘$\mathbf{u}$’ and
$\mathbf{R_{g}}_{(\theta_{0},\sigma_{0})}(\mathbf{s})$ be the correlation
matrix associated with the sparse ‘$\mathbf{s}$’ configuration with the same
number of antennas, $K$. The $k$th eigenvalue $v_{\mathbf{z}M}(k)$ of
$\mathbf{R}^{M}_{\mathbf{g}(\theta_{0},\sigma_{0})}(\mathbf{z})$ is related to
its corresponding eigenvlaue $v_{\mathbf{z}}(k)$ of
$\mathbf{R_{g}}_{(\theta_{0},\sigma_{0})}(\mathbf{z})$ by [26],

$v_{\mathbf{z}M}(k)=v^{M}_{\mathbf{z}}(k),\,\,\,\,\forall\,M\geq 0.$ (2.10)

For the Gaussian spatial channel, $\mathbf{Tr}$
$(\mathbf{R}^{M}_{\mathbf{g}(\theta_{0},\sigma_{0})}(\mathbf{u}))>\mathbf{Tr}\,(\mathbf{R}^{M}_{\mathbf{g}(\theta_{0},\sigma_{0})}(\mathbf{s}))$
(proof in section 2.7) along with Eq. (2.10), yields

$\sum_{k=1}^{K}v^{M}_{\mathbf{u}}(k)>\sum_{k=1}^{K}v^{M}_{\mathbf{s}}(k),\,\,\,\,\,\forall\,M\geq
2.$ (2.11)

From Eq. (2.11), it can be readily shown that
$max\,(v_{\mathbf{u}}(k))>max\,(v_{\mathbf{s}}(k))$. Here, we make use of the
fact that all the eigenvalues of the correlation matrices are greater or equal
to zero.

(a)

(b)

Figure 2.1: (a) Circular model; (b) Correlation coefficient as a function of
lags

Therefore, for the Gaussian scattering model where the correlation function is
monotonically decreasing with sensors spacing, the optimum sparse array would
always cluster with minimum spatial separation, configuring a ULA.

The correlation between consecutive sensors for the circular model is given by
[27],

$r_{c}(\theta_{0},\sigma_{0})=\frac{1}{P}\sum_{i=0}^{P-1}e^{-j2\pi(\delta(k-l))cos(\theta_{0}+\theta_{i})},$
(2.12)

where $r_{c}(\theta_{0},\sigma_{0})$ is the $k,l$th element of the correlation
matrix $\mathbf{R_{c}}_{(\theta_{0},\sigma_{0})}$ and $\theta_{i}$’s are
circularly distributed around the source as shown in Fig. 2.1a. Contrary to
Gaussian model, the sensor data correlation in circular case shows oscillatory
behaviour (Fig. 2.1b) as a function of lags (Eq. (2.12)). We can, however,
bound the upper and lower limits of the optimum SNR as follows:

$\frac{\mathbf{Tr}\,(\mathbf{R_{c}}_{(\theta_{0},\sigma_{0})}(\mathbf{w}))}{K}\leq
SNR_{o}\leq\mathbf{Tr}\,(\mathbf{R_{c}}_{(\theta_{0},\sigma_{0})}(\mathbf{o})).$
(2.13)

$\mathbf{R_{c}}_{(\theta_{0},\sigma_{0})}(\mathbf{o})$ and
$\mathbf{R_{c}}_{(\theta_{0},\sigma_{0})}(\mathbf{w})$ are the optimum
‘$\mathbf{o}$’ and worst ‘$\mathbf{w}$’ array correlation matrices,
respectively. In the optimal case, the eigenvalues are maximally spread,
whereas the worst possibility for MaxSNR arises when all the eigenvalues are
equal. We also note that Eq. (2.11) in fact determines the eigen-spread of the
correlation matrix asymptotically. It can be shown that this equation remains
valid for circular correlation matrix for some $\zeta$ sufficiently large,
such that
$\sum_{k=1}^{K}v^{M}_{\mathbf{o}}(k)>\sum_{k=1}^{K}v^{M}_{\mathbf{s}}(k),\,\,\,\,\,\forall\,M\geq\zeta$.
Therefore, finding the optimum configuration amounts to maximizing
$\sum_{k=1}^{K}v^{M}_{\mathbf{z}}(k)$ or equivalently, Tr
($\mathbf{R}^{M}_{\mathbf{c}(\theta_{0},\sigma_{0})}(\mathbf{z})$) for any
$M\geq\zeta$, over all possible configurations. Though maximizing Tr
($\mathbf{R}^{M}_{\mathbf{c}(\theta_{0},\sigma_{0})}(\mathbf{z})$) is
computationally less expensive than maximizing the principal eigenvalue, yet
it is highly computationally involved. Therefore, in the next section we
resort to lower bound relaxation to design the optimum configuration.

###  2.4 Optimum sparse array design

Following the approach in [20], we assume that we have an estimate of
$\mathbf{R_{(\theta_{0},\sigma_{0})}}$, which is the full antenna array source
correlation matrix. Then, the problem in Eq. (2.9) can be rewritten as
follows:

$\displaystyle\underset{\mathbf{z}}{\text{max}}$
$\displaystyle||\mathbf{R_{(\theta_{0},\sigma_{0})}(z)}||_{2},$ (2.14) s.t.
$\displaystyle||\mathbf{z}||_{0}=K.$

Here, $||.||_{0}$ determines the cardinality of selection vector $\mathbf{z}$.
Given $\mathbf{e_{0}}$, the principal eigenvector corresponding to the full
antenna array, we approximate the thinned vector
$\mathbf{e_{0}}(\mathbf{z})/||\mathbf{e_{0}}(\mathbf{z})||_{2}$ as the
principal eigenvector of the selected $K$-element subarray $\mathbf{z}$ [28].
The problem in Eq. (2.14) can then be approximated by:

$\displaystyle\underset{\mathbf{z}}{\text{max}}$
$\displaystyle\frac{\mathbf{e_{0}}^{H}(\mathbf{z})\mathbf{R_{(\theta_{0},\sigma_{0})}}(\mathbf{z})\mathbf{e_{0}}(\mathbf{z})}{||\mathbf{e_{0}}(\mathbf{z})||_{2}^{2}},$
(2.15) s.t. $\displaystyle||\mathbf{z}||_{0}=K.$

This approximation represents a lower bound of optimum SNR. Define,
$\tilde{\mathbf{R}}_{\theta,\sigma_{0}}=\mathbf{R}_{(\theta_{0},\sigma_{0})}\circ(\mathbf{e_{0}}\mathbf{e_{0}}^{H})$
and $\tilde{\mathbf{e_{o}}}=\mathbf{e^{*}_{o}}\circ\mathbf{e_{o}}$. Equation
(2.15) can be rephrased as follows:

$\displaystyle\underset{\mathbf{z}}{\text{max}}$
$\displaystyle\,\,\,\,\frac{\mathbf{z}^{T}\mathbf{\tilde{R}_{\theta,\sigma_{0}}z}}{\mathbf{z}^{T}\mathbf{\tilde{e_{0}}}},$
(2.16) s.t. $\displaystyle\,\,||\mathbf{z}||_{1}=K,$
$\displaystyle\,\,0\leq\mathbf{z}\leq 1.$

The constraint in Eq. (2.15) is relaxed to affine equality constraint
($||.||_{1}$ denotes $l^{1}$-norm) and a box constraint, but the objective
function still remains non-convex. Therefore, we resort to iterative first
order Taylor approximation as follows:

$\displaystyle\underset{\mathbf{z}}{\text{max}}$
$\displaystyle\quad\quad\frac{-\mathbf{z}^{iT}\mathbf{\tilde{R}_{\theta,\sigma_{0}}z}^{i}+2\mathbf{z}^{iT}\mathbf{\tilde{R}_{\theta,\sigma_{0}}z}}{\mathbf{z}^{T}\mathbf{\tilde{e_{0}}}},$
(2.17) s.t. $\displaystyle\quad\quad||\mathbf{z}||_{1}=K,$
$\displaystyle\quad\quad 0\leq\mathbf{z}\leq 1.$

Here, $i$ is the iteration number. This linear fractional program (LFP) can be
turned into LP by simple change of variables,
$\alpha=1/\mathbf{z}^{T}\mathbf{\tilde{e_{0}}}$ and
$\mathbf{v}=\bf{z}/\mathbf{z}^{T}\mathbf{\tilde{e_{0}}}$ as follows [29],

$\displaystyle\underset{\mathbf{v},\alpha}{\text{max}}$
$\displaystyle\quad\quad{-\mathbf{z}^{iT}\mathbf{\tilde{R}_{\theta,\sigma_{0}}z}^{i}\alpha+2\mathbf{z}^{iT}\mathbf{\tilde{R}_{\theta,\sigma_{0}}v}},$
(2.18) s.t.
$\displaystyle\quad\quad\mathbf{1}^{T}\mathbf{v}-K\alpha=0,\,\,\mathbf{\tilde{e_{0}}}^{T}\mathbf{v}=1,$
$\displaystyle\quad\quad\mathbf{v}\geq 0,\,\,\mathbf{v}-\alpha\leq
0,\,\,\alpha\geq 0.$

yielding, the estimate of the selection vector $\mathbf{z}=\mathbf{v}/\alpha$.

###  2.5 Simulations

For both scattering models, we select $K=9$ sensors from $N=21$ possible
equally spaced locations with inter-element spacing of $\lambda/2$. The source
SNR is $0$ dB.

(a)

(b)

(c)

(d)

Figure 2.2: Output SNR comparison for various array configurations; (a)
Gaussian model; (b) circular model. Beampattern of optimum array; (c) Gaussian
model; (d) circular model.

####  2.5.1 Gaussian model

Figure 2.2a plots the optimum SNR for all possible array configurations in
ascending order of output SNR for Gaussian spread source with centre angle of
900 and variance of 50. As expected, the optimum array emerges as a ULA with
output SNR of 8 dB. The lower bound relaxation is also depicted in Fig. 2.2a
and is shown to offer a good metric in the underlying case. The ULA has more
than 3 dB advantage over the worst array configuration having less than 5 dB
output SNR. The worst array configuration is shown in the Fig. 2.3a where ‘.’
and ‘$\times$’ represent the presence and absence of sensor respectively. We
also observe that if sensor malfunction prevents a contiguous uniformly spaced
antenna array configuration, the optimum sparse array opts to minimally
stretch, incorporating the next closest antenna position, as shown in the Fig.
2.3b. In order to simulate this case, we set antenna 9 as a faulty antenna.
The output SNR corresponding to this new configuration is 7.9 dB which is 0.1
dB less than the optimum array configuration. This lower SNR is the price paid
by including a smaller correlation value corresponding to antenna position 10
compared to that of antenna position 9. The output SNR corresponding to
coprime and nested sparse arrays, as depicted in Fig. 2.2a, are significantly
less as compared to the ULA. Figure 2.2c shows the optimum beampattern
corresponding to the different configurations with ULA giving the widest main
lobe with the highest gain possible at the scatterer’s centre. Moreover, the
sidelobes for ULA are significantly lower as compared to other sparse arrays
which is highly desirable.

####  2.5.2 Circular model

Figure 2.2b shows the scenario for circular scattering model with a single
source at the broadside with the spatial spread of $30^{0}$. It shows that the
optimum sparse array (shown in Fig. 2.3c) has SNR of $5.68$ dB, whereas the
worst sparse array (shown in Fig. 2.3d) has output SNR of $3$ dB, which is
more than 2.5 dB down as compared to the optimum array topology.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 2.3: (a) Worst sparse array (Gaussian); (b) Second best (Gaussian); (c)
Optimum array (circular); (d) Worst sparse array (circular); (e) Nested array;
(f) Coprime array

It is informative to compare the performance of optimum array with the ULA,
which is a de facto array configuration in many applications. The ULA gives
output SNR of 5.28 dB which is 0.4 dB lower than the optimum performance. The
significant difference however lies in the beampattern of the two arrays, as
shown in Fig. 2.2d. Contrary to the optimum configuration, the ULA attempts to
maximize the output SNR by placing a null exactly in the centre of the
scatterer beam which is highly undesirable. Figure 2.2b also shows that the
optimum sparse array has a clear advantage over coprime and nested array
topologies in terms of output SNR. This is beacuse the optimum array manages
wider mainlobe with higher gain where the scatterers are most dense (Fig.
2.2d). Figure 2.4 shows that better performance of the optimum sparse array is
more pronounced at the broadside, whereas the ULA is the optimum array
configuration for DOAs near the array end-fire location. It can be seen that
the performance of the optimum array and sub optimum sparse arrays differ
significantly over a wide field of view.

###  2.6 Conclusion

This chapter considered optimum sparse array configuration for maximizing the
beamformer output SNR for a single source that is seen to the receiver through
its local scatterers. It is shown that for the Gaussian local scattering
model, the correlation is weakened monotonically across the receiver antennas.
As such, the optimum configuration, in seeking to capture the highest spatial
correlation values, becomes the ULA. We showed that for a circular local
scattering model, the optimum sparse array loses uniformity in quest of
including the high correlation values corresponding to large antenna
separations. In both cases, we solved the optimization problem both
iteratively and by enumerations and showed strong agreement between the two
methods.

Figure 2.4: Output SNR for different arrays vs centre angle.

###  2.7 Appendix

Proof of the result used in Eq. (2.11):

$\displaystyle\mathbf{Tr}\,(\mathbf{R}^{M}_{\mathbf{g}(\theta_{0},\sigma_{0})}(\mathbf{z}))$
$\displaystyle\approx\mathbf{Tr}\,((\mathbf{a}_{{\theta_{0}}}(\mathbf{z})\mathbf{a}^{H}_{{\theta_{0}}}(\mathbf{z})\circ\mathbf{B}_{(\theta_{0},\sigma_{0})}(\mathbf{z}))^{M})$
(2.19)
$\displaystyle=\mathbf{Tr}\,(\mathbf{a}_{{\theta_{0}}}(\mathbf{z})\mathbf{a}^{H}_{{\theta_{0}}}(\mathbf{z})\circ\mathbf{B}^{M}_{(\theta_{0},\sigma_{0})}(\mathbf{z}))$
$\displaystyle=\mathbf{Tr}\,(\mathbf{B}^{M}_{(\theta_{0},\sigma_{0})}(\mathbf{z})).$

For Gaussian model,
$\mathbf{B}_{(\theta_{0},\sigma_{0})}(\mathbf{u})\geq\mathbf{B}_{(\theta_{0},\sigma_{0})}(\mathbf{s})>0$.
Here, ‘$\geq$’ means element wise comparison and strict equality holds only
for diagonal entries. This implies,

$\displaystyle\mathbf{B}^{M}_{(\theta_{0},\sigma_{0})}(\mathbf{u})$
$\displaystyle>\mathbf{B}^{M}_{(\theta_{0},\sigma_{0})}(\mathbf{s}),\,\,\,\,\quad\quad\forall\,M\geq
2$ (2.20)
$\displaystyle\mathbf{Tr}\,(\mathbf{B}^{M}_{(\theta_{0},\sigma_{0})}(\mathbf{u}))$
$\displaystyle>\mathbf{Tr}\,(\mathbf{B}^{M}_{(\theta_{0},\sigma_{0})}(\mathbf{s})).$

Combining (2.19) and (2.20), we have,

$\mathbf{Tr}\,(\mathbf{R}^{M}_{\mathbf{g}(\theta_{0},\sigma_{0})}(\mathbf{u}))>\mathbf{Tr}\,(\mathbf{R}^{M}_{\mathbf{g}(\theta_{0},\sigma_{0})}(\mathbf{s}))\quad\forall\,M\geq
2$

∎

## Chapter 3Hybrid Sparse Array Beamforming Design for General Rank Signal
Models

###  3.1 Introduction

Sparse array design through sensor selection reduces system receiver overhead
by lowering the hardware costs and processing complexity. It finds
applications in sensor signal processing for communications, radar, sonar,
satellite navigation, radio telescopes, speech enhancement and ultrasonic
imaging [1, 2, 3, 4, 5, 6]. One primary goal in these applications is to
determine sensor locations to achieve optimality for some pre-determined
performance criteria. This optimality includes minimizing the mean radius of
the confidence ellipsoid associated with the estimation error covariance
matrix [5], and lowering the Cramer Rao bound (CRB) for angle estimation in
direction finding problem [30]. The receiver performance then depends largely
on the operating environment, which may change according to the source and
interference signals and locations. This is in contrast to sparse arrays whose
configurations follow certain formulas and seek to attain high extended
aperture co-arrays. The driving objective, in this case, is to enable
direction of arrival (DOA) estimation of more sources than physical sensors.
Common examples are structured arrays such as nested and coprime arrays [7, 8,
10].

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 often
assumed that the number of grid points, spaced by half wavelength, is
unlimited. However, in many applications, there is a constraint on the spatial
extent of the system aperture. In this case, a structured array, in seeking to
maximize the number of spatial autocorrelation lags, may find itself placing
sensors beyond the available physical aperture. The problem then becomes that
of dual constraints, one relates to the number of sensors, and the other to
the number of grid-points.

With a limited aperture constraint invoked, few sensors may in fact be
sufficient to produce a desirable filled structured co-array, even with
narrowband assumption and without needing wideband or multiple frequencies
[31]. In this case, any additional sensors, constitute a surplus that can be
utilized to meet an environment-dependent performance criterion, such as
maximum signal-to-interference and noise ratio (SINR). Thereby, one can in
essence reap the benefits of structured and non-structured arrays. This
paradigm calls for a new aperture design approach that strives to provide
filled co-arrays and, at the same time, be environment-sensitive. This hybrid
design approach is the core contribution of this chapter.

Sparse sensor design has thoroughly been studied to economize the receive
beamformer [32, 33, 34, 35, 36, 37, 15, 38, 39, 40, 41, 42, 43, 44]. However,
in contrast to MaxSINR design, the main focus of the efforts, therein, was in
achieving desirable beampattern characteristics with nominal sidelobe levels,
since the sparse beamformer is susceptible to high sidelobe levels. For
example, an array thinning design was proposed for sidelobe minimization in
[36] by starting from a fully populated array and sequentially removing
sensors in a systematic manner. Instead, the sparse array design presented in
[37] to optimize the peak sidelobe level involves a joint design of sensor
locations and their corresponding beamforming weights. A beampattern matching
design explained in [15] can effectively recover sparse topologies through an
iterative cyclic approach. Additionally, global optimization tools such as
Genetic Algorithms/Simulated Annealing and convex relaxation schemes based on
re-weighted $l_{1}$-norm minimization have been rigorously exploited in sensor
selection problem for synthesizing a user-specified receive beampattern
response [39, 40, 41, 42, 43, 44].

In environment-dependent array design, signal power estimation and enhancement
in an interference active environment 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]. It is noted that with
sparse array, 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 finding maximum SINR over all
possible sparse array configurations. Maximum signal to noise ratio (MaxSNR)
and MaxSINR have been shown to yield significantly efficient beamforming with
performance depending mainly on the positions of the sensors as well as the
locations of sources in the field of view (FOV) [11, 13, 14].

In this chapter, we consider a bi-objective optimization problem, namely
achieving the filled co-array and maximizing the SINR. The proposed technique
enjoys key advantages as compared to state-of-the-art sparse aperture design,
namely, (a) It does not require any a priori knowledge of the jammers
directions of arrival and their respective power which is implicitly assumed
in previous contributions [20, 48, 12]. As such, it is possible to directly
work on the received data correlation matrix (b) It extends to spatial spread
sources in a straightforward way.

Figure 3.1: Block diagram of adaptive switched sensor beamformer

The proposed hybrid approach first determines a prefixed sparse array that
results in a filled co-array with minimum number of sensors. This prefixed
configuration could be a minimum redundancy array (MRA) [7], nested or coprime
array configuration that fills the aperture under consideration with minimal
sensors, allowing maximum degrees of freedom for SINR maximization. This
prefixed sensor configuration can be achieved by an optimization problem
involving the minimum number of sensors spanning a pre-determined aperture.
However, for the scope of this chapter, the prefixed configuration is set by
MRA or other structured arrays. The remaining sensors after forming the
prefixed array are utilized to maximize the SINR. The cascade nature of the
proposed hybrid approach is relatively simpler than the ultimate design
approach that produces the optimum filled sparse array that maximizes SINR.
Environment-dependent array design lowers the hardware complexity by reducing
the expensive transmission chains through sensor switching as shown in the
block diagram in Fig. 3.1. The proposed hybrid approach, however, has an added
advantage of offering a simplified sensor switching in time-varying
environment. This is attributed to large number of fixed location sensors
which would always remain non-switched, irrespective of the sources and
interferences in the FOV.

The proposed hybrid approach is particularly permissive as the number $N$ of
possible sensor locations increases. To further clarify, it is noted that
sparse arrays having $N$ available sensors can typically span a filled array
aperture of the order of $\mathcal{O}(N(N-1)/2)$ [8]; conversely, given an
aperture spanning $N$ possible sensor locations, only $\mathcal{O}(N^{1/2})$
sensors are sufficient to synthesize a fully augmentable array design. This
emphasizes the fact that as the possible aperture size increases, then
relatively few sensors are required to meet the full augmentability condition,
leaving more degrees of freedom to optimize for SINR enhancement. The hybrid
approach also lends itself to more desirable beampattern characteristics by
maintaining minimum spacing between sensor elements. It is important to note
that having fully augmentable arrays not only provide the benefits of
simplified sensor switching and improved identifiability of large number of
sources, but also they ensure the availability of full array data covariance
matrix essential to carry optimized SINR configuration [49], [50]. Therefore,
the proposed simplified hybrid sensor switching architecture ensures the
knowledge of global data statistics at all times, in contrast to previous
efforts in [51, 52, 53] that sort to optimize data dependent microphone
placement viz a viz transmission power. The proposed methodology therein
targets a different objective function and primarily relies on local
heuristics. In this case, sensor switching comes with an additional
implementation overhead, in an attempt to recursively match the performance
offered by the knowledge of global statistics.

We consider the problem of MaxSINR sparse arrays with limited aperture for
both single and higher rank signal correlation matrices. The case of single
rank correlation matrix arises when there is one desired source signal in the
FOV, whereas the case of higher rank signal model occurs for spatially spread
source. The problem is posed as optimally selecting $P$ sensors out of $N$
possible equally spaced grid points. Maximizing SINR amounts to maximizing the
principal eigenvalue of the product of the inverse of data correlation matrix
and the desired source correlation matrix [25]. Since it is an NP hard
optimization problem, we pose this problem as QCQP with weighted $l_{1}$-norm
squared to promote sparsity. The re-weighted $l_{1}$-norm squared relaxation
is effective for reducing the required sensors and minimizing the transmit
power for multicast beamforming [2]. We propose a modified re-weighting matrix
based iterative approach to control the sparsity of the optimum weight vector
so that $P$ sensor fully augmentable hybrid array is finally selected. This
modified regularization re-weighting matrix based approach incorporates the
prefixed structured array assumption in our design and works by minimizing the
objective function around the presumed prefixed array.

The rest of the chapter is organized as follows: In the next section, we state
the problem formulation for maximizing the output SINR under general rank
signal correlation matrix. Section 3.3 deals with the optimum sparse array
design by semidefinite relaxation (SDR) and proposed modified re-weighting
based iterative algorithm of finding $P$ sensor fully augmentable hybrid
sparse array design. In section 3.4, with the aid of number of design
examples, we demonstrate the usefulness of fully augmentable arrays achieving
MaxSINR and highlight the effectiveness of the proposed methodology for sparse
array design. Concluding remarks follow at the end.

###  3.2 Problem Formulation

Consider $K$ desired sources 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)=\sum_{k=1}^{K}(\alpha_{k}(t))\mathbf{s}(\theta_{k})+\sum_{l=1}^{L}(\beta_{l}(t))\mathbf{v}(\theta_{l})+\mathbf{n}(t),$
(3.1)

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

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

The inter-element spacing is denoted by $d$, ($\alpha_{k}(t)$, $\beta_{l}(t))$
$\in\mathbb{C}$ denote the complex amplitudes of the incoming baseband signals
[54]. The additive Gaussian noise $\mathbf{n}(t)$ $\in\mathbb{C}^{N}$ has a
variance of $\sigma_{n}^{2}$ at the receiver output. 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),$ (3.3)

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

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

For statistically independent signals, the desired source correlation matrix
is given by,
$\mathbf{R}_{s}=\sum_{k=1}^{K}\sigma^{2}_{k}\mathbf{s}(\theta_{k})\mathbf{s}^{H}(\theta_{k})$,
where, $\sigma^{2}_{k}=E\\{\alpha_{k}(t)\alpha_{k}^{H}(t)\\}$. Likewise, we
have 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 (3.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},$ (3.5) s.t.
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R}_{s}\mathbf{w}\geq 1.$

It is noted that the equality constraint in (4) is relaxed in (5) due to the
inclusion of the constraint as part of the objective function, and as such,
(5) converges to the equality constraint. Additionally, the optimal solution
in (5) is invariant up to uncertainty of the absolute powers of the sources of
interest. Accordingly, the relative power profile of the sources of interest
would suffice. For a single desired point source, this implies that only the
knowledge of the DOA of the desired source is sufficient rather than the exact
knowledge of the desired source correlation matrix. Similarly, neither the
source power nor the average power of the scatterers is required in (5) for
spatially spread sources when the spatial channel model, such as the Gaussian
or circular, is assumed [21]. 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].

There exists a closed form solution of the above optimization problem 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 (3.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}\\}.$
(3.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 matrix. It is to be noted that the rank of the desired source
signal correlation matrix equals $K$, i.e. the cardinality of the desired
sources.

###  3.3 Optimum sparse array design

The problem of locating the maximum principal eigenvalue among all the
correlation matrices associated with $P$ sensor selection is a combinatorial
optimization problem. The constraint optimization (3.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},$ (3.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}$. We assume that we have an estimate of all the filled co-array
correlation lags corresponding to the correlation matrix of the full aperture
array. The problem expressed in (3.7) can be relaxed to induce the sparsity in
the beamforming weight vector $\mathbf{w}$ without placing a hard constraint
on the specific cardinality of $\mathbf{w}$, as follows [55];

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

Here, $||.||_{1}$ is the sparsity inducing $l_{1}$-norm and $\mu$ is a
parameter to control the desired sparsity in the solution. Even though the
relaxed problem expressed in (3.8) is not exactly similar to that of (3.7),
yet it is well known that $l_{1}$-norm regularization has been an effective
tool for recovering sparse solutions in many diverse formulations [56, 57].
The problem in $(\ref{b2_ch3})$ can be penalized instead by the weighted
$l_{1}$-norm function which is a well known sparsity promoting formulation
[58],

$\displaystyle\underset{\mathbf{w\in\mathbb{C}}^{N}}{\text{minimize}}$
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R_{xx}}\mathbf{w}+\mu(||(\mathbf{b}^{i}\circ|\mathbf{w}|)||_{1}),$
(3.9) s.t. $\displaystyle\quad\mathbf{w}^{H}\mathbf{R_{s}}\mathbf{w}\geq 1.$

where, “$\circ$” denotes the element wise product, “$|.|$” is the modulus
operator and $\mathbf{b}^{i}\in\mathbb{R}^{N}$ is the regularization re-
weighting vector at the $i$th iteration. Therefore, $(\ref{c2_ch3})$ is the
sequential optimization methodology, where the regularization re-weighting
vector $\mathbf{b}^{i}$ is typically chosen as an inverse function of the
beamforming weight vector obtained at the previous iteration. This, in turn,
suppresses the sensors corresponding to smaller beamforming weights, thereby
encouraging sparsity in an iterative fashion. The weighted $l_{1}$-norm
function in $(\ref{c2_ch3})$ is replaced by the $l_{1}$-norm squared function
which does not alter the regularization property of the weighted $l_{1}$-norm
function [2],

$\displaystyle\underset{\mathbf{w\in\mathbb{C}}^{N}}{\text{minimize}}$
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R_{xx}}\mathbf{w}+\mu(||(\mathbf{b}^{i}\circ|\mathbf{w}|)||^{2}_{1}),$
(3.10) s.t. $\displaystyle\quad\mathbf{w}^{H}\mathbf{R}_{s}\mathbf{w}\geq 1.$

The semidefinite formulation (SDP) of the above problem can then be realized
by re-expressing the quadratic form,
$\mathbf{w}^{H}\mathbf{R_{xx}}\mathbf{w}=$Tr$(\mathbf{w}^{H}\mathbf{R_{xx}}\mathbf{w})=$Tr$(\mathbf{R_{xx}}\mathbf{w}\mathbf{w}^{H})=$
Tr$(\mathbf{R_{xx}}\mathbf{W})$, where Tr(.) is the trace of the matrix.
Similarly, the regularization term
$||(\mathbf{b}^{i}\circ|\mathbf{w}|)||^{2}_{1}=(|\mathbf{w}|^{T}\mathbf{b}^{i})((\mathbf{b}^{i})^{T}|\mathbf{w}|)=\mathbf{|w|}^{T}\mathbf{B}^{i}\mathbf{|w|}=$Tr$(\mathbf{B}^{i}\mathbf{|W|})$.
Here, $\mathbf{W}=\mathbf{w}\mathbf{w}^{H}$ and
$\mathbf{B}^{i}=\mathbf{b}^{i}(\mathbf{b}^{i})^{T}$ is the regularization re-
weighting matrix at the $i$th iteration. Utilizing these quadratic expressions
in (3.10) yields the following problem [59, 60, 2],

$\displaystyle\underset{\mathbf{W\in\mathbb{C}}^{N\times
N},\mathbf{\tilde{W}\in\mathbb{R}}^{N\times N}}{\text{minimize}}$
$\displaystyle\quad\text{Tr}(\mathbf{R_{xx}}\mathbf{W})+\mu\text{Tr}(\mathbf{B}^{i}\mathbf{\tilde{W}}),$
(3.11) s.t. $\displaystyle\quad\text{Tr}(\mathbf{R}_{s}\mathbf{W})\geq 1,$
$\displaystyle\quad\mathbf{\tilde{W}}\geq|\mathbf{W}|,$
$\displaystyle\quad\mathbf{W}\succeq 0,\,\text{Rank}(\mathbf{W})=1.$

The function “$|.|$” returns the absolute values of the entries of the matrix,
“$\geq$” is the element wise comparison and “$\succeq$” denotes the
generalized matrix inequality. The auxiliary matrix
$\mathbf{\tilde{W}}\in\mathbb{R}^{N\times N}$ implements the weighted
$l_{1}$-norm squared regularization along with the re-weighting matrix
$\mathbf{B}^{i}$. The rank constraint in (3.11) is non convex and therefore
need to be removed. The rank relaxed approximation works well for the
underlying problem. In case, the solution matrix is not rank $1$, we can
resort to randomization to harness rank $1$ approximate solutions [61].
Alternatively, one could minimize the nuclear norm of $\mathbf{W}$, as a
surrogate for $l_{1}$-norm in the case of matrices, to induce sparsity in the
eigenvalues of $\mathbf{W}$ and promote rank one solutions [62, 63]. The
resulting rank relaxed semidefinite program (SDR) is given by;

$\displaystyle\underset{\mathbf{W\in\mathbb{C}}^{N\times
N},\mathbf{\tilde{W}\in\mathbb{R}}^{N\times N}}{\text{minimize}}$
$\displaystyle\quad\text{Tr}(\mathbf{R_{xx}}\mathbf{W})+\mu\text{Tr}(\mathbf{B}^{i}\mathbf{\tilde{W}}),$
(3.12) s.t. $\displaystyle\quad\text{Tr}(\mathbf{R}_{s}\mathbf{W})\geq 1,$
$\displaystyle\quad\mathbf{\tilde{W}}\geq|\mathbf{W}|,$
$\displaystyle\quad\mathbf{W}\succeq 0.$

In general, QCQP is NP hard and cannot be solved in polynomial time. The
formulation in (3.12) is clearly convex, in terms of unknown matrices, as all
the other correlation matrices involved are guaranteed to be positive
semidefinite. The sparsity parameter $\mu$ largely determines the cardinality
of the solution beamforming weight vector. To ensure $P$ sensor selection,
appropriate value of $\mu$ is typically found by carrying a binary search over
the probable range of $\mu$. After achieving the desired cardinality, the
reduced size thinned correlation matrix $\mathbf{R_{xx}}$ is formed
corresponding to the non-zero values of $\mathbf{\tilde{W}}$. The reduced
dimension SDR is now solved with setting $\mu=0$, yielding optimum beamformer
$\mathbf{w}_{o}=\mathscr{P}\\{\mathbf{W}\\}$.

####  3.3.1 Fair gain beamforming

The optimization in (3.12) strives to incorporate the signal from all the
directions of interest while optimally removing the interfering signals. To
achieve this objective, the optimum sparse array may show leaning towards a
certain source of interest, consequently, not offering fair gain towards all
sources. In an effort to promote equal gain towards all sources, we put a
separate constraint on the power towards all desired sources as follows;

$\displaystyle\underset{\mathbf{W\in\mathbb{C}}^{N\times
N},\mathbf{\tilde{W}\in\mathbb{R}}^{N\times N}}{\text{minimize}}$
$\displaystyle\quad\text{Tr}(\mathbf{R_{xx}}\mathbf{W})+\mu\text{Tr}(\mathbf{B}^{i}\mathbf{\tilde{W}}),$
(3.13) s.t. $\displaystyle\quad\text{Tr}(\mathbf{R}_{k}\mathbf{W})\geq
1,\,\,\,\,\forall k\in(1,2,3...K)$
$\displaystyle\quad\mathbf{\tilde{W}}\geq|\mathbf{W}|,$
$\displaystyle\quad\mathbf{W}\succeq 0.$

Here, $\mathbf{R}_{k}=\mathbf{s}(\theta_{k})\mathbf{s}^{H}(\theta_{k})$ is the
rank $1$ covariance matrix associated with the source at DOA $(\theta_{k})$.
However, the above SDR can be solved to an arbitrary small accuracy $\zeta$,
by employing interior point methods involving the worst case complexity of
$\mathcal{O}\\{$max$(K,N)^{4}N^{(1/2)}\log(1/\zeta)\\}$ [61].

Table 3.1: Proposed algorithm to achieve desired cardinality of optimal weight
vector

0: Data correlation matrix $\mathbf{R_{xx}}$, $N$, $P$, look direction DOA’s
$\theta_{k}$, hybrid selection vector $\mathbf{z}$.

0: $P$ sensor beamforming weight vector $\mathbf{w}_{o}$, Initialize
$\epsilon$.Initialize $\mu_{lower}$, $\mu_{upper}$ (Initializing lower and
upper limits of sparsity parameter range for binary search for desired
cardinality $P$)FSDR: Initialize $\mathbf{B=zz}^{T}$. NFSDR: For optimum array
design without the augmentability constraint, initialize $\mathbf{z}$ to be
all ones vector, $\mathbf{B=zz}^{T}$ (all ones matrix). Perturbed-NFSDR:
Locate the sensor $i$ such that, if not selected, results in the minimum
compromise of the objective function. Perturb $\mathbf{z}$ at position $i$,
$\mathbf{z}(i)=\mathbf{z}(i)+\gamma$, afterwards calculating
$\mathbf{B=zz}^{T}$.

while (Cardinality of $\mathbf{w}_{o}$ $\neq$ $P$) do

Update $\mu$ through binary search.

for (Typically requires five to six iterations) do

Run the SDR of (3.12) or (3.13) (Fair gain case).

Update the regularization weighting matrix $\mathbf{B}$ according to (3.15).

end for

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}\\}$.

return $\mathbf{w}_{o}$

####  3.3.2 Modified re-weighting for fully augmentable hybrid array

For the case without the full augmentability constraint the regularization re-
weighting matrix $\mathbf{B}$ is initialized unweighted i.e. by all ones
matrix and the $m,n$th element of B is iteratively updated as follows [58],

$\mathbf{B}_{m,n}^{i+1}=\frac{1}{|\mathbf{W}_{m,n}^{i}|+\epsilon}.$ (3.14)

The parameter $\epsilon$ avoids the unwanted case of division by zero, though
its choice is fairly independent to the performance of the iterative algorithm
but at times very small values of $\epsilon$ can result in the algorithm
getting trapped in the local minima. For the hybrid array design, we
initialize the re-weighting matrix instead as an outer product of hybrid
selection vector $\mathbf{z}$. The hybrid selection vector $\mathbf{z}$ is an
$N$ dimensional vector containing binary entries of zero and one, where, zeros
correspond to the pre-selected sensors and ones correspond to the remaining
sensors to be selected. Hence, the cardinality of $\mathbf{z}$ is equal to the
difference of the total number of available sensors and the number of pre-
selected sensors. This modified re-weighting approach ensures that the sensors
corresponding to the pre-selected configuration is not penalized as part of
the regularization, hence, $\mathbf{B=zz}^{T}$, thrives solutions that
incorporate the pre-selected array topology. The modified penalizing weight
update for the hybrid array design can be expressed as;

$\mathbf{B}^{i+1}=(\mathbf{zz}^{T})\varoslash({|\mathbf{W}^{i}|+\epsilon}).$
(3.15)

The symbol “$\varoslash$” denotes element wise division. For the hybrid
design, (15) is proposed with appropriate selection of $\mathbf{z}$, as
explained above, and hereafter referred to as the Fixed SDR (FSDR). The array
designed without the augmentability consideration is the special case of (15)
with $\mathbf{z}$ being an all ones vector and the algorithm is subsequently
regarded as the Non-Fixed SDR (NFSDR). The pseudo-code for controlling the
sparsity of the optimal weight vector $\mathbf{w}_{o}$ is summarized in Table
3.1.

####  3.3.3 Symmetric arrays

The solution of the NFSDR formulation is penchant for symmetric arrays in the
case of symmetric initialization vector $\mathbf{z}$. The plausible
explanation is as follows. We first show that the beamforming weights which
maximizes the output SINR for symmetric sparse array topologies are conjugate
symmetric w.r.t. the array center.

######  Proposition 1.

The conjugate symmetry of the optimal weight vector holds for centro-symmetric
sparse array configurations in case of the general rank desired source model.

(Refer to the section 3.6 for the proof.) ∎ We observe that the regularized
cost function does not invoke sparsity until after the first few initial
iterations. Consequently, the initial solutions of the semidefinite program
has symmetric coefficients as the NFSDR seeks near optimal solutions which are
analytically shown to be conjugate symmetric. Moreover, the iterative sparsity
enhancing formulation introduces sparsity by penalizing the beamforming weight
vector according to (3.15), where, it only accounts the magnitude of the
beamforming weights. Therefore, at each iteration the regularization re-
weighting matrix $\mathbf{B}$ happens to penalize the solution weight vector
in a symmetric fashion around the array center. Thus, the iterative NFSDR
sparse solution favors symmetric configurations by discarding corresponding
symmetric sensors simultaneously. Though, the symmetric configuration can be
suitable for certain applications [64], and can have desirable performance,
yet, it reduces the available degrees of freedom. Therefore, to avoid
curtailing the available degrees of freedom, we perturb the re-weighting
regularization matrix $\mathbf{B}$ at the initial iteration, as follows. From
$N$ prospective locations, find the sensor position, which if not selected,
results in the least compromise of the objective function performance.
Corresponding to the aforementioned position, set the regularization weight to
be relatively high through perturbation by parameter $\gamma$. By so doing, we
resolve the issues arising from the symmetric regularization re-weighting
matrix. This modified algorithm is henceforth referred to as the perturbed-
NFSDR and is detailed in Table 3.1.

Figure 3.2: Output SINR for different array topologies

###  3.4 Simulations

In this section, we show the effectiveness of the proposed techniques for the
sparse array design for MaxSINR. We initially examine the proposed approach
for array configurability by considering arbitrary arrays without the
augmentability constraint. In the later examples, we demonstrate the
effectiveness of fully augmentable hybrid sparse array design through linear
and 2D arrays. We focus on the EM modality, and as such we use antennas for
sensors.

####  3.4.1 Single point source

We select $P=8$ antennas from $N=16$ possible equally spaced locations with
inter-element spacing of $\lambda/2$. Figure 3.2 shows the output SINR for
different array configurations for the case of single desired point source
with its DOA varying from $40^{0}$ to $140^{0}$. The interfering signals are
located at $20^{0}$ and $\pm 10^{0}$ degree apart from the desired source
angle. To explain this scenario, suppose that the desired source is at
$60^{0}$, we consider the respective directions of arrival of the three
interfering signals at $40^{0}$, $50^{0}$ and $70^{0}$. The SNR of the desired
signal is $10$ dB, and the interference to noise ratio (INR) is set to $10$ dB
for each scenario. The input SINR is $-4.9$ dB. The upper and lower limit of
the sparsity parameter $\mu$ is set to $1.5$ and $0.01$ respectively,
$\gamma=0.05$ and $\epsilon=0.1$. From the Fig. 3.2, it is evident that the
NFSDR-approach performs close to the performance of the optimum array found by
exhaustive search ($12870$ possible configurations), which has very high
computational cost attributed to expensive singular value decomposition (SVD)
for each enumeration. Moreover, the perturbed-NFSDR algorithm results in
comparable or better performance. Except for the slightly lower performance at
the desired source of DOA of $70^{0}$, we observe that for the desired source
of DOA at $90^{0}$, $100^{0}$ and $130^{0}$, the perturbed-NFSDR recovers a
sparse array with better performance than the NFSDR-approach. For the other
DOAs, the perturbed-NFSDR recovers the same symmetric configuration as that
recovered by the NFSDR-approach. This emphasizes that the perturbed-NFSDR does
not eliminate the possibility of symmetric solutions and optimizes over both
the symmetrical and unsymmetrical array configurations. On average, the
proposed algorithms takes six to seven iterations to converge to the optimum
antenna locations; hence, offering considerable savings in the computational
cost. It is of interest to compare the optimum sparse array performance with
that of compact uniform linear array (ULA). It can be seen from Fig. 3.2, that
the optimum sparse array offers considerable SINR advantage over the compact
ULA for all source angles of arrival. The ULA performance degrades severely
when the source of interest is more towards the array end-fire location. In
this case, the ULA fails to resolve and cancel the strong interferers as they
are located close to the desired source.

Figure 3.3: Average Output SINR for different array topologies over $6000$
Monte Carlo trials

(a)

(b)

(c)

(d)

Figure 3.4: Array configurations obtained for the point source at the array
broadside (a) Optimum (Enumeration) (b) NFSDR-approach (c) Perturbed-NFSDR (d)
Worst performing array configuration

For the case of the desired source at the array broadside, the maximum output
SINR of the optimum array found through enumeration (Fig. 3.4a) is $19$ dB.
The optimum array design obtained through the NFSDR-approach yields an output
SINR of $18.6$ dB, which is $0.4$ dB less than the corresponding SINR of the
optimum array found through exhaustive search. The broadside source arrays are
shown in the Fig. 3.4 (where green-filled circle indicates antenna present
whereas gray-filled circle indicates antenna absent). The sparse array
recovered through NFSDR-approach is clearly a symmetric configuration (Fig.
3.4b). Figure 3.4c shows the sparse array found after addressing the symmetry
bias by the approach explained in Section 3.3.3. The SINR for this non-
symmetric configuration is $18.7$ dB and is suboptimal merely by $0.3$ dB. It
is worth noticing that the worst performing sparse array configuration (Fig.
3.4d) comparatively engages larger array aperture than the optimum array found
through enumeration (Fig. 3.4a), yet it has an output SINR as low as $2.06$
dB. This emphasizes the fact that if an arbitrary sparse array structure is
employed, it could degrade the performance catastrophically irrespective of
the occupied aperture and could perform far worst than the compact ULA, which
offers modest output SINR of $15.07$ dB for the scenario under consideration.

##### Monte Carlo Simulation

To thoroughly examine the performance of the proposed algorithms under random
interfering environments, we perform 6000 Monte Carlo simulations. For this
purpose, the desired source DOA is fixed with SNR of $10$ dB, and eight
interferences are generated which are uniformly distributed anywhere from
$20^{0}$ to $160^{0}$. The INRs of these sources are uniformly drawn from $10$
dB to $15$ dB. We choose 8 antennas out of 16 possible locations. The upper
and lower limit of the sparsity parameter $\mu$ is set to 3 and 0.01
respectively, $\gamma=0.1$ and $\epsilon=0.05$. The performance curves are
shown in Fig. 3.3 for the desired source fixed at $11$ different DOAs varying
from $40^{0}$ to $140^{0}$. On average, the proposed perturbed-NFSDR algorithm
consistently provided superior SINR performance. However, this performance is
around $1.2$ dB suboptimal than the average SINR computed through enumeration.
The average SINR performance of the perturbed-NFSDR algorithm is around $0.35$
dB better than the proposed NFSDR-approach. This is because the degrees of
freedom are limited by the inherent array symmetry enforced by the re-weighted
optimization scheme. The performances of the proposed algorithms are compared
with the design methodology proposed in [48], which relies on the a priori
knowledge of the interference steering vectors and respective powers. It is
noted that in the underlying scenario the design in [48] is more than $1$ dB
suboptimal than the proposed algorithms and around $2$ dB suboptimal as
compared to the performance upper bound. The algorithm in [48] relies on
successive linear approximation of the objective function as opposed to the
quadratic implementation of the SDR, thereby suffering in performance. The
SINR performances for the compact ULA, sparse ULA and randomly employed sparse
topology are also shown in the Fig. 3.3, further highlighting the utility of
sparse array design.

(a)

(b)

(c)

Figure 3.5: (a) Antenna array multiple sources (NFSDR-approach) (b) Fair gain
$10$ element antenna array (NFSDR-approach) (c) Hybrid $10$ antenna array for
multiple desired sources (FSDR)  Figure 3.6: Beampattern for multiple point
sources

(a)

(b)

(c)

Figure 3.7: (a) $14$ element antenna array (NFSDR-approach) (b) Hybrid $14$
antenna sparse array ($8$ prefixed, $6$ selected through FSDR) (c) Hybrid $14$
antenna sparse array ($8$ prefixed, $6$ selected through FSDR)

####  3.4.2  Multiple point sources

For the multiple point sources scenario, consider three desired signals
impinging from DOAs $40^{0}$, $65^{0}$ and $90^{0}$ with SNR of $0$ dB each.
Unlike the example in 3.4.1, we set four strong interferers with INR of $30$
dB are operational at DOAs $50^{0}$, $60^{0}$, $120^{0}$ and $150^{0}$. In so
doing, we analyze the robustness of the proposed scheme under very low input
SINR of $-36.02$ dB. We select $10$ antennas out of $18$ available slots. The
optimum array recovered through convex relaxation is shown in Fig. 3.5a. This
configuration results with an output SINR of $11.85$ dB against SINR of $12.1$
dB for the optimum configuration found through enumeration. For the fair gain
beamforming, we apply the optimization of (13) and the array configuration for
MaxSINR for the fair gain beamforming is shown in Fig 3.5b. The output SINR
for the fair beamforming case is $11.6$ dB which is slightly less than the
optimum array without the fair gain consideration ($11.85$ dB). However, the
advantage of fair beamforming is well apparent from the beampatterns in both
cases as shown in Fig 3.6, where the gain towards the source at $65^{0}$ is
around $4.24$ dB higher than the case of optimum array without the fair gain
consideration. The maximum gain deviation for the fair gain case is $3.5$ dB
vs. $8$ dB variation without the fair gain consideration. The SINR of compact
ULA is compromised more than $3$ dB as compared to the optimum sparse array
(Fig. 3.5a) obtained through the proposed methodology. This improved
performance is due to the optimum sparse array smartly engaging its degrees of
freedom to eradicate the interfering signals while maintaining maximum gain
towards all sources of interest.

####  3.4.3  Fully augmentable linear arrays

Consider selecting $14$ antennas out of $24$ possible available locations with
antenna spacing of $\lambda/2$. A desired source is impinging from DOA of
$30^{0}$ and SNR of $10$ dB, whereas narrowband jammers are operating at
$20^{0}$, $40^{0}$ and $120^{0}$ with INR of $10$ dB each. The range of $\mu$
and other parameters are the same as in 3.4.1. Optimum array configuration
(Fig. 3.7a) achieved through convex relaxation (NFSDR-approach) has an output
SINR of $21.29$ dB as compared to SINR of $21.32$ dB of an optimum array
recovered through enumeration ($1.96*10^{6}$ possible configurations). It
should be noted that the array recovered without filled co-array constraint is
not essentially fully augmentable as is the case in the optimum array (Fig.
3.7a) which clearly has missing co-array lags.

In quest of fully augmentable array design we prefix 8 antennas (red elements
in Fig. 3.7b) in a minimum redundancy array (MRA) configuration over 24
uniform grid points. This provides 24 consecutive autocorrelation lags. We
are, therefore, left with six antennas to be placed in the remaining 16
possible locations ($8008$ possible configurations). We enumerated the
performance of all possible hybrid arrays associated with underlying MRA
configuration and found the output SINR ranges from $18.1$ dB to $21.3$ dB.
Figure 3.7b shows the configuration recovered through the proposed approach
which has an output SINR of $20.96$ dB. The proposed approach thus recovers
the hybrid sparse array with performance close to the best possible, moreover
it approximately yields $3$ dB advantage over worst fully augmentable hybrid
array. As MRAs are not unique we started with a different 8 element MRA
structured array (red elements in Fig. 3.7c), to further reinforce the
effectiveness of fully augmentable sparse arrays. The dynamic performance
range associated with MRA of Fig. 3.7c, is from $17.59$ dB to $21.3$ dB. The
performance in this case is very similar to the aforementioned MRA
configuration with the output SINR of $21.08$ dB for the hybrid array
recovered through proposed methodology (Fig. 3.7c). The maximum possible SINR
offered by both hybrid arrays is $21.3$ dB which is extremely close to SINR
performance of $21.32$ dB offered by the optimum array without augmentability
constraint.

Figure 3.8: Average Output SINR for different array topologies over $3500$
Monte Carlo trials

##### Monte Carlo Simulation

We generate 3500 Monte Carlo simulations for comparison between the
performance of the sparse arrays that are designed freely and that of sparse
array design involving full augmentability constraint. We choose $16$ antennas
out of $24$ available locations. The desired source DOA is fixed with SNR of
$10$ dB as in 3.4.1. We assume twelve narrowband interferences drawn uniformly
from $20^{0}$ to $160^{0}$ with respective INRs uniformly distributed from
$10$ dB to $15$ dB. For binary search, the upper and lower limit of the
sparsity parameter $\mu$ is 5 and 0.01 respectively and $\epsilon=0.1$, for
all 3500 scenarios. Fig. 3.8 shows the average SINR performance, where the
proposed NFSDR-approach is only $0.57$ dB suboptimal relative to the optimum
array found through enumeration (choosing 16 antennas out of 24 involves
$735471$ prospective configurations). However, this performance is achieved by
sparse arrays without ensuring the augmentabilty constraint. Therefore, we
prefix $8$ antennas in MRA topology, namely Hybrid $1$ and Hybrid $2$ prefix
configurations, shown in red circles in Figs. 3.7b and Fig. 3.7c respectively.
The MaxSINR performance, found by enumeration, for either of the underlying
hybrid topologies competes very closely as evident in Fig. 8. The average
MaxSINR (found by enumeration), under both prefixed configurations, is only
compromised by $0.28$ dB relative to the average MaxSINR performance offered
without the augmentability constraint. It is noted that in this case, the
possible sparse configurations are drastically reduced from $735471$ to
$12870$ (choose the remaining $8$ antennas from the remaining $16$ possible
locations due to prefixing $8$ antennas a priori). It is clear from Fig. 3.8
that the proposed FSDR algorithm successfully recovers the hybrid sparse array
with an average SINR performance loss of $0.8$ dB. We remark that the
performance of the hybrid sparse array is still slightly better than the
optimum sparse array receive beamforming proposed in [48] that assumes the
knowledge of jammers’ steering vectors and utilizes all the available degrees
of freedom, unlike the hybrid sparse array.

####  3.4.4  Fully augmentable 2D arrays

Consider a $7\times 7$ planar array with grid pacing of $\lambda/2$ where we
place 24 antennas at 49 possible positions. A desired source is impinging from
elevation angle $\theta=50^{0}$ and azimuth angle of $\phi=90^{0}$. Here,
elevation angle is with respect to the plane carrying the array rather than
reference from the zenith. Four strong interferes are impinging from
($\theta=20^{0}$, $\phi=30^{0}$), ($\theta=40^{0}$, $\phi=80^{0}$),
($\theta=120^{0}$, $\phi=75^{0}$) and ($\theta=35^{0}$, $\phi=20^{0}$). The
INR corresponding to each interference is $20$ dB and SNR is set to $0$ dB.
There are of the order of $10^{14}$ possible 24 antenna configurations, hence
the problem is prohibitive even by exhaustive search. Therefore, we resort to
the upper bound of performance limits to compare our results. Here, we utilize
the fact that the best possible performance occurs when the interferes are
completely canceled in the array output and the output SINR in that case would
equal the array gain offered by the 24 element array which amounts to $13.8$
dB. Figure 3.9 shows the optimum antenna locations recovered by the proposed
NFSDR-approach. The output SINR for this configuration is $13.68$ dB which is
sufficiently close to the ideal performance. It should be noted that again the
array recovered in the Fig. 3.9 is not fully augmentable as it is missing
quiet a few correlation lags.

We now introduce the condition of full augmentability by placing 19 antennas
in nested lattice configuration [65] to form a filled co-array (red elements
in Fig. 3.10). The rest of five available antennas can be placed in the
remaining 30 possible locations hence resulting in approximately $1.5*10^{5}$
possibilities. Figure 3.10 shows the hybrid sparse geometry recovered by FSDR
algorithm and offers SINR of $13.25$ dB which is around $0.4$ dB less than the
optimum array. The performance range of the hybrid arrays associated with the
structured nested lattice array ranges from $11.4$ dB to $13.38$ dB (found
through exhaustive search). In this regard the FSDR algorithm finds the hybrid
sparse array with the performance degradation of little more than $0.1$ dB.
The worst performing hybrid array (Fig. 3.11) has an output SINR of $11.4$ dB
and is around $2$ dB lower than the best performing hybrid sparse array.

It is of interest to compare the performance of aforementioned sparse arrays
with a compact $2$D array. For this purpose, we chose a $6\times 4$
rectangular array. The compact rectangular array performs very poorly in the
underlying scenario and has an output SINR of $7.8$ dB which is more than $5$
dB down from the hybrid sparse array recovered through the semidefinite
relaxation. This performance degradation is very clear from the beampattern of
both arrays shown in Figs. 3.12 and 3.13 (normalized beampattern in dB). In
the case of the hybrid sparse array recovered through FSDR (Fig. 3.10), the
target has the maximum gain towards the direction of interest with minimum
gain simultaneously towards all unwanted DOAs (Fig. 3.12). In contrast, it is
clear from Fig. 3.13 that the beampattern of the compact rectangular array
could not manage maximum gain towards the direction of interest while
effectively rejecting the interfering signals. Although, the $6\times 5$ and
$6\times 6$ compact arrays utilize $6$ and $12$ additional sensors, yet the
respective output SINRs of $9.04$ dB and $11$ dB are considerably suboptimal
relative to the proposed solutions. It is noted that adding 18 additional
sensors resulting in $7\times 6$ rectangular array has an output SINR of
$12.87$ dB. Still, the 24 element free-design as well as the hybrid design
outperform the compact $42$ element rectangular array. However, a $49$ element
fully populated $7\times 7$ rectangular array has an output SINR of $14.37$
dB, which is marginal improvement given the SINR of 24 element designed
topologies. The hybrid array also appears to be more robust as it has higher
dynamic performance range threshold ($11.4$ dB). The performance of
arbitrarily designed arrays is more prone to deteriorate catastrophically even
far worse than that of the compact uniform or rectangular arrays.

Figure 3.9: $24$ element antenna sparse array (NFSDR-approach)

We also test the fully augmentable array design for the case of multiple point
source scenario described previously (Section 3.4.2). The hybrid array
recovered through proposed methodology is shown in the Fig. 3.5c (red elements
showing the $7$ element MRA). The output SINR is $11.566$ dB and is
sufficiently close to the performance achieved through enumeration.

Figure 3.10:  $24$ element hybrid antenna sparse array ($19$ prefixed, $5$
selected through FSDR) Figure 3.11:  $24$ element worst performing hybrid
antenna sparse array ($19$ prefixed, $5$ selected)

###  3.5 Conclusion

This chapter considered fully augmentable sparse array configurations for
maximizing the beamformer output SINR for general rank desired signal
correlation matrices. It proposed a hybrid sparse array design that
simultaneously considers co-array and environment-dependent objectives. The
proposed array design approach uses a subset of the available antennas to
obtain a fully augmentable array while employing the remaining antennas for
achieving the highest SINR. It was shown that the hybrid design is data driven
and hence practically viable, as it ensures the availability of the full data
correlation matrix with a reasonable trade off in the SINR performance. We
applied the modified re-weighting QCQP which proved effective in recovering
superior SINR performance for hybrid sparse arrays in polynomial run times.
The proposed approach was extended for fair gain beamforming towards multiple
sources. We solved the optimization problem by both the proposed algorithms
and enumeration and showed strong agreement between the two methods.

Figure 3.12: Beampattern for the antenna array in Fig. 3.10 Figure 3.13:
Beampattern for a $6\times 4$ compact rectangular array

###  3.6 Appendix

####  3.6.1 Proof of the Conjugate symmetric property of optimal weight vector

The correlation matrix $\mathbf{R}$ for centro-symmetric arrays have a
conjugate persymmetric structure such that [66]:

$\mathbf{TR^{{}^{\prime}}T}=\mathbf{R}$ (3.16)

Here $\\{^{\prime}\\}$ is the conjugate operator and $\mathbf{T}$ is the
transformation matrix which flips the entries of a vector upside down by left
multiplication;

$\mathbf{T}=\begin{bmatrix}0&\dots&0&0&1\\\ 0&\dots&0&1&0\\\
\vdots&\dots&&\vdots\\\ 1&\dots&0&&0\end{bmatrix}$

The optimal weight vector which maximizes the SINR is given by;

$\mathbf{w}_{o}=\mathscr{P}\\{\mathbf{R_{s^{{}^{\prime}}}}^{-1}\mathbf{R_{s}}\\}$
(3.17)

where,

$\\{\mathbf{R_{s^{{}^{\prime}}}}^{-1}\mathbf{R_{s}}\\}\mathbf{w}_{o}=\Lambda_{max}\mathbf{w}_{o}$
(3.18)

Using the relation in (3.16), (3.18) can be re-expressed as follows,

$\displaystyle\\{\mathbf{(TR^{{}^{\prime}}_{s^{{}^{\prime}}}T)^{-1}}\mathbf{(TR^{{}^{\prime}}_{s}T)}\\}\mathbf{w}_{o}$
$\displaystyle=\Lambda_{max}\mathbf{w}_{o}$ (3.19)
$\displaystyle\\{\mathbf{T^{-1}(R^{{}^{\prime}}_{s^{{}^{\prime}}})^{-1}T^{-1}}\mathbf{(TR^{{}^{\prime}}_{s}T)}\\}\mathbf{w}_{o}$
$\displaystyle=\Lambda_{max}\mathbf{w}_{o}$

Multiplying both sides by $\mathbf{T}$ and applying the conjugate operator,

$\\{\mathbf{R_{s^{{}^{\prime}}}}^{-1}\mathbf{R_{s}}\\}\mathbf{T}\mathbf{w}^{{}^{\prime}}_{o}=\Lambda_{max}\mathbf{T}\mathbf{w}^{{}^{\prime}}_{o}$
(3.20)

From (3.20), we note, that $\mathbf{T}\mathbf{w}_{o}^{{}^{\prime}}$ is also
the principal eigenvector associated with matrix
$\mathbf{R_{s^{{}^{\prime}}}}^{-1}\mathbf{R_{s}}$. Since the principal
eigenvector of the positive definite Hermitian matrix is unique up to the
scalar complex multiplier, this directly implies that;

$\mathbf{w}_{o}=\mathbf{T}\mathbf{w}_{o}^{{}^{\prime}}$

∎

## Chapter 4Sparse Array Design for Maximizing the Signal-to-Interference-
plus-Noise-Ratio by Matrix Completion

###  4.1 Introduction

Sensor selection schemes strive to optimize various performance metrics while
curtailing valuable hardware and computational resources. Sparse sensor
placement, with various design objectives, has successfully been employed in
diverse application areas, particularly for enhanced parameter estimation and
receiver performance [1, 2, 4, 44, 5, 15, 6, 64]. The sparse array design
criteria are generally categorized into environment-independent and
environment-dependent performance metrics. The former are largely benign to
the underlying environment and, in principle, seek to maximize the spatial
degrees of freedom by extending the co-array aperture. This enables high
resolution direction of arrival (DOA) estimation possibly involving more
sources than the available physical sensors [7, 8, 10, 31, 67]. Environment-
dependent objectives, on the other hand, consider the operating conditions
characterized by emitters and targets in the array field of view, in addition
to receiver noise. In this regard, applying such objectives renders the array
configuration as well as the array weights time-varying in response to dynamic
and changing environment.

In this chapter, we focus on optimum sparse array design for receive
beamforming that maximizes the output signal-to-interference and noise ratio
(MaxSINR) [68, 47, 60, 69, 70]. It has been shown that optimum sparse array
beamforming involves both array configuration and weights, and can yield
significant dividends in terms of SINR performance in presence of desired and
interfering sources [11, 13, 14, 20, 12, 48, 28]. However, one key challenge
in implementing the data-dependent approaches, like Capon beamforming, is the
need to have the exact or estimated values of the data autocorrelation
function across the full sparse array aperture [47, 25]. This underlying
predicament arises as the sparse array design can only have few active sensors
at a time, in essence making it difficult to furnish the correlation values
corresponding to the inactive sensor locations.

To address the aforementioned problem, we propose in this chapter a matrix
completion strategy assuming a single desired source and multiple interfering
sources. This strategy permits the interpolation of the missing data
correlation lags, thus enabling optimum “thinning” of the array for MaxSINR.
The low rank matrix completion has been utilized successfully in many
applications, including the high-resolution direction of arrival estimation.
We compare the matrix completion strategy to the hybrid sparse array design
that has been recently introduced and which also provides full spatial
autocorrelation function for array thinning [71, 72]. The fundamental thrust
of the hybrid design is to pre-allocate some of the available sensors in such
a way so as to ensure that all possible correlation lags can be estimated. In
this case, the difference between the available sensors and those pre-
allocated can be utilized for maximum SINR. In essence, the hybrid design
locks few spatial degrees of freedom in an attempt to making the full
autocorrelation matrix available to carry out the array optimization at all
times. In that sense, it is a hybrid between structured and non-structured
arrays. With pre-allocated sensors, the design approach offers a simplified
antenna switching as the environment changes. In contrast, the matrix
completion-based design is not tied in to any pre-allocated sensor position
and, therefore, has the ability to optimize over all the available sensor
locations. However, low rank matrix completion is a pre-processing step that
is required every time we decide on sensor selection as the environment
changes. This significantly adds to the overall overhead and computational
complexity. We examine both approaches using estimated autocorrelation
function, in lieu of its exact values, and compare their respective
performances under different settings and degrees of freedom.

Figure 4.1: Block diagram implementing adaptive beamforming and antenna
switching

It is worth noting that MaxSINR sparse array design using either is an
entwined optimization problem that jointly optimizes the beamforming weights
and determines the active sensor locations. The optimization is posed as
finding $P$ sensor positions out of $N$ possible equally spaced grid points
for the highest SINR performance. It is known that maximizing the SINR is
equivalent to the problem of maximizing the principal eigenvalue of the
product of the inverse of data correlation matrix and the desired source
correlation matrix [25]. However, the maximum eigenvalue problem over all
possible sparse topologies is a combinatorial problem and is challenging to
solve in polynomial times. To alleviate the computational complexity of
exhaustive combinatorial search, we pose this problem as successive convex
approximation (SCA) with reweighted $l_{1}$-norm regularization to promote
sparsity in the final solution.

To proceed with the SCA optimization, it is essential to input the algorithm
with the full data correlation matrix. For the hybrid design, all the
correlation lags are available and, therefore, we resort to averaging across
the available correlation lags to harness a Toepltiz matrix estimate of the
received data. On the other hand, a sparse array designed freely without
preallocating sensor locations necessitates the use of low rank matrix
completion to interpolate the missing lags and subsequently applying the SCA
optimization [73]. The word ‘free’ implies no preset position of any of the
sensors involved. It is shown that the matrix completion is an effective
approach to accomplish the MaxSINR sparse design. The performance of matrix
completion can potentially surpass the hybrid design at the expense of more
involved sensor switching and additional computational complexity stemming
from the Toeplitz interpolation of the missing correlation lags. The overall
system implementation is depicted in Fig. 4.1.

The rest of the chapter is organized as follows: In the next section, we state
the problem formulation for maximizing the output SINR. Section 4.3 details
the SCA for arrays designed freely alongside the hybrid design approach and
the associated modified SCA optimization. Section 4.4 explains the matrix
completion approach. In section 4.5, with the aid of Monte Carlo simulations,
we compare the performance of hybrid-designed arrays viz a viz freely-designed
arrays in a limited snapshot environment. Concluding remarks follow at the
end.

###  4.2 Problem Formulation

We consider an emitter source in the presence of narrowband interfering
signals. The signals impinge on a uniform grid of $N$ linear elements with the
inter-element spacing of $d$ and the received signal is given by,

$\mathbf{x}(n)=b_{s}(n)\mathbf{s}(\theta)+\sum_{k=1}^{I}b_{ik}(n)\mathbf{i}(\theta_{k})+\mathbf{v}(n)$
(4.1)

The sampling instance is $n$, $I$ denotes the number of interfering sources
and ($b_{s}(n)$, $b_{ik}(n))$ $\in\mathbb{C}$ are the baseband signals for the
source and interferences, respectively. The steering vector corresponding to
the direction of arrival of desired source $\mathbf{s}({\theta})$
$\in\mathbb{C}^{N}$ is given by,

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

The interference steering vectors $\mathbf{i}({\theta_{k}})$ are similarly
defined. The additive noise $\mathbf{v}(n)$ $\in\mathbb{C}^{N}$ is Gaussian
with variance $\sigma_{v}^{2}$. The beamformer processes the received signal
$\mathbf{x}(n)$ linearly to improve SINR. The beamformer output $y(n)$ is
given by,

$y(n)=\mathbf{w}_{o}^{H}\mathbf{x}(n)$ (4.3)

The optimal beamforming weights $\mathbf{w}_{o}$ that maximizes SINR is given
by solving the following optimization problem [25];

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

The source correlation matrix,
$\mathbf{R}_{s}=\sigma^{2}\mathbf{s}(\theta)\mathbf{s}^{H}(\theta)$, with
power $\sigma^{2}=E\\{b_{s}(n)b_{s}^{H}(n)\\}$. The sum of the interference
and noise correlation matrix is
$\mathbf{R}_{i}=\sum_{k=1}^{I}\sigma^{2}_{k}\mathbf{i}(\theta_{k})\mathbf{i}^{H}(\theta_{k})$
$+\sigma_{v}^{2}\mathbf{I}_{N\times N}$, with the $k$th interference power
$\sigma^{2}_{k}=E\\{b_{ik}(n)b_{ik}^{H}(n)\\}$. Since
$\mathbf{R_{x}}=\mathbf{R}_{s}+\mathbf{R}_{i}$, then formulation (4.4) can be
written as part of the objective function as follows [25],

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

where the equality constraint is relaxed due to the inclusion of the
relationship between the data and signal autocorrelation matrices in the cost
function. The optimum solution of the above problem only requires the
knowledge of the received data correlation matrix
$\mathbf{R_{x}}=E(\mathbf{x}\mathbf{x}^{H})$ and the DOA of the desired
source. The former can readily be estimated from the received data vector
$\mathbf{x}$ over $T$ snapshots,
$\mathbf{\hat{R}_{x}}=\frac{1}{T}\sum_{n=1}^{T}\mathbf{x}(n)\mathbf{x}^{H}(n)$.

The analytical solution of the optimization problem is given by
$\mathbf{w}_{o}=\\{\mathbf{R}_{i}^{-1}\mathbf{s}(\theta)\\}$ with the optimum
output SINRo;

$\text{SINR}_{o}=\frac{\mathbf{w}_{o}^{H}\mathbf{R}_{s}\mathbf{w}_{o}}{\mathbf{w}_{o}^{H}\mathbf{R}_{i}\mathbf{w}_{o}}=\Lambda_{max}\\{\mathbf{R}^{-1}_{i}\mathbf{R}_{s}\\},$
(4.6)

which is in fact the maximum eigenvalue ($\Lambda_{max}$) of the product of
inverse of data correlation matrix and the desired source correlation matrix.
In the next section, the formulation in (4.5) is extended to the sparse
beamformer design.

###  4.3 Sparse array design through SCA algorithm

The expression in (4.6) is applicable to any array topology, including uniform
and sparse arrays with the respective correlation matrices. To achieve sparse
solutions, given the knowledge of full correlation matrix, (4.5) is introduced
with an additional constraint,

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

The operator $||.||_{0}$ denotes the $l_{0}$ norm which constrains the
cardinality of the weight vector $\mathbf{w}$ to the number of available
sensors, $P$. The problem in (4.7) is clearly non convex involving a hard
constraint, rendering the formulation challenging to solve in polynomial time
[55].

The objective function and quadratic constraint in (4.7) are interchanged,
transforming into equivalent formulation as follows,

$\displaystyle\underset{\mathbf{w\in\mathbb{C}}^{N}}{\text{maximize}}$
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R}_{s}\mathbf{w},$ (4.8) s.t.
$\displaystyle\quad\mathbf{w}^{H}\mathbf{R_{x}}\mathbf{w}\leq 1$
$\displaystyle\quad||\mathbf{w}||_{0}=P$

In general, the beamforming weight vector is complex valued, however the
quadratic functions are real. The real and imaginary entries of the optimal
weight vector are typically decoupled, permitting the involvements of only
real unknowns. This is achieved through concatenating the beamforming weight
vector and defining the respective correlation matrices [74],

$\,\,\quad\quad\quad\quad\quad\tilde{\mathbf{R}}_{s}=\begin{bmatrix}\text{real}({\mathbf{R}}_{s})&-\text{imag}({\mathbf{R}}_{s})\\\
\\\ \text{imag}({\mathbf{R}}_{s})&\text{real}({\mathbf{R}}_{s})\\\
\end{bmatrix},\quad\quad\quad\quad\quad\tilde{\mathbf{w}}=\begin{bmatrix}\text{real}({\mathbf{w}})\\\
\\\ \text{imag}({\mathbf{w}})\\\ \end{bmatrix}$ (4.9)
$\displaystyle\tilde{\mathbf{R}}_{x}=\begin{bmatrix}\text{real}({\mathbf{R}}_{x})&-\text{imag}({\mathbf{R}}_{x})\\\
\\\ \text{imag}({\mathbf{R}}_{x})&\text{real}({\mathbf{R}}_{x})\\\
\end{bmatrix}$ (4.10)

Replacing $\mathbf{R_{s}}$ and $\mathbf{R_{x}}$ by $\tilde{\mathbf{R}_{s}}$
and $\tilde{\mathbf{R}_{x}}$ respectively, (4.8) can be expressed in terms of
real variables,

$\displaystyle\underset{\mathbf{\tilde{w}\in\mathbb{R}}^{2N}}{\text{maximize}}$
$\displaystyle\quad\mathbf{\tilde{w}}^{{}^{\prime}}\tilde{\mathbf{R}}_{s}\mathbf{\tilde{w}}$
(4.11) s.t.
$\displaystyle\quad\mathbf{\tilde{w}}^{{}^{\prime}}\mathbf{\tilde{R}_{x}}\mathbf{\tilde{w}}\leq
1$ $\displaystyle\quad||\mathbf{w}||_{0}=P$

The quadratic constraint clearly has the convex feasibility region, however,
there is still a non convex constraint involving the $l_{0}$ norm. In order to
realize the convex feasible region, the $l_{0}$ norm is typically relaxed to
the $l_{1}$ norm, which has been effectively used in many sparse recovery
applications. The maximization problem is first transformed to a minimization
in order to move the $l_{1}$ norm constraint to the objective function and
realize a sparse solution. This is achieved by reversing the sign of the
entries of the desired source correlation matrix
$\bar{\mathbf{R}}_{s}=-\mathbf{\tilde{R}}_{s}$,

$\displaystyle\underset{\mathbf{\tilde{w}\in\mathbb{R}}^{2N}}{\text{minimize}}$
$\displaystyle\quad\mathbf{\tilde{w}}^{{}^{\prime}}\bar{\mathbf{R}}_{s}\mathbf{\tilde{w}}$
(4.12) s.t.
$\displaystyle\quad\mathbf{\tilde{w}}^{{}^{\prime}}\mathbf{\tilde{R}_{x}}\mathbf{\tilde{w}}\leq
1$ $\displaystyle\quad||\mathbf{w}||_{0}=P$

To convexify the objective function, the concave objective is iteratively
approximated through successive linear approximation. The approximation
coefficients $\mathbf{m}^{i}$ and ${b^{i}}$, are updated iteratively
$\mathbf{m}^{i+1}=2\bar{\mathbf{R}}_{s}\mathbf{\tilde{w}}^{i},b^{i+1}=-\mathbf{\tilde{w}}^{i}{{}^{\prime}}\bar{\mathbf{R}}_{s}\mathbf{\tilde{w}}^{i}$
by first order approximation, resulting in the following form,

$\displaystyle\underset{\mathbf{\tilde{w}\in\mathbb{R}}^{2N}}{\text{minimize}}$
$\displaystyle\quad\mathbf{m}^{i}{{}^{\prime}}\mathbf{\tilde{w}}+b^{i}$ (4.13)
s.t.
$\displaystyle\quad\mathbf{\tilde{w}}^{{}^{\prime}}\mathbf{\tilde{R}_{x}}\mathbf{\tilde{w}}\leq
1$ $\displaystyle\quad||\mathbf{w}||_{0}=P$

Finally, the non convex $l_{0}$ norm is relaxed through minimizing the mixed
$l_{1-\infty}$ norm to recover sparse solutions,

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

The summation implements the $l_{1}$ norm that is minimized as a convex
surrogate of $l_{0}$ norm. The vector
$\mathbf{\tilde{w}}_{k}\in\mathbb{R}^{2}$ has two entries containing the real
and imaginary parts of the beamforming weight corresponding to the $k$th
sensor. The $||.||_{\infty}$ selects the maximum entry of
$\mathbf{\tilde{w}}_{k}$ and discourages the real and imaginary entries
concurrently. This is because not selecting a sensor implies the simultaneous
removal of both the real and corresponding imaginary entries in the final
solution vector. The sparsity parameter $\mu$ is set to zero for the first few
initial iterations to allow the solution to converge to optimal solution for
the full array elements. The sparsity parameter $\mu$ by itself does not
guarantee the final solution to be $P$ sparse. To guarantee a $P$ sparse
solution, the optimization problem is solved successively against different
values of $\mu$. The values of $\mu$ are typically given by a binary search
over the possible upper and lower limit of $\mu$ until the algorithm converges
to $P$ sensors [2].

Table 4.1: SCA for sparse array beamforming.

0: Received data sparse correlation matrix $\mathbf{R}_{P}$, look direction
DOA $\theta$.

0: $P$ sensor beamforming weight vector Matrix Completion: Run Eq. (4.4) for
free design and Toeplitz averaging for hybrid design to estimate the full
correlation matrix. Set the lowest eigenvalues of $\mathbf{\hat{R}_{x}}$
corresponding to the noise subspace to be equal to the noise floor.
Initialization: Initialize the beamforming vectors randomly to find
$\mathbf{m}$ and $b$. Initialize $\epsilon$, $\mu=0$.

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

Run Eq. (4.16).

end whileInitialize $\mathbf{h}^{i}$= all ones vector, Binary vector for
hybrid design.Select $\mu$ (Binary search)

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

Run Eq. (4.16) . (for initial iteration use $\mathbf{m}^{i}$ and $b^{i}$ from
previous while loop)

Update the regularization weighting parameter,
$\mathbf{h}^{i+1}(k)=\frac{1}{||\mathbf{\tilde{w}}_{k}^{i}||_{2}+\epsilon}$,
Update $\mathbf{m}^{i}$ and $b^{i}$

end while

After achieving the desired cardinality, analytically solve for
$\mathbf{\tilde{w}}$ corresponding to the selected sensor locations, yielding,
optimal weight vector.

return Optimal weight vector $\mathbf{w}_{o}$

####  4.3.1 Hybrid sparse array design

Formulation (4.14) penalizes all the sensor weights rather judiciously in an
effort to optimize the objective function. We refer to this approach as free-
design. On the other hand, the hybrid sparse array design, penalizes only some
sensor weights, leaving the remaining sensors to assume prefixed positions.
These position are chosen to guarantee full augmentatbility of the sparse
array, i.e., provide the ability to estimate the autocorrelation at all
spatial lags across the array aperture. This provide the means for thinning
the array and carrying out sparse optimization all the times. In order to
discriminate the prefixed sensors from those which are available for design,
the weighted formulation is adopted, in turn modifying (4.14) as follows,

$\displaystyle\underset{\mathbf{\tilde{w}\in\mathbb{R}}^{2N}}{\text{minimize}}$
$\displaystyle\quad\mathbf{m^{i}{{}^{\prime}}}\mathbf{\tilde{w}}+b^{i}+\mu(\sum_{k=1}^{N}\mathbf{h}(k)||\mathbf{\tilde{w}}_{k}||_{\infty})$
(4.15) s.t.
$\displaystyle\quad\mathbf{\tilde{w}}^{{}^{\prime}}\mathbf{\tilde{R}_{x}}\mathbf{\tilde{w}}\leq
1$

The weighting vector $\mathbf{h}$ is a binary vector with $1^{\prime}s$ and
$0^{\prime}s$ entries. The entries corresponding to the prefixed sensor
locations are set to $0$ while the remaining entries are initialized to $1$.
In this way, the partial penalization is implemented in (4.15) that ensures
the sparsity is not enforced to the prefixed locations. The weighted
penalization can easily be extended to the reweighting formulation which can
further promote sparsity and facilitates the $P$ sparse solution [58]. This is
achieved by iteratively updating weighting vector $\mathbf{h}$ [41, 42],

$\displaystyle\underset{\mathbf{\tilde{w}\in\mathbb{R}}^{2N}}{\text{minimize}}$
$\displaystyle\quad\mathbf{m^{i}{{}^{\prime}}}\mathbf{\tilde{w}}+b^{i}+\mu(\sum_{k=1}^{N}\mathbf{h}^{i}(k)||\mathbf{\tilde{w}}_{k}||_{\infty})$
(4.16) s.t.
$\displaystyle\quad\mathbf{\tilde{w}}^{{}^{\prime}}\mathbf{\tilde{R}_{x}}\mathbf{\tilde{w}}\leq
1$

The re-weighting vector $\mathbf{h}^{i}$, at the $i$-th iteration, is updated
as an inverse function of the beamforming weights at the present iteration,

$\mathbf{h}^{i+1}(k)=\frac{1}{||\mathbf{\tilde{w}}_{k}^{i}||_{2}+\epsilon}$
(4.17)

This relatively suppresses the low magnitude weights in the next iteration to
accelerate sparsity. The parameter $\epsilon$ avoids the case of division by
zero. The reweighting is applied to both the freely designed array and the
hybrid design. For the former, the vector $\mathbf{h}$ is initialized to all
$1^{\prime}s$ vector and updated iteratively. However, to preserve the
prefixed sensor locations for the hybrid design, the entries of
$\mathbf{h}^{i}$ corresponding to the prefixed locations must remain zero for
all iterations, while the remaining entries are initialized to $1$ and updated
as explained above. The procedure is summarized in Table 4.1.

###  4.4 Toeplitz matrix completion and Fully augmentable completion through
averaging

The key concern in the free-design sparse array formulation is the assumption
regarding the knowledge of the full array correlation matrix. This is because
the data from only $P$ active sensors is available to estimate the correlation
matrix. The full correlation matrix, in this case, is not readily available
and could have many missing correlation lags. Many different approaches for
sparse matrix completion, under variant assumptions about the data model, have
been considered in the literature including high resolution DOA estimation. We
adopt a positive semidefinite Toepltiz matrix completion scheme that
effectively exploits the structure of the unknown correlation matrix. It is
well known that the narrowband far field sources impinging on the ULA
resultantly has the hermitian positive definite correlation matrix having the
Toeplitz structure. Along with the Toepltiz positive definite condition, the
trace heuristic is incorporated to interpolate the missing lags. The trace
heuristics is 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, rendering gridless recovery of the underlying narrowband
sources, thus recovering the missing correlation lags [75, 76, 77, 78, 79].
The matrix completion problem is, therefore, written as,

$\displaystyle\underset{l\in\mathbb{C}^{N}}{\text{minimize}}$
$\displaystyle\quad||Toeplitz(l)\odot\mathbf{Z}-\mathbf{R}_{P}||_{F}^{2}+\zeta\text{Tr}(Toeplitz(l))$
s.t. $\displaystyle\quad Toeplitz(l)\succeq 0$ (4.18)

Here, $l$ is a complex vector with a real first element, then $Toeplitz(l)$
returns the symmetric Toeplitz matrix having $l$ and $l^{H}$ defining its
first row and column respectively. Matrix $\mathbf{R}_{P}$ is the received
data correlation matrix with missing correlation lags. The entries
corresponding to the missing correlation lags are set to zero. The symbol
‘$\odot$’ denotes the element wise multiplication and ‘$\succeq$’ denotes the
matrix inequality enforcing the positive semidefinite constraint. The matrix
$\mathbf{Z}$ is a binary matrix which only fits the non zero elements in
$\mathbf{R}_{P}$ to the unknown Toepltiz matrix. The function
‘$||.||_{F}^{2}$’ is the square of the Frobenius norm of the matrix which
seeks to minimize the sum of error square between the observed correlation
values and the corresponding entries of the unknown Toepltiz matrix. The
symbol ‘$\zeta$’ gives the trade off between the denoising term and the trace
heuristic pursuing simpler model. The nominal value of the parameter ‘$\zeta$’
is typically tuned from the numerical experience for the underlying problem.
However, the Toeplitz estimate can potentially be ill conditioned having quite
a few eigenvalues close to zero. We utilize the maximum likelihood estimate of
the interpolated Toeplitz correlation matrix by incorporating the knowledge of
the noise floor. In so doing, the eigenvalues corresponding to the noise
subspace are set equal to the noise floor.

Unlike the free-design sparse array, where missing lags manifest themselves as
zero values at all entries of some of the autocorrelation matrix sub-
diagonals, the hybrid design would ensure that at least one element in each
matrix sub-diagonal is available. This facilities the Toeplitz estimation of
the received data correlation matrix by averaging the non zero correlation
entries across each sub-diagonal. The averaging scheme, however, does not
guarantee the positive definiteness of the Toeplitz estimate [49], [50]. This
renders the formulation in (4.16) non convex, which essentially requires
$\mathbf{R_{x}}$ to be positive semidefinite. In order to circumvent this
issue, we return to the maximum likelihood estimate adopted for the matrix
completion approach to facilitate a positive definite estimate by eliminating
the negative eigenvalues typically appearing in the noise subspace. Finally,
the estimated data correlation matrix $\mathbf{\hat{R}_{x}}=Toeplitz(l)$ is
used in lieu of $\mathbf{R_{x}}$ to carry out the data dependent optimization
for MaxSINR.

###  4.5 Simulations

We show examples under different design scenarios to access the performance of
the proposed methodology achieving MaxSINR. We establish two performance
benchmarks in order to examine the sensitivity of the proposed algorithm to
the initial array configuration. This is because the matrix interpolation
approach is guided on the initial configuration that decides the location of
the missing entries in the data correlation matrix. The initial configuration
refers to the $P$-element sparse array topology at the start before commencing
of any adaptation process. In general, the initial configuration could be any
random array, or the optimized configuration from the preceding operating
conditions. The first performance benchmark applies the SCA algorithm under
the assumption that the data from all the perspective sensor locations is
available. In this way, the actual full correlation matrix utilizing $T$
snapshots is input to the SCA algorithm. Clearly, the performance of the
aforementioned benchmark is not reliant on the initial configuration but is
dependent on the observed data realization and the number of snapshots.
Another deterministic performance benchmark assumes perfect knowledge of the
full correlation matrix, representing the case of unlimited data snapshots. To
draw a proper distinction, the former would be referred as the ‘Full
correlation statistics-limited snapshots (FCS-LSS),’ and the latter is
henceforth called the ‘Full correlation statistics-unlimited snapshots (FCS-
USS)’.

####  4.5.1 Example comparing both designs

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

Figure 4.2: (a) Initial configuration; randomly selected 16 antennas from 36
(b) Initial configuration leading to fully augmentable array (c) Freely
designed array (d) Hybrid designed array (e) Initial random configuration;