Improved Coherence Index-Based Bound in Compressive Sensing

Within the compressive sensing (CS) paradigm, sparse signals can be reconstructed based on a reduced set of measurements, whereby reliability of the solution is determined by its uniqueness. With its mathematically tractable and feasible calculation, the coherence index is one of very few CS uniqueness metrics with considerable practical importance. We propose an improvement of the coherence-based uniqueness relation for the matching pursuit algorithms. Starting from a simple and intuitive derivation of the standard uniqueness condition, based on the coherence index, we derive a less conservative coherence index-based lower bound for signal sparsity. The results are generalized to the uniqueness condition of the $l_0$ -norm minimization for a signal represented in two orthonormal bases.