The Shift Bound for Abelian Codes and Generalizations of the Donoho-Stark Uncertainty Principle

• Published in: IEEE transactions on information theory 2019-08, Vol.65 (8), p.4673-4682
• Main Authors: Feng, Tao, Hollmann, Henk D. L., Xiang, Qing
• Format: Article
• Language: English
• Subjects: Abelian code; Algebra; Donoho-Stark uncertainty principle; Fourier transform; Fourier transforms; Group theory; Harmonic analysis; Indexes; Information theory; Sharpening; shift bound; Uncertainty; Uncertainty principles
• ISSN: 0018-9448; 1557-9654
• DOI: 10.1109/TIT.2019.2906301

Let G be a finite abelian group. If f: G\rightarrow {\mathbf{C}} is a nonzero function with Fourier transform \hat {f} , the Donoho-Stark uncertainty principle states that | {\mathrm{ supp}}(f)|| {\mathrm{ supp}}(\hat {f})|\geq |G| . The purpose of this paper is twofold. First, we present the shift bound for abelian codes with a streamlined proof. Second, we use the shifting technique to prove a generalization and a sharpening of the Donoho-Stark uncertainty principle. In particular, if f: G\rightarrow {\mathbf{F}} is a non-zero function from G to a field {\mathbf{F}} , and if f has a Fourier transform \hat {f} , the sharpened uncertainty principle states that | {\mathrm{ supp}}(f)|| {\mathrm{ supp}}(\hat {f})|\geq |G|+| {\mathrm{ supp}}(f)|-|H({\mathrm{ supp}}(f))| , where H({\mathrm{ supp}}(f)) is the stabilizer of {\mathrm{ supp}}(f) in G .