Exact Support and Vector Recovery of Constrained Sparse Vectors via Constrained Matching Pursuit
Loading...
Links to Files
Permanent Link
Author/Creator
Author/Creator ORCID
Date
2019-03-18
Type of Work
Department
Program
Citation of Original Publication
Jinglai Shen, Seyedahmad Mousavi , Exact Support and Vector Recovery of Constrained Sparse Vectors via Constrained Matching Pursuit, Mathematics , Optimization and Control, 2019, https://arxiv.org/abs/1903.07236
Rights
This item is likely protected under Title 17 of the U.S. Copyright Law. Unless on a Creative Commons license, for uses protected by Copyright Law, contact the copyright holder or the author.
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.