Full spark frames

DOI10.1007/S00041-012-9235-4zbMATH Open1257.42040arXiv1110.3548OpenAlexW2022267471MaRDI QIDQ1934656FDOQ1934656

Authors: Boris Alexeev, Jameson Cahill, Dustin G. Mixon 

Publication date: 29 January 2013

Published in: The Journal of Fourier Analysis and Applications (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1110.3548

Recommendations

• About the systems with full spark
• Processing of sparse signals and mutual coherence of ``measurable vectors
• Full-spark frames arising from one-parameter groups
• Full spark frames in the orbit of a representation
• Full spark frames and totally positive matrices

zbMATH Keywords

sparsityframessparkerasures

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General harmonic expansions, frames (42C15)

Cites Work

• Phaselift: exact and stable signal recovery from magnitude measurements via convex programming
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• Decoding by Linear Programming
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
• The Kadison–Singer Problem in mathematics and engineering
• Title not available (Why is that?)
• The road to deterministic matrices with the restricted isometry property
• An uncertainty principle for cyclic groups of prime order
• On the Vector Representation of Matroids
• Grassmannian frames with applications to coding and communication
• On sparse reconstruction from Fourier and Gaussian measurements
• On Representatives of Subsets
• Performance Analysis for Sparse Support Recovery
• The restricted isometry property and its implications for compressed sensing
• NP is as easy as detecting unique solutions
• Optimal frames for erasures.
• Symmetric informationally complete quantum measurements
• Steiner equiangular tight frames
• Painless reconstruction from magnitudes of frame coefficients
• On signal reconstruction without phase
• Achieving the Welch Bound With Difference Sets
• Two are better than one: fundamental parameters of frame coherence
• Equiangular tight frames from Paley tournaments
• Fast Sparse Representation Based on Smoothed ℓ0 Norm
• On the conditioning of random subdictionaries
• Title not available (Why is that?)
• On minimization on Stiefel manifolds
• Sparse Bayesian Learning for Basis Selection
• Finite frame varieties: Nonsingular points, tangent spaces, and explicit local parameterizations
• Chebotarëv and his density theorem
• Optimally Sparse Frames
• Generalized Vandermonde Determinants and Roots of Unity of Prime Order
• Optimal approximation of sparse hessians and its equivalence to a graph coloring problem
• A note on equiangular tight frames
• Fingerprinting With Equiangular Tight Frames
• A Theory for Sampling Signals From a Union of Subspaces
• Sampling Theorems for Signals From the Union of Finite-Dimensional Linear Subspaces
• A parameterized view on matroid optimization problems
• Rank-deficient submatrices of Fourier matrices
• Lower Bounds on Crosspoints in Concentrators

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
• Sparse matrices in frame theory
• Smoothness in Some Varieties with Dihedral Symmetry and the DFT Matrix
• Dihedral group frames which are maximally robust to erasures
• Balanced frames: a useful tool in signal processing with good properties
• 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 \(\ell_1\)-synthesis method in dictionary-based compressed sensing
• Towards a classification of incomplete Gabor POVMs in ℂ ^d
• Spark-level sparsity and the \(\ell_1\) tail minimization
• The Paulsen problem made simple
• Full spark frames in the orbit of a representation
• On structural decompositions of finite frames
• On root frames in \(\mathbb{R}^d\)
• Prime tight frames
• Equiangular tight frames with simplices and with full spark in \(\mathbb{R}^d\)
• Reconstruction of signals from magnitudes of redundant representations: the complex case
• Nilpotent bridging for unions of two bases
• Fusion frame homotopy and tightening fusion frames by gradient descent
• Bridging erasures and the infrastructure of frames
• Characterization of (weak) phase retrieval dual frames
• Full spark frames and totally positive matrices
• A primal Douglas-Rachford splitting method for the constrained minimization problem in compressive sensing
• Connectivity and Irreducibility of Algebraic Varieties of Finite Unit Norm Tight Frames
• Tight and full spark Chebyshev frames with real entries and worst-case coherence analysis
• Toric symplectic geometry and full spark frames
• Full-spark frames arising from one-parameter groups
• Preserving injectivity under subgaussian mappings and its application to compressed sensing
• Riesz bases of exponentials on unbounded multi-tiles
• Group-theoretic constructions of erasure-robust frames
• ABOUT THE SYSTEMS WITH FULL SPARK
• 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
• Title not available (Why is that?)
• An effective algorithm for the spark of sparse binary measurement matrices
• Equiangular tight frames that contain regular simplices
• Atomic norm minimization for decomposition into complex exponentials and optimal transport in Fourier domain
• Processing of sparse signals and mutual coherence of ``measurable vectors
• Surgery of frames in Hilbert spaces
• Sparsity and spectral properties of dual frames
• Numerically erasure-robust frames
• 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
• Three proofs of the Benedetto-Fickus theorem
• Optimal Parseval frames: total coherence and total volume
• Dual frames compensating for erasures -- a non-canonical case

Uses Software

• PhaseLift

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)