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
- scientific article; zbMATH DE number 5137323 (Why is no real title available?)
- scientific article; zbMATH DE number 3572315 (Why is no real title available?)
- A Theory for Sampling Signals From a Union of Subspaces
- A note on equiangular tight frames
- A parameterized view on matroid optimization problems
- 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
- Lower Bounds on Crosspoints in Concentrators
- NP is as easy as detecting unique solutions
- On Representatives of Subsets
- On minimization on Stiefel manifolds
- On signal reconstruction without phase
- On sparse reconstruction from Fourier and Gaussian measurements
- On the Vector Representation of Matroids
- On the conditioning of random subdictionaries
- 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
(57)- Phase retrieval via polarization in dynamical sampling
- Phase retrieval of real-valued signals in a shift-invariant space
- The road to deterministic matrices with the restricted isometry property
- Tight and full spark Chebyshev frames with real entries and worst-case coherence analysis
- Matrix methods for perfect signal recovery underlying range space of operators
- Time-frequency analysis on flat tori and Gabor frames in finite dimensions
- Norm retrieval algorithms: a new frame theory approach
- Sparse matrices in frame theory
- Balanced frames: a useful tool in signal processing with good properties
- Dihedral group frames which are maximally robust to erasures
- Phase retrieval from very few measurements
- Uniform excess frames in Hilbert spaces
- Symplectic geometry and connectivity of spaces of frames
- Parseval transforms for finite frames
- Computing the spark: mixed-integer programming for the (vector) matroid girth problem
- A null space analysis of the _1-synthesis method in dictionary-based compressed sensing
- Spark-level sparsity and the \(\ell_1\) tail minimization
- The Paulsen problem made simple
- Towards a classification of incomplete Gabor POVMs in ℂ d
- Restoring the signal by modules of measurement
- On structural decompositions of finite frames
- Full spark frames in the orbit of a representation
- On root frames in \(\mathbb{R}^d\)
- Prime tight frames
- Three proofs of the Benedetto-Fickus theorem
- Reconstruction of signals from magnitudes of redundant representations: the complex case
- Equiangular tight frames with simplices and with full spark in \(\mathbb{R}^d\)
- Nilpotent bridging for unions of two bases
- Bridging erasures and the infrastructure of frames
- Fusion frame homotopy and tightening fusion frames by gradient descent
- Characterization of (weak) phase retrieval dual frames
- Full spark frames and totally positive matrices
- About the systems with full spark
- A primal Douglas-Rachford splitting method for the constrained minimization problem in compressive sensing
- Toric symplectic geometry and full spark frames
- Smoothness in some varieties with dihedral symmetry and the DFT matrix
- Full-spark frames arising from one-parameter groups
- Preserving injectivity under subgaussian mappings and its application to compressed sensing
- Group-theoretic constructions of erasure-robust frames
- Riesz bases of exponentials on unbounded multi-tiles
- Signal reconstruction from frame and sampling erasures
- A Quiver Invariant Theoretic Approach to Radial Isotropy and the Paulsen Problem for Matrix Frames
- Saving phase: injectivity and stability for phase retrieval
- Erasure recovery matrices for encoder protection
- Safe feature elimination for non-negativity constrained convex optimization
- Maximum robustness and surgery of frames in finite dimensions
- Robust Phase Retrieval Algorithm for Time-Frequency Structured Measurements
- Optimal Parseval frames: total coherence and total volume
- An effective algorithm for the spark of sparse binary measurement matrices
- Equiangular tight frames that contain regular simplices
- Connectivity and irreducibility of algebraic varieties of finite unit norm tight frames
- Sparsity and spectral properties of dual frames
- Atomic norm minimization for decomposition into complex exponentials and optimal transport in Fourier domain
- Processing of sparse signals and mutual coherence of ``measurable vectors
- Numerically erasure-robust frames
- Dual frames compensating for erasures -- a non-canonical case
- Surgery of frames in Hilbert spaces
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)
