  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.
