2026/07/30 by Zhao Song
Computer Science · Mathematics · #cs.DS #math.PR
arxiv created 2026/07/30 · arxiv updated 2026/07/31
We prove an improved restricted isometry bound for Gaussian partial circulant matrices with arbitrary prescribed sampling sets. There is a universal constant C>0 such that the following holds. Let 1≤ K≤ m≤ N be positive integers, let Ω⊂\mathbb ZN be any fixed set with |Ω|=m, and let g∼\mathcal N(0,IN). For every δ,η∈(0,1), the normalized partial circulant matrix generated by g has the RIP of order K with constant at most δ, with probability at least 1-η over the draw of g, provided m≥ Cδ-2K max\log2(eK)log(2N)log(em),log(2/η)\. The proof refines the Maurey entropy step in the chaos-process argument by combining a noncommutative Khintchine inequality with a Schatten moment estimate controlled by m, replacing one factor log(2N) in the Krahmer--Mendelson--Rauhut bound by log(em).