On Sparse Representation in Fourier and Local Bases

I just received the following from Pier Luigi:

Dear Igor,

I hope things are good with you and sorry for this email out of the blue.

I am writing to you because together with Yue Lu from Harvard University we have revisited the classical
problem of finding the sparse representation of a signal in a pair of bases, specifically Fourier and local bases,
and introduced a polynomial complexity algotithm, ProSparse, that solves the problem under the unicity constraint only. Thus the algorithm
works also when l_1 fails. In this way we implicitly demonstrate that the sparse representation problem for these specific structured dictionaries is not NP hard.

This is a result that applies, currently, to a limited number of cases, but given that it looks at the sparse representation problem in a way different from the traditional l_1 approach, I thought that this may
intrigue the nuit-blanche community. And this is why I'm contacting you. If you think it is worth it, you may consider mentioning it
in your blog.

The paper is open-access and is available at:

http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=6918471&tag=1

all the best,
Pier Luigi

Thanks Pier Luigi ! Here is the paper:

 

     

On Sparse Representation in Fourier and Local Bases by Pier Luigi Dragotti and Yue M. Lu

We consider the classical problem of finding the sparse representation of a signal in a pair of bases. When both bases are orthogonal, it is known that the sparse representation is unique when the sparsity K of the signal satisfies K lt 1/μ(D), where μ(D) is the mutual coherence of the dictionary. Furthermore, the sparse representation can be obtained in polynomial time by Basis Pursuit (BP), when K lt 0.91/μ(D). Therefore, there is a gap between the unicity condition and the one required to use the polynomial-complexity BP formulation. For the case of general dictionaries, it is also well known that finding the sparse representation under the only constraint of unicity is NP-hard. In this paper, we introduce, for the case of Fourier and canonical bases, a polynomial complexity algorithm that finds all the possible K-sparse representations of a signal under the weaker condition that K lt √2/μ(D). Consequently, when K lt 1/μ(D), the proposed algorithm solves the unique sparse representation problem for this structured dictionary in polynomial time. We further show that the same method can be extended to many other pairs of bases, one of which must have local atoms.Examples include the union of Fourier and local Fourier bases, the union of discrete cosine transform and canonical bases, and the union of random Gaussian and canonical bases.

An implementation can be found here.

  Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.