34
$\begingroup$

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.

Improve this question
$\endgroup$
16
  • 1
    $\begingroup$ Does your definition of "positive semidefinitedefinite" require hermitian (or real symmetric) matrices? To avoid confusion, it's worth mentioning this, as some authors do not require this. $\endgroup$
    – Robert Israel
    Commented Apr 16, 2023 at 21:47
  • 3
    $\begingroup$ This is sdp, indeed. See Theorem 2.1 in doi.org/10.1016/0022-1236(89)90050-5. $\endgroup$
    – Narutaka OZAWA
    Commented Apr 17, 2023 at 5:48
  • 6
    $\begingroup$ In addition to the MO bounty we're offering a $5k prize for algorithms (or lower bounds) for this question. You can find details here: alignment.org/blog/prize-for-matrix-completion-problems $\endgroup$
    – Paul Christiano
    Commented May 3, 2023 at 16:52
  • 1
    $\begingroup$ This problem goes by the name "Positive Semi Definite Matrix Completion", see for instance the 1997 review by Monique Laurent. It is related to the question of whether a graph with given edge lengths can be embedded into Euclidean space, which is amenable to semi-definite programming (SDP). However, it seems people don't know bounds on the "number of digits" of a solution to the SDP, so that the problem may even fail to be in NP. Do you care about such numerical artifacts, or only about the combinatorics problem itself? $\endgroup$
    – Bruno Le Floch
    Commented May 4, 2023 at 22:02
  • 2
    $\begingroup$ $O(mn)$ seems like an unreasonably fast algorithm. If $m$ is small relative to $n$, such an algorithm won’t even be able to write down a candidate value for each of the unassigned entries in the matrix. There are cases where one can find solutions faster than one can write them down, but that typically requires a large amount of structure to develop an implicit representation. I’m not an expert in matrix completions, but is there a reason to think this exists? Can one convert a $O(mn^2)$ solution to a $O(mn)$ one? $\endgroup$
    – Stella Biderman
    Commented May 5, 2023 at 12:26

3 Answers 3

Reset to default
5
$\begingroup$

This sufficient condition (thank you, Daniel) might be useful: The partial matrix $M$ can be associated with an undirected graph $G$ ($N$ vertices, with vertex $i$ and $j$ connected if $M_{ij}$ is specified). If $G$ is a chordal graph (no minimal cycle of length $\geq 4$) then the matrix $M$ has a PSD completion.

There exist efficient tests for chordality, see Testing Chordal Graphs with CUDA. (If have understood this algorithm correctly, it takes $O(N)$ time.)

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ My understanding is that this is the result: G is chordal <=> every partial matrix supported on G, that is not already non-PSD in the revealed entries, can be completed to a full PSD matrix. But this doesn't exclude the possibility of a specific matrix having a PSD completion, with the graph not being chordal. $\endgroup$
    – Daniel Paleka
    Commented Apr 17, 2023 at 9:48
  • $\begingroup$ @DanielPaleka --- that is correct, thanks for specifying this. $\endgroup$
    – Carlo Beenakker
    Commented Apr 17, 2023 at 9:57
  • $\begingroup$ Thanks for pointing that out. Random sparse graphs seem like a hard case, which I think are far from chordal. And if we pick an arbitrary graph G and arbitrary PSD matrix M, and then reveal the corresponding entries from M, there will always be a PSD completion. $\endgroup$
    – Paul Christiano
    Commented Apr 17, 2023 at 15:44
  • $\begingroup$ The condition "$M$ is PSD in its specified entries" is still missing from this answer: a non-PSD matrix with all entries specified gives a trivial counterexample of what is stated here. $\endgroup$
    – Bruno Le Floch
    Commented May 4, 2023 at 8:31
4
$\begingroup$

Your problem is an special case of a wide class of optimization problems called Semidefinite Programming (or SDP for short). The goal of SDP is to solve the problem $$ \begin{aligned} \min _{X \in \mathbb{S}^n} & \langle C, X\rangle \\ \text { subject to } & \left\langle A_i, X\right\rangle=b_i, \quad i=1, \ldots, m \\ & X \succeq 0 \end{aligned}. $$ Here the matrices $C$,$A_i$ and scalars $b_i$ are given, and our goal is the minimize the inner product $\langle C, X\rangle$ subject to the given constraints. Your problem can be seen as the special case where $C=0$. The most common algorithm for solving SDPs is the interior point method, but their exact running time is still an active area of research.

It is also worth mentioning SDP has a nice dual problem that allows you to certify that it is not feasible using the Farkas lemma.

Improve this answer
$\endgroup$
5
  • $\begingroup$ If I understand correctly OP's problem is equivalent not to minimizing $\langle C,X\rangle$ but to determining if the feasible region is empty; is that correct? Is this what you meant with $C=0$? $\endgroup$
    – Federico Poloni
    Commented Apr 17, 2023 at 12:17
  • 4
    $\begingroup$ I agree that this is a semidefinite program, but it seems like a generic algorithm for SDPs won't run in time $O(mn)$. To run fast enough I'd guess we need to exploit the fact that each constraint is on a single entry of $X$. To put it more sharply, we're trying to solve this problem faster than you can even test whether a matrix is PSD. $\endgroup$
    – Paul Christiano
    Commented Apr 17, 2023 at 15:37
  • 2
    $\begingroup$ For interior point methods in particular, my understanding is that a single iteration takes time at least $n^{\omega}$, and the main open question is how many iterations are required. But if $m = O(n)$ then we can't afford to do even a single iteration of an interior point method. $\endgroup$
    – Paul Christiano
    Commented Apr 17, 2023 at 15:47
  • $\begingroup$ I don’t immediately see how to do it, but my low confidence guess is that matrix multiplication is reducible to this problem, and thus beating $n^\omega$ is impossible. $\endgroup$
    – Geoffrey Irving
    Commented May 9, 2023 at 18:25
  • $\begingroup$ Oops, I was assuming $m = \Theta(n^2)$, which wouldn’t contradict $O(nm)$. $\endgroup$
    – Geoffrey Irving
    Commented May 9, 2023 at 18:36
1
$\begingroup$

I can't comment, so I'll write this as an answer: The problem seems to me to be equivalent to what is called "PSDMCP" here, with a pretty significant research history behind it and a strong connection to the "Euclidean distance matrix completion problem" (EDMCP in that review). See also here.

So I'd guess that answering the specific question is beyond the scope of a MO post...

Improve this answer
$\endgroup$
4
  • $\begingroup$ Digging a bit in the literature it seems people care mostly about the low-rank case, namely embedding into a Euclidean space of a fixed dimension and asking about complexity as the graph size grows. This leads to an NP-hard problem. Did you find interesting references that do not impose a rank condition? $\endgroup$
    – Bruno Le Floch
    Commented May 4, 2023 at 23:37
  • $\begingroup$ epubs.siam.org/doi/abs/10.1137/… doesn't seem to talk about rank conditions when defining the main problem (P). $\endgroup$
    – Duyal Yolcu
    Commented May 5, 2023 at 0:17
  • $\begingroup$ My second link in the answer pure.uvt.nl/ws/portalfiles/portal/1215894/Matrix.pdf also discusses arbitrary k first (and defines the fixed-k problem later); the names are "EDM" vs. "EDMk". Of course, k=n will always be high enough... $\endgroup$
    – Duyal Yolcu
    Commented May 5, 2023 at 0:23
  • $\begingroup$ Definitely agree that this a PSD matrix completion problem. I haven't found any references exploring very fast algorithms for this problem, or even clearly stating the fastest known algorithm, or conjecturing the optimal runtime. Have you seen some discussion in the literature? (My sense is that most active work on this topic seems focused on rank constraints or norm minimization problems rather than very fast existence checks.) $\endgroup$
    – Paul Christiano
    Commented May 5, 2023 at 17:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .