Functional Donoho-Elad-Gribonval-Nielsen-Fuchs Sparsity Theorem

2025/09/01 by Krishna, K. Mahesh
#42C15 #46B45 #94A12 #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Information Theory (cs.IT) #Optimization and Control (math.OC)

paper · doi:10.48550/arxiv.2510.09609

Abstract

Celebrated breakthrough sparsity theorem obtained independently by Donoho and Elad [Proc. Natl. Acad. Sci. USA, 2003] and Gribonval and Nielsen [IEEE Trans. Inform. Theory, 2003] and Fuchs [IEEE Trans. Inform. Theory, 2004] says that unique sparse solution to NP-Hard ℓ₀-minimization problem can be obtained using unique solution to P-Type ℓ₁-minimization problem. In this paper, we extend their result to abstract Banach spaces using 1-approximate Schauder frames. We notice that the `normalized' condition for Hilbert spaces can be generalized to a larger extent when we consider Banach spaces.

Citations

• Noncommutative Donoho-Elad-Gribonval-Nielsen-Fuchs Sparsity Theorem
• Towards characterizations of approximate Schauder frame and its duals for Banach spaces
• The Computational Complexity of the Restricted Isometry Property, the\n Nullspace Property, and Related Concepts in Compressed Sensing
• Theory and Applications of Compressed Sensing
• The Power of Convex Relaxation: Near-Optimal Matrix Completion
• From Sparse Solutions of Systems of Equations to Sparse Modeling of Signals and Images
• The Dantzig selector: Statistical estimation when p is much larger than n
• Stable Signal Recovery from Incomplete and Inaccurate Measurements
• Stable signal recovery from incomplete and inaccurate measurements
• Decoding by Linear Programming
• Near Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• Robust Uncertainty Principles: Exact Signal Reconstruction from Highly Incomplete Frequency Information
• Atomic Decomposition by Basis Pursuit
• Sparse Approximate Solutions to Linear Systems

Related

• Noncommutative Donoho-Elad-Gribonval-Nielsen-Fuchs Sparsity Theorem
• Dilation theorem for p-approximate Schauder frames for separable Banach spaces
• Lp Quasi-norm Minimization: Algorithm and Applications
• Sparse Representer Theorems for Learning in Reproducing Kernel Banach Spaces
• The (abc,pqr)-problem for Approximate Schauder Frames for Banach Spaces