On Sparse Representation in Fourier and Local Bases

DOI10.1109/TIT.2014.2361858zbMATH Open1359.94044arXiv1310.6011OpenAlexW2029740707MaRDI QIDQ2979178FDOQ2979178

Authors: Pier Luigi Dragotti, Yue M. Lu 

Publication date: 2 May 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: 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<1/mu(D)$, where $mu(D)$ is the mutual coherence of the dictionary. Furthermore, the sparse representation can be obtained in polynomial time by Basis Pursuit (BP), when $K<0.91/mu(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<sqrt2/mu(D)$. Consequently, when $K<1/mu(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.

Full work available at URL: https://arxiv.org/abs/1310.6011

Mathematics Subject Classification ID

Application of orthogonal and other special functions (94A11)

Cited In (8)

• On sparse representation of analytic signal in Hardy space
• Computing Sparse Representations of Multidimensional Signals Using Kronecker Bases
• Sampling and reconstruction of sparse signals on circulant graphs. An introduction to graph-FRI
• A tree-based dictionary learning framework
• On sparse representation in pairs of bases
• Expander \(\ell_0\)-decoding
• Sparse approximation using new greedy-like bases in superreflexive spaces
• On Sparse Representations in Arbitrary Redundant Bases

This page was built for publication: On Sparse Representation in Fourier and Local Bases

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2979178)