Submodularity is a discrete domain functional property that can be interpreted as mimicking the role of well-known convexity/concavity properties in the continuous domain. Submodular functions exhibit strong structure that lead to efficient optimization algorithms with provable near-optimality guarantees. These characteristics, namely, efficiency and provable performance bounds, are of particular interest for signal processing (SP) and machine learning (ML) practitioners, as a variety of discrete optimization problems are encountered in a wide range of applications. Conventionally, two general approaches exist to solve discrete problems: 1) relaxation into the continuous domain to obtain an approximate solution or 2) the development of a tailored algorithm that applies directly in the discrete domain. In both approaches, worst-case performance guarantees are often hard to establish. Furthermore, they are often complex and thus not practical for large-scale problems. In this article, we show how certain scenarios lend themselves to exploiting submodularity for constructing scalable solutions with provable worst-case performance guarantees. We introduce a variety of submodular-friendly applications and elucidate the relation of submodularity to convexity and concavity, which enables efficient optimization. With a mixture of theory and practice, we present different flavors of submodularity accompanying illustrative real-world case studies from modern SP and ML. In all of the cases, optimization algorithms are presented along with hints on how optimality guarantees can be established.

Multiple-input multiple-output (MIMO) radar is known for its superiority over conventional radar due to its antenna and waveform diversity. Although higher angular resolution, improved parameter identifiability, and better target detection are achieved, the hardware costs (due to multiple transmitters and multiple receivers) and high-energy consumption (multiple pulses) limit the usage of MIMO radars in large scale networks. On one hand, higher angle and velocity estimation accuracy is required, but on the other hand, a lower number of antennas/pulses is desirable. To achieve such a compromise, in this paper, the Cramér-Rao lower bound (CRLB) for the angle and velocity estimator is employed as a performance metric to design the antenna and the pulse placement. It is shown that the CRLB derived for two targets is a more appropriate criterion in comparison with the single-target CRLB since the two-target CRLB takes into account both the mainlobe width and the sidelobe level of the ambiguity function. In this paper, several algorithms for antenna and pulse selection based on convex and submodular optimization are proposed. Numerical experiments are provided to illustrate the developed theory.

Multiple input multiple output (MIMO) radar is known for its superiority over conventional radar due to its antenna and waveform diversity. However, the increased hardware cost (due to multiple transmitters and receivers), power consumption (due to multiple transmitters and pulses), and computational complexity (due to numerous pulses) form the drawbacks of MIMO radar. On one hand, a higher estimation accuracy is required, but on the other hand, a lower number of active antennas/pulses is desirable. Therefore, in this paper, by proposing a convex optimization approach for the general case of transmitter-receiver-pulse selection, we will minimize the total number of active antennas/pulses in order to guarantee a prescribed performance accuracy. The performance measure we will optimize is the Cramer-Rao lower bound (CRLB) for the angle and velocity estimation accuracy of two targets, which provides a trade-off between the main beamwidth and the sidelobe level (SLL) of the ambiguity function.