Robust Recovery of Robinson Property in L^p-Graphons: A Cut-Norm Approach

2023/03/29 by Mahya Ghandehari, Ghandehari, Mahya, Teddy Mishura +1
Mathematics · Physics and Astronomy · Engineering · #Random Matrices and Applications #Quantum optics and atomic interactions #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.2303.16598

Abstract

This paper investigates the Robinson graphon completion/recovery problem within the class of L^p-graphons, focusing on the range 5 5, any L^p-graphon w can be approximated by a Robinson graphon, with error of the approximation bounded in terms of Λ(w). When viewing w as a noisy version of a Robinson graphon, our method provides a concrete recipe for recovering a cut-norm approximation of a noiseless w. Given that any symmetric matrix is a special type of graphon, our results can be applicable to symmetric matrices of any size. Our work extends and improves previous results, where a similar question for the special case of L^∞-graphons was answered.

Related

• A Partial Characterization of Robinsonian L^p Graphons
• Cut norm discontinuity of triangular truncation of graphons
• Graphons, cut norm and distance, couplings and rearrangements
• A sampling construction of graphon 1-norm convergence
• Optimal graphon estimation in cut distance