Paper ID: 1432 Title: Deterministic Symmetric Positive Semidefinite Matrix Completion
Current Reviews

Submitted by Assigned_Reviewer_35

Q1: Comments to author(s). First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. (For detailed reviewing guidelines, see http://nips.cc/PaperInformation/ReviewerInstructions)
[Summary]
Reconstruction of a symmetric positive semi-definite matrix is studied
under the assumption that the matrix elements are sampled on a given
collection of the principal minors. The necessary and sufficient
conditions for the exact reconstruction in the noiseless case have
been provided (Theorems 1 and 2), an algorithm to solve a problem
instance has been proposed, and a non-probabilistic bound on estimation
error in the noisy case has been proved (Theorem 4).

[Quality]
The problem seemed at first not so interesting, but the author has studied
it thoroughly, and has eventually arrived at a nontrivial non-probabilistic
bound on estimation error (Theorem 4), which is very interesting.

[Clarity]
This paper is very clearly written and quite easy to read.

[Originality]
The problem studied in this paper should be original,
since as far as my knowledge it has not been studied before.
The problem is also motivated by real-world problems, which
makes this paper more appealing.

[Significance]
The study has been motivated by real-world applications. Necessary
and sufficient conditions have been obtained. The proposed algorithm
has been proved to solve all problems which should be solvable in the
noiseless case. A non-probabilistic bound on error in the estimate
has been obtained in the noisy case. These aspects make the paper
very significant.
Reconstruction of a symmetric positive semidefinite matrix has been studied under a unique, but well-motivated, setting, to obtain non-trivial and plausible results. This paper thus reports an interesting piece of work.

Submitted by Assigned_Reviewer_37

Q1: Comments to author(s). First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. (For detailed reviewing guidelines, see http://nips.cc/PaperInformation/ReviewerInstructions)
This paper considers the problems of completing a positive semidefinite matrix when the observations are in the forms of principal minors. The proposed algorithm is quite natural and intuitive, and is shown to succeed under minimal deterministic conditions. A stability analysis is also given when the observations are noisy. The paper is well written and the presentation is clear. My main concerns are there might be some limitations with the results in the paper:

(1) It is not immediately clear that given the full set Omega of observed entries, how to extract and order the principal minors Omega_k such that the assumption (A3) is satisfied. Is this problem trivial, or does it requires some intelligence? This issue is not addressed explicitly in Algorithm 1 and the experiments.

(2) The algorithm and its proof seem to rely heavily on the assumption that the observations are exactly in the form of principal minors (or a superset of it), and the minors have sufficient overlaps. It is unclear if the performance is sensitive to deviations in the observation pattern.

(3) The requirement on the observation pattern means either the observations have to come naturally in the form of principal minors with overlaps, or the practitioner must have complete control over the sampling process and can query the entries in this particular way. This might limit the applicability of the algorithm. It would be more convincing if the author can present experiments on at least one real-world dataset which meets such sampling requirement.

(4) The analysis in Theorem 4 does not provide much information beyond that the error goes to zero as the noise goes to zero (which is not too surprising as the problem is over-determined). The error bound depends exponentially on k and involves powers of the eigen gaps, so the bound might be quite large. Experiment is given for noisy completion but for a limited setting with matrices of tiny sizes.
The paper considers an interesting problem, and the proposed solution is intuitive and comes with guarantees. However, the results might have several issues that need to be addressed, and the experiments only consider very small problems.

Submitted by Assigned_Reviewer_45

Q1: Comments to author(s). First provide a summary of the paper, and then address the following criteria: Quality, clarity, originality and significance. (For detailed reviewing guidelines, see http://nips.cc/PaperInformation/ReviewerInstructions)
PAPER SUMMARY

In 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.

This 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.