Asking for some clarifications: 1. For both problems, should the solution work for an adversarially chosen set of m entries? 2. For both problems, can we read more entries of the matrix if it helps our solution? In particular can we WLOG assume we know the diagonal entries in case that helps in some way.
Yes, the algorithm should work for adversarial inputs.
For the second problem you can effectively read more entries since you can compute any given entry of AAT in time O(n). For the first problem you can’t read more entries. But you can assume WLOG that you have the diagonal—if you don’t have any given diagonal entry, you might as well just set it to infinity in the completion, effectively removing that whole row and column from the problem. So we can just remove all rows and columns for which you don’t have the diagonal, and be left with a matrix where all diagonal entries are known.
I’m not sure this is true. Consider the 2x2 matrix ((?, 1),(1,0)). Removing the first row and the first column leaves you with ((0)), which is a PSD 1x1 matrix. That being said, there is no value of ? for which the 2x2 matrix is PSD.
I agree with your example. I think you can remove the row/column if there are no known 0s on the diagonal, and I also think you can first WLOG remove any rows and columns with 0s on the diagonal (since if there are any other known non-zero entries in their row or column then the matrix has no PSD completions).
I’m also happy to just assume the diagonal entries are known. I think these are pretty weird corner cases.
It’s not quite this simple, the same issue arises if every PSD completion of the known-diagonal minor has zero determinant (e.g. ((?, 1, 2), (1, 1, 1), (2, 1, 1))). But I think in that case making the remaining diagonal entries large enough still makes the eigenvalues at least −ε, which is good enough.
What matters is not whether or not there is another 0 on the diagonal, but whether or not there is another PSD non definite matrix on the diagonal. For example, in the comment from Jacob_Hilton, they introduce the 2x2 matrix ((1,1),(1,1)), with eigenvalues [0,1], which is a PSD non definite.
I agree with assuming that all diagonal entries are known. You can even assume that all entries are 1 on the diagonal WLOG.
Just to spell it out, am I right in thinking that you can scale all the matrix elements so that each entry on the diagonal is the sign of its original value, i.e. −1 or 1, but if the resulting diagonal contains any −1s then it can’t be PSD?
Yes indeed. One definition of a PSD matrix is some matrix M such that, for any vector X, XTMX≥0 (so, it defines some kind of scalar product).
If Mi,i=y, then you can always divide the whole row/column by √y, which is equivalent to applying some scaling, this won’t change the fact that M is PSD or not.
If Mi,i=−1, then if you try the vector X:∀j≠i,Xj=0;Xi=1, you can check that XTMX=−1, thus the matrix isn’t PSD.
Asking for some clarifications:
1. For both problems, should the solution work for an adversarially chosen set of m entries?
2. For both problems, can we read more entries of the matrix if it helps our solution? In particular can we WLOG assume we know the diagonal entries in case that helps in some way.
Yes, the algorithm should work for adversarial inputs.
For the second problem you can effectively read more entries since you can compute any given entry of AAT in time O(n). For the first problem you can’t read more entries. But you can assume WLOG that you have the diagonal—if you don’t have any given diagonal entry, you might as well just set it to infinity in the completion, effectively removing that whole row and column from the problem. So we can just remove all rows and columns for which you don’t have the diagonal, and be left with a matrix where all diagonal entries are known.
I’m not sure this is true. Consider the 2x2 matrix ((?, 1),(1,0)). Removing the first row and the first column leaves you with ((0)), which is a PSD 1x1 matrix. That being said, there is no value of ? for which the 2x2 matrix is PSD.
I agree with your example. I think you can remove the row/column if there are no known 0s on the diagonal, and I also think you can first WLOG remove any rows and columns with 0s on the diagonal (since if there are any other known non-zero entries in their row or column then the matrix has no PSD completions).
I’m also happy to just assume the diagonal entries are known. I think these are pretty weird corner cases.
It’s not quite this simple, the same issue arises if every PSD completion of the known-diagonal minor has zero determinant (e.g. ((?, 1, 2), (1, 1, 1), (2, 1, 1))). But I think in that case making the remaining diagonal entries large enough still makes the eigenvalues at least −ε, which is good enough.
What matters is not whether or not there is another 0 on the diagonal, but whether or not there is another PSD non definite matrix on the diagonal. For example, in the comment from Jacob_Hilton, they introduce the 2x2 matrix ((1,1),(1,1)), with eigenvalues [0,1], which is a PSD non definite.
I agree with assuming that all diagonal entries are known. You can even assume that all entries are 1 on the diagonal WLOG.
I changed the statement to assume the diagonal is known, I agree this way is cleaner and prevents us from having to think about weird corner cases.
Just to spell it out, am I right in thinking that you can scale all the matrix elements so that each entry on the diagonal is the sign of its original value, i.e. −1 or 1, but if the resulting diagonal contains any −1s then it can’t be PSD?
Yes indeed. One definition of a PSD matrix is some matrix M such that, for any vector X, XTMX≥0 (so, it defines some kind of scalar product).
If Mi,i=y, then you can always divide the whole row/column by √y, which is equivalent to applying some scaling, this won’t change the fact that M is PSD or not.
If Mi,i=−1, then if you try the vector X:∀j≠i,Xj=0;Xi=1, you can check that XTMX=−1, thus the matrix isn’t PSD.