Revisiting Matching Pursuit: Beyond Approximate Submodularity
This work addresses signal representation tasks, such as angle of arrival estimation, by providing a more theoretically grounded and effective greedy algorithm, though it is incremental as it builds on existing matching pursuit frameworks.
The paper tackled the problem of selecting a subset of vectors for optimal signal representation by introducing a submodular function in expectation, which guarantees near-optimality through a greedy algorithm and improves upon traditional matching pursuit methods. Numerical experiments on angle of arrival estimation demonstrated benefits over existing algorithms.
We study the problem of selecting a subset of vectors from a large set, to obtain the best signal representation over a family of functions. Although greedy methods have been widely used for tackling this problem and many of those have been analyzed under the lens of (weak) submodularity, none of these algorithms are explicitly devised using such a functional property. Here, we revisit the vector-selection problem and introduce a function which is shown to be submodular in expectation. This function does not only guarantee near-optimality through a greedy algorithm in expectation, but also alleviates the existing deficiencies in commonly used matching pursuit (MP) algorithms. We further show the relation between the single-point-estimate version of the proposed greedy algorithm and MP variants. Our theoretical results are supported by numerical experiments for the angle of arrival estimation problem, a typical signal representation task; the experiments demonstrate the benefits of the proposed method with respect to the traditional MP algorithms.