Deterministic Sensing Matrices Arising From Near Orthogonal Systems

Compressed sensing is a novel sampling theory, which provides a fundamentally new approach to data acquisition. It asserts that a sparse or compressible signal can be reconstructed from much fewer measurements than traditional methods. A central problem in compressed sensing is the construction of the sensing matrix. While random sensing matrices have been studied intensively, only a few deterministic constructions are known. Among them, most constructions are based on coherence, which essentially generates matrices with low coherence. In this paper, we introduce the concept of near orthogonal systems to characterize the matrices with low coherence, which lie in the heart of many different applications. The constructions of these near orthogonal systems lead to deterministic constructions of sensing matrices. We obtain a series of m×n binary sensing matrices with sparsity level k=Θ(m^(1/2)) or k=O((m/logm)^(1/2)). In particular, some of our constructions are the best possible deterministic ones based on coherence. We conduct a lot of numerical experiments to show that our matrices arising from near orthogonal systems outperform several typical known sensing matrices.