Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization

Summary

This paper proposed a method called MatrixIRLS to solve the EDG problem, an important problem in various fields, especially when pairwise distance is partially observed. The proposed method improves the number of random sampled distances to guarantee local convergence to the ground truth.

Strengths

The related work is discussed comprehensively. The method and theory seem solid. Experiments are convincing.

Weaknesses

1. There are quite a few typos or undefined notation that make some of the paragraphs hard to read. For example: a. Line 66, $\nu$ is not defined. Although it’s briefly mentioned in line 80, its rigorous definition is on Page 5. I suggest the following change to line 66: $O()$ (where $\nu$ is the coherence factor, see \cref{def:4.1} for details). b. Line 158, $\sigma_i(\cdot)$ is not defined, tho I can guess the meaning. c. Line 165: $X^{(k)}$ should be $X$. d. Eq (5) gives the update from k to k+1, while Eq (6) gives the rule from k-1 to k. e. Eq(9), at the end, there is a missing comma. 2. Figure 2 looks great, but it will be even better if we can observe the claimed rate $O(\nu rn\log n)$ empirically.

Questions

1. There are some vertical space issues, like Line 286 for Section 5. 2. Can the authors briefly discuss the main challenges for global convergence?

Rating

6

Confidence

3

Soundness

4

Presentation

3

Contribution

4

Limitations

Discussed in the supplementary material. I suspect the file in the supplementary zip file should be the main submitted file.

Summary

The paper studies the under-constrained problem to reconstruct n ordered points in Euclidean space R^r, which are given by fewer than all n(n-1)/2 pairwise distances.

Strengths

The authors should be highly praised for clearly stating main Problem 1 on page 1 and for formulating main Theorems 4.2 and 4.5 almost rigorously. Problem 1 is well-motivated by the AlphaFold approach to protein folding prediction when a protein backbone in 3D is reconstructed form partially known distances between alpha-carbon atoms.

Weaknesses

Different from the initial Problem 1, the actual considered problem is the rank minimization in (1) after line 54. Does the paper explain anywhere why it makes sense to minimize this integer rank of a Gram matrix even if we forget about initial points. Another weakness is the practical impossibility of solving this rank minimization, which is claimed in line 54 to be NP-hard. It would be useful to re-phrase a problem in another way that allows a polynomial solution. More importantly, the rank minimization in (1) and algorithm MatrixILRS appeared under the same name but with slightly different notations in the earlier paper [KV21]. So the problem and algorithm in the submitted paper look incremental updates of the past work, which even uses the same names, includes similar theorems, example structures and pseudo-codes.

Questions

For a simple example, if n=4 points in the plane are given by 4 distances that are edge lengths of a quadrilateral on these 4 points, then what's the meaning of this rank minimization in this case? Can Problem 1 be explicitly solved in some partial cases, e.g. for 5 distances on 4 points in the plane? In Def 3.2, is w_alpha a matrix n x n? In lines 177-178, how is measurement operator <w_alpha_l,X> computed? Are angle brackets missed for l>m in line 178? The concept of a nu-incoherent matrix appears in Theorems 4.2, 4.5 without earlier explanations. What are these matrices? The words "coherence factor" appear for the first time in line 80 without defining this factor nu. Also, nu appears earlier in line 66, still without explanations. Is it the same "coherence" appearing much later in Definition 4.1? The word "probability" appears for the first time in Theorem 4.2, later again in Theorem 4.5. How is the probability space defined to make the convergence with "high probability" meaningful? In Theorem 4.3, can mu be large enough so that the resulting inequality becomes equality and hence no convergence is guaranteed? What are the values of mu in the experiments form section 5? Lines 251-252 say that "an adaptation of the proof of [KV21] to the EDG setting is not possible due to non-orthogonality of the basis {w_alpha}_alpha of Definition 3.2". What specific step in the past proof requires this orthogonality? Lines 857-858 say that "The Procrustes analysis uses similarity transformations like scaling, rotation and maps into a common reference frame [ADSVF23]". However the minimization after line 859 includes only translations and orthogonal maps. Was uniform scaling missed? Why is the minimum achieved over infinitely many possible translations? Does this Procrustes distance satisfy the metric axioms and what is its computational complexity in the number of points? The biggest concern is line 82 saying that "from which the geometry of the points P is trivially recovered". Main Algorithm 1 (MatrixIRLS) outputs a matrix X^(k) through some iterative optimization. Why is this final n x n matrix realizable by n points in a Euclidean space R^r? For instance, we cannot arbitrarily choose 6 pairwise distances between 4 points in the plane. Even if these distances are positive and satisfy triangle inequalities, they should also satisfy a complicated polynomial equation saying that the tetrahedron on these 4 points has volume 0. For n>4 points, there are many more such equations, so a random symmetric matrix of positive numbers is realized by points with probability 0.

Rating

4

Confidence

4

Soundness

2

Presentation

2

Contribution

2

Limitations

This submission seems an incremental improvement of the past work [KV21] with little comparison between the two papers.

Summary

This paper tackles the problem of reconstructing geometric configurations from minimal Euclidean distance samples. The authors propose an innovative algorithm based on iteratively reweighted least squares (IRLS) within a non-convex optimization framework. They provide a local convergence guarantee for the method, ensuring accurate geometry recovery from a minimal number of random distance samples. Additionally, the paper establishes a restricted isometry property (RIP) relevant to other non-convex approaches. Numerical experiments demonstrate the algorithm’s efficiency and robustness compared to state-of-the-art methods.

Strengths

1. The paper introduces a novel application of IRLS for non-convex optimization in Euclidean Distance Geometry (EDG) problems. Establishing the local convergence guarantee and RIP is a significant theoretical contribution. 2. The paper is well-researched, with rigorous theoretical analysis and proofs supporting the proposed method’s convergence and efficiency. The empirical validation through both synthetic and real-world datasets adds robustness to the claims. 3. The paper is well-structured and clearly written, making complex mathematical concepts accessible. The detailed algorithmic steps enhance understanding. 4. The proposed method addresses a fundamental problem in various applications, such as molecular conformation and sensor network localization. The ability to achieve accurate reconstruction with fewer samples has significant implications for data efficiency in these fields.

Weaknesses

1. The paper compares the proposed method with a few state-of-the-art algorithms. Including more diverse comparisons, particularly with newer methods covered in the existing literature, would provide a more comprehensive evaluation. 2. The experiments could be enhanced by adding more parameter analysis or robustness analysis. For example, testing the performance under different parameters (n, r, k) on the ill-conditioned data will further validate the effectiveness of the proposed method. 3. The paper provides a local convergence guarantee, but a more detailed discussion on the global convergence properties of the algorithm would be beneficial.

Questions

1.How sensitive is the proposed algorithm to the choice of parameters, such as rank estimate in the IRLS framework? Providing guidelines or heuristics for parameter selection would be helpful. 2.In the additional experiments presented in Appendix E.1, why does the MatrixIRLS method exhibit a large standard deviation when rho is in the range of 2.5 to 3.5? This suggests that the method is not very stable or robust across all settings. Considering the success probability, ALM performs better than MatrixIRLS. Could you explain the potential reasons for this discrepancy? 3.The time complexity of the MatrixIRLS algorithm appears to be missing a component in Step 7, which involves singular value decomposition with a complexity of O(n^3). Given this, what is the scalability of the MatrixIRLS method, such as the maximum problem size that can be solved within one hour? 4.Will the results of the MatrixIRLS method converge to the same solution as MDS when there is no incomplete information? *Small suggestions:* 1.The linewidth and point size is too large in Figs. 2, 6(b), and 7(b). 2.No captions in Figs. 6 and 7. 3.Mixed use of fig. and Figure. 4.Some typos: Line 52: should satisfy also satsify Line 813: figure Figure

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

It would be beneficial to include the scalability limitations, such as the maximum problem size that can be solved.

Summary

The paper examines the problem of recovering point locations based on incomplete pairwise Euclidean distance information. The problem is cast as a low-rank matrix recovery problem, and an algorithm based on iteratively-reweighted least squares is proposed. The authors derive a lower bound for the minimum number of required samples for reconstruction, and show that their algorithm has quadratic convergence. Experimental results show that their method has comparable results to other state-of-the-art methods for most data, but is also uniquely robust to ill-conditioned cases where other methods fail to converge.

Strengths

* Provides the first theoretical convergence guarantee at the optimal amount of samples for the studied pairwise distance problem under non-convex optimization. * Performance comparable to state of the art methods are demonstrated on * The method converges quickly and effectively even for ill-conditioned matrices, where previous state of the art methods fail. * Detailed theoretical derivations and proofs. * An complete anonymized code repository is provided for reproducibility.

Weaknesses

* Example data is somewhat small-scale and synthetic, but appears sufficient for comparison with other recovery methods. * While this is not a weakness of the paper, my own theoretical background is insufficient to verify some of the proofs, such as the construction of the dual basis followed by the establishment of the restricted isometry property condition.

Questions

* While number of steps/time to convergence is shown for ill-conditioned matrix experiments, they are not shown for real data experiments. How much faster does the proposed MatrixIRLS derivative converge compared to ALM? Are they comparable? * Are there applicable downstream machine learning/deep learning applications that require this kind of point recovery, where improved results could be further demonstrated?

Rating

7

Confidence

2

Soundness

4

Presentation

4

Contribution

3

Limitations

The authors address the limitations of their work in detail in the paper, and there are no societal impacts to be addressed.