Timeline for Quickly determining if a matrix has any PSD completion
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 4, 2023 at 8:31 | comment | added | Bruno Le Floch | The condition "$M$ is PSD in its specified entries" is still missing from this answer: a non-PSD matrix with all entries specified gives a trivial counterexample of what is stated here. | |
| Apr 17, 2023 at 15:44 | comment | added | Paul Christiano | Thanks for pointing that out. Random sparse graphs seem like a hard case, which I think are far from chordal. And if we pick an arbitrary graph G and arbitrary PSD matrix M, and then reveal the corresponding entries from M, there will always be a PSD completion. | |
| Apr 17, 2023 at 11:20 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
edited body
|
| Apr 17, 2023 at 9:57 | comment | added | Carlo Beenakker | @DanielPaleka --- that is correct, thanks for specifying this. | |
| Apr 17, 2023 at 9:48 | comment | added | Daniel Paleka | My understanding is that this is the result: G is chordal <=> every partial matrix supported on G, that is not already non-PSD in the revealed entries, can be completed to a full PSD matrix. But this doesn't exclude the possibility of a specific matrix having a PSD completion, with the graph not being chordal. | |
| Apr 17, 2023 at 7:20 | history | edited | Carlo Beenakker | CC BY-SA 4.0 |
added 69 characters in body
|
| Apr 17, 2023 at 6:33 | history | answered | Carlo Beenakker | CC BY-SA 4.0 |