Timeline for Quickly determining if a matrix has any PSD completion
Current License: CC BY-SA 4.0
28 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S May 11, 2023 at 18:08 | history | bounty ended | CommunityBot | ||
| S May 11, 2023 at 18:08 | history | notice removed | CommunityBot | ||
| May 7, 2023 at 13:52 | comment | added | Rodrigo de Azevedo | @PaulChristiano Please consider appending such important information to the question itself. Also, please consider providing some incomplete matrices for testing and benchmarking, say, in some GitHub repo. | |
| May 7, 2023 at 13:50 | comment | added | Paul Christiano | Sparsity pattern is adversarial. That said, as far as I am aware random sparsity patterns are hard and solving it in the random sparsity case would be nice. On the other hand, it's very important the entries themselves be adversarial rather than e.g. drawing positives from a wishart distribution. | |
| May 6, 2023 at 23:26 | comment | added | Bruno Le Floch | There may be a way based on alternate projections on the set of PSD and the set of matrices with the correct $m$ entries. This is inspired by reading Higham 2000 - Computing the nearest correlation matrix—a problem from finance. | |
| May 6, 2023 at 22:30 | comment | added | Rodrigo de Azevedo | @PaulChristiano Can you tell anything about the sparsity pattern? Here is what I have in mind. | |
| May 5, 2023 at 17:35 | comment | added | Paul Christiano | I don't care about the exact version of the problem. I mentioned epsilon slop, which I hope fixes such issues: we are allowed to answer arbitrarily if there are PSD completions but no completion with all eigenvalues at least epsilon, and I'm happy for polylogarithmic overhead in epsilon and the max matrix entry. | |
| May 5, 2023 at 17:29 | comment | added | Paul Christiano | If m < n then you can just ignore any rows/columns that have all ?s (i.e. insert 0s everywhere). | |
| May 5, 2023 at 12:57 | comment | added | Rodrigo de Azevedo | Related | |
| May 5, 2023 at 12:26 | comment | added | Stella Biderman | $O(mn)$ seems like an unreasonably fast algorithm. If $m$ is small relative to $n$, such an algorithm won’t even be able to write down a candidate value for each of the unassigned entries in the matrix. There are cases where one can find solutions faster than one can write them down, but that typically requires a large amount of structure to develop an implicit representation. I’m not an expert in matrix completions, but is there a reason to think this exists? Can one convert a $O(mn^2)$ solution to a $O(mn)$ one? | |
| May 4, 2023 at 23:32 | comment | added | Bruno Le Floch | Of course, the probably-unknown complexity of your problem in the bit model (namely counting bits used by coordinates) does not tell us anything about the complexity in the real model (namely ignoring issues of numerics). This discussion of NP should not be confused with the known fact (irrelevant to the present discussion) that the same question with a fixed bound on the matrix rank is NP hard. | |
| May 4, 2023 at 22:19 | answer | added | Duyal Yolcu | timeline score: 1 | |
| May 4, 2023 at 22:02 | comment | added | Bruno Le Floch | This problem goes by the name "Positive Semi Definite Matrix Completion", see for instance the 1997 review by Monique Laurent. It is related to the question of whether a graph with given edge lengths can be embedded into Euclidean space, which is amenable to semi-definite programming (SDP). However, it seems people don't know bounds on the "number of digits" of a solution to the SDP, so that the problem may even fail to be in NP. Do you care about such numerical artifacts, or only about the combinatorics problem itself? | |
| May 3, 2023 at 16:52 | comment | added | Paul Christiano | In addition to the MO bounty we're offering a $5k prize for algorithms (or lower bounds) for this question. You can find details here: alignment.org/blog/prize-for-matrix-completion-problems | |
| S May 3, 2023 at 16:51 | history | bounty started | Paul Christiano | ||
| S May 3, 2023 at 16:51 | history | notice added | Paul Christiano | Draw attention | |
| Apr 17, 2023 at 6:49 | history | became hot network question | |||
| Apr 17, 2023 at 6:33 | answer | added | Carlo Beenakker | timeline score: 5 | |
| Apr 17, 2023 at 6:21 | answer | added | Magi | timeline score: 4 | |
| Apr 17, 2023 at 5:48 | comment | added | Narutaka OZAWA | This is sdp, indeed. See Theorem 2.1 in doi.org/10.1016/0022-1236(89)90050-5. | |
| Apr 17, 2023 at 5:40 | comment | added | Rodrigo de Azevedo | Have you tried reducing it to a semidefinite program? | |
| Apr 17, 2023 at 5:37 | history | edited | Rodrigo de Azevedo | CC BY-SA 4.0 |
edited tags
|
| Apr 17, 2023 at 1:43 | comment | added | Paul Christiano | I added "(real, symmetric)" for clarity. I think the problem is equivalent regardless of which definition you use. | |
| Apr 17, 2023 at 1:43 | history | edited | Paul Christiano | CC BY-SA 4.0 |
added 18 characters in body
|
| Apr 16, 2023 at 23:11 | comment | added | ndrwnaguib | would the problem be simpler had the PSD matrix been decomposed into $Q\Lambda Q^{\top}$? | |
| Apr 16, 2023 at 21:47 | comment | added | Robert Israel | Does your definition of "positive semidefinitedefinite" require hermitian (or real symmetric) matrices? To avoid confusion, it's worth mentioning this, as some authors do not require this. | |
| Apr 16, 2023 at 20:07 | history | edited | Paul Christiano | CC BY-SA 4.0 |
added 199 characters in body
|
| Apr 16, 2023 at 19:52 | history | asked | Paul Christiano | CC BY-SA 4.0 |