Wireless Body Area Networks with Minimum Energy Consumption
There are two optimisation problems here:


To get the sensing matrix $\mathcal{A}$
To recover the signal by $y = \mathcal{A} x$


Out of these two problems, the first one is the one that is solved off-line to obtain a sensing matrix $\mathcal{A}$ that appears to be more "suitable" to a particular family of signals.

The second optimisation problem is the standard compressive sensing recovery and this is the bit that might take more CPU effort to be solved. 

For an indication about the kind of effort required, you might want to have a look at this page, the code it provides and specifically the Optimization/l1eq_pd.m file.

This is the entry point to a generic CS "solver" that then calls other optimisation algorithms contained in Optimization/.

If you take a look in there you can see that you can expect matrix multiplications, matrix inversion, point to point multiplications of sequences and other less intensive operations.

All of these also depend on the amount of data captured, so you might have to do some experimentation with realistic signals from the domain you are dealing with to get a more accurate idea of how much computational effort is required and therefore how much power to solve these problems.

It certainly looks more like a problem for a Raspberry Pi Zero rather than an Arduino type of CPU, if you are considering a mobile / wearable application.

Hope this helps.