Performance-Complexity Tradeoffs in Greedy Weak Submodular Maximization with Random Sampling

Abolfazl Hashemi, Haris Vikalo, Gustavo de Veciana

Many problems in signal processing and machine learning can be formalized as weak submodular optimization tasks. For such problems, a simple greedy algorithm (\textsc{Greedy}) is g…