We consider the problem of recovering a symmetric, positive semidefinite (SPSD) matrix from a subset of its entries, possibly corrupted by noise. In contrast to previous matrix recovery work, we drop the assumption of a random sampling of entries in favor of a deterministic sampling of principal submatrices of the matrix. We develop a set of sufficient conditions for the recovery of a SPSD matrix from a set of its principal submatrices, present necessity results based on this set of conditions and develop an algorithm that can exactly recover a matrix when these conditions are met. The proposed algorithm is naturally generalized to the problem of noisy matrix recovery, and we provide a worst-case bound on reconstruction error for this scenario. Finally, we demonstrate the algorithm's utility on noiseless and noisy simulated datasets.

APPENDIX A. Visualizing the Wishart Distribution The Wishart distribution is a generalization to multiple dimensions of the chi-squared distribution, or in the case of non-integer degrees of freedom, of the gamma distribution. We show in fig.5 that for a 1-dimensional and equal to 1 Σ scale matrix, the Wishart distribution W 1( n, 1) is equivalent to the χ 2 ( n) distribution. Figure 5: Monodimensional Wishart Distribution and χ 2 (n) distribution comparison Save for this simple case, being the Wishart a distribution over matrices, it is a generally hard task to visualize it as a density function. Samples can be however drawn from it and the eigenvectors and eigenvalues of the resulting sampled matrix can be exploited to define an ellipse. An example of this technique is shown in fig.6.

We consider the problem of recovering a symmetric, positive semidefinite (SPSD) matrix from a subset of its entries, possibly corrupted by noise. In contrast to previous matrix recovery work, we drop the assumption of a random sampling of entries in favor of a deterministic sampling of principal submatrices of the matrix. We develop a set of sufficient conditions for the recovery of a SPSD matrix from a set of its principal submatrices, present necessity results based on this set of conditions and develop an algorithm that can exactly recover a matrix when these conditions are met. The proposed algorithm is naturally generalized to the problem of noisy matrix recovery, and we provide a worst-case bound on reconstruction error for this scenario. Finally, we demonstrate the algorithm's utility on noiseless and noisy simulated datasets.