This comment proposes a strategy for (2) I’ll call Active Matrix Completion (AMC), which allows querying of elements of AAT given some cost/budget. In our case, each query takes O(n), so we can afford O(m) total queries.
Some notes:
O(n) seems really fast—for instance, evaluating the bilinear form uT(AAT)v=(Au)T(Av) takes O(n^2). This makes me suspect any solution to (2) will rely on some form of AMC.
AMC exists in literature—this paper gives a nice introduction and (I think) proves that O(n*rank(A)) queries suffice.
One strategy that seems intuitively appealing is querying enough elements to guarantee that the resulting adjacency graph is chordal, which (I think) allows for efficient PSD completion (see Vandenberghe; algorithm 10.2). Thus, the following proposition is stronger than (2):
PROPOSITION: given a graph G = (V, E) with n nodes and m edges, can we efficiently (in O(mn) time) determine a small (with at most Cm edges for universal constant C) chordal completion of G?
The proposition seems “too good to be true”, especially since chordal completion seems like a hard computational problem (NP-complete, no great approximations are known), so I’m most interested in easy counterexamples. For instance, a “small” graph with only “large” chordal completions would confirm the falsehood of the proposition.
This comment proposes a strategy for (2) I’ll call Active Matrix Completion (AMC), which allows querying of elements of AAT given some cost/budget. In our case, each query takes O(n), so we can afford O(m) total queries.
Some notes:
O(n) seems really fast—for instance, evaluating the bilinear form uT(AAT)v=(Au)T(Av) takes O(n^2). This makes me suspect any solution to (2) will rely on some form of AMC.
AMC exists in literature—this paper gives a nice introduction and (I think) proves that O(n*rank(A)) queries suffice.
One strategy that seems intuitively appealing is querying enough elements to guarantee that the resulting adjacency graph is chordal, which (I think) allows for efficient PSD completion (see Vandenberghe; algorithm 10.2). Thus, the following proposition is stronger than (2):
PROPOSITION: given a graph G = (V, E) with n nodes and m edges, can we efficiently (in O(mn) time) determine a small (with at most Cm edges for universal constant C) chordal completion of G?
The proposition seems “too good to be true”, especially since chordal completion seems like a hard computational problem (NP-complete, no great approximations are known), so I’m most interested in easy counterexamples. For instance, a “small” graph with only “large” chordal completions would confirm the falsehood of the proposition.
So, uh, any graph theory experts around?