Hello, and welcome to the Paper of the Day (Po’D): On Theorem 10 Edition. Today’s paper is now available with early access: B. L. Sturm, B. Mailhé, and M. D. Plumbley, “On Theorem 10 in “On Polar Polytopes and the Recovery of Sparse Representations”,” IEEE Trans. Info. Theory (in publication).
Though my past 16 months have for the most part been active in a completely different topic, I have been able to have some fun in sparse approximation theory. In this paper, we illuminate two previous results about exact recovery, and in the process, discover a more general exact recovery condition for basis pursuit (BP). I found this work fascinating for several reasons. The first is that it is not exactly trivial when considering dictionaries that do not have unit-norm atoms in orthogonal matching pursuit (OMP) and BP. The second reason is that this led us to an ERC of BP different from Tropp’s. The third reason is that the previous result of Plumbley — which is not wrong, but does not express the properties of any recovery algorithm — led us to investigate the nestedness properties of OMP and BP. And this shows that OMP and BP are quite different algorithms in the nestedness department.
With regardless to that last point, we have an ICASSP paper this year: B. Mailhé, B. L. Sturm, and M. D. Plumbley, “Recovery of nested supports by greedy sparse representation algorithms“, Proc. ICASSP, 2013.