Reviews: Fast greedy algorithms for dictionary selection with generalized sparsity constraints

This paper studies the problem of dictionary selection, where the goal is to pick k vectors among a collection of n d-dimensional vectors such that these vectors can approximate T data points in a sparse representation. This problem is well-studied and the authors propose a new algorithm with theoretical guarantees which is faster than previous algorithms and which can handle more general constraints. This algorithm is based on a previous algorithm for the related problem of two stage submodular maximization called replacement greedy. It is first shown that replacement greedy also enjoys approximation guarantees for dictionary selection. Then, the authors further improve this algorithm to obtain replacement OMP, which is faster.