Reconstructing undirected graphs from eigenspaces
| Autor: | Yohann De Castro, Espinasse, T., Rochet, P. |
|---|---|
| Přispěvatelé: | Laboratoire de Mathématiques d'Orsay (LM-Orsay), Centre National de la Recherche Scientifique (CNRS)-Université Paris-Sud - Paris 11 (UP11), Probabilités, statistique, physique mathématique (PSPM), Institut Camille Jordan [Villeurbanne] (ICJ), École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Mathématiques Jean Leray (LMJL), Centre National de la Recherche Scientifique (CNRS)-Université de Nantes - UFR des Sciences et des Techniques (UN UFR ST), Université de Nantes (UN)-Université de Nantes (UN) |
| Jazyk: | angličtina |
| Rok vydání: | 2017 |
| Předmět: |
FOS: Computer and information sciences
Information Theory (cs.IT) Computer Science - Information Theory [MATH.MATH-IT]Mathematics [math]/Information Theory [math.IT] Machine Learning (stat.ML) Mathematics - Statistics Theory Statistics Theory (math.ST) [STAT.TH]Statistics [stat]/Statistics Theory [stat.TH] [STAT.OT]Statistics [stat]/Other Statistics [stat.ML] Methodology (stat.ME) Statistics - Machine Learning FOS: Mathematics [STAT.ME]Statistics [stat]/Methodology [stat.ME] Statistics - Methodology |
| Zdroj: | Journal of Machine Learning Research Journal of Machine Learning Research, Microtome Publishing, 2017 HAL Yohann De Castro Scopus-Elsevier |
| ISSN: | 1532-4435 1533-7928 |
| Popis: | In this paper, we aim at recovering an undirected weighted graph of $N$ vertices from the knowledge of a perturbed version of the eigenspaces of its adjacency matrix $W$. For instance, this situation arises for stationary signals on graphs or for Markov chains observed at random times. Our approach is based on minimizing a cost function given by the Frobenius norm of the commutator $\mathsf{A} \mathsf{B}-\mathsf{B} \mathsf{A}$ between symmetric matrices $\mathsf{A}$ and $\mathsf{B}$. In the Erd\H{o}s-R\'enyi model with no self-loops, we show that identifiability (i.e., the ability to reconstruct $W$ from the knowledge of its eigenspaces) follows a sharp phase transition on the expected number of edges with threshold function $N\log N/2$. Given an estimation of the eigenspaces based on a $n$-sample, we provide support selection procedures from theoretical and practical point of views. In particular, when deleting an edge from the active support, our study unveils that our test statistic is the order of $\mathcal O(1/n)$ when we overestimate the true support and lower bounded by a positive constant when the estimated support is smaller than the true support. This feature leads to a powerful practical support estimation procedure. Simulated and real life numerical experiments assert our new methodology. Comment: 25 pages, some figures. Final version |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|