@article{Lu:2018:10.1109/TIT.2017.2735450,
author = {Lu, Y and Onativia, J and Dragotti, P},
doi = {10.1109/TIT.2017.2735450},
journal = {IEEE Transactions on Information Theory},
pages = {2639--2647},
title = {Sparse representation in Fourier and local bases Using ProSparse: a probabilistic analysis},
url = {http://dx.doi.org/10.1109/TIT.2017.2735450},
volume = {64},
year = {2018}
}

Download

TY  - JOUR
AB  - 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 generatingfunction 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.
AU  - Lu,Y
AU  - Onativia,J
AU  - Dragotti,P
DO  - 10.1109/TIT.2017.2735450
EP  - 2647
PY  - 2018///
SN  - 0018-9448
SP  - 2639
TI  - Sparse representation in Fourier and local bases Using ProSparse: a probabilistic analysis
T2  - IEEE Transactions on Information Theory
UR  - http://dx.doi.org/10.1109/TIT.2017.2735450
UR  - http://hdl.handle.net/10044/1/50069
VL  - 64
ER  - 

Download