2025/04/20 by Aldahleh, K., Iosevich, A., Iosevich, J. +3 · 2 citations
#42B10 #94A12 #Classical Analysis and ODEs (math.CA) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2504.14702
Given a signal f:G→ℂ, where G is a finite abelian group, under what reasonable assumptions can we guarantee the exact recovery of f from a proper subset of its Fourier coefficients? In 1989, Donoho and Stark established a result \citeDS89 using the classical uncertainty principle, which states that |supp(f)|⋅|supp(f)|≥ |G| for any nonzero signal f. Another result, first proven by Santose and Symes \citeSS86, was based on the Logan phenomenon \citeL65. In particular, the result showcases how the L1 and L2 minimizing signals with matching Fourier frequencies often recovers the original signal. The purpose of this paper is to relate these recovery mechanisms to additive energy, a combinatorial measure denoted and defined by Λ(A)=| \ (x1, x2, x3, x4) ∈ A4 | x1 + x2 = x3 + x4 \ |, where A⊂ℤNd. In the first part of this paper, we use combinatorial techniques to establish an improved variety of the uncertainty principle in terms of additive energy. In a similar fashion as the Donoho-Stark argument, we use this principle to establish an often stronger recovery condition. In the latter half of the paper, we invoke these combinatorial methods to demonstrate two Lp minimizing recovery results.