Timeline for Quickly determining if a matrix has any PSD completion
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 5, 2023 at 17:33 | comment | added | Paul Christiano | Definitely agree that this a PSD matrix completion problem. I haven't found any references exploring very fast algorithms for this problem, or even clearly stating the fastest known algorithm, or conjecturing the optimal runtime. Have you seen some discussion in the literature? (My sense is that most active work on this topic seems focused on rank constraints or norm minimization problems rather than very fast existence checks.) | |
| May 5, 2023 at 0:23 | comment | added | Duyal Yolcu | My second link in the answer pure.uvt.nl/ws/portalfiles/portal/1215894/Matrix.pdf also discusses arbitrary k first (and defines the fixed-k problem later); the names are "EDM" vs. "EDMk". Of course, k=n will always be high enough... | |
| May 5, 2023 at 0:17 | comment | added | Duyal Yolcu | epubs.siam.org/doi/abs/10.1137/… doesn't seem to talk about rank conditions when defining the main problem (P). | |
| May 4, 2023 at 23:37 | comment | added | Bruno Le Floch | Digging a bit in the literature it seems people care mostly about the low-rank case, namely embedding into a Euclidean space of a fixed dimension and asking about complexity as the graph size grows. This leads to an NP-hard problem. Did you find interesting references that do not impose a rank condition? | |
| S May 4, 2023 at 22:19 | review | First answers | |||
| May 5, 2023 at 1:02 | |||||
| S May 4, 2023 at 22:19 | history | answered | Duyal Yolcu | CC BY-SA 4.0 |