Sensor array design through submodular optimization

Gal Shulkind, Stefanie Jegelka, Gregory W. Wornell

Research output: Contribution to journalArticlepeer-review

7 Scopus citations


We consider the problem of far-field sensing by means of a sensor array. Traditional array geometry design techniques are agnostic to prior information about the far-field scene. However, in many applications such priors are available and may be utilized to design more efficient array topologies. We formulate the problem of array geometry design with scene prior as one of finding a sampling configuration that enables efficient inference, which turns out to be a combinatorial optimization problem. While generic combinatorial optimization problems are NP-hard and resist efficient solvers, we show how for array design problems the theory of submodular optimization may be utilized to obtain efficient algorithms that are guaranteed to achieve solutions within a constant approximation factor from the optimum. We leverage the connection between array design problems and submodular optimization and port several results of interest. We demonstrate efficient methods for designing arrays with constraints on the sensing aperture, as well as arrays respecting combinatorial placement constraints. This novel connection between array design and submodularity suggests the possibility for utilizing other insights and techniques from the growing body of literature on submodular optimization in the field of array design.

Original languageEnglish
Article number8482297
Pages (from-to)664-675
Number of pages12
JournalIEEE Transactions on Information Theory
Issue number1
StatePublished - Jan 2019
Externally publishedYes


  • Array design
  • far field sensing
  • submodular optimization


Dive into the research topics of 'Sensor array design through submodular optimization'. Together they form a unique fingerprint.

Cite this