题目：On the restricted isometry property of the Paley matrix and related results

报告人：Shohei Satake，Kumamoto University, Japan

时间：27 Dec，9:40am

腾讯会议ID: 100 963 177

摘要：

Matrices with restricted isometry property (RIP) have important applications to signal processing since, by adopting them, it is possible to measure and recover sparse signals using significantly fewer measurements than the dimension of the signals.

It is known that the problem checking whether a given matrix has RIP is NP-hard. Thus, many publications have attempted to give deterministic constructions of matrices having RIP. Most of known constructions of M × N matrices use the coherence to estimate RIP, however, it can certify the (K, δ)-RIP with only K = O(√M), which follows from the Welch bound. This barrier for the magnitude of the order of K is called the square-root bottleneck or quadratic bottleneck. From this situation, the following problem arises.

In this talk, assuming that the widely-believed Paley graph conjecture, we first show that the Paley matrix has RIP breaking through the quadratic bottleneck, for any sufficiently large prime p, including primes p ≡ 3 (mod 4). Second, corresponding to a result by Bandeira, Mixon and Moreira (2017) estimating the clique number of the Paley graph, we prove that the RIP of the Paley matrix implies a new upper bound on the size of transitive subtournaments (i.e., ones with no directed cycles) in the Paley tournament. The bound here is significantly better than the existing bounds by Tabib (1986), Momihara and Suda (2017) for this tournament.

This talk is based on arXiv:2011.02907.