  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.
