Parallel implementation of orthogonal matching pursuit in OpenCL

ABSTRACT: Orthogonal matching pursuit (OMP) is one of the most effective techniques to recover a sparse signal from limited number of measurements. However, when the number of measurements necessary is very large recovering the sparse signal would a challenge for CPU. In this thesis we aim to improve the performance of large array reconstruction by using parallel computing technology. We use Open Computing Language (OpenCL) in implementing parallel OMP in CPU and GPU. We also make some modification in pseudoinverse algorithm (i.e. using QR decomposition instead of naive matrix inverse) to improve the robustness of the implementation. To examine the performance and quality of implementation, we consider signals of four different sizes (i.e. small, medium, large and massive) and evaluate the results. We can obtain better performance (over 2 times faster) for signals of large and massive sizes in terms of the speed and accuracy of the reconstruction. Thanks to portability of OpenCL, the proposed implementation can be run on all kind of devices such as embedded devices, smart phones, and laptops. Keywords: Compressive Sensing, Orthogonal Matching Pursuit, OpenCL, Graphic Processing Unit, Central Processing Unit. …………………………………………………………………………………………………………………………………………………………………………………………………………