Sensing dictionary construction for orthogonal matching pursuit algorithm in compressive sensing

Abstract

<p>In compressive sensing, the fundamental problem is to reconstruct sparse signal from its nonadaptive insufficient linear measurement. Besides sparse signal reconstruction algorithms, measurement matrix or measurement dictionary plays an important part in sparse signal recovery. Orthogonal Matching Pursuit (OMP) algorithm, which is widely used in compressive sensing, is especially affected by measurement dictionary. Measurement dictionary with small restricted isometry constant or coherence could improve the performance of OMP algorithm. Based on measurement dictionary, sensing dictionary can be constructed and can be incorporated into OMP algorithm. In this thesis, two methods are proposed to design sensing dictionary. In the first method, sensing dictionary design problem is formulated as a linear programming problem. The solution is unique and can be obtained by standard linear programming method such as primal-dual interior point method. The major drawback of linear programming based method is its high computational complexity. The second method is termed sensing dictionary designing algorithm. In this algorithm, each atom of sensing dictionary is designed independently to reduce the maximal magnitude of its inner product with measurement dictionary. Compared with linear programming based method, the proposed sensing dictionary design algorithm is of low computational complexity and the performance is similar. Simulation results indicate that both of linear programming based method and the proposed sensing dictionary designing algorithm can design sensing dictionary with small mutual coherence and cumulative coherence. When the designed sensing dictionary is applied to OMP algorithm, the performance of OMP algorithm improves.</p>