Sparse Representation in Fourier and Local Bases Using ProSparse: A Probabilistic Analysis
From MaRDI portal
Publication:4569209
DOI10.1109/TIT.2017.2735450zbMATH Open1390.94286arXiv1611.07971OpenAlexW2963505610WikidataQ62005488 ScholiaQ62005488MaRDI QIDQ4569209FDOQ4569209
Authors: Yue M. Lu, Jon Oñativia, Pier Luigi Dragotti 
Publication date: 27 June 2018
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1611.07971
Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Combinatorial probability (60C05)
Cited In (3)
This page was built for publication: Sparse Representation in Fourier and Local Bases Using ProSparse: A Probabilistic Analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4569209)
