Greedy approximation algorithms for sparse collections

2022/02/21 by Guillermo Rey, Rey, Guillermo
Mathematics · #Advanced Harmonic Analysis Research #Analytic Number Theory Research #Classical Analysis and ODEs (math.CA) #FOS: Mathematics #Mathematical Approximation and Integration

paper · pdf · doi:10.48550/arxiv.2202.10267

openalex publication_date 2022/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We describe a greedy algorithm that approximates the Carleson constant of a collection of general sets. The approximation has a logarithmic loss in a general setting, but is optimal up to a constant with only mild geometric assumptions. The constructive nature of the algorithm gives additional information about the almost-disjoint structure of sparse collections. As applications, we give three results for collections of axis-parallel rectangles in every dimension. The first is a constructive proof of the equivalence between Carleson and sparse collections, first shown by Hänninen. The second is a structure theorem proving that every collection E can be partitioned into O(N) sparse subfamilies where N is the Carleson constant of E. We also give examples showing that such a decomposition is impossible when the geometric assumptions are dropped. The third application is a characterization of the Carleson constant involving only L^1,∞ estimates.

Related

• Sparse approximation by greedy algorithms
• Sparse approximation using new greedy-like bases in superreflexive spaces
• Approximating Small Sparse Cuts
• Sparse approximation and recovery by greedy algorithms in Banach spaces
• Sparse Approximation in Lattices and Semigroups