Full Spark Frames

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 s...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of fourier analysis and applications 2012-12, Vol.18 (6), p.1167-1194
Main Authors: Alexeev, Boris, Cahill, Jameson, Mixon, Dustin G.
Format: Article
Language:English
Subjects:
Abstract Harmonic Analysis
Approximations and Expansions
Fourier Analysis
Mathematical Methods in Physics
Mathematics
Mathematics and Statistics
Partial Differential Equations
Signal processing
Signal,Image and Speech Processing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 new constructions using the discrete Fourier transform. 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.
ISSN:1069-5869
1531-5851
DOI:10.1007/s00041-012-9235-4