Fast Implementation of Matching Pursuit

As part of sparse-plex, we provide a fast CPU based implementation of Matching Pursuit.

This is written in C++ and uses the BLAS and LAPACK features available in MATLAB MEX extensions. The implementation is available in the function spx.fast.mp. The corresponding C code is in spx_matching_pursuit.cpp.

Benchmarks

System configuration

OS	Windows 7 Professional 64 Bit
Processor	Intel(R) Core(TM) i7-3630QM CPU @ 2.40GHz
Memory (RAM)	16.0 GB
Hard Disk	SATA 120GB
MATLAB	R2017b

We compare following algorithms:

• greedy_mp.m function in sparsify.
• Our C++ version in sparse-plex.

Our implementation is about 3.8 times faster.

The benchmark generation code is in compare_mp_speeds.m.

The work load consists of a Gaussian dictionary of size \(100 \times 1000\). 1000 signals are constructed so that the benchmarks can run reasonable duration. 8-sparse representations are constructed for each randomly generated signal in the given dictionary.

Output of the comparison script:

Time taken by MATLAB implementation: 3.790
Time taken by C++ implementation: 0.990
Gain: 3.83