Computing maximum likelihood thresholds using graph rigidity
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2022
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929349268078592 |
|---|---|
| author | Bernstein, Daniel Irving Dewar, Sean Gortler, Steven J. Nixon, Anthony Sitharam, Meera Theran, Louis |
| author_facet | Bernstein, Daniel Irving Dewar, Sean Gortler, Steven J. Nixon, Anthony Sitharam, Meera Theran, Louis |
| contents | The maximum likelihood threshold (MLT) of a graph $G$ is the minimum number of samples to almost surely guarantee existence of the maximum likelihood estimate in the corresponding Gaussian graphical model. Recently a new characterization of the MLT in terms of rigidity-theoretic properties of $G$ was proved \cite{Betal}. This characterization was then used to give new combinatorial lower bounds on the MLT of any graph. We continue this line of research by exploiting combinatorial rigidity results to compute the MLT precisely for several families of graphs. These include graphs with at most $9$ vertices, graphs with at most 24 edges, every graph sufficiently close to a complete graph and graphs with bounded degrees. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2210_11081 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Computing maximum likelihood thresholds using graph rigidity Bernstein, Daniel Irving Dewar, Sean Gortler, Steven J. Nixon, Anthony Sitharam, Meera Theran, Louis Combinatorics Metric Geometry Statistics Theory 62H12 (Primary), 52C25 (Secondary) The maximum likelihood threshold (MLT) of a graph $G$ is the minimum number of samples to almost surely guarantee existence of the maximum likelihood estimate in the corresponding Gaussian graphical model. Recently a new characterization of the MLT in terms of rigidity-theoretic properties of $G$ was proved \cite{Betal}. This characterization was then used to give new combinatorial lower bounds on the MLT of any graph. We continue this line of research by exploiting combinatorial rigidity results to compute the MLT precisely for several families of graphs. These include graphs with at most $9$ vertices, graphs with at most 24 edges, every graph sufficiently close to a complete graph and graphs with bounded degrees. |
| title | Computing maximum likelihood thresholds using graph rigidity |
| topic | Combinatorics Metric Geometry Statistics Theory 62H12 (Primary), 52C25 (Secondary) |
| url | https://arxiv.org/abs/2210.11081 |