PDF logo Full spark frames

by Boris Alexeev, Jameson Cahill, and Dustin G. Mixon


Finite frame theory has a number of real-world applications. In applications like sparse signal processing, data transmission with robustness to erasures, and reconstruction without phase, there is a pressing need for deterministic constructions of frames with the following property: every size-M subcollection of the M-dimensional frame elements is a spanning set. Such frames are called full spark frames, and this paper provides constructions using Vandermonde matrices and discrete Fourier transforms. Later, we prove that full spark Parseval frames are dense in the entire set of Parseval frames, meaning full spark frames are abundant, even if one imposes an additional tightness constraint. Finally, we prove that testing whether a given matrix is full spark is hard for NP under randomized polynomial-time reductions, indicating that deterministic full spark constructions are particularly significant because they guarantee a property which is otherwise difficult to check.

Approximate citation

Boris Alexeev, Jameson Cahill, and Dustin G. Mixon
Full spark frames
Journal of Fourier Analysis and Applications 18 (2012), no. 6, 1167–1194.

Useful links

PDF logoDirect PDF link
Journal icon Published journal version
DOI icon Persistent document object identifier (DOI)
arXiv icon arXiv online preprint server version
MathSciNet icon Math Reviews (MathSciNet) review
Google Scholar icon Google Scholar entry
BiBTeX icon Individual BiBTex entry