Exact Support and Vector Recovery of Constrained Sparse Vectors via Constrained Matching Pursuit

Abstract

Matching pursuit, especially its orthogonal version and other variations, is a greedy algorithm widely used in signal processing, compressed sensing, and sparse modeling and approximation. Inspired by constrained sparse signal recovery, this paper proposes a constrained matching pursuit algorithm and develops conditions for exact support and vector recovery on constraint sets via this algorithm. We show that exact recovery via constrained matching pursuit not only depends on a measurement matrix but also critically relies on a constraint set. We thus identify an important class of constraint sets, called coordinate projection admissible set, or simply CP admissible sets. This class of sets includes the Euclidean space, the nonnegative orthant, and many others arising from various applications; analytic and geometric properties of these sets are established. We then study exact vector recovery on convex, CP admissible cones for a fixed support. We provide sufficient exact recovery conditions for a general fixed support as well as necessary and sufficient recovery conditions for a fixed support of small size. As a byproduct of our results, we construct a nontrivial counterexample to the necessary conditions of exact vector recovery via the orthogonal matching pursuit given by Foucart, Rauhut, and Tropp, when the a given support is of size three. Moreover, by making use of cone properties and conic hull structure of CP admissible sets and constrained optimization techniques, we also establish sufficient conditions for uniform exact recovery on CP admissible sets in terms of the restricted isometry-like constant and the restricted orthogonality-like constant.