Click here to flash read.
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.
