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.
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.