Abstract: 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.
Recommendations
Cites work
- A note on equiangular tight frames
- A parameterized view on matroid optimization problems
- A Theory for Sampling Signals From a Union of Subspaces
- Achieving the Welch Bound With Difference Sets
- An uncertainty principle for cyclic groups of prime order
- Chebotarëv and his density theorem
- Decoding by Linear Programming
- Equiangular tight frames from Paley tournaments
- Fast Sparse Representation Based on Smoothed ℓ0 Norm
- Fingerprinting With Equiangular Tight Frames
- Finite frame varieties: Nonsingular points, tangent spaces, and explicit local parameterizations
- Generalized Vandermonde Determinants and Roots of Unity of Prime Order
- Grassmannian frames with applications to coding and communication
- scientific article; zbMATH DE number 5137323 (Why is no real title available?)
- scientific article; zbMATH DE number 3572315 (Why is no real title available?)
- Lower Bounds on Crosspoints in Concentrators
- NP is as easy as detecting unique solutions
- On minimization on Stiefel manifolds
- On Representatives of Subsets
- On signal reconstruction without phase
- On sparse reconstruction from Fourier and Gaussian measurements
- On the conditioning of random subdictionaries
- On the Vector Representation of Matroids
- Optimal approximation of sparse hessians and its equivalence to a graph coloring problem
- Optimal frames for erasures.
- Optimally Sparse Frames
- Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization
- Painless reconstruction from magnitudes of frame coefficients
- Performance Analysis for Sparse Support Recovery
- Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
- Rank-deficient submatrices of Fourier matrices
- Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
- Sampling Theorems for Signals From the Union of Finite-Dimensional Linear Subspaces
- Sparse Bayesian Learning for Basis Selection
- Steiner equiangular tight frames
- Symmetric informationally complete quantum measurements
- The restricted isometry property and its implications for compressed sensing
- The road to deterministic matrices with the restricted isometry property
- Two are better than one: fundamental parameters of frame coherence
Cited in
(61)- Equiangular tight frames that contain regular simplices
- Spark-level sparsity and the _1 tail minimization
- Uniform excess frames in Hilbert spaces
- Computing the spark: mixed-integer programming for the (vector) matroid girth problem
- Symplectic geometry and connectivity of spaces of frames
- The Paulsen problem made simple
- Toric symplectic geometry and full spark frames
- Phase retrieval of real-valued signals in a shift-invariant space
- Full spark frames in the orbit of a representation
- Atomic norm minimization for decomposition into complex exponentials and optimal transport in Fourier domain
- Processing of sparse signals and mutual coherence of ``measurable vectors
- Balanced frames: a useful tool in signal processing with good properties
- Saving phase: injectivity and stability for phase retrieval
- Sparse matrices in frame theory
- An effective algorithm for the spark of sparse binary measurement matrices
- Erasure recovery matrices for encoder protection
- Safe feature elimination for non-negativity constrained convex optimization
- Group-theoretic constructions of erasure-robust frames
- Nilpotent bridging for unions of two bases
- A primal Douglas-Rachford splitting method for the constrained minimization problem in compressive sensing
- Phase retrieval from very few measurements
- Maximum robustness and surgery of frames in finite dimensions
- Equiangular tight frames with simplices and with full spark in \(\mathbb{R}^d\)
- On structural decompositions of finite frames
- Reconstruction of signals from magnitudes of redundant representations: the complex case
- About the systems with full spark
- Dihedral group frames which are maximally robust to erasures
- Sparsity and spectral properties of dual frames
- Numerically erasure-robust frames
- Parseval transforms for finite frames
- Restoring the signal by modules of measurement
- Prime tight frames
- Riesz bases of exponentials on unbounded multi-tiles
- Smoothness in some varieties with dihedral symmetry and the DFT matrix
- Tight and full spark Chebyshev frames with real entries and worst-case coherence analysis
- The road to deterministic matrices with the restricted isometry property
- Full spark frames and totally positive matrices
- Full-spark frames arising from one-parameter groups
- A Quiver Invariant Theoretic Approach to Radial Isotropy and the Paulsen Problem for Matrix Frames
- Surgery of frames in Hilbert spaces
- Connectivity and irreducibility of algebraic varieties of finite unit norm tight frames
- Bridging erasures and the infrastructure of frames
- Towards a classification of incomplete Gabor POVMs in ℂ d
- On root frames in \(\mathbb{R}^d\)
- Characterization of (weak) phase retrieval dual frames
- Optimal Parseval frames: total coherence and total volume
- Dual frames compensating for erasures -- a non-canonical case
- Robust Phase Retrieval Algorithm for Time-Frequency Structured Measurements
- Matrix methods for perfect signal recovery underlying range space of operators
- Time-frequency analysis on flat tori and Gabor frames in finite dimensions
- Fusion frame homotopy and tightening fusion frames by gradient descent
- Norm retrieval algorithms: a new frame theory approach
- Three proofs of the Benedetto-Fickus theorem
- Robustness of frames and totally nonsingular matrices
- Doubly transitive equiangular tight frames that contain regular simplices
- Permutation-invariant representations with applications to graph deep learning
- Unique reconstruction from mean-field measurements
- A null space analysis of the _1-synthesis method in dictionary-based compressed sensing
- Signal reconstruction from frame and sampling erasures
- Preserving injectivity under subgaussian mappings and its application to compressed sensing
- Phase retrieval via polarization in dynamical sampling
This page was built for publication: Full spark frames
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1934656)
