Back to Search
Start Over
Sparse Representation in Fourier and Local Bases Using ProSparse: A Probabilistic Analysis.
- Source :
-
IEEE Transactions on Information Theory . Apr2018, Vol. 64 Issue 4, p2639-2647. 9p. - Publication Year :
- 2018
-
Abstract
- Finding the sparse representation of a signal in an overcomplete dictionary has attracted a lot of attention over the past years. This paper studies ProSparse, a new polynomial complexity algorithm that solves the sparse representation problem when the underlying dictionary is the union of a Vandermonde matrix and a banded matrix. Unlike our previous work, which establishes deterministic (worst-case) sparsity bounds for ProSparse to succeed, this paper presents a probabilistic average-case analysis of the algorithm. Based on a generating-function approach, closed-form expressions for the exact success probabilities of ProSparse are given. The success probabilities are also analyzed in the high-dimensional regime. This asymptotic analysis characterizes a sharp phase transition phenomenon regarding the performance of the algorithm. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 64
- Issue :
- 4
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 128558535
- Full Text :
- https://doi.org/10.1109/TIT.2017.2735450