Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2303.16598 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910463252496384 |
|---|---|
| author | Ghandehari, Mahya Mishura, Teddy |
| author_facet | Ghandehari, Mahya Mishura, Teddy |
| contents | This paper investigates the Robinson graphon completion/recovery problem within the class of $L^p$-graphons, focusing on the range $5<p\leq \infty$. A graphon $w$ is Robinson if it satisfies the Robinson property: if $x\leq y\leq z$, then $w(x,z)\leq \min\{w(x,y),w(y,z)\}$. We demonstrate that if a graphon possesses localized near-Robinson characteristics, it can be effectively approximated by a Robinson graphon in terms of cut-norm. To achieve this recovery result, we introduce a function $Λ$, defined on the space of $L^p$-graphons, which quantifies the degree to which a graphon $w$ adheres to the Robinson property. We prove that $Λ$ is a suitable gauge for measuring the Robinson property when proximity of graphons is understood in terms of cut-norm. Namely, we show that (1) $Λ(w)=0$ precisely when $w$ is Robinson; (2) $Λ$ is cut-norm continuous, in the sense that if two graphons are close in the cut-norm, then their $Λ$ values are close; and (3) for $p > 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^\infty$-graphons was answered. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2303_16598 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Robust Recovery of Robinson Property in $L^p$-Graphons: A Cut-Norm Approach Ghandehari, Mahya Mishura, Teddy Combinatorics 05C62, 15A83, 15B52 This paper investigates the Robinson graphon completion/recovery problem within the class of $L^p$-graphons, focusing on the range $5<p\leq \infty$. A graphon $w$ is Robinson if it satisfies the Robinson property: if $x\leq y\leq z$, then $w(x,z)\leq \min\{w(x,y),w(y,z)\}$. We demonstrate that if a graphon possesses localized near-Robinson characteristics, it can be effectively approximated by a Robinson graphon in terms of cut-norm. To achieve this recovery result, we introduce a function $Λ$, defined on the space of $L^p$-graphons, which quantifies the degree to which a graphon $w$ adheres to the Robinson property. We prove that $Λ$ is a suitable gauge for measuring the Robinson property when proximity of graphons is understood in terms of cut-norm. Namely, we show that (1) $Λ(w)=0$ precisely when $w$ is Robinson; (2) $Λ$ is cut-norm continuous, in the sense that if two graphons are close in the cut-norm, then their $Λ$ values are close; and (3) for $p > 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^\infty$-graphons was answered. |
| title | Robust Recovery of Robinson Property in $L^p$-Graphons: A Cut-Norm Approach |
| topic | Combinatorics 05C62, 15A83, 15B52 |
| url | https://arxiv.org/abs/2303.16598 |