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

MaRDI QIDQ6431258FDO

Authors Mahya Ghandehari, Teddy Mishura

Publication date 29 March 2023

Mathematics Subject Classification ID

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

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.

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)