When I tried asking about this problem, and referenced the above comment about being able to assume that all entries on the diagonal are positive, GPT-4 said the following:
If an n×n matrix is a symmetric positive semidefinite (PSD) matrix, it can be interpreted as a Gram matrix representing the dot products of a set of n vectors, and this configuration has 0 stress.
To understand this, let’s first consider what a Gram matrix is. Given a set of n vectors v_1, v_2, …, v_n in a d-dimensional space, the Gram matrix G is an n×n matrix where the entry G(i, j) is the dot product of vectors v_i and v_j:
G(i, j) = v_i • v_j
A Gram matrix is always symmetric (i.e., G(i, j) = G(j, i)) and positive semidefinite.
Now, let’s consider the stress function in the context of multidimensional scaling (MDS). The stress function measures the difference between the given dissimilarities (distances) and the distances in the lower-dimensional space. When the stress is 0, this means that the distances in the lower-dimensional space exactly match the given dissimilarities.
Is GPT-4 correct? If so, am I interpreting it correctly that this problem could be rephrased as “given an incomplete set of m desired pairwise distances between n points, determine whether there exists some configuration of those points in an n-dimensional space such that the pairwise distances between those points are exactly as desired”?
Since we are only given m distances maybe a numerical algorithm for MDS might work. For example we might start with a random nxn matrix and minimize the strain by gradient descent. For the desired runtime this would just have to converge in $O(m/n)$ steps. I’m not sure if this is realistic though. Also there might be better numerical algorithms for this specific problem. Has anyone looked into this yet?
I think running a single strain minimization iteration on m points in n dimensions takes O(m*n) steps. So there would need to be some reason to expect that it would converge in some constant (though possibly large) number of steps.
Unless you’re saying “for each node, run the strain minimization step until it converges, then do the same for each subsequent node”. I don’t know if the greedy algorithm works there, but if it does then maybe?
Also I kinda expect that if there’s something that works in O(n*m*log(m)) that’s probably fine.
(and yeah, “try the greedy exact solution for each node” was my “dumb solution” attempt).
I think your interpretation is correct, I’m not entirely sure. There might be n+1 points in total, because the diagonal coefficients give you the distance to 0 I think?
The Gram matrix bit is certainly correct, though I’m not sure how the distances come into it. The m constraints are constraints on dot products, so more angles (well, cosines) than distances between vectors.
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.
You mean as in, if I have two points xi and xj, then (xi−xj)2=x2i+x2j−2xi⋅xj?
Guess so, but yeah, I just don’t tend to think of it immediately as a part of the distances rather than just vectors. It works though since you mentioned the diagonal elements are known.
When I tried asking about this problem, and referenced the above comment about being able to assume that all entries on the diagonal are positive, GPT-4 said the following:
Is GPT-4 correct? If so, am I interpreting it correctly that this problem could be rephrased as “given an incomplete set of m desired pairwise distances between n points, determine whether there exists some configuration of those points in an n-dimensional space such that the pairwise distances between those points are exactly as desired”?
Since we are only given m distances maybe a numerical algorithm for MDS might work. For example we might start with a random nxn matrix and minimize the strain by gradient descent. For the desired runtime this would just have to converge in $O(m/n)$ steps. I’m not sure if this is realistic though. Also there might be better numerical algorithms for this specific problem. Has anyone looked into this yet?
I think running a single strain minimization iteration on
mpoints inndimensions takes O(m*n) steps. So there would need to be some reason to expect that it would converge in some constant (though possibly large) number of steps.Unless you’re saying “for each node, run the strain minimization step until it converges, then do the same for each subsequent node”. I don’t know if the greedy algorithm works there, but if it does then maybe?
Also I kinda expect that if there’s something that works in
O(n*m*log(m))that’s probably fine.(and yeah, “try the greedy exact solution for each node” was my “dumb solution” attempt).
I think your interpretation is correct, I’m not entirely sure. There might be n+1 points in total, because the diagonal coefficients give you the distance to 0 I think?
The Gram matrix bit is certainly correct, though I’m not sure how the distances come into it. The m constraints are constraints on dot products, so more angles (well, cosines) than distances between vectors.
If you are given the dot products exactly, that’s equivalent to being given the distances exactly.
(I think this reduction goes the wrong way though, if I wanted to solve the problem about distances I’d translate it back into dot products.)
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.
You mean as in, if I have two points xi and xj, then (xi−xj)2=x2i+x2j−2xi⋅xj?
Guess so, but yeah, I just don’t tend to think of it immediately as a part of the distances rather than just vectors. It works though since you mentioned the diagonal elements are known.