Similar sensing matrix pursuit: An efficient reconstruction algorithm to cope with deterministic sensing matrix

• This paper presents a unique way to solve the K-spare vector reconstruction problem.
• This paper presents a novel SSMP algorithm to cope with the deterministic sensing matrix with high coherence.
• This paper presents an efficient way to analyze the original sensing matrix based on similarity.
• This paper builds similar compact sensing matrix with low coherence, which guarantees perfect reconstruction of sparse vector with high probability.
• This paper presents a simulation example of the DOA estimation problem using compressed sensing techniques in sensor array processing.

Deterministic sensing matrices are useful, because in practice, the sampler has to be a deterministic matrix. It is quite challenging to design a deterministic sensing matrix with low coherence. In this paper, we consider a more general condition, when the deterministic sensing matrix has high coherence and does not satisfy the restricted isometry property (RIP). A novel algorithm, called the similar sensing matrix pursuit (SSMP), is proposed to reconstruct a K-sparse signal, based on the original deterministic sensing matrix. The proposed algorithm consists of off-line and online processing. The goal of the off-line processing is to construct a similar compact sensing matrix containing as much information as possible from the original sensing matrix. The similar compact sensing matrix has low coherence, which guarantees a perfect reconstruction of the sparse vector with high probability. The online processing begins when measurements arrive, and consists of rough and refined estimation processes. Results from our simulation show that the proposed algorithm obtains much better performance while coping with a deterministic sensing matrix with high coherence compared with the subspace pursuit (SP) and basis pursuit (BP) algorithms.