How to reduce the computational complexity for the OMP based compressive sensing algorithm, so that we can use it for FPGA implementation and test for real time applications, like wireless sensors?
OMP attempts to solve the following problem:
min_x ||b - Ax||_2^2 s.t. ||x||_0
The main difference between MP and OMP is that OMP ensures that the selected atoms are orthogonal, hence, the atom "updating" step is the most crucial for OMP.
The Matching Pursuit toolkit (MPTK) implementation in MATLAB have reduced the complexity of MP from O(N^2) to O(Nlog2N) via FFT to reduce the correlations time between the signal and the atoms and using shift-invariant dictionaries of Gabor and Chirped Gabor atoms:
https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1660699
In the case of OMP, a number of implementations have reduced the complexity by choosing a sub-dictionary that includes the last atom selected and orthogonalized the decomposition only on this sub-dictionary. The sub-dictionary matrix is a Gram-matrix whose atoms are orthogonal if their support do not overlap (time/frequency content):
https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=4960366
Available implementations in MATLAB are given by the SPAMS library:
http://spams-devel.gforge.inria.fr
Depending on your application, if you consider that the atoms selected must be orthogonal continue using OMP, otherwise MP can give you an accurate estimation.
- Badges
- Science topic