I think you can convert between the two representations in O(m) time, which would mean that any algorithm that solves either version in O(n*m) solves both in O(n*m).
Do you have some large positive and negative examples of the kinds of sparse matrix you’re trying to check for the existence of a PSD completion on, or alternatively a method for generating such examples with a known ground truth? I have a really dumb idea for a possible algorithm here (that shamelessly exploits the exact shape of this problem in a way that probably doesn’t generalize to being useful for broader problems like MDS) that I think would complete in approximately the time constraints you’re looking for. It almost certainly won’t work, but I think it’s at least worth an hour of my time to check and figure out why (especially since I’m trying to improve my linear algebra skills anyway).
Edit: there’s the obvious approach, which I’m trying, of “start with only 1s on the diagonal and then keep adding random entries until it no longer has a PSD completion, then removing random entries until it does, and repeat to build a test set” but I doubt that covers the interesting corners of the problem space.
Edit 2: the really dumb thing does not work. I think I haven’t ruled out that a slightly less dumb approach could work though?
Edit 3: never mind, my really dumb “solution” requires inverting a matrix that is, in the worst case, nxn, if e.g. you have an input that looks like
1 n n n n n n
n 1 - - - - n
n - 1 - - - n
n - - 1 - - n
n - - - 1 - n
n - - - - 1 n
n n n n n n 1
you’ll have to invert 6 2x2 matrices and one each of 3x3 to 7x7 matrices.
I think you can convert between the two representations in
O(m)time, which would mean that any algorithm that solves either version inO(n*m)solves both inO(n*m).Do you have some large positive and negative examples of the kinds of sparse matrix you’re trying to check for the existence of a PSD completion on, or alternatively a method for generating such examples with a known ground truth? I have a really dumb idea for a possible algorithm here (that shamelessly exploits the exact shape of this problem in a way that probably doesn’t generalize to being useful for broader problems like MDS) that I think would complete in approximately the time constraints you’re looking for. It almost certainly won’t work, but I think it’s at least worth an hour of my time to check and figure out why (especially since I’m trying to improve my linear algebra skills anyway).
Edit: there’s the obvious approach, which I’m trying, of “start with only 1s on the diagonal and then keep adding random entries until it no longer has a PSD completion, then removing random entries until it does, and repeat to build a test set” but I doubt that covers the interesting corners of the problem space.
Edit 2: the really dumb thing does not work. I think I haven’t ruled out that a slightly less dumb approach could work though?
Edit 3: never mind, my really dumb “solution” requires inverting a matrix that is, in the worst case, nxn, if e.g. you have an input that looks like
you’ll have to invert 6 2x2 matrices and one each of 3x3 to 7x7 matrices.