Near-Optimal Greedy Sensor Selection for MVDR Beamforming with Modular Budget Constraint

Abstract

In this paper, we present a greedy sensor selection algorithm for minimum variance distortionless response (MVDR) beamforming under a modular budget constraint. In particular, we propose a submodular set-function that can be maximized using a linear-time greedy heuristic that is near optimal. Different from the convex formulation that is typically used to solve the sensor selection problem, the method in this paper neither involves computationally intensive semidefinite programs nor convex relaxation of the Boolean variables. While numerical experiments show a comparable performance between the convex and submodular relaxations, in terms of output signal-to-noise ratio, the latter finds a near-optimal solution with a significantly reduced computational complexity.