On the restricted isometry property of the Paley matrix

2020/10/19 by Satake, Shohei · 1 citation
#05C20 #94A08 #Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.2011.02907

Abstract

In this paper, we prove that the Paley graph conjecture implies that the Paley matrix has restricted isometry property (RIP) beating the square-root bottleneck for the sparsity level. Moreover, we show that the RIP of the Paley matrix implies an improved bound on the size of transitive subtournaments in the Paley tournament.

Cited by

• Square-Difference-Free Sets beyond the Three-Quarter Barrier

Related

• On Compressed Sensing Matrices Breaking the Square-Root Bottleneck
• On the Paley RIP and Paley graph extractor
• The road to deterministic matrices with the restricted isometry property
• Restricted Isometry Property for General p-Norms
• Explicit construction of RIP matrices is Ramsey-hard