Following up on the entries to the 21st Matlab programming contest featuring compressed sensing, there is an on-going discussion between some of you in the comment section of this entry. If you are submitting to this contest, please let me know where you contribution is. Right now R seems to have gotten the best results to a score of 73801 when the best is currently in the vicinity of 28000 range (and it has been there for a while now). I like the fact that the entries are running on somebody else's machine and how easy it is to create a new entry based on somebody else's.I note several of R's very valid comments on the contest with regards to 'real' compressed sensing. Here they are:
I completely agree. The results are depressing, on the other hand (on my local machine) if I run spgl1 as the "solver" then the results improve dramatically. You start to see stuff that resemble images.
Like I said before this is not really "canonical" compressed sensing for several reasons. Here are two important ones:
- You should not be allowed to adaptively sample.
- You should not be penalized for the sampling cost. I found it impossible to generate a full random {0,1} measurement matrix (easily convertible to {-1 1}). The only sampling scheme I could get away with is this silly random sparse one. My experiments timed out otherwise.
- Given the time constraints (and rules) of the contest, you can't run powerful algorithms like l1 minimization or Total Variation minimization. Nor can you really use good sparsity bases without a lot of programming effort...
Despite all the above, I am still disappointed with the results
More precisely, you can use a test given by the contest to see if your algorithm can work on your machine. Using SPGL1 here what R finds:
To follow up on that, just by running 100 iterations of spgl1 (a fast l1 minimization algorithm) the reconstruction error is reduced by a factor of 3-5 on the provided test cases, and this is over the best that I can currently do with iterative soft and hard thresholding in the contest.
and finally:
After much tinkering, I got the score down to around 75000.It is one thing for the contest to allow for people to run their algorithm on their cloud (no need to have a Matlab licence) but eventually, there is a reason why all these reconstruction solvers were made the way they were: They are not simple. I also totally agree that if you get penalized because you are spending too much time in your algorithm defining a dictionary (like the DCT)in R's algorithm) while at the same time allowing competitors to overfit their algorithms to the specific solution being sought, then maybe this is not such a good exercise after all. Like R, Amit, The Vlad and Ngoc Minh, I am yearning for a better solution. We used to be 10 times larger than the best score, R's solution is only about less than 3 times.
On the sampling side, I used jittered sampling. On the reconstruction side,
basically, I used iterative soft-thresholding with variable thresholds (one for low freq and one for high freq), with cooling (i.e., the thresholds decrease with the iteration count). Note that this is a poor man's substitute for a good l1 minimization algorithm (spgl1 does much better (now, 2-3 times lower error) on the contest's training set and in much shorter time (about a half), but its too hard to convert the code so that it complies with the contest rules).
In short, despite the non-canonical CS scenario, CS techniques (even when not used to full force) can still be made to work, albeit with much effort.
Here is The Vlad comment that summarizes also some of these issues with the contest:
Hi R,
I ran your algorithm, and while the results are certainly an improvement over the previous version, they are still underwhelming. I entered an algorithm that simply solves laplace's equation based on M randomly-sampled pixel values ('vladirator10'), and this did much better than the compressive sensing algorithms. The winning entries are, of course, highly optimized hacks on hacks, so it's obviously difficult to compete with those. But still, any thoughts why the performance of the compressive sensing algorithms is so poor?
For more entries/comments on the contest, you can use the comment section of this entry and you can even be anonymous doing so.
Credit: NASA/JPL/Space Science Institute , Dione Sliding by Tethys
I think adaptive vs. fixed sampling makes a huge difference for practical problems ...
ReplyDeleteAlthough asymptotically optimal for signals that are highly sparse, in practice CS does not compete that well even with traditional (linear) sampling schemes.
I especially like the comment "simply solves laplace's equation [...]" which shows quite nicely the fact that linear method competes well with L1 and randomized measurement.
You really need to work hard and use stronger prior (TV, sample only high frequencies, use complicated bayesian priors) to make CS better than a simple low pass acquisition on natural images.
The cost for non adaptive CS is typically a factor 5 ~ 7 (with respect to best M term approximation) for a 1% RMS error on Lena image, which is more than the cost of a linear coding.
Anonymous, I think you have it upside down :).
ReplyDeleteCompressed sensing does not claim to be an optimal compression scheme. It provides a relatively cheap, possibly universal acquisition protocol. For instance, if sensors are expensive, you can't build an array of them and a CS architecture like Rice's CS camera may be an option... or when acquisition time is an issue (like in MRI) or when transmission (communication) and on-board processing costs are an issue, CS approaches are useful...
To reiterate, so far, CS is not competitive from a rate-distortion point of view but it provides an alternative acquisition scheme when some type of cost (time, money, power, radiation,... ) prohibits traditional sensing.
Thus, what is noteworthy here is that CS (ignoring issues like quantization) comes within a constant of what is possible with "traditional" sensing.
Again, with the current state-of-the-art, CS does not claim to be an optimal coding scheme.
Yes you are definitely right.
ReplyDeleteI think you misunderstood my point. I just wanted to make clear that using CS technics to beat traditional problems (such as coding) simply does not make sense.
In theory it makes sense, because of the asymptotic optimality result (for signals in l^p for p<1, CS approximation is asymptotically as good as non-linear approximation). In practice, because of the constant it performs worse even for very large images (that furthermore are not in l^p for p<1 ... but this is yet another issue).
And in my opinion, this Matlab challenge is just about this : it is a classical image processing problem, and should definitely not be solved with fixed measures and a blind L1 prior.
This symptomatic of this CS hype that makes many people focus on wrong problems (see also the wired article for a related issue).
I am happy to see that reader of this blog are aware of these difficulties !
-- best
I guess I did misunderstand your point! We agree on pretty much everything then. In fact, by the time I figured out the problems with the rules of the contest, I was too insistent on improving the score at least to with an order of magnitude of the adaptive schemes to avoid having people deduce that CS sucks.
ReplyDelete