We consider the decision problem asking whether a partial rational symmetric matrix with an all-ones diagonal can be completed to a full positive semidefinite matrix of rank at most k. We show that this problem is $\NP$-hard for any fixed integer k≥2.
I’m still stretching my graph-theory muscles to see if this technically holds for k=∞ (and so precisely implies the NP-hardness of Question 1.) But even without that, for applied use cases we can just fix k to a very large number to see that practical algorithms are unlikely.
Nope, I’m withdrawing this answer. I looked closer into the proof and I think it’s only meaningful asymptotically, in a low rank regime. The technique doesn’t work for analyzing full-rank completions.
It can be decided in O(nω√m) time by semidefinite programming, and I’d guess that most researchers would expect it can be done in time O(nω) (which is the runtime of PSD testing, i.e. the case when m=n2).
More generally, there’s a large literature on positive semidefinite completions which is mostly concerned with finding completions with particular properties. Sorry for not better flagging the state of this problem. Those techniques don’t seem super promising for getting to O(mn).
I think it can be done in O(nω), where I recall for non-expert’s convenience that ω is the exponent of matrix multiplication / inverse / PSD testing / etc. (all are identical). Let Mn be the space of n×n matrices and let V be the (2m−n)-dimensional vector space of matrices with zeros in all non-specified entries of the problem. The maximum-determinant completion is the (only?) one whose inverse is in V. Consider the map V→Mn,B↦B−1 and its projection f:V→V where we zero out all of the other entries. The function f can be evaluated in time O(nω). We wish to solve f(B)=A. This should be doable using a Picard or Newton iteration, with a number of steps that depends on the desired precision.
Would it be useful if I try to spell this out more precisely? Of course, this would not be enough to reach O(mn) in the small m case. Side-note: The drawback of having posted this question in multiple places at the same time is that the discussion is fragmented. I could move the comment to mathoverflow if you think it is better.
Agree about the downside of fragmented discussion, I left some time for MO discussion before posting the bounty but I don’t know how much it helped.
I agree that some approach like that seems like it could work for O(nω). I’m not familiar with those techniques and so don’t know a technique that needs O(logϵ) iterations rather than O(√m) or O(ϵ−1). For Newton iteration it seems like you need some kind of bound on the condition number.
But I haven’t thought about it much, since it seems like something fundamentally different is needed to break O(nω). I believe that one of those might just work out of the box.
Wait which algorithm for semidefinite programming are you using? The ones I’ve seen look like they should translate to a runtime even slower than O(nω√m). For example the one here:
Also, do you have a source for the runtime of PSD testing being nω? I assume no lower bound is known, i.e. I doubt PSD testing is hard for matrix multiplication. Am I wrong about that?
That’s a good question. From what I’ve seen, PSD testing can be done by trying to make a Cholesky decomposition (writing the matrix as LL∗ with L lower-triangular) and seeing if it fails. The Cholesky decomposition is an LU decomposition in which the lower-triangular L and upper-triangular U are simply taken to have the same diagonal entries, so PSD testing should have the same complexity as LU decomposition. Wikipedia quotes Bunch and Hopcroft 1974 who show that LU decomposition can be done in O(nlog27) by Strassen, and presumably the more modern matrix multiplication algorithms also give an improvement for LU.
I also doubt that PSD testing is hard for matrix multiplication, even though you can get farther than you’d think. Given a positive-definite matrix A whose inverse we are interested in, consider the 2n×2n block matrix (AididC). It is positive-definite if and only if all principal minors are positive. The minors that are minors of A are positive by assumption, and the bigger minors are equal to det(A) times minors of C−A−1, so altogether the big matrix is positive-definite iff C−A−1 is. Continuing in this direction, we can get in O(PSD) time (times logϵ) any specific component of A−1. This is not enough at all to get the full inverse.
There is a simple intuition for why PSD testing cannot be hard for matrix multiplication or inversion: regardless of how you do it and what matrix you apply it to, it only gives you one bit of information. Getting even just one bit of information about each matrix element of the result requires n2 applications of PSD testing. The only way out would be if one only needed to apply PSD testing to tiny matrices.
Yeah, I can believe the problem is NP hard if you need to distinguish ±ε eigenvalues in time O(1) rather than O(logϵ). I don’t understand exact arithmetic very well but it seems wild (e.g my understanding is that no polynomial time algorithm is known for testing 3√n1+3√n2+…+3√nk>0).
Question 1 is very likely NP-hard. https://arxiv.org/abs/1203.6602 shows:
I’m still stretching my graph-theory muscles to see if this technically holds for k=∞ (and so precisely implies the NP-hardness of Question 1.) But even without that, for applied use cases we can just fix k to a very large number to see that practical algorithms are unlikely.
Nope, I’m withdrawing this answer. I looked closer into the proof and I think it’s only meaningful asymptotically, in a low rank regime. The technique doesn’t work for analyzing full-rank completions.
It can be decided in O(nω√m) time by semidefinite programming, and I’d guess that most researchers would expect it can be done in time O(nω) (which is the runtime of PSD testing, i.e. the case when m=n2).
More generally, there’s a large literature on positive semidefinite completions which is mostly concerned with finding completions with particular properties. Sorry for not better flagging the state of this problem. Those techniques don’t seem super promising for getting to O(mn).
I think it can be done in O(nω), where I recall for non-expert’s convenience that ω is the exponent of matrix multiplication / inverse / PSD testing / etc. (all are identical). Let Mn be the space of n×n matrices and let V be the (2m−n)-dimensional vector space of matrices with zeros in all non-specified entries of the problem. The maximum-determinant completion is the (only?) one whose inverse is in V. Consider the map V→Mn,B↦B−1 and its projection f:V→V where we zero out all of the other entries. The function f can be evaluated in time O(nω). We wish to solve f(B)=A. This should be doable using a Picard or Newton iteration, with a number of steps that depends on the desired precision.
Would it be useful if I try to spell this out more precisely? Of course, this would not be enough to reach O(mn) in the small m case. Side-note: The drawback of having posted this question in multiple places at the same time is that the discussion is fragmented. I could move the comment to mathoverflow if you think it is better.
Agree about the downside of fragmented discussion, I left some time for MO discussion before posting the bounty but I don’t know how much it helped.
I agree that some approach like that seems like it could work for O(nω). I’m not familiar with those techniques and so don’t know a technique that needs O(logϵ) iterations rather than O(√m) or O(ϵ−1). For Newton iteration it seems like you need some kind of bound on the condition number.
But I haven’t thought about it much, since it seems like something fundamentally different is needed to break O(nω). I believe that one of those might just work out of the box.
Wait which algorithm for semidefinite programming are you using? The ones I’ve seen look like they should translate to a runtime even slower than O(nω√m). For example the one here:
https://arxiv.org/pdf/2009.10217.pdf
Also, do you have a source for the runtime of PSD testing being nω? I assume no lower bound is known, i.e. I doubt PSD testing is hard for matrix multiplication. Am I wrong about that?
That’s a good question. From what I’ve seen, PSD testing can be done by trying to make a Cholesky decomposition (writing the matrix as LL∗ with L lower-triangular) and seeing if it fails. The Cholesky decomposition is an LU decomposition in which the lower-triangular L and upper-triangular U are simply taken to have the same diagonal entries, so PSD testing should have the same complexity as LU decomposition. Wikipedia quotes Bunch and Hopcroft 1974 who show that LU decomposition can be done in O(nlog27) by Strassen, and presumably the more modern matrix multiplication algorithms also give an improvement for LU.
I also doubt that PSD testing is hard for matrix multiplication, even though you can get farther than you’d think. Given a positive-definite matrix A whose inverse we are interested in, consider the 2n×2n block matrix (AididC). It is positive-definite if and only if all principal minors are positive. The minors that are minors of A are positive by assumption, and the bigger minors are equal to det(A) times minors of C−A−1, so altogether the big matrix is positive-definite iff C−A−1 is. Continuing in this direction, we can get in O(PSD) time (times logϵ) any specific component of A−1. This is not enough at all to get the full inverse.
There is a simple intuition for why PSD testing cannot be hard for matrix multiplication or inversion: regardless of how you do it and what matrix you apply it to, it only gives you one bit of information. Getting even just one bit of information about each matrix element of the result requires n2 applications of PSD testing. The only way out would be if one only needed to apply PSD testing to tiny matrices.
Thanks for the clarification! I assumed the question was using the bit computation model (biased by my own experience), in which case the complexity of SDP in the general case still seems to be unknown (https://math.stackexchange.com/questions/2619096/can-every-semidefinite-program-be-solved-in-polynomial-time)
Yeah, I can believe the problem is NP hard if you need to distinguish ±ε eigenvalues in time O(1) rather than O(logϵ). I don’t understand exact arithmetic very well but it seems wild (e.g my understanding is that no polynomial time algorithm is known for testing 3√n1+3√n2+…+3√nk>0).