Reviews: k-Support and Ordered Weighted Sparsity for Overlapping Groups: Hardness and Algorithms

Summary: This paper designs new norms for group sparse estimation. The authors extend the k-support norm and the ordered weighted norm to the group case (with overlaps). The resulting (latent) norms are unfortunately NP-hard to compute, though. The main contribution is an algorithm based on tree decomposition and dynamic programming for computing the best approximation (under the Euclidean norm) under group cardinality constraints. This algorithm improves the previous work by a factor of m (# of groups).