Given $m$ entries of an $n \times n$ matrix, is it possible to determine in $O(m n)$ time whether there is any positive semidefinite completion?

Slightly more precisely: for simplicity let's assume all diagonal entries are known to be $1$. Can I distinguish matrices that have a completion where all eigenvalues are at least $\epsilon$ from those that have no positive definite completion, in time $\tilde{O}(m n \log \epsilon)$?

Note that if the matrix is already complete, then $mn = n^3$ and so this is just testing positive definiteness in time $O(n^3 \log \epsilon)$ which is certainly possible. "Determine if a completion exists" seems like the simplest question about positive definite completions, and $O(mn)$ is roughly the fastest that you could reasonably hope to decide if one exists for arbitrary sparsity patterns.

This question was motivated by searching for very fast matrix completion algorithms. I would be happiest if it was possible to compute the maximum determinant completion in time $O(mn)$. I don't expect that to be possible, so I'm trying to understand whether we can get a cruder (implicitly represented) completion in so little time. Many approaches would be off the table if my question has a negative answer, but I haven't made much progress on either algorithms or hardness results. I also haven't been able to find any helpful prior work, but I'm not familiar with the literature on matrix completion and it would be great if there's something I've overlooked.

Given $m$ entries of an $n \times n$ matrix, is it possible to determine in $O(m n)$ time whether there is any positive semidefinite completion?

Slightly more precisely: for simplicity let's assume all diagonal entries are known to be $1$. Can I distinguish matrices that have a (real, symmetric) completion where all eigenvalues are at least $\epsilon$ from those that have no positive definite completion, in time $\tilde{O}(m n \log \epsilon)$?

Note that if the matrix is already complete, then $mn = n^3$ and so this is just testing positive definiteness in time $O(n^3 \log \epsilon)$ which is certainly possible. "Determine if a completion exists" seems like the simplest question about positive definite completions, and $O(mn)$ is roughly the fastest that you could reasonably hope to decide if one exists for arbitrary sparsity patterns.

This question was motivated by searching for very fast matrix completion algorithms. I would be happiest if it was possible to compute the maximum determinant completion in time $O(mn)$. I don't expect that to be possible, so I'm trying to understand whether we can get a cruder (implicitly represented) completion in so little time. Many approaches would be off the table if my question has a negative answer, but I haven't made much progress on either algorithms or hardness results. I also haven't been able to find any helpful prior work, but I'm not familiar with the literature on matrix completion and it would be great if there's something I've overlooked.

Given $m$ entries of an $n \times n$ matrix, is it possible to determine in $O(m n)$ time whether there is any positive semidefinite completion?

Slightly more precisely: for simplicity let's assume all diagonal entries are known to be $1$. Can I distinguish matrices that have a completion where all eigenvalues are at least $\epsilon$ from those that have no positive definite completion, in time $\tilde{O}(m n \log \epsilon)$?

Note that if the matrix is already complete, then $mn = n^3$ and so this is just testing positive definiteness in time $O(n^3 \log \epsilon)$.

This question was motivated by searching for very fast matrix completion algorithms. I would be happiest if it was possible to compute the maximum determinant completion in time $O(mn)$. I don't expect that to be possible, but I'm trying to understand whether we can get a cruder (implicitly represented) completion in so little time. Many approaches would be off the table if my question has a negative answer. I haven't made much progress on either algorithms or hardness results. I also haven't been able to find any helpful prior work, but I'm not familiar with the literature on matrix completion and it would be great if there's something I've overlooked.

Given $m$ entries of an $n \times n$ matrix, is it possible to determine in $O(m n)$ time whether there is any positive semidefinite completion?

Slightly more precisely: for simplicity let's assume all diagonal entries are known to be $1$. Can I distinguish matrices that have a completion where all eigenvalues are at least $\epsilon$ from those that have no positive definite completion, in time $\tilde{O}(m n \log \epsilon)$?

Note that if the matrix is already complete, then $mn = n^3$ and so this is just testing positive definiteness in time $O(n^3 \log \epsilon)$ which is certainly possible. "Determine if a completion exists" seems like the simplest question about positive definite completions, and $O(mn)$ is roughly the fastest that you could reasonably hope to decide if one exists for arbitrary sparsity patterns.

This question was motivated by searching for very fast matrix completion algorithms. I would be happiest if it was possible to compute the maximum determinant completion in time $O(mn)$. I don't expect that to be possible, so I'm trying to understand whether we can get a cruder (implicitly represented) completion in so little time. Many approaches would be off the table if my question has a negative answer, but I haven't made much progress on either algorithms or hardness results. I also haven't been able to find any helpful prior work, but I'm not familiar with the literature on matrix completion and it would be great if there's something I've overlooked.