Performance Guarantees of the Thresholding Algorithm for the Co-Sparse Analysis Model

The co-sparse analysis model for signals assumes that the signal of interest can be multiplied by an analysis dictionary \Omega, leading to a sparse outcome. This model stands as an interesting alternative to the more classical synthesis based sparse representation model. In this work we propose a theoretical study of the performance guarantee of the thresholding algorithm for the pursuit problem in the presence of noise. Our analysis reveals two significant properties of \Omega, which govern the pursuit performance: The first is the degree of linear dependencies between sets of rows in \Omega, depicted by the co-sparsity level. The second property, termed the Restricted Orthogonal Projection Property (ROPP), is the level of independence between such dependent sets and other rows in \Omega. We show how these dictionary properties are meaningful and useful, both in the theoretical bounds derived, and in a series of experiments that are shown to align well with the theoretical prediction.