Sparse Representation in Fourier and Local Bases Using ProSparse: A Probabilistic Analysis

DOI10.1109/TIT.2017.2735450MaRDI QIDQ4569209zbMATH OpenOpenAlexWikidataFDO

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)

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

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Combinatorial probability (60C05)

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.

Cited in

(3)

• A New Method Using Table to Sparse Representation in Pairs of Bases with Matching Pursuits
• ProSparse
• On sparse representation in pairs of bases

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)