Theoretical Guarantees of Recovery Algorithms for Ternary Sparse Signals

Abstract

This paper focuses on the problem of recovering ternary sparse signals with s nonzero entries of 1 and −1. We propose three novel algorithms: ternary matching pursuit (TMP), ternary generalized orthogonal matching pursuit (TGOMP), and piecewise ternary generalized orthogonal matching pursuit (PTGOMP). First, inspired by the binary matching pursuit algorithm, we introduce the TMP algorithm, which assigns values of 1 or −1 based on the most correlated residual, and provide theoretical guarantees based on the mutual coherence, denoted by $µ$ and the restricted isometry property of the measurement matrix, respectively. Second, we propose the TGOMP algorithm, by selecting multiple $(M)$ indices at each iteration in order to improve the performance of the TMP algorithm. We establish a sufficient condition $µ < 1/(2s − 1)$ that ensures the TGOMP algorithm selects $M$ correct indices and corresponding entries of $x$ in each iteration. Especially, all correct indices and entries can be selected in the first iteration. Additionally, we present a sufficient condition based on the restricted isometry property that guarantees all correct indices are selected in at most s iterations. Third, we propose the PTGOMP algorithm, which employs a piecewise selection strategy at each iteration, further improves recovery performance. Theoretical guarantees for the PTGOMP algorithm are derived based on the mutual coherence, showing its advantages in ternary sparse signal recovery. Finally, we validate the effectiveness of our algorithms through simulations and numerical experiments, demonstrating that combining appropriate matrix structures with suitable sparsity patterns can significantly improve recovery performance.