Deterministic Symmetric Positive Semidefinite Matrix Completion
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.
PAPER SUMMARYIn this paper, the authors propose a model and an algorithm for completing a symmetric, positive semidefinite matrix. Unlike prior work that assumes that the observed entries are drawn uniformly at random, this work assumes that the observed entries come from deterministic collection of its principal sub matrices. The paper derives either necessary or sufficient conditions on these sub matrices that guarantee the perfect recovery of the unknown entries. The paper also considers the case where the data is corrupted by noise and derives an upper bound on the error between the estimated and the true matrix.  Simulations on synthetic data verify the correctness of the proposed model.SPECIFIC COMMENTSThis paper is well-organized and mathematically rigorous. The theoretical analysis is novel since it addresses deterministic matrix completion model with specific structure. In particular, rather than addressing the well studied case where the observed entries are drawn uniformly at random, the paper assumes that the observed entries are drawn from a set of principal sub matrices that satisfy certain properties. Perfect matrix completion can be achieved in the noiseless case, while an upper bound is derived for the noisy case. Overall, I find the results in this paper to be very novel. I only have a few minor comments below that can help improve clarity. My most important comment is that the experiments can be improved by adding a comparison with other methods as well as experiments on real data.1) The term "minor" usually refers to the "determinant of some smaller square matrix". In this paper, the term is used to refer to the sub matrix itself without the determinant. I suggest the authors use a different name to avoid confusion.2) Some of the notation is confusing. For example, C_l and C(\rho_l, :) are both used to refer to the same matrix, which is confusing to the reader.3) The proposed model and algorithm are based on several assumptions on the principal sub matrices of the data matrix. In practice, it is not clear if these assumptions are satisfied in real world applications. For example, given a dataset, how does one derive the collection of principal sub matrices  that satisfy assumptions A1-A3? Or if these assumptions fail, is there a way of permuting the rows and columns of the given matrix so that the assumptions are satisfied?4) In the experiments, the authors did simulations on synthetic data to verify the correctness of the algorithm. However there is no comparison with other matrix completion methods, which is not convincing enough to show the advantage of the proposed algorithm. It would have been nice to see an example where standard matrix completion algorithms fail, but the propose algorithm succeeds. Also, the paper would be strengthened if there were simulations on real data. One specific example that comes to mind is motion segmentation in computer vision, where the missing entries occur due to appearance and disappearance of moving objects in a video. In that case, principal sub matrix patterns show up naturally.