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

arXiv2303.16598MaRDI QIDQ6431258FDOQ6431258

Mahya Ghandehari, Teddy Mishura

Publication date: 29 March 2023

Abstract: In this paper, we study the Robinson graphon completion/recovery problem for the class of $L^p$-graphons. We introduce a function $Lambda$ on the space of $L^p$-graphons, which measures the extent to which a graphon $w$ exhibits the Robinson property: for all $x<y<z$, $w(x,z)leqminw(x,y),w(y,z)$. We prove that the function $Lambda$ satisfies the following: (1) $Lambda$ is compatible with the cut-norm, in the sense that if two graphons are close in the cut-norm, then their $Lambda$ values are close; and (2) when $p>5$, every $L^p$-graphon $w$ can be approximated by a Robinson graphon, with error of the approximation bounded in terms of IN{$Lambda(w)$}. When $w$ is a noisy version of a Robinson graphon, our method provides a concrete formula for recovering the Robinson graphon approximating $w$ in cut-norm.

Mathematics Subject Classification ID

Matrix completion problems (15A83) Random matrices (algebraic aspects) (15B52) Graph representations (geometric and intersection representations, etc.) (05C62)

This page was built for publication: Robust Recovery of Robinson Property in $L^p$-Graphons: A Cut-Norm Approach

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6431258)