I understand this bounty is roughly closed, but the page is still listed as bounty active and my attempt took me only a couple hours.
Problem 2 is solvable when there are simple restrictions on the entries chosen.
Restriction 1: No diagonal entries need to be correct.
Solution:
Let C = AAT
For each entry c_ij we construct the matrix with only c_ii, c_ij, c_ji , c_jj and all else zero. Clearly this matrix is constructible in O(n) work. So all entries can be constructed in this way. Note if c_ij and c_ji are requested, only construct one matrix for the pair. Repeating this for all m does O(nm) work.
We then sum all such matricies to get our estimate E. Only the diagonal will possibly need summing so O(nm) work is done.
Clearly each constructed matrix is positive semidefinite as it is a principal submatrix of C.
The sum is also positive semidefinite because the individual matricies are positive semidefinite.
Restriction 2:
Only 1 entry per row-column number is needed other than the main diagonal.
The above solution still works.
I understand this bounty is roughly closed, but the page is still listed as bounty active and my attempt took me only a couple hours.
Problem 2 is solvable when there are simple restrictions on the entries chosen.
Restriction 1: No diagonal entries need to be correct. Solution: Let C = AAT For each entry c_ij we construct the matrix with only c_ii, c_ij, c_ji , c_jj and all else zero. Clearly this matrix is constructible in O(n) work. So all entries can be constructed in this way. Note if c_ij and c_ji are requested, only construct one matrix for the pair. Repeating this for all m does O(nm) work. We then sum all such matricies to get our estimate E. Only the diagonal will possibly need summing so O(nm) work is done. Clearly each constructed matrix is positive semidefinite as it is a principal submatrix of C. The sum is also positive semidefinite because the individual matricies are positive semidefinite.
Restriction 2: Only 1 entry per row-column number is needed other than the main diagonal. The above solution still works.