12-27【Shohei Satake】 腾讯会议 吴文俊数学重点实验室组合图论系列讲座之163

发布者:万宏艳发布时间:2020-12-23浏览次数:519


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


报告人:Shohei SatakeKumamoto University, Japan


时间:27 Dec9: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 suciently 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.