Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization
Authors: Ipsita Ghosh
Abiy Tasissa
Christian Kümmerle
Venue: NeurIPS 2024 poster (2024)
Keywords: Euclidean distance geometry
non-convex optimization
iteratively reweighted least squares
low-rank
data efficiency
convergence guarnatees
restricted isometry property
dual basis
Primary area: optimization

Abstract: The problem of finding suitable point embedding or geometric configurations given only Euclidean distance information of point pairs arises both as a core task and as a sub-problem in a variety of machine learning applications. In this paper, we aim to solve this problem given a minimal number of distance samples. 
To this end, we leverage continuous and non-convex rank minimization formulations of the problem and establish a local convergence  
guarantee for a variant of iteratively reweighted least squares (IRLS), which applies if a minimal random set of observed distances is provided.
 As a technical tool, we establish a restricted isometry property (RIP) restricted to a tangent space of the manifold of symmetric rank-$r$ matrices given random Euclidean distance  measurements, which might be of independent interest for the analysis of other non-convex approaches.  Furthermore, we assess data efficiency, scalability and generalizability of different reconstruction algorithms through numerical experiments with simulated data as well as real-world data, demonstrating the proposed algorithm's ability to identify the underlying geometry from fewer distance samples compared to the state-of-the-art.
 
 The Matlab code can be found at \href{https://github.com/ipsita-ghosh-1/EDG-IRLS}{github\_SEGRED}

Sample-Effccient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization
Ipsita Ghosh
Abiy Tasissa Department of Mathematics
Department of Computer Science University of North Carolina Charlotte ighosh28charlotte.ee edu
Tufts University
Abiy TbiyyTaaissa@tufts..o edu
Christian Kümmerle
Department of Computer Science University of North Carolina at Charlotte edu
Abstract
The problem of finding suitable point embedding or geometric configurations given only Euclidean distance information of point pairs arises both as a core task and as a sub-problem in a variety of machine learning applications. In this paper, we aim to solve this problem given minimal number of distance samples. To this end, we leverage continuous and non-convex rank minimization formulations of the problem and establish local convergence guarantee for variant of iteratively reweighted least squares (IRLS), which applies if minimal random set of observed distances is provided. As technical tool, we establish restricted isometry property (RIP) restricted to a tangent space of the manifold of symmetric rank-r matrices given random Euclidean distance measurements, which might be of independent interest for the analysis of other non-convex approaches. Furthermore, we assess data efficiency, scalability and generalizability of different reconstruction algorithms through numerical experiments with simulated data as well as real-world data, demonstrating the proposed algorithm's 's ability to identify the underlying geometry from fewer distance samples compared to the state-of-the-aa
The Matlab code can be found at github EDG-IRLS
Introduction
Euclidean Distance Geometry (EDG) problems have applications spanning diverse domains, from comprehending protein structures through molecular conformations [MMLL19 MMWL22] pre-
diction of molecular conformations in computational chemistry [DPRVI5 SWBB97] and aiding dimensional reduction machine learning [TSO00] facilitating localization in sensor networks [FQX19], coupled with its role in solving partial differential equations on manifolds |L77 This emphasizes its broad impact in computational sciences. [LLMM14) proposes embedding entities based on Distance Geometry Problems (DGP), where object positions are determined based on subset of pairwise distances or inner products which significantly reduces computational complexity compared to traditional word embedding methods.
Problem 1. Mathematically, consider a collection of n points p, in an r-dimensional Euclidean space with coordinates P PP. P2. ..., Pn] E r whose pairwise squared Euclidean distances are given by di [lp 122 for each 1 i #
where || - denotes the Euclidean norm. Given only partial information of the (d,z) such that only subset of cardinality goal is to reconstruct the geometry of the points, that is to recover the point coordinates P.
n(n 1)/2 is known, the
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

If all the distances between the points are provided, the problem is known as multidimensional scaling [L144 GCKG23], and closed solution formula exists. However, this is not the case for the incomplete setup which is the focus of this work, and in which only partial information of the pairwise distances
available.
has shown effectiveness in predicting the three- dimensional structure of protein given input its amino acid sequence. AlphaFoldd, which uses an attention mechanism-basee transformer architecture [VSP+17] is trained on known sequences and structures from the Protein Data Bank [HMBGGG + 00) and determines the distances between the C. atoms of all residue pairs in protein. Subsequently, as a subproblem, this distance information is used to predict the protein's 's structure by identifying the foldings within the protein molecule. In the context of this subproblem, where the input is the predicted pairwise distances, a linear mapping can be used to predict geometric coordinates. However, many of the predicted distances might not be accurate, which is why low confidence regions of the resulting structures, as indicated by the predicted local-distance difference test (pLDDT) [JEP+21], could be masked, and a new structure could subsequently be re-computed based on the distance entries of the medium-to-hige confidence regions using high-accuracy solution algorithms for Problem !
For instance, AlphaFold [SE] 20,
JEP 21
In the context of the Problem 1 we have access to subset of entries of this D = [dL matrix, defined
by the index set Ω C {1,..... n)2 Now, we formulate the Gram matrix X P P. residing in the set of real-valued symmetric matrices S,. This matrix has a lower rank r compared to the symmetric distance matrix D E S, (X E R=** X = x which has rank of + 2 [DPVI15)
To make the solution translation invariant, the centroid of the points must be the origin, i.e., E Pr. 0. To ensure this, the Gram matrix should satisfy also satisfy X 1 = 0, where E is the vector all ones. Based on these observations, we can frame Problem as an instance of the computationally challenging NP-hard rank minimization [Reell] problem defined by
min XES,,X-1=0077 rank(X) subject to X X
2X
Dij
for all (1. E 2 (1)
incorporating also the positive semi-definiteness constraint X - 0, which comes from the observation that X P is also PSD.
P
From an optimization perspective, this manimiiniiizttion problem is highly complex due to its non- convexity and non-smoothness. Being an NP-hard problem [TLI8] Hen95 MW97], it is extremely difficult to solve directly. Consequently, a significant amount of existing research [Recl]] I D CR09 CWI8 Gro 1 [L18) has focused minimizing the convex envelope of the rank function, known as the nuclear norm, instead. However, it was observed that for related low-rank matrix completion problem, such convex relaxations are not as data-efficient other formulations ALMT14
TW13), while posing also computational limitations [CC14).
In this paper, we study the question of, given incomplete distance information Problem I how many samples are necessary to ensure accurate recovery? (TL18) established convergence with Q(vrnlog' r1) uniformly random samples for solving (1) using a nuclear norm surrogate. While there are numerous results for non-convex methods in other low-rank recovery problems [KV21 CLC19 [3n there are currently only few non-convex algorithm specifically designed for EDG problems available [TLI8 [SLCT23 ZCZ22 NKKS19 LS24. To the best of our knowledge, only NKKSS LS24 provide convergence guarantees the non-convex setting. Unlike generic low- rank matrix recovery problems (RFP10), EDG problems share the complexities of low-rank matrix completion problems, such as the absence of a direct uniform null space property [RXHI]] or a restricted isometry property [RFPIO]. Additionally, the underlying measurement basis in EDG problems is not orthonormal, making it impossible to directly use the analysis of standard matrix completion to provide guarantees for techniques using the Gram matrix- matrix-based low-rank modelling of Problem
1.1 Our Contribution
In this paper, we propose and analyze an algorithm for the EDG problem based on the iteratively reweighted least squares framework (MatrixIRLS, see Section 3), for which we show that vn
N(vrn log(n)) (where is the coherence factor) randomly sampled distances are sufficient to guarantee local convergence to the ground truth, X with a quadratic rate as shown Theorem 4.3 from which the geometry of the points P is trivially recovered. The sample complexity assumption

---

of Theorem 4.3 matches the lower bound of low-rank matrix completion problems as established in [CTTO]. Section [ we construct a dual basis (Lemma 4.4) that spans S, which enables to show the restricted isometry property (RIP) restricted to tangent space of the manifold of symmetric rank-r in Theorem 4.5 for our approach, which can be of independent interest for the analysis of other nonconvex algorithms.
While the convergence statement of Theorem 4.3 only applies in a local neighborhood of ground truth, the indicated data-efficiency of the proposed method is numerically validated through different experiments Section [ on synthetic and real data in comparison to the state-of-the-arr methods. Furthermore, we demonstrate that MatrixIRLS method is robust to ill-conditioned data, further highlighting its flexibility. In the Supplementary material, we discuss the limitations in Appendix B Additionally, we provide proof' related to the the theoretical results of Section in Appendices B
[ We further discuss the numerical considerations of our experiments in Appendix F. about the computational complexity of the algorithm in detail in Appendix F
We discuss
Related Work
Early research on EDG problems focused on establishing its mathematical properties like defining the conditions under which a distance matrix can be represented in Euclidean space space[Gow88 Gow855 YH38
YH38 (ARO5). A comprehensive overview of EDG applications, including molecular conformations, wireless sensor networks. robotics, and manifold learning. is available in [Lib20]. Motivated by the molecular conformation problem, [BJ95] relates this Euclidean distance matrix completion to graph realization problem by showing that such matrices can be completed if the graph is chordal. Other than graph theoretic approaches, as a technical tool, various optimization strategies [Hen95] MW97 Tro00 have been deployed to solve EDG problems. [AKW99] proposes a primal- dual interior point algorithm that solves an equivalent semi-definite programming problem. However, none these works provide theoretical reconstruction guarantees in the incomplete setup of Problem
While providing an accurate modelling of Problem [ the rank minimization formulation (I) poses challenges due to its non-convex and non-smooth nature. There is a mature existing literature [DR66] CR09, CWI8 Groll around replacing the rank function, rank(X), with the sums of its singular values o (X) (also known the nuclear norm). Building
the rank minimization [ of the EDG problem, [TL88) minimizes the convex nuclear norm surrogate of the inferred Gram matrix. They propose dual basis approach that enables a theoretical guarantee for this type of nuclear norm minimization formulation of the EDG problem.
formulation
From a practical point of view, it is well-know that the convex approach is computationally intensive, as the arithmetic complexity is cubic n, the dimension of X [CC14). It also tends to demand more data samples than non-convex alternatives, making it less efficient in terms of data [ALMT14 TW13)
To mitigate these issues, recent studies have shifted focus to non-convex methods such as matrix factorization [SL16] MWCC20 ZCZ22). These methods optimize a function involving data-fit objective regularized by squared Frobenius norms of the factor matrices, which are computationally more feasible and data-efficient. Few "non-convex" algorithms are based on matrix factorization like the work in BM03
Based on a similar formulation, ScaledSGD [ZC222 is a preconditioned stochastic gradient descent method aimed at robustness for ill-conditioned problems. Additionally, some of the most effective techniques for low-rank matrix completion involve minimizing smooth objectives on the Riemannian manifold of fixed-rank matrices, providing scalability and the potential to reconstruct the matrix with fewer samples, although they lack strong performance guarantees [Van | WCCL20 BA 15 BNZ2T].
ReiEDG (SLCT23 a Riemannian- gradient descent strategy utilizing the sampling operator on St which is non-convex approach to solving the EDG problem. However, it does not provide convergence guarantees. To the best of our knowledge, [NKKST9 LS24] are the non-convex approaches for solving the EDG problem in the Gram-matrix based low-rank modeling (1) of Problem [ The work in [NKKS19] proposes an algorithm based on Riemannian optimization over a manifold and provides convergence guarantees. These guarantees are derived from extended Wolfe conditions. However, is not explicitly detailed how these convergence guarantees depend on problem parameters such as the sampling model and the number of samples (see Remark III.8 in INKKS19). Similarly, the study in [LS24] employs a Riemannian framework and provides local convergence guarantees under Bernoulli sampling. Nonetheless, [LS24] does not clarify whether
3

---

the proposed algorithm achieves local linear convergence. In contrast to these studies, the algorithm proposed in this paper achieves local quadratic convergence under uniform sampling of the distances.
To handle the non-smoothness and non-convexity of rank minimization problems of the type (1) iteratively reweighted least squares (IRL.) algorithms take different route than methods based on [BM03] or Riemannian methods by minimizing sequence of quadratic majorizing functions of smoothed rank surrogates [DDFGIO] FRWIL MF10 KS18 KV21J. IRLS algorithms have been studied extensively over the years, as indicated by [aw6] GR97, Bur [2]. In the context of low- rank matrix completion, IRLS algorithms are known be among the most Mltaa-ffficien methods available, while being amenable to a rigorous convergence analysis [FRWI]] MFI0, KS18 KV21].
Most recently, [V21] provided an improvement on previous instantiations of the IRLS framework [FRWIT MF KS18 for low-rank optimization problems by providing an improved reweighting strategy, for which the authors show local convergence guarantee that is applicable for low-rank matrix completion, given random entrywise samples of minimal sample complexity. The algorithm we propose in Section 3 is similar KV21, Algorithm 1] and Theorem 4.3 follows partially the
proof strategy of related result in [KV21). However, the setup of Problem I does not allow direct adaptation of both the implementation and analysis of KV21 due to the non-orthogonality of the measurement basis.
3 MatrixIRLS for Euclidean Distance Geometry
In this section, provide a detailed outline and description of the iteratively reweighted least squares method in the context of the EDG reconstruction problem. To this end, we define preliminaries for stating the algorithm. MatrixIRLS, defined in Algorithm Danrtthmmhhhaa hhelow, can be interpreted as hybrid of smoothing method [Che12) and a Majorization iiniiittiioiiimiaatttoo algorithm (SBP17). In particular, the proposed algorithm minimizes smoothed log-det objectives defined as F. (x) = Ex (X))
log |o), fo log(e) ( if <c
if C
(2)
which is a continuously differentiable function with e L-iischitzz gradient KV21].
We can decompose X by X U dg(ro)U", where y {+1,-10) It is clear that the optimization landscape of F. crucially depends on the smoothing parameter c. Instead minimizing F, directly, our method minimizes, for k E N, c > and X quadratic model that is related to the second- order Taylor expansion of the function fe at the current iterate and its information is encoded in weight operator [V21] defined below in Definition 3.I
Definition 3.1 ( X E Sn be matrix with singular value decomposition X
U dg((r))U where y E [+1,-1] i.e., U E Sn are orthonormal matrices. We define the weight operator core matrix Hx,e E Sn of X for smoothing parameter & > O such that
(Hx,e)ij = (max(ox, e) max(o);)))
for each i,j E (l,..., n) and the weight operator Wx,e
S. + Sn, which maps any Z E S, to
Wx.c (Z) = U Hx. (UTZU)] UT,
where denotes the entrywise ore Hadamard product of two matrices.
Our method is designed to provide iterates that satisfy the constraints of the formulation ( at each iteration. They can be encoded using the following definition.
Definition 3.2. Given n E N, let = {a = (i,5) 11s iisi<js n} be the index set of upper triangular indices.
We define the operator basis (WaJaslL(t.Dieee where
eeeeT eje] e,e, - -eee, if (i,j) EI, (e T + 1e,),
W.
(4)
if a = (i, for some E [l,...,n),
where e; E I2t is the i-th standard basis vector.

---

Given a set (or multiset) of indices S2 = {a am C of cardinality m = |S2], we define the measurement operator A = Aq Sn + IR th t which maps X E Sn to A(X) whose f-th coordinate defined as a (War X) for & S m and A(X) = (W(t-m,E-m) m) X) for l > m.
The basis W a of Definition 3.2 can be considered as an extended definition of the primal basis used which guarantees that the Gram matrix corresponds to points whose centroid is located at the origin. Accordingly, we can define the constraint set corresponding to Gram matrices of points that are centered and simultaneously satisfy the pairwise distance constraints of Problem [ {X E Sn A(X) [D: O]}. The algorithm below minimizes the quadratic, majorizing model of the objective F., (-) given k, while satisfying the measurement operator based on the sampled distances. Equivalently, we can define the main computational step of the method as
in TLI8 L124], but additionally able encode the constraint X
X (k+1)=
arg min st. A(X) -[x;)
(X. (x))),
(5)
where Wi : Sn + Sn is defined as W3 W Wx(+),e, with the definition of the weight operator
Definition 3.1 above. With this preparation, we provide an outline of MatrixIRLS in Algorithm below. Equation provides suitable update rule for the smoothing parameter sequence (cx kEN that
enables the computation of only = O(7) singular triplets of each algorithmic iterate [KV21).
Algorithm MatrixIRLS for Euclidean Distance Geometry Problems
Input: Index pairs Ω 1, distances Dạ (d.j)) rank estimate F. Output: X (k) X after suitable stopping condition.
Initialize k = 0, 6o xo and Wo Td. for k 1,2..... do
Solve weighted least squares: Solve (5)
x W WF (AW A-) y
(6)
Update smoothing: Compute 7 + 1-th singular value of (*) to update
<k- 03 (X()))
ég min
Update weight operator: For ny == i [m] (X > Ex]1, compute the first 7ą singular
values of (1) and matrices (k) E g"xr, with leading ra left singular vectors of (*) to update Wt W Xxwieee defined in Definition 3.1
end for
3.1 Computational Considerations
The computational complexity of this above algorithm can be computed from the steps and (7) In
our numerical implementation, we largely follow the tangent space formulation of the weighted least squares step (6) cf. [VVI Section 3), which involves the solution of an order O ) = ((rr) linear system if provided reference implementation arises from the fact that AA" not the identity. The per-iteration time complexity of our method is dominated by O(mrr + N2 (nner)) where No inner is the number of inner iteration bound of the iterative linear system solver. Detailed FLOPs calculation is shown in Appendix F
is chosen as the ground truth rank. An additional difficulty we overcame in the
4 Theoretical Analysis
In this section, discuss about the local convergence of MatrixIRLS in Section 4. and establish RIP restricted to the tangent space of the manifold of symmetric rank-r matrices at the ground truth Gram matrix X in Section 4.2
4.1 Local Convergence Analysis of Algorithm
I
well-known the literature on low-rank matrix completion that for an entrywise measurement basis, recovery from generic measurements is more difficult if most information of the low-rank
5

---

matrix is concentrated in few entries, and this observation is typically captured by the notion of incoherence [CR09 Rec I Chel5]. For the purpose of the EDG problem of interest, we use the following coherence notion, which has appeared in similar form in [L.88.
Definition 4.1 (Coherence for Gram matrices in the EDG problem. (TL8)). Let X S, be of
rank r. Let T = Tx = {ZX + XZ" Z E I= I be the tangent space onto the rank-r manifold M, = {Z E S, : rank = r) at X. We say that X has coherence with respect to the basis Joet of the subspace (X E Sp X1 = 0} if
PT w3)² 2 and
Σ BET
(PTV wa) S 4v- n
IAX aET
max aE
BEI
where Pr: : Sn + S,, denotes the projection operator onto T and { is dual basis of {w,, Joss. which means that (Wo, v.)) 6, for each 3 6,. = 1 for a and equal 0 otherwise). Remark 4.2. In [L18 Definition 1], the coherence constant y was required to satisfy third condition (see ITLI (Ineq. 14)l). However, this condition is not needed for our proofs, which is why can use the weaker definition of Definition 4.1 Similar improvements for the standard basis incoherence
notion were achieved in [Che15]. In TL.18 Lemma 21J, it was shown that up constants, the definition above is equivalent to a coherence condition with respect to the standard hasis Rec Che15].
Following the conventional sampling approach in the existing literature Ree Che 15 CWB08), the index set is 52 = je) C contains m samples drawn uniformly at random without replacement.
Theorem 4.3 (Local convergence of MatrixIRLS for EDG with Quadratic Rate). Let X E Sp be a matrix of rank that is v-incoherent, and let A S.. + pm+ be the measurement operator corresponding to an index set Q C I of size m = [St] that is drawn uniformly without replacement. There exist constants C C and C such that the following holds. (a) If the sample complexity fulfills m 2 Cvrn log n, and if (b) the output matrix (() E Sn, of the k-th iteration of MatrixIRLS for EDG with inputs y = )) and F updates the smoothing parameter in (7) such that Cj-
Tr+1 (X()) and fulfills ||X(k) -X" 1s=
m
or (X") where K. = 01 (X
(*xd?((lgn)) vn-
is the condition number of X", then the local convergence rate is quadratic in the sense that (((k++)-xxlsss S <min(u|[X (x)) -x01 , -x)ls) with μ = (oa ((1+6K),,(X9)
and furthermoree (k++) to x with high probability.
(The values of the constants C* = 10 = 21v5,C = 4900 are explicitly derived in the Supple- mentary material.)
In other words, Theorem 4.3 indicates Algorithm D converges to the ground truth with high probability with sample complexity of Q(vnn log logn), n), if initalized close to the ground truth Gram matrix. We refer to Appendix D for its proof.
Our theorem's 's sample complexity requirement aligns with the lower bound for generic low-rank matrix completion problems, as established in [CTTO]. We note that this theorem only provides local convergence guarantee for Algorithm [ This is in line with the strongest known results for IRLS algorithms optimizing non-convex objectives [For10] KV21 PKV22]. We provide numerical evidence in Section 5 that the minimal sample complexity assumption (a) of Theorem 4.3 indeed captures the generic reconstruction ability of the method. To the best of our knowledge, Theorem 4.3 represents the first convergence guarantee for any algorithm for Problem I that applies at the optimal order ((rr log r) of provided pairwise distances, and furthermore, the first theoretical guarantee for any non-convex optimization framework for Problem [
4.2 Dual Basis Construction and Local Restricted Isometry Property on Tangent Spaces
While convergence result similar to Theorem had been previously obtained for IRLS algorithm for low-rank matrix completion [V22]) an adaptation of the proof of KV21 to the EDG setting is not possible due to non-orthogonality of the basis {Wa)a of Definition 3.2
In order to prove Theorem 4.3 we establish a restricted isometry property of suitably defined
sampling operator (see (9) with respect to the tangent space of the manifold of symmetric rank-r
matrices at the ground truth Gram matrix X = P P. To formulate this sampling operator and the
respective RIP condition, we construct dual basis to the measurement basis {Wa)o of Definition 3.2

---

Lemma 4.4 (Dual Basis Construction). Let n E N, [ n) be the index set and (wo Joelulp be the primal basis of Definition 3.2 with In = [(i,)) (1).., If
ifa = EI, a aaja a
Va
(8)
C,0 a,a;
where a, =; e, e E [I,...,n]. then [vaJoelupp is dual basis with respect to Joalul ie., (VaJa and (WaJa c are bi-orthogonal.
Lemma 4.4 extends the dual basis construction of TLI8
LT24], in which the duality of Vael
with respect to [WaJoel was shown. The proof of Lemma 4.4 is detailed in Appendix B.1
Unlike the basis pair of [TLI8 LT24], our bases span the entire space of symmetric matrices S, (see Appendix (..nnd which enables us to show the following restricted isometry property.
Theorem 4.5 (Restricted Isometry Property for Sampling Operator Qa) Let L = n(n - 1)/2. 0 < < 1.2 and S2 C. be multiset of size m sampled independently with replacement. Define the sampling operator Qn S, - Sn such that
Oa =
Σ
W.)
GEBU(E,)
where Wa and Va as in and respectively. X E Sn be a v-incoherent matrix whose kangent space onto the manifold M, of symmetric rank-r matrices is denoted as To Txo. Let PTo Sn, + Sn be the projection operator associated to To. Then |Pr, 2n PTo - PTo Prolls__ S e holds with probability at least
provided that
2 (49/E))mm) logn.
The dual basis discussed in Section spans the space of n X n symmetric matrices. This construction has been crucial in proving the RIP restricted to the tangent space Tx of rank constrained smooth manifold M,. This construction could also be valuable for analyzing other non-convex algorithms. A detailed proof of Theorem 4.5 is provided in Appendix C This proof is achieved by using concentration inequalities like the Matrix Bernstein inequality theorem C.I in multiple lemmas stated and proved in detail in the supplemental material.
3 aalong with the extension for the diagonal entries together
Since the existing literature for nonconvex approaches for solving Problem Jacks this property, this approach of establishing RIP by restricting it to the tangent space can be useful for the analysis of other nonconvex methods. The RIP condition, originally introduced in the context of compressed sensing Can08), is fundamental assumption in the literature low-rank matrix recovery ([ZL]2) Che 15 KV21 CZ33. A tangent-space restricted RIP has been has been useful for analyzing the convergence
and performance properties of other non-convex methods GLMI6 LZ23 LHL220 ZLTWI8] in non-EDG setting.
5 Numerical Experiments
We evaluate the performance of MatrixIRLS, Algorithm 1 for instances of the EDG reconstruction Problem
[ i terms of data efficiency across multiple datasets in comparison to other state-of-the-ant art methods in the literature. We compare the performance of MatrixIRLS with three other algorithms: (a) ALM, an augmented Lagrangian method that minimizes the non-convex formulation defined by millper*** Tr(P P) subject to Ra(P P) Re(X"),
with Ra being equal to the sampling operator On restricted to Zt which is based on a Burer-Monteiro factorization of the Gram matrix, and which has been studied in the numerical experiments of [TL18), (b) ScaledSGD [ZCZ22] which is preconditioned stochastic gradient descent method designed to be robust with respect to ill-conditioned problems, (c) RieEDG (SLCT23 which is a Riemannian-
gradient descent approach based the sampling operator (9) restricted Ω. The choice of these algorithms is based on their robustness to noise as claimed in the respective papers.
5.1 Synthetic Data
We first consider synthetic data, where select 500 points p [Pi; .... Pn.] E R
from standard Gaussian distribution at random such that (p.), i.i.d. NO 1) for all i,j, which
7

---

defines the ground truth Gram matrix X = POTP" We are provided with m [2t] Euclidean distances, where the point index pair set 12 {(i.j) E [m] x [n]. j} is sampled uniformly at random. This is parametrized by the oversampling factor mr-r(r-1)72 where the denominator is the degrees of freedom (discussed in Appendix E.4 To understand the efficiency of the algorithm over a range of ranks and across different oversampling factors p. we conduct phase transition experiments for all the above mentioned algorithms. We define successful recovery the case of the relative Procrustes distance dpmerostes Pree, Po) (discussed in Appendix E.3 between the recovered matrix P ree and ground truth coordinate matrix p does exceed tolerance threshold tol = 10-3 We chose the Procrustes distance at it is a shape preserving distance that accounts also for differences in scaling and alignment between the reconstructed geometries. We observe the performance of the algorithms as shown in the Figure [ for ranks between 2 to 5 and oversampling factor ranging from to 4 over 24 instances.
In Figure M each entry on the figure represents the probability of success of an algorithm for the given rank ground truth rank and oversampling factor p over 24 instances In terms of the recovery of the ground truth, we notice a comparable performance for the MatrixIRLS and ALM. However, the other two algorithms RieEDG and ScaledSGD, for the given success tolerance, the recovery of a ground truth is only possible if more samplies corresponding to larger oversampling factor are provided, for any of the ranks considered. This emphasizes that MatrixIRLS is able achieve state-of-the-ae data efficiency.
0.8
0.6
Rank
Rank
Rank
3
0.4
0.2
Oversampling factor
Oversampling factor
Ovensampling factor
Oversampling factor
(4) MatrixIRLS
(b) ALM
(c) RicEDG
(d) ScaledSGD
Figure Success probabilities for recovery different algorithms, given Gaussian ground truths X of different ranks, computed across 24 instances.
In order to understand the scalability of the proposed algorithm, have provided the time of completion of MatrixIRLS in Table The first two rows shows that for fixed oversampling factorp = 3. are able to recover the points the magnitude of 10*, is just 13.7 minutes. So to further test the scalability, we also looked at the time to completion when less number samples are provided ( p 2.5). In that setup 10000 takes 57.5 minutes recover with high precision.
5.2 Illconditionee Data
We now assess the performance of the different EDG methods on ill-conditioned data. Ill-conditioning in the point matrix in particular arises in situations where, for example, r-dimensional points are approximately following an r 1-dimensional geometry, a situation which often arises when available distance information if affected by outliers (ZC722)
Similar the setup above, we construct Gram matrices X S,, of rank 108 corresponding to = 400 random data points pd e 1g"x=
with condition
number = 01 ox, generated with random orthogonal singular vectors and singular values o, (X") interpolated between and 1 with decay of order ((i-2) Figure shows the success probability of different algorithms for ill-conditioned ground truths.
To have a deeper insight into the algorithm's performance, Figure shows the per-iterate relative reconstructed error of the four algorithms on this ill-conditioned data oversampling factor of p for a representative problem instance. This reconstructed error refers to the Procrustes distance between the ground truth pe and the recovered pk at each iteration k. We observe that for ill-conditioned data, MatrixIRLS is the only method that can recover the ground truth up to
For example, for rank r and oversampling factor p. if out of the 24 instances, in 12 such cases, the Procrustes distance based error is less than the threshold, then the probability of success is _

---

reasonable precision, achieving relative error of = 10 after around 35 iterations (top of Figure whereas the other methods do not achieve errors below 10-3 even after 100000 iterations. While one iteration of MatrixIRIS typically has a longer runtime than an iteration of any of the other algorithms due to second-order nature, we also provide visualization of the observed runtimes of the methods in the bottom of Figure [] It can be seen that MatrixIRIS is able reconstruct the geometry of the challenging problem around 200 seconds up to a high precision. Additionally, we run study the algorithms' behavior across different oversampling factors between p 1 and = for 24 random problem instances, visualized Figure 4 The box plots indicate visualize median relative Procrustes eтrоr together with the relevant 25% and 75% quantiles of the observed error distribution. We observe that MatrixIRLS has consistent convergence for ill-conditioned data even for lower oversampling rates long p 2 1.5.
MatrixIRLS
ALM
(c) ScaledSGD
RieEDG
Figure 2: Empirical success probabilities for recovery for different algorithms, given ill-conditioned ground truths X of different ranks, computed across 8 instances.
Retaite Enoor
10-4
Soale5CC ATM MarmitaL
10a
10
10a
10
10
10a
Relative Pracmesss
Teerations
109
10-4
Reldive Erree
10-4
RIAENG
ALM
10
10
10
10
10a
202
10a
2
Runtime scconds
Oversampling
Figure 3: Top: Relative error plot. Bottom: Runtime across iterates for one instance.
Figure 4: Performance of EDG completion algorithms over 24 instances on ill-conditioned data.
Real Data
To assess the performance of Algorithm I in realistic setups, consider the task of molecular conformation, i.e., we aim to reconstruct the 3D structure of a molecule from partial information about the distances of its atoms. For experiments. molecule (1BPM) from the Protein Data Bank [HMBFGG+00) which is collected using X-ray diffraction experiments nuclear magnetic resonance (NMR) spectroscopy.
determine the structures of protein
The goal of this experiment is to reconstruct the point matrix p from [ distance samples as defined in Problem For the IBPM protein data the rank of the input matrix is 3. We conduct the experiments corresponding to oversampling factors p between and Like the previous setup, here successful recovery refers to the case where the relative Procrustes distance, that is the metric dprocrustes (P Pree, P0) between the recovered matrix Prec and ground truth coordinate matrix PO does not exceed tolerance threshold tol across 24 independent realizations. The error analysis for this Appendix(E [E]
experiment is shown in Figures 7a and 7b
It is evident that MatrixIRIS and ALM have comparable results in recovering the geometry of the data given lesser samples, where as algorithms like ScaledSGD or RieRDG are unable to reconstruct geometries even when the oversampling rate is as high p 4. In the fig. 5 convergence

---

with high precision for MatrixIRLS from p 2.5 for Protein which means that it recovered the ground truth with around 0.5% samples.
Figure 5: Reconstruction of Protein 1BPM molecule Figure Reconstruction of Protein 1BPM molecule by MatrixIRLS with 0.5% samples
by MatrixIRLS with 0.6% samples
In the Figure 6 the reconstructed protein in blue is aligned with the ground truth structure of the protein in pink. We available, the reconstruction exactly matches with the ground truth.
that when the oversampling 3.5, which is when there is 0.6% samples
In order to understand the runtime of the different algorithms Table reports the reconstruction times for each the four algorithms applied the 1BPM Protein data (with datapoints n = 3672) in low-data regime with oversampling factor of p 3. It can be seen that MatrixIRLS is with 7.08 minutes around times faster than ALM, which needed 23.04 minutes until convergence. While these times certainly depend on the precise choice of stopping criteria for each algorithm (we used the ones indicated in Appendix this shows that the proposed method competitive terms of clock time.
Datapoints
Relative Error
Time (mins)
Algorithm
Relative Error
Time until
Convergence (mins)
500
1.04 x 10-7
0.03
1000
1.19 x 10-7
0.07
ALM
5.6 10-6
23.4
3000
1.37 x 10-12
0.8
RieEDG
5.6 10
116.6
5000
8.56 x 10-13
5.6
ScaledSGD
2.4 10-2
20.1
7000
2.26 10-12
8.5
MatrixIRLS
2.7 x 10-12
7.08
10000
4.06 x 10-11
13.7
Table 2: Runtime comparison for different ge-
Table 1: Execution time MatrixIRLS vs problem size n for Gaussian data with over- sampling factor p
ometry reconstruction algorithms from partially known pairwise distances for IBPM Protein data
(n = 3672, r 3), oversampling factor p
For the implementation of the other algorithms, we use the authors' code for the respective approaches (discussed in Appendix EE.. We include another set of experiments US cities data (0020), in the Appendix
6 Conclusion
In this paper, we address the challenge of reconstructing suitable geometric configurations using minimal Fuclidean distance samples. By leveraging continuous and non-convex rank minimization formulations, we develop a variant of the iteratively reweighted least squares (IRLS) algorithm and establish local convergence guarantee under the condition of minimal random set of observed distances. Our contribution also includes the proof of restricted isometry property (RIP) restricted to the tangent space of the manifold of symmetric rank-r matrices, result which might be of independent interest for the analysis other non-convex methods. As future work further analysis be established. Through numerical validation we conclude that the
on the global convergence algorithm is able to achieve state-of of-the-art data efficiency.
Acknowledgement
Abiy Tasissa acknowledges partial support from the National Science Foundation through grant DMS-2205 2208392.
10

---

References
[ADSVF23] A. Andreella, R. De Santis, A. Vesely, and L. Finos. Procrustes- based distances for exploring 32(3):867-882, 2023,
matrices similarity. Statistical Methods & Applications,
[AKW99] A. Y. Alfakih, A. K. Khandani, and H. Wolkowicz. Solving Euclidean Distance Matrix Complction Problems Via Semidefinite Programming. Computational Optimization and Applications, 12:13-30, 1999.
[AIf05] A. Y. Alfakih. On the uniqueness of Euclidean distance matrix completions: the case of points in general position. Linear Algebra and its Applications, 397:265- 277, 2005.
[ALMT14] D. Amelunxen, M. Lotz, M. B. McCoy, and J. A. Tropp. Living on the edge: Phase transitions in convex programs with random data. Information and Inference: A Journal of the IMA, 3(3):224-294, 2014.
[BA15] N. Boumal and P.-A. Absil. Low-rank matrix completion via preconditioned optimization the Grassmann manifold. Linear Algebra and its Applications, 15(475):200-23,, 2015.
[BJ95] M. Bakonyi and C. R. Johnson. The Fuclidian Distance Matrix Completion Problem. SIAM J. Matrix Anal. Appl., 16:646-654, 1995.
[BM03] S. Burer and R. D. Monteiro. A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Mathematical Programming, 95(2):329-357, 2003.
[BNZ21] J. Bauch, B. Nadler, and P. Zilber. Rank 2r iterative least squares: efficient recovery of ill-conditioned low rank matrices from few entries. SIAM J. Math. Data Sci., 3(1):439-4455 2021.
[Bou20] N. Boumal. An introduction optimization smooth manifolds. Available on- line at http: // sma. epfl. ch/ "nbowmal/ book/ IntroOpttimonnsfoolds Boumal 1__ 2020. pdf November, 2020.
[Bur12] C. Burrus. Iterative reweighted least squares. OpenStax CNX. Available online: http://enx. ooy2ommmmn2220007772222444444772
12, 2012.
[Can08] E. J. Candès. The restricted isometry property and its implications for compressed sensing. Comptes Rendus Mathematique, 346(9):589-59)) 2008
[CC14] Y. Chen and Chi. Robust Spectral Compressed Sensing via Structured Matrix Completion. IEEE Trans. Inf. Theory, 60(10))6576-600 2014.
[Che12] X. Chen. Smoothing methods for nonsmooth, nonconvex minimization. Math. Program., 134(1):71-99 2012.
[Che15] Y. Chen. Incoherence-Opineee Matrix Completion. IEEE Trans. Inf. Theory, 61(5):2909 2923, 2015.
[CLC19] Y. Chi, Y. M. Lu, and Y. Chen. Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview. IEEE Trans. Signal Process., 67(20):529--526,, 2019.
[CR09] E. J. Candès and B. Recht. Exact matrix completion via convex optimization. Found. Comput. Math., 96)7717-772, 2009.
[CT10] E. J. Candès and T. Tao. The Power of Convex Relaxation: Near-Optimal Matrix Completion. IEEE Trans. Inf. Theory, 56(5):2053-20) 2080, 2010.
[CW18] J.-F. Cai and K. Wei. Exploiting the Structure Effectively and Efficiently in Low- Rank Matrix Recovery. Processing, Analyzing and Learning of Images, Shapes, and Forms, 19:21 pp., 2018.

---

[CWB08] E. Candès, M. B. Wakin, and S. Boyd. Enhancing Sparsity by Reweighted é1-
Minimization. The Journal of Fourier Analysis and Applications, 14:877-905, 2008.
[CZ13] T. T. Cai and A. Zhang. Sharp RIP bound for sparse signal and low-rank matrix recovery. Applied and Computational Harmonic Analysis, 35(1):74 93, 2013.
[DDFG10] I. Daubechies, R. Derer,, M. Foraasie,, and Güntürk. Iteratively Reweighted Least Squares Minimization for Sparse Recovery. Commun. Pure Appl. Math., 63:1-38, 2010.
[DPRV15] I. Dokmanic, R. Parhizkar, J. Ranieri, and M. Vetterli. Euclidean Distance Matrices: Essential theory, algorithms, and applications. IEEE Signal Processing Magazine, 32(6):12-30, 2015.
[DR16] M. Davenport and J. Romberg. Overview of Low-Rank Matrix Recovery From Incomplete Observations. IEEE J. Sel. Topics Signal Process., 10:608-622 -2208 2016.
[For10] M. Fornasier. Numerical Methods for Sparse Recovery. In M. Fornasier, editor, Theoretical Foundations and Numerical Methods for Sparse Recovery, volume of Radon Series Computational and Applied Mathematics, pages 93-200. De Gruyter, Berlin, 2010.
[FQX19] J. Fliege, H.-D. Qi, and N. Xiu. Euclidean distance matrix optimization for sensor network localization. In Cooperative Localization and Navigation, pages 99-126. CRC Press, 2019.
[FRW11] M. Fornasier, H. Rauhut, and R. Ward, Low-rank Matrix Recovery via Iteratively Reweighted Least Squares Minimization. SIAM J. Optim., 21(4):1614-1640, 2011.
[GCKG23] B. Ghojogh, M. Crowley, F. Karray, and A. Ghodsi. Multidimensional Scaling, Sammon Mapping, and Isomap, pages 185-205, Springer International Publishing, Cham, 2023.
[GLM16] R. Ge. J. D. Lee, and T. Ma. Matrix Completion has No Spurious Local Minimum. Advances in Neural Information Processing Systems (NIPS), pages 2973-2981, 2016.
[Gow85] J. C. Gower. Properties Euclidean and non-Euclidean distance matrices. Linear Algebra and its Applications, 67:81-97, 1985.
[GR97] I. F. Gorodnitsky and B. D. Rao. Sparse signal reconstruction from limited data using FOCUSS: A weightttted minimum norm algorithm. IEEE Trans. Signal Process., pages 600-616, 1997.
[Grol1] 1] D. Gross. Recovering Bank Matrices From Few Coefficients in Any Basis. IEEE Trans. Inf. Theory, 57(3):1548 1566, 2011.
[Hen95] B. Hendrickson. The Molecule Problem: Exploiting Structure in Global Optimiza- tion. SIAM Journal on Optimization, 5(4):835- 857, 1995.
[HMBFGG 00] J. W. Helen M. Berman, Z. Feng, T. N. B. Gary Gilliland, N. S. Helge Weissig, and P. E. Bourne. The Protein Data Bank, Nucleic Acids Research, Volume 28, Issue 1, I January 2000, Pages 235-242, 2000.
[HS52] M. R. Hestenes and E. Stiefel. Methods of Conjugate Gradients for Solving Linear Systems. Journal of research of the National Bureau Standards, 49(1), 1952.
[JP+211 J. Jumper, R. Evans, A. Pritzel, T. Green, M. Figurnov, O. Ronneberger, K. Tun- yasuvunakool, R. Bates, A. Zidek, A. Potapenko, al. Highly accurate protein structure prediction with AlphaFold. Nature, (96(177)))7733--55557 2021.
12

---

[KS18] C. Kümmerle and J. Sigl. Harmonic Mean Iteratively Reweighted Least Squares for Low-Rank Matrix Recovery. J. Mach. Learn. Res., 19(47):1-49, 2018.
[KV21] C. Kümmerle and C. M. Verdun. A scalable second order method for ill-conditioned matrix completion from few samples. In International Conference on Machine Learning, pages 5872-5883, 2021.
[Law61] Lawson. Contributions to the Theory of Linear Least Maximum Approximation. Ph. D. Thesis, Univ. of Calif., Los Angeles, 1961.
[LHLZ20] Y. Luo, W. Huang, X. Li, and A. R. Zhang. Recursive Importance Sketching for Rank Constrained Least Squares: Algorithms and High-order Convergence. arXiv preprint wrXiv:201..08300 2020.
[Lib20] L. Liberti. Distance geometry and data science. Top, 28(2):271-333) 2020.
[L1.17] R. Lai and J. Li. Solving Partial Differential Equations on Manifolds From Incom- plete nnee-Pooit Distance, 2017.
[LLMM14] L.. Liberti, C. Lavor, N. Maculan, and A. Mucherino. Euclidean Distance Geometry and Applications. SIAM Review, 56(1):3 69, 2014.
[LS224] Y. Li and X. Sun. Sensor Network Localization via Riemannian Conjugate Gradient and Rank Reduction. IEEE Transactions on Signal Processing, 2024.
[LT24] S. Lichtenberg and A. Tasissa. A dual basis approach to multidimensional scaling. Linear Algebra and its Applications, 682:86-95. 2024.
[LZ23] Y. Luo and A. R. Zhang. Low-rank Tensor Estimation via Riemannian Gauss- Newton: Statistical Optimality and Second-Orde Convergence. The Journal of 2023.
Machine Learning Research,
[Meu06] G. Meurant. The Lanczos and Conjugate Gradient Algorithms: From Theory to Finite Precision Computations. Society for Industrial and Applied Mathematics., 2006.
[MF10] K. Mohan and M. Fazel. Reweighted nuclear norm minimization with application to system identification, In Proceedings of the American Control Conference, pages 2953-2959. IEEE, 2010.
[Mir60] L. Mirsky. Symmetric Gauge Functions And Unitarily Invariant Norms. The Quarterly Journal of Mathematics, 11(1):50-59) 1960.
[MM15] C. Musco and C. Musco. Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition. In Advances in Neural Infor- mation Processing Systems (NIPS), pages 1396-1404, 2015.
[MMLL19] T. Malliavin, A. Mucherino, C. Lavor, and L. Liberti. Systematic Exploration of Protein Conformational Space Using a Distance Geometry Approach. Journal of Chemical Information and Modeling, 59, 08 2019.
[MMWL22] M. Masters, A. H. Mahmoud, Y. Wei, and M. A. Lill. Deep Learning Model for Flexible and Efficient Protein-Ligand Docking, ICLR2022 Machine Learning for Drug Discovery. 2022.
[MW97] J. J. Moré and Z. Wu. Global Continuation for Distance Geometry Problems. SIAM Journal on Optimization, 7(3):8 14,836,,,, 1997.
[MCC200] C. Ma. Wang, Y. Chi, and Chen. Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution. Foundations of Computational Mathematics, 20:451-633 2020.
13

---

[NKKS19] L. T. Nguyen, J. Kim, S. Kim, and B. Shim. Localization of IoT networks via low- rank matrix completion. IEEE Transactions on Communications, 67(8):5833-5847, 2019.
[PKV22] Peng, C. Kümmerle, and R. Vidal. Global Linear and Local Superlinear Con-
vergence of IRLS for Non-Smooth Robust Regression. In Advances in Neural Information Processing Systems (NewrIPS), volume 35, pages 28972-28987, 2022.
[Rec11] B. Recht. A Simpler Approach to Matrix Completion. J. Mach. Learn. Res., 12:3413-3430, 2011.
[RFP10] B. Recht, M. Fazel, and P. A. Parrilo. Guaranteed Minimum- Raan Solutions of Linear Matrix Equations via Nuclear Norm Minimization. SIAM Rev. 52(3):71-- 501, 2010.
[RXHII] B. Recht, W. Xu, and B. Hassibi. Null space conditions and thresholds for rank minimization. Mathematical programming, 127:175-200 2011.
[SBP17] Y. Sun, P. Babu, and D. P. Palomar. Majorization Majorization-MMniizzttooo Signal Processing, Communications, and Machine Learning. IEEE Trans. Signal Process., 65(3):794-81 2017.
Minimization Algorithmss in
[S] A. W. Senior, R. Evans, J. Jumper, J. Kirkpatrick, L. Sifre, T. Green, C. Qin, A. Židek, A. W. Nelson, A. Bridgland, et al. Improved protein structure prediction us3ing potentials from deep learning. Nature, 577(7792):706-710 2020.
[SL16] R. Sun and Z.-Q. Luo. Guaranteed Matrix Completion via Non- Factoriza- tion. IEEE Transactions on Information Theory, (2(11):6535-657 November 2016.
[SLCT23] C. Smith, S. P. Lichtenberg, H. Cai, and A. Tasissa. Riemannian Optimization for Euclidean Distance Geometry. In OPT 2023: Optimization for Machine Learning, 2023.
[Ste06] M. Stewart. Perturbation of the SVD in the presence of small singular values. Linear Algebra Appl., 419(1):53-77, 2006.
[SWBB97] D. C. Spellmeyer, A. K. Wong, M. J. Bower, and J. M. Blaney. Conformational analysis using distance geometry methods. Journal of Molecular Graphics and Modelling. 15(1):18-36, 1997.
[TL18] A. Tasissa and R. Lai. Exact reconstruction of euclidean distance geometry problem using low-rank matrix completion. IEEE Transactions on Information Theory. 55(5):3124-3144 2018.
[Tro00] M. W. Trosset.
Distance matrix completion by numerical optimization. Computa- tional Optimization and Applications, 17:11-20 1-22, 2000.
[Trol]] 1] A. Tropp. User-Friendly Tail Bounds for Sums of Random Matrices. Foundations of Computational Mathematics, 12(4):389 August 2011.
[TSLO0] J. B. Tenenbaum, V. Silva, and C. Langford. global geometric framework for nonlinear dimensionality reduction. science, -90(5550):2319222222 2000.
[TW13] J. Tanner and K. Wei. Normalized Iterative Hard Thresholding for Matrix Comple- tion. SIAM J. Sci. Comput., 35(5):$104-$122) 2013.
[UU20] U.S. Geological Survey and U.S. Census Bureau. US Cities Dataset. Available at 2020.
https://siimpeeaag com/
[Van13] B. Vandereycken. Low-Rank Matrix Completion by Riemannian Optimization. SIAM J. Optim., 23(2), 2013.
14

---

[VSP* 17] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[WCCL20] K. Wei, J.-F. Cai, T. F. Chan, and S. Leung. Guarantees of Riemannian optimization for low rank matrix completion. Inverse Probl. Imaging. 14(2):233-28) 265, 2020.
[Woo50] M. A. Woodbury. Inverting modified matrices. Memorandum report, 42(106))336, 1950.
[YH38] G. M. Young and S. Householder. Discussion of points in terms of their mutual distances. Psychometrika, 3:19-22, 1938.
[ZCZ22] J. Zhang. H.-M. Chiu, and R. Y. Zhang. Accelerating SGD for Highly III- Conditioned Huge-Scale Online Matrix Completion. Advances in Neural Informa- tion Processing Systems, 55:37559-37560 2022.
[ZL12] Y.-B. Zhao and D. Li. Reweighted f--minimization for sparse solutions to underde- termined linear systems. SIAM J. Optim., 22(3):0055-108; 2012.
[LLW188] Z. Zhu, Q. Li, G. Tang, and M. B. Wakin. Global Optimality in Low-Rank Matrix Optimization. IEEE Trans. Signal Process., 66(13):3614-3628, 2018.
15

---

Supplementary Material
A
Limitations
For method, the limited convergence radius leads the convergence guarantee locally. Addi- tionally, the runtime per iteration is larger compared to other non-convex methods [ZC722 TL18 SLCT23] but our method achieves convergence in less than tenth of the number of iterations of the other methods. For some datasets like the Protein (IBPM) [HMBFGG*00) ALM has a superior performance for oversampling factor (p) between 1 and 1.5.
B Dual Basis Construction
In this section, we provide the proof the bi-orthogonality of the basis defined in Lemma 4.4 with respect the measurement basis Definition (322] and furthermore establish properties of the basis pair in Appendix will be useful later on.
B.1 Proof of Lemma
Proof of Lemma 4.4 For simplicity of the proof, we denote the two cases of Definition 3.2 separately. This helps us divide the proof into multiple subcases.
With L n(n-1) let [0(1.2)
"(n-1.n)] _ be a matrix whose columns enumerate the vectorized dual basis elements Va where (i.j) E I, and let VE E R=*xx consist of vectorized dual basis vectors V(i.i) with i E fI...., Similarly, W E Raxx and WE I 2 are defined using vectorized basis elements {wa) As establishing duality between the two basis sets is equivalent to bi-orthogonality of the basis elements, it remains to show that the extended basis matrices V = [ViVe] E R=*x x and W [W] e] E R L+n satisfy the relationship
W
W = Id,
W
W
W
where Id is the identity matrix.
In coordinate-ve wise notation, this means that for a (1, and (k, 1), with S SiSss n and 1 < k < IS < n, we must show that (Was Vg) = -a,0 where Wa and V are columns of W and V respectively.
From Claim 3.1 of [LT24] is clear that the dual of W. We require to show the biorthogonality for the extended parts.
First we show that, for of the form (i,
(Wa: Va)
(Wa,i, Vi.))
(c I +11.0, c,o,T - -aaa?)
(10)
((e: I e,,, (1 o, e,e,T) (e; IT, a.a, (1 e, a,a,)
Let decompose the summand (e, TT, a,aT) in detail, so that we can derive the remaining calculations in a similar manner,
(e -T ",a,..) = (e; I e,e,)) - (e. T 1e,T (e, IT 1 e T) + (e, IT 1 1
n2
1
11
n
0.
16

---

Putting this value back in (10) we can complete the rest of the calculation in similar manner and finally arrive at the following,
(Way Va)
(Wa,i: Ve.1)
(e:
, ,,,,, + +1 e1, e,e,)) - (er "T,, + (1.e,, a.a,
[1+1-0-1
2
1.
Now, let us look the case where = (i, and 3 (i.j) and i * j. Using a similar calculation can show that,
(W va) = (We,s Ys.s)
(e, 1 -1.e, a,a,)
2 (10: ,,,0,) - (1.c)) , (e, 1e..1..1... 1T, [,aa)))) + (1 e. a,a,))
= 00-0 0+0
=0. 0.
Also, between the wa and V where a = (i,j) with s <i<js n and B = (k: 1:) with I k S n, can show similar relation by
(Wa, vz)
(Wi.j. Vk.k)
2 ( + +jj - -ii - ej exya axet
6 + +bjkk - -0-0- (ōi, ) 1- 1 - (ōj.a - (
2/ -1)
2
(6i, (0 -+1
+
1
1
dgn + 1 -5 + 88g
1
61, + .8ik 6i,Kdi,e + 8i + -j,k
2
n
n²
n
- 2- 25
+
+ 26,
+
n
n?
1
(
2
81
O.
Finally, we need to show for wa with a = (i,d) for S i n and Va where = (k, 1) with 1 1 k < 1 < that the respective dot product is 0. This is verified by the calculation
(Wa: va) 4 (e, I +1.e, egee +ejeT)
(lo, 1T, ,Too)))))))) + (c: 1 .qe)) + (1 o. oz + (1 (1.c,, qee))
(ōudu dada + dada + 64.5a)
(óury + dudu + sada + 64gs)
(45
Su
5k1
17

---

Hence combining the above parts we have proved that V is the dual of W.
B.2 Properties of Dual Basis
Lemma B.1. WVT maps n x n symmetric matrices to itself.
Proof. Let x be a vectorized representation of a symmetrie matrix X. Then, using the dual basis
expansion, x can be represented as: x WVTx. x. We now apply the the operator WVT to x.
[WVT)WVTx WVTx.
where the last equality follows from the fact that V is dual to W.
Lemma B.2. For orthonormal basis {wa} and {v.) y as defined in Definition 3.2 the spectral norm of WVT is that is
WV
=1.
(11)
5,00
Proof. By definition,
WWV 1ss
WVVx Note that ||+||==1
max
WV V (WW W)
By construction the dual basis, (WTW) VV -1- Therefore, V(W an orthog- onal projection operator onto the column space of V. If x is a vectorized representation of any symmetric matrix, using Lemma B.I the projection operator is identity operator. Hence, its operator norm is 1.
C Sampling Operator Bounds and Proof of Tangent Space Restricted Isometry Properties
In this section, we first state the matrix Bernstein [Trol]] concentration inequality for rectangular matrices, which is repeatedly used in the proofs further in the section. We then provide proof for the bound of our sampling operator Co and then we conclude this section by proving the RIP restricted to the tangent space of manifold of symmetric rank-7 matrices the ground truth X
Theorem C.1 (Matrix Bernstein for rectangular matrices [Toll Theorem 1 1.6)). Consider the finite sequence (Zv) of independent, random matrices with dimension d d2. Assume that each random matrix satisfies
E Zu] = 0 and Z S
R almost surely,
Define
0² = max Σ E El Zi
Σ E Zzz Zi|
Then, for all 2
-22/2 o2 + Rt/3
P
Σ
Zu]
2t
S (d1 + dz) exp
(12)
Lemma C.2 (Spectral Norm Bound for Sampling Operator 2a). Let n be the dimension of the input matrix and let Ω (ie, jt) C I be multiset double indices fulfilling m L n(n 1)/2 that are sampled independently with replacement. Consequently, we have that with probability of at
least 1 2. the sampling operator On Sn + Sn, of
fulfills
log
10 I1.m 20L
1.
m
18

---

Proof. We defin,,
Ro = VSn W
= Σe Vawa a
(13)
OE
So from (13)
Rn Rs
On RS +V W
On' Ro' + L
WE
In order to provide bound for Qa, we first evaluate a bound for Rg. We would use concentration inequality of Theorem C.I for computing the bound of On Let us define
1 VWT m
2
Vo w
(14)
We compute the expectation of
n by,
L
E [
= E
Vos
az
VW
m
L
L
VW
Va
Was
m
m
(15)
1
VW
VWT
m
0
Now let us compute the bound for Z₁
1
|
||s
Vag
w T
VW
1
Vay.
W
+
VW
(16)
m
8.0
m
Sx0
VA
w
T
+
1
S.0
We use triangle inequality in the first inequality and since the spectral norm of VWT is 1, we arrive the second inequality. Now, we can further bound the spectral norm of Vos w T by.
Vo, W 1ll. = max (V. Vol
W W oz
T
| 1|
Va.
Way 11
(17)
Vau la
|ay
1 4 4
So from (16)
we get
4L + 1
<
(18)
m
19

---

We take the product of ž₁ and z as,
Zk
Vox
W
VW
W
vwT)
111
m
m
a2
m
1
WV
VWT)
Way
Vap
m
m
m
Ok
m
L
L
(Way
V
Vog
(
V
VW
(WV
Vay W oa
m
on
m
m
WV VWT)
+
m
Now taking expectation on both side of the above relation we get;
2
(Wor Von
Van Wor Te)
L
(a
Vol VW )
m3
m
Vax W (WVT
+E
(WV
VWT)
m
m
T22
T
E
m
(War
Van
Van w
Way
T
E
m
W
Von
vWT)
1500
1500
vW
|
+
Vos W
+
E
WV
m
m
8x0
1,2
L
(War val vWJ)
Wai
Vas Van worl
+
m²
m2
8
8x
L
VWJ) az
Wax
+
L
m
m
500
1,2
max Way Van Va, w
Is
I,
WV
T
VW
m²
m²
WV
VWT
m
m
Sm0
16L + 2L +1
m2
(19)
Since expectation is a linear operator we can preserve the equality in the first equality, then we use triangle inequality in the first inequality. We further use that the spectral norm of WV is 1 and arrive at the second inequality. Further using (17) we bound the expression in the last inequality. As per Theorem C.
we now compute the product of 2 and z
L T
L w
Va
VW
(
Vay
VWTJT
m
m
m
an
m
L
1
L
T
VWTJ
WVT)
m
Okk
m
m
L?
m²
(Vor
W
Wa
Way
m
(Va
W
as
WVT)
L
(VWT Woe
(VW
WV
m?
m²
20

---

Now taking expectation on both side of the above relation we get;
L
[[(zz
Von wae Way varlll
m
100
Vas
WV w
L km
m
500
1
L
(VW
T Wax Yau
1
T. m²
m
(20)
1,2
Van W T
Way vT
vW WVT
max
+
m
m²
9
L VW
WV
+
m
m
8.c
16L + 2L+1
+
m2
So, now by Matrix Bemsstein Inequality as stated Theorem
C.1
E 2
=0
The value of the bound of zy is denoted by R in Theorem
C.I
So R in this case is
4L
Z 900 R
Further a defined by max Ex E E(z22))
Σx 2(z
as per Theorem
We have,
16L + 2L +
16L + 2L +1
0² m
m2
So as per Theorem C.I
-
> 0, P(I
Σ
z 2xlls> 2t) $ 2n exp(
(21)
02
R
Recalling the definition of z from (14)
zu Ils St = - - 11.m St
1=1
Therefore,
L On' ||
-
m
<
I
Qn' VV
1l + +|| 11
(22)
m
+++
with probability 2n exp(
We have arrived the above incquality from the definition of On and that the spectral norm the extended basis of the dual pair, V V E is 1.
a² 3
Since T. = n(n 1) so, T,2
<
nLL
We can further simplify the denominator by the following,
2
Rt
161. +
4L
02
3
m
3m
16I
2L
2Lt
(23)
+
+
m
m
(16L + 3 2t)
m
21

---

We arrive at the first inequality by using 1 _ L and
4L+1 3m
6L
3m
So using this relation, let us assume that / 201
Jog
m
Further let us simply Equation (23) by using this value of t. Since by Theorem 4.3 where K = Cvr, so
m 2 Kn log n.
log 12
Kn. hence we can say simplify Equation (23) further by the following.
Rt (16L + 2t)
0²
3
log n
16L + 3+2 202
(24)
167 + 3 +2 2 1
2 Kn
m
L
(60L)
We arrive at the third inequality bu using the expression for and using Then, deduce the following from Equation (24)
Logn
Kn'
20 L log
2
2m
exp
02
RL 3
= exp
6012
400
< exp
log n
120
exp(3.33 log( -))
nz /)
1
S cxp(log(
1
n
So the probability in (21) becomes 2n 1 If we use (22) then we can conclude that that the spectral n3 Ing + 1): Hence, we can say that the spectral norm of Qn is m
norm of Qn is bounded by (20L bounded by 200L
log n + +1) with probability of 1 2
Now we prove the restricted isometry property of the sampling operator Oo with respect to the tangent space of the rank-r matrix manifold at the ground truth, stated in Theorem 4.5
Proof of Theorem 4.5 Then,
Define z
L.rr Way Van Pro
1 Pr, Pr. m
E E(zx) =
L Pr, Pr.
Way VoT Pro
PI, WV T Pro
m
1 Pr, WV PI. Pro
(25)
1=1
1
Pr. WV Pr Pr.
Pr. WVT Pro
m
m
22

---

Now we calculate the spectral norm of Z
I,
7 |s.
Pio Wan Vos
Pio
P1o WVT
m
m
500
L Pro Wan voa Pro
+
Pro WV PTo
500
L IP Wan
1P Vaulle
(26)
171
m
2L
2vr
2vr
V
T
n
m
4
1
mn
m
The third inequality follows from the coherence bounds as in Definition 4.1
L Pro v Pro 1 Pro PT.
- Pro Wa, PT. 1 Pro WVTP))
ziz
L²
L
! Pro Vos w Pb War v PTb)
Poo Way PIo WV
Pro)
m²
L
PI, VW PI Way voL PIa)
Pr. VW. WV Pr.
m²
m²
We use that P2 Pro in the second equality further calculate the expectation of the above equality,
1
E(2iz*) = E
Pro
Van w Pso Wan V Pro) - E((
Pro
Vol w
PTo WV Pro)
m
m
L
E((
Pib
VW
PI. Pro War Van Pro)) + E
PIo
VW
Pr PI, WV WV.)
m
m
L2
E(
PIo
Vaz
W
Pio Was VOe Pro)
Pro
VW
PI,
PI
m²
m²
PIo
VW PI.PI WV Pro
+
Pro
VW
Pr, PI. WVTT.. PTo
m²
m
L Pro Van w Pro Way V Pro)
E m²
Pr.
VW
VW
PT, Pr.
WV PT. Pro
m²
since WV Ld, we can adjust summand at the seocond equality. Defining the random operator 2n == in Pro Wai Vaz Pro, we see that 2, from above satisfies Z₁- Z 1 Pr. WV WV,r, and therefore m
E - PI. WV TVT
With this definition, and for the fact that positive
matrices satisfies
||A Blls_- I max([I-Alss_ [BBlls ). bound the spectral norm of the expectation in the
following way
PIo NVVTRR, VW Pro
m
800
(27)
S max
|E
m²
For any M E nxn it follows from the definition of 2
L (VoL. Pr. (M)) (W..) m
2y (M)
(Pro Mi (W.c),
m
23

---

L
4 (Way) Pro (M)) (Vor)=
(M)
(Tr, ()) (Voz)
m
m
and thus
L Zz (M) =
-
(Pri (Pc( 21 (M)) (Vaz)
L
(Pro (War); (Pro (Vo.), M/Pr. (Waz)) Pro (Vaz)
m2
1,2
Pro (Waz. (V (Voc)
m2
Now using the incoherence condition such as Definition 4.1 and [L18 Lemma 22]. we can argue that
L
B
2
11 5:
máx t=1
PPr (we) 11 ||
Pro Von You Prollls
m²
1,2
max
PPr (w
Pub veve TPr
m?
t=1
L
L
mäx m² 8=1
L
PPr, (we) |/
max PP (Var))l 1=1
L
(2v ") - (8y
1
m
L
L
1222
16
m 2
n
Now we get from (27)
L
(16
I mmx
1 n²
(28)
m
So by Triangle Inequality,
L
u2p2
L
22
E 2 zk)
S m
16
16
(29)
m²
n²
m
n2
Now we need to compute similar bounds for B[z,2,]]
L m
E
Pro Was Van Pro Vor Way Pro
1000
P Pro T Pro wev Pro vew, vew
max
|rA, W.v, Pr.Vew/ Pro lle
(30)
max IP Val 11 max | Way. 1!
L y2,² (B==)
L
(2v
m²
n
16
n?
So similar to (29)
we apply Triangle Inequality on (30) and get,
L
u292
L
22,2)
Σ
|[(zzt))
S m
16 n²
16
(31)
m²
n²
1=1
Sxc
m=
24

---

Now, we can upproximate this bound in the following way. Since L = n(n-1)
L n² this bound can be written as
2p2
22p²
E (Z
16
8
(32)
112
9:c
Comparing the equations (31) and (32) as & is larger than vr. So
we can argue that the bound on
(31) is larger than that of (32)
2
MTL
E (
S
(33)
55c
So, now by Matrix Bemsstein Inequality stated Theorem C.1
E (z
The value of the bound of zy denoted by in Theorem C.I
So R in this case is
4vr I 7 1s. S R
Further a is defined by max (Zzz2,)
EZ Zk ) as per Theorem
We have,
m
m
o² max
Σ
E (2
Σ
z zx
800
800
0² L 4vr
m
71
So as per Theorem C.1
Vt 0, P(I
Σ zulls 2) 2n exp(
(34)
0²
Now we would calculate the bound for the above probability, In this scenario, since n(n-1) we can bound (o + Re by the following inequality in the second,
3
(02
R
Avr
AvrL
6
3
4
+
3
3m
SurL
+
3m
9vrL
We use & is less than 1 in the first inequality and the the second summand is less than ar in the second inequality. Here further we used that < and 2 1, 2 1 and bound the probability as follows,
2
2n exp
<
2n exp
0
2
2n exp
18vr
49vrn 2 log n
< 2n exp
18vr
98 log
< 2n exp
18
25

---

19yar So, given that m 2 z log n holds true, we can arrive at the first inequality above, further, since
n(n=1) so we can say, L S n² / hence we get the second inequality. We can bound this further
2
by.
98 log
2n exp
2n exp
02 +
ltc 3
< 2n exp
4 log n2
1 log
< 2n exp
2 n2
Hence we can conclude from here that Now can derive the bound ||Pro On PTo Prolls following argument,
- k= 2/ 1.s
< 6) holds with probability of
73.
2
in the statement of Theorem 4.5 by the
L
L Way
Σ
Zk
Pio m
V Pro
- Pr. WV PTo)
800
1=1
800
Pro Rí PTo Pro WV
8x
Pro Rín Pro + PROVEVEE
(Pro WVT
PTo + Pro WEVE
500
Pro en -P
Sc
8mc
We get the get implication by adjusting the equation with addition and subtraction of Pr, W I because Pro WV PTo + Pro w WEVEL So, we have proved the assertion of Theorem 4.5 is true with a probability of
V Pr, = Pr, WVT PT, and WV Pro Pro
Following Proposition 3.1 in [XHII if we change the sampling model sampling without replacement we should have the same bound with same failure probability.
D Proof of Local Quadratic Convergence
In this section we provide the proof of the local convergence theorem stated in Theorem 4.3
Lemma D.1. Let < 3, let X E Sn be a v-incoherent matrix. Let Pr, : Sn - Sn, be the projection operator associated to To. Then assume that the following three conditions hold:
(a) For On Sn + Sn be defined as in (13) from m. independent uniformly sampled locations, we have:
2n lls.. S (20T,)
log m + 1).
(b) The tangent space To Tx" onto the rank-r manifold To
Pro On Pro -
Pro
5 SE
(35)
(c) The spectral norm distance between X and X fulfills:
x - x 11s00 s
or (X.)
(36)
200
logn n
26

---

Then the tangent space T = Tx onto the rank-r manifold at X fulfills:
Pr 2n Pr P
Pr Pril S
I 4s
(37)
Lemma D.1 is a literal adaptation of [KV21] Lemma B.3] to the operator on which is why we omit Lemmas B.8 and B.9 of [V22 in the same way for our proofs.
its proot. Similarly,
Lemma D.2. Let X Sn be matrix of rank that is v-incoherent, and let Ω (iz, j0 be a random index set of cardinality [92] = m that is sampled uniformly without replacement, or alternatively, sampled independently with replacement. There exists constants C, C, C1 such that if
m 2 Curn log
(38)
then, with probability at least 2r. the following holds: For each matrix X S fulfiliing
vm
X 111ss> S
Tw/lonn (x"),
(39)
it follows that the projection Pr, Sn + Sn onto the tangent space Ta = TT satisfies
2
Pr, On Pr,
Pro 800
5
and furthermore,
log ni
||l| S CLVy
IIPT (n)lle.
for each matrix 1) E ker Qa in the null space of the operator On : Sn Sn
Proof of Lemma D.2
Assume that there are locations Ω (it, jt m in sampled inde-
pendently uniformly with replacement, where fulfills (38) with C == 49/e² and
0.1. By
Lemma C.2 it follows that the corresponding operator Qa from Lemma fulfills
log
Qn Ils_ < (20L)
+
(40)
m
event called eg, which occurs with probability of at least - and by Theorem 4.5 the tangent space To M, corresponding to the pu Mo-incoherent rank-r matrix X fulfills
Pro PiPro Pro
Se
event called en,7, which occurs with probability of least - n 2 Let ē (M) E Raxa is such that ( l S (X.) with
10- If
(41)
200L logn
+
20 10--10L///
log
m
m
it follows by Lemma D.1 that on the event En 7 En,ro the tangent space T. = (()) onto the rank-r
manifold at (k) fulfills
2
Pr. PnPr. - Pri
< 47 5"
(42)
8.00
Next, we claim that on the event En n En,To
log nh
||||| s ËLV
|| (n)lle.
(43)
for any for each matrix 7) ker Qq in the null space of the operator Oa S, - Sn,
Let E ker On- Then
27

---

IPr, (n)lli-
(Pr Pri (n))
(PLs (1) (1), Pn 2n Pni (1)
+ (Pn(():
Pr,(1) (n).
PP,, 2n Pr, (2((1))
S (Pr. Pr. On Pr. (1)
+ P1p, (1)l
PTr - PP,, On PT. I1s I1Pra (1))l
- (T). Og Pri (m)
4e (T)ll))
Using (42) in the last inequality, implies that
Prr, (1)) 11 -
(Pr, (1), Pr. 2n Pr, (1))
5c
(Pr, (1). 2n Pr, (r))
5c
<
(Pr, (1)², On Prù (n))
4c
1
K
(On Pr. (1), Pr. (n)
4
(44)
1
K
(On Pr. (1), Pr. Pr. (n))
4
1
<
(Pr, On Pr, (r), (1))
4c
<
(Pri (1). Pr. 2n Pr, (1))
4c
< 4c (Pr( 1,_ l On Pry (1)ll
Dividing by Irrr (1) on both sides we get,
S 1- 4E IPr, 11 ll Qa Pr. (n)lee
$ Qa Pn (n)ll
Since spectral norm of Pr.- is bounded by 1. Furthermore, we used that S 10 in the last inequality.
Since 77 E ker Co. it holds that
0 = (n()ll = On (Pra (n) + Pry (1) 2 2n Pr. (1)llr - 11 2n Pry (1)llr
so that
|| On Pr. (v)] < 2a Pro (n)llr S (201g) log n + +1)11P24(1) (m)llF.
m
where we used (40) in the last inequality. Inserting this above, we obtain
|nll = ||Prs (n) + 1Pr4(1)11B (1) < (2(201)/ log
m + +1) 2 +1 IIPry (n)ll
logn n iPPT4 (1)
<5 (211
m
Since L log > So we get
log n m
||lll s ČIV
IIPr (n)lle.
(45)
28

---

for the constant defined by,
Č= v5. 21
Moreover, we observe that for C = 20C
where C1 the constant of (39) it holds that
Civm
و 10
log 20
Lylogg
implying that the two statements of Lemma D.2 are satisfied on the event Eg n En,r, if holds. By the above mentioned probability bounds and union bound, Ep n Ea,T, occurs with probability of at least 2n 2n- finishing the proof for the sampling with replacement model. By the argument of Proposition of [e, the result extends to the model of sampling locations drawn uniformly random without replacement, with the same probability bound. This concludes the proof of
Lemma D.2
The following lemma will also play a role in the proof of Theorem 4.3
Lemma D.3. Let C, C, be the constants of Lemma D.2 and po be the incoherence factor of rank-r matrix X 1f
m 2 Curn logn
and 1f (k) x()) X fulfills
|ss (xr((X))
with
Civm T.Vlog
10C vm
{ = min
81 8T./rts//lgr
then, on the event of Lemma D.2 it holds that
logn n (vn r r) 1
11s. S &2LL
(46)
Proof. First, we compute that
PPr. (1F= = IPr4 (x( + I |l
Σ (x())) + | (8)
(())))
1=+11
vn (x(1)) | Un S.. [ 11s.
1113
I nn (x(+))
(1 () Vroi (x))
(x) 1/3
Vn ro (k)
(1 - (X) Vik,
where 0 <<< < such that (x
(k)
X I (X.), using Lemma D.4 twice in the fourth
inequality and |AB F < A - |B|| r all matrices A and B, referring to the notations of lemma
B.8 KV21 see below) for Uo. Eo. Vo. U(k) and (((h)
Using Lemma D.2 for (k)
X x obtain on the event on which the statement of
Lemma D.2 holds that
log
[1s,. S (k) S CL
IIPTT (1)
m
log n
1
Vn Vn-ro++1((1)) +
o, (x(X))
|log
8- 1010 6-10CVmmTTh (8) 8Lylog n
< <UL
(nn VV--oo44 ror-00 (x (1)+
m
29

---

since C1 1_
200
after rearranging we get,
i (1-2) (17 (1) llsm s sēw
log m (vn - 110-))+011(0X0 (x(1))
which implies the statement of this lemma.
Lemma D.4 (Wedin's bound [Ste06]). Let X and X be two matrices of the same size and their singular value decompositions
Σ ( Σ
) and == (Ū ú.)
V V
1 0
x X XU
U1)
v
where the submatrices have the sizes of corresponding dimensions. Suppose that 6, a satisfying O < ô S. a are such that S O (2) and maxx (max(_]]
(E a Then
| Ull S S/2 X X|ss= and
X X||s S
V Vils V2
(47)
Now using the above lemma let conclude the proof for the theorem,
Proof of Theorem 4.3 Let k ky and X be the k-th iterate of MatrixIRLS fro EDG with
the parameters stated Theorem 4.3 Under the sampling model of Theorem 4.3 the number
of samples fulfills m 2 Cvrn log n, where C is the constant of Lemma D.2 know from Lemma D.
if furthermore (K = (A) x fulfills
||) S (X)
(48)
with
Civm
s LvVlon
(49)
holds with probability of least 1 2n Then, by lemma B.9 of [K22]
<(02
Ö (C
(K+11)
X 11
[ls)
(50)
m
We denote the event that this is fulfilled by E. Furthermore, this event, if & < 1/2 in (48) and denoting the condition number by x = 01 (x,)/a,("))) , it follows from .lemma B.8 of [V21], that
(++1) 1 S
( log
L
4a, (x0) (#t + 4exl117 ||s (*) + 2111 11)
m
Furthermore, ((() E R denotes the best rank-r approximation of (k) norm, estimate that
(k) in any unitarily invariant
S ( = X (l I |x(()) 1 = [1) 1s
Inserting these two bounds into (50) we obtain
L
|1 (k+1)) |و = (k+11) x I
40, 4x, (1 6x) || 133
m
Finally, if, additionally, (48) satisfied for
E L / 4(1 + 6x)
(51)
we conclude that
|17 (k+1)l|s
< (1)
30

---

and also, we observe quadratic decay in the spectral error such that
|17 (++++)
||5m0 I | 11
with constant μ L 4(1 (X)
This shows condition b of Theorem 4.3
To show the remaining statement, we can use Lemma D.3 show that if ( is close enough X we can ensure that the (r+ 1)-st singular value 0, More precisely, assume now the stricter assumption of
of the current iterate strictly decreasing.
vmyr
||7
( Is
12C'L(log n) for
(52)
In fact, if & fulfills (4) and (51) we can conclude that on the event E,
0 5 1)
= 11
1 ||nn(*+2)||s.
C L log
40, (x²"x" (1 61s) (17
Is (ss
m
C Log
mm
40,(X" (1 6k)
m
12C Vn
log n1 (vn - r (X (8))
Ea, (x))2
S (x(+1(((
using Lemma D.3 for one factor (k)) |ls and (52) for the other factor (k) lls in the third
inequality, and (51) the last inequality. Taking the update rule (7) for the smoothing parameter into account, this implies that E 0r+1 = (x++))), which ensures that the first statement of
Theorem 4.3 is fulfilled likewise for iteration + By induction, this implies that (k+E) 8-000 x which finishes the proof Theorem
E Numerical Considerations
E.1 Experiments more real data
As a continuation Section 5 we provide the error analysis for the 1BPM protein data whose corresponding recovery visualizations are found in Figures 7a and The figure Figure 7 Procrustes distance between the recovered matrix from the samples provided and the ground-truth for both datasets. Similar the phase transition diagram of the Gaussian data, we observe the probability of success observed over these 24 instances in fig. 76
shows the
TiLIIT TTTT
Reliaive Proenvaes Liver
0.8
EUEEDC
Probahilit
10
0.4
SoleDoD
10
Ovver campling
Oversampling
The relative Procrustes the algorithms for different (b) The probubility for the algorithms for different oversampling rates [orIBPM protein data
sampling rates for 1BPM protein data.
Figure
Next, we evaluate the performance of MatrixIRIS (Algorithm D. on the US cities dataset (0020) in comparison the aforementioned algorithms. In this setup, given [Ω]] Euclidean
31

---

distances v - + - Φ,)² and Φs 9j of 2920 cities in the United States, whose squares can be arranged in an incomplete distance matrix D E S, that serves as an input for the reconstruction algorithms. Like the previous setup of Section 5 the set Ω consider different choices of parameterized by the oversampling factor p. Here, for the US cities the rank of the input matrix is 2. In Figure Sa we observe a similar pattern to that Figure 7a for the US cities data. The success probability Figure also shows a similar pattern to that Figure 4
between vectors containing longitude and latitude values X, A3
of point index pairs is sampled uniformly random, and we
Relizive Procnuies liver
0.8
AIM
Succes Prefabiitt
10-4
0.4
Stalec SGD
Heale 3515
10"
2.5
Oversampling
Overampling
The relative Procrustes the algorithms for different (h) The probability for the algorithms for different oversampling rates for US cities data
sampling rates for US citics
Figure 8
We visualize the reconstruction of the US cities data shown in Figure
50
50
40
40
40
120
-100
-80
60
120
100
-80
60
-1200
1000
60
(a)
(b)
(c)
Figure 9: Visualizations of the recovery of US cities data by MatrixIRLS for oversampling rates 1.5, 2.5, 3.5 in 9a
9c respectivlly
In this paper, have adapted the authors' codes of ScaledSGD ZCZ22 ALM [TL88 and Ma
trxIRLS [V2I] from their respective githubs. The code of RicEDG (SLCT23 KV21), has been obtained from the author through personal communication.
E.2 Choice of parameters
MatrixIRLS:
The algorithm is configured with the following options:
The input parameter for MatrixIRLS includes the number of outer IRLS iterations No the number of inner iterations No Noner the tolerance, which is the stopping criteria for algorithm lolo Sumer- For large datasets like the UScities data and Protein data N 400, although the algorithm converges within 120 iterations. We run the experiments with No innerr 2000 and tol = 10 In a smaller setup of the synthetic data perform the experiments with n = 500 points with same parameters. although convergence of MatrixIRLS is observed much faster. To put more emphasis on the per iteration error, study the experiment on per-iterate analysis with more iterations.
Augmented Lagrangian Method: For the Augmented Lagrangian method(ALM) we have same number iterations which is parametrized as No fisstorder for the -Brrliii gradient method in the code. There are 3 stopping criteria for the BB gradient method which are parametrised by xtol. tol and glol on the iterate, functional value of the iterate and the gradient of the function respectively. As mentioned in [TL18), the relative change in
32

---

Energy is the stopping criterion for the algorithm and the tolerance for that measure is set at 10- for our experiments. Similar the above setup, for larger dataset, more iterations are observed so that we can achieve fair comparison between all the algorithms.
Scaled SGD: This method uses the learning rate and the number of iterations No firstorder as the parameters. For all the experiments the value of N firstorder are kept constant across the methods. however, based on the dimension of the input which is n, the iterations are modified achieve fair comparison. The learning is at 0.2, which based on the respective paper (7C722)
Riemmanian Gardient: This method has parameters, number of iterations which is same N firstorder: the thresholding tolerance which has same value as the toler.
E.3 Distance metric
The success of proabbility in the experiments of Section S is with respect to the Procrustes distance. The Procrustes analysis uses similarity transformations like scaling, rotation and maps into a common reference frame [ASVF23)) If we consider our problem, this distance is considered with the ground truth as the reference frame and is defined as
min QeRrxr AER* |Q (Po + tt
Preel|F subject to QTQ=
E,4 Degrees of freedom
We count the degrees of freedom in the spectral decomposition of a rank-r symmetric matrix: A UDU where is an orthogonal matrix and D diagonal matrix consisting of the eigenvalues of A on the diagonal. In U there are total r unit norm constraints and there are total z(r-1) constraints to the orthogonality of the columns vectors of U which follow from (u, Uy) 0 for i + j and i E (1 and j E (1.2....r') r). Therefore, the total number of constraints is r(r- + r(r+1) The total degrees of freedom in D is Hence, the total degrees of freedom of
is:
r(r r(r 1r++1) 1), = nr
r(r
nr (r
2
F Computational Complexity
For a symmetric matrix X E Sn, we write its eigendecomposittin (with magnitude decaying eigenvalues) such that
x= Unl
A LY -
(53)
where U E Raxr U, E (=x(a-r) are matrices with orthonormal columns and A diag(70), yo,) and A dg. 7aa) diagonal matrices with entries X; = 7i7i where a; is the i-th singular value of X and n E (+1} sign. Furthermore, we denote by T,(X) the best
rank-r approximation of which can be written such that
T,(X)
arg min
I
X UAUT.
(54)
Zzrank(Z)
where -| can be any unitarily invariant norm, due to the Eckardt- Young-Mirsky Eckardt-Young-Mee theorem MMr600]
using the established notation.
The computational complexity of Algorithm is dominated by the solution of the weighted least squares problem (5) and the computational of spectral information used in the update of the smoothing
parameter eş of (7) and the weight operator update
(7)
(see also Definition (.1]
For solving (5) we consider detailed in Appendix F. based solving linear system with the
dimensionality tangent space T7,, y.yg The tangent space formulation can be derived from
(6) via the Iitemman-Morrisse Woodbury [Woo50] formula using the weight operator structure.
In order to update the smoothing parameter and the weight operator we compute the SVD of the iterate by approximating top singular vectors and corresponding values following Randomized Block Krylov Methods [MM15]. This computation takes O(((m + nr)r log
33

---

F1
Tangent Space Implementation
Let M, ==
X Sn rank(()) r) the manifold of symmetric rank-r matrices and let X Sn
be as in (53) In this case, given r E N. we can write the tangent space of M, at (X) as
R
R (xx(n-r)
T = (x) UU
R (m--)x
[UU_]
M
M
[UL]" M, E S,,M, E (ex(n-)) arbitrary
(55)
M2 0
( + +
- (--UU") + (I- -U- : E T,, P2 E [R")
U + U +1' :1 E S,,12 g"xr, JU T'T2- 0), 0),
see also [3n [oou20] Chapter 7.5].
If Pr: Sn S,, is the orthogonal projection operator that projects symmetric matrices onto T as used in Theorem 4.3 we note that
( UU XUUT + +UU UU ) + UU UU--UUJXUU)
which can be decomposed such that
Pr XX = (X),
where the action of Pr Rr(a+r) Sn can be described
Pr(1) = UT U + UU +
with 11 E S, being the result of an (r² x 1) to (r x r) reshaping of the first r² coordinates of y and 22 E R=xr the result of an (rn x 1) to (n x r) reshaping of the remaining coordinates of y. Further, we used the notation of the adjoint operator Pt Sn Br(atr) of Pr which maps X E S, to the vectorization y of [1 [ [2] = {UT XU, (I UU XUJ.
Due to the fact that the weight operator Wx W )x of Definition 3.1 associated to the iterate (A) E S, and the smoothing parameter 6 is self- self-adjoint and invertible, we can write its inverse as
W Pr. D Pt. + EL Pry Pia) (r
(56)
where DEL E
a diagonal matrix with entries (x(((( (x) (x), where either or are smaller or equal than see also [K Eq. (12)), and Tr Tr (xc0),Mr is the tangent space at Tr, (x(+)) onto the rank-rk
max( or (X (1),, cx) max(a,
manifold.
Recall from 7
that the the defining equation for the next iterate ( given Wy is
(k+1) = WE A' (AWE" A²) '
y.
(57)
Using (66) we see that
(AW k AA*) = A (Pr, D St Tr + & [I Pr. PT. A = =A (Pr. (D51 Ts.s P+.) A EAA
(58)
and, using the Sherman--oorison-Wonnn -ooddbry (Woo50) formula, we have that
(A(W(()))-A-))
=
2 E (AA')- APT. (6.C + P7 A" (AA")) APT)) A" (AA')-- -APT,
-AA0(A-0)-- -2 -===--A1" (AA'))1 APT, M Pp. (AA')-1
(59)
with linear system matrix M ( (AA')) -APL) noting that C
( is invertible since (D > &x for all diagonal indices. The observation of (59) can be turned an efficient implementation of the weighted least squares computing ((++1), which is
presented in Algorithm 2 It can shown that Algorithm 2 indeed computes X ((++)) implicitly, cf.
Lemma I We omit its proof, which follows the proof of [V2[ Lemma A.1].
34

---

Algorithm 2 Tangent space implementation of weighted least squares step in Algorithm
Input: Set Q2 observation distances D (dg) (i.))n singular vectors E R x
v(k) Ruxr and singular values o(M) Oth smoothing parameter ej. projection
(0)
%
Pr. Pri. (7R-1) E (Raa(ntre) of solution - E gra-i( of linear system (60) for previous iteration k - 1.
1: Compute hy := PTy A (AA")-* - (2 (D 2 - + Pñ A' (AAr) -PT, %k Brr(ntra)
2: Solve
M h2
(60)
for ArA Sx by the conjugate gradient method HS52 Meu06], where
M = o (D - -e1 + P7 A" (AA)) APT.
3: Compute 7% = 7% + Ykk.
(0)
4: Compute residual r == (AA')- (y APTr (7x) ER"
Output: rk+1 E t and 7 T (n+rr))
Lemma F.1. If E RR" and 7k (R((((ru)) is the output of Algorithm (6) of Algorithm fulfills
then X (k+1) as in step
(k+1) (rk++) + Pr. (7k)
= Ar*(ra+)) + UT + +T
where I'1 E 1R is the matricization of the first rž elements of and I12 E ax the matriciza- tion of the reamining elements.
Algorithm 3 Implementation UT A m R
Input: Input vector = [/1, 92, .... Bm J. Ω (ie.)0 C. I be a multiset of double indices.
S >m
Ei=:(iie))e for same yee, T
S, = m
10 for some Vieje c
S3 = Zm (ieeiteee
S S + S2 SS -ST
saved as sparse matrix.
V1 = U S
> 4rm flops. rm flops.
V2 T yym+l, Vntea T 1
V3 = T . 1m ... bm+n]
>> 2rn flops
V V1 V2 + V
Output: V
Total of rm + 3rn flops.
Algorithm 4 Implementation of AAA" B mm
Input: Q (ir C I be a multiset of double indices fulfilling m L nnn 1)/2 that are sampled independently with replacement, the vector = [1,, U2, ..... Vm++n)-
Load S from Algorithm
3 which computes A (y).
) T2 = [e]] Se,, m
T. Sc;,
(= Jien for s
1:(6.de) so
Tg (e), Se je E0
T3 Ti T2 T2 - TJ
b 4m + 2n flops
avg 1 [-m+n
D flops
Tg = [0m+1 + avg. Vntn + avg]
D n flops
Output: [T;: Tol
Total of 4m + 4n flops
35

---

Algorithm 5 Implementation P7.A" R R((ntt)
Input: Input vector y (11, 1/, m... Vm+a] Rm+* index set Q left singular vector matrix
U RTxr.
A = VE R"x" from Algorithm
> O(r(m + +)) flops
T E Rexr.
b Or) flops
M T ER
b O(r2) flops
T2 [A] M
Output: (Tı,
Lemma F.1 shows that an iterate X (k++) can be represented via only m + T 12 ra) parameters. In the remainder of this discussion, we will assume that ri = r, which the case in most cases in practice if the rank estimate F of Algorithm is chosen f == r.
To quantify the computational cost of Algorithm we assume fixed number No Ninner of CG iterations (60) When applying the system matrix M via matrix-vector multplication, we observe that its first summand ei (Dr² I diagonal and thus results in Orr(n + +r) flops per CG iteration. A² (AA*)= API. we define below algorithms that efficiently implement the application of the operators PiAA" :R*+n Rr(x+)) (Algorithm 5) AA" R= m== (Algorithm 4 and APr (R(())) > B=
To quantify the matrix-vector multiplication cost of its second summand PT,
(Algorithm 60. As auxiliary function, we also provide an implementation of U A R R (Algorithm below.
The application of (ALA")-1 1m + m can be achieved by an inexact iterative solver that applies Algorithm 4 a fixed number N of iterations, which costs O((m + n)N). Since the time complexity of Algorithm 5 and Algorithm are O(r2n + rmm), we obtain one matrix vector multiplication with M from Algorithm 2 a time complexity of O + rm + (m++))
Since No ozner CG iterations used, we obtain total time complexity of O(N (oner ( rmm+ (m+ N)) for Algorithm 2 In our experiments, we observe that a small number N 10 of iterations for solving the system associated to (AA*) is sufficient to obtain high-accuracy solutions.
This breakdown of the computational costs of each algorithm is shown in Algorithm
to Algorithm 0
Algorithm Implementation .AP Rr(n+r) -> m++
Input: (Ti,Ta) [2]. index set Ω2 left singular vectors U Raxr M T T E Rexn
D O(P2) flops from Algorithm
z = EΣk= U (M.))) (L.c)E for some
((mr) flops
+ ( 1 Kg M (RA (Gr some
((r)) flops
2 1= k ((kie) ) (tude)e
((Tr) flops
C E== ag (M (R e (Eede)e
O(mr) flops
a C Σ U (1 (( (lee) for forsome
O(mr) flops
a = a +
Un (T) (Kajee) (1 some
0(mr) flops
a = &
1 U (T) ((K.s)) (erd)en
0(mr flops
a =
1==10 Ck=(UU) (U) (T Desy (n
0(mr) flops
Ç = Z 2a.
(> =
n
U ((,))
O(rr) flops
= M
O(mr) flops
f/ = I
b
O(mr) flops
C2 (EE (T (T2)
O(rr) flops
73 c2 UT
O(mr) flops
G = + +
Output: [(1
36

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Main claims of the paper weaved in Abstract and Introduction. There is separate subsection in the Introduction dedicated to discuss the contributions of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
In the Appendix B of this paper, we mention the limitation of this paper.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer:[Yes)
37

---

Every lemma/ theorems stated in the paper (Section and appendices C and D include the assumptions in the respective statements.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: The related link to the anonymized Github respository is provided in the Appendix D
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
38

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
All references of code and reference code provided in the paper. [TODO]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://niis.co cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ ccippi.cc/pulli///grg guwdes/ddeeeee CooeeSumeeieeeeeeeeeee ssi onyolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: Experimental details are provided in Section 5 and discussion on the choice of parameters is provided in the Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper reperreport error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:[
Justification: In the Section 5 the experiments are performed on multiple independant
realizations and respective boxplots of error are shown in Appendix E provide statistical significance of the experiments.
All the figures
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
39

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
Question:
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: The experiements were performed on single node of compute cluster
equipped with dual 24-core Intel Xeon Gold 6248R CPUs, utilizing 32 parallel tasks.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question:
Does the research conducted the paper conform, in every respect, with the http://pww....ppooooo//cccceaaaa
NeurlPS Code of Ethics
Answer: [Yes]
Justification: [TODO]
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: In the introduction and in related work we highlight the impac the work. These provide foundational algorithmic research to reconstruction algorithms which has applications in molecular conformation, sensor network localization. There is no potential negative docial impact of this work.
40

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., denloymemt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The paper uses data that are publicly available. The data sources are cited properly in Section
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer:[Yes]
Throughout the paper we cite the different information that we used from the existing literature. Additionally, in the Appendix E. provide links to the Github repositories that we used for reference.
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
41

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The link to the anonymized version of the repository containing our experi- ments have been provided in Appendix E
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mmodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: NA
Justification:
The paper does not involve crowdsourcing nor research with human subjects.r
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [TODO]
Guidelines:
42

---

The answer NA means that the paper does not involve crowdsoureing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
43


Reviews:
[{"review_id": "xUpgjrsEws", "reviewer": "Reviewer_rCFC", "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.", "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?\n* Are there applicable downstream machine learning/deep learning applications that require this kind of point recovery, where improved results could be further demonstrated?", "limitations": "The authors address the limitations of their work in detail in the paper, and there are no societal impacts to be addressed.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "* Provides the first theoretical convergence guarantee at the optimal amount of samples for the studied pairwise distance problem under non-convex optimization. \n* Performance comparable to state of the art methods are demonstrated on \n* The method converges quickly and effectively even for ill-conditioned matrices, where previous state of the art methods fail. \n* Detailed theoretical derivations and proofs. \n* 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. \n* 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your constructive reviews our submission. We address your questions below.\n\n> 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?\n\nWe did not include runtime comparisons for this molecular confirmation problem in the submission as the respective protein geometries can be executed in an offline manner. However, we agree that despite of this, it is important that the algorithmic runtime does not become prohibitive for relevant problem instances. We have provided in Table 1 in the attached PDF the reported reconstruction times for each of the four algorithms applied to the 1BPM Protein data of Subsection 5.3 (with $n=3672$ datapoints) in a low-data regime with oversampling factor of $\\rho=3$. \n\nIt can be seen that MatrixIRLS is with $7.08$ minutes around $3$ times faster than ALM, which needed $23.4$ minutes until convergence. While these times certainly depend on the precise choice of stopping criteria for each algorithm (we used the ones indicated in Appendix E.2), this shows that the proposed method is competitive in terms of clock time (we also note that we obtain a considerably higher accuracy solution in this time than ALM). \nWe will include such a comparison in the final version of the paper.\n\n> Are there applicable downstream machine learning/deep learning applications that require this kind of point recovery, where improved results could be further demonstrated?\n\nIn the introduction of the manuscript, we have outlined a possible pathway for including Euclidean geometry reconstruction algorithms such the method presented into a protein structure prediction pipeline as used by AlphaFold 1-3. In particular, it could be possible to obtain a subset of high-confidence distance predictions by, e.g., a Transformer architecture, which could be combined with a MatrixIRLS-type geometry reconstruction to improve overall performance. Testing this was beyond the scope of this work due to the complexity of the overall pipeline.\nFurthermore, related reconstruction problems can be used to obtain faster word embeddings in natural language processing, see for example the paper [\"Distance geometry for word representations and applications\" by Khalife et al., Journal of Computational Mathematics and Data Science 6 (2023)]. Improvements could be demonstrated if favorable tradeoffs between computational complexity and downstream accuracy of MatrixIRLS-based tokenizers could be observed compared to non-distance geometry based tokenizers.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XG0Ik1qAKc", "reviewer": "Reviewer_wbRb", "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.", "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.\n\n2.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?\n\n3.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?\n\n4.Will the results of the MatrixIRLS method converge to the same solution as MDS when there is no incomplete information?\n\n*Small suggestions:*\n\n1.The linewidth and point size is too large in Figs. 2, 6(b), and 7(b).\n\n2.No captions in Figs. 6 and 7.\n\n3.Mixed use of fig. and Figure.\n\n4.Some typos: \n\nLine 52: should satisfy also satsify\n\nLine 813: figure Figure", "limitations": "It would be beneficial to include the scalability limitations, such as the maximum problem size that can be solved.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "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.\n\n2. 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.\n\n3. The paper is well-structured and clearly written, making complex mathematical concepts accessible. The detailed algorithmic steps enhance understanding.\n\n4. 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.\n\n2. 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.\n\n3. The paper provides a local convergence guarantee, but a more detailed discussion on the global convergence properties of the algorithm would be beneficial.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your constructive and very detailed feedback to our submission. A point-by-point response and clarification regarding your comments follows below.\n\n**Weaknesses**\n\n> 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.\n\nWe tried to be as comprehensive as reasonably possible in our experimental evaluation, including relevant methods ScaledSGD [ZCZ22] and RieEDG [SLCT23], the latter of which was very recently presented at a NeurIPS 2023 workshop. Another Riemannian method, which comes with an interesting theoretical analysis, was publicly available only in March 2024 [LS24]. Unfortunately, the authors of [LS24] do not provide a publicly available implementation, which made it not possible for us to reimplement their method and include fair algorithmic comparisons at short notice. For this reason, we contend that our evaluations are fair and comprehensive. We are open to suggestions for further methods to compare with.\n\n> 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.\n\nWe conducted additional experiments exploring the empirical performance of the considered algorithms in the case of ill-conditioned ground truth Gram matrices with $\\kappa = 10^5$, considering now also $n=500$ and different choices of $r \\in \\{2,3,4,5\\}$ as in the setting of Figure 1 of the submitted manuscript (Gaussian ground truth) and different oversampling factors $\\rho$. The results can be found in Figure 1 of the attached PDF. It can be observed that RieEDG and ScaledSGD struggle considerably in this setting. On the other hand, the significant advantage of MatrixIRLS compared to ALM (reconstruction already with $\\rho=1.5$ vs. with $\\rho=2$ for MatrixIRLS vs. ALM) remains consistent for these different parameter choices. We also refer to our reply to your Question 1 for another robustness experiment.\n\n> 3. The paper provides a local convergence guarantee, but a more detailed discussion on the global convergence properties of the algorithm would be beneficial.\n\nWe refer to our reply to a similar question of Reviewer fWZw below.\n\n**Questions**\n\n> 1. How sensitive is the proposed algorithm to the choice of parameters, such as rank estimate in the IRLS framework? Guidelines or heuristics [...] for parameter selection?\n\nThank you for suggesting this insightful experiment. In order to compare the robustness with respect to the choice of the rank estimate (called $\\tilde{r}$ for MatrixIRLS) for each of the four considered algorithms, we ran experiments over $8$ independent instances where the underlying rank estimate provided in the algorithm ($\\tilde{r}$) is different from the actual rank ($r$) of the problem. For $n = 500$ and $r=5$ in a setup as in Figure 1 of the submission, we report in Figure 2 of the attached PDF that the median recovery error of MatrixIRLS only slightly deteriorates for $\\tilde{r} \\in \\{6,7, 10\\}$, and has a slight robustness advantage compared to ALM, whereas RieEDG performs significantly worse. None of the algorithms succeeds if $\\tilde{r}< r$ is chosen.\n\nIn many geometry reconstruction problems, however, there is a natural rank estimate choice based on the dimension of the geometry (e.g., $r=3$ for 3D problems), which makes $\\tilde{r}$ easy to choose. If the dimensionality of the points to be embedded is not known, our experience suggests that when in doubt, a slightly higher $\\tilde{r}$ than the true dimension (up to factor $2$ overestimation) will still lead to good results.  \n\n> 2. 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? [...] Considering the success probability, ALM performs better than MatrixIRLS. Could you explain the potential reasons for this discrepancy?\n\nThe large standard deviation of MatrixIRLS in that experiment for $\\rho \\in [2.5,3]$ is due to the phenomenon that due to the randomness in the sampling pattern, MatrixIRLS sometimes does not converge to a meaningful ground truth, whereas it converges to very high precision in other cases. ALM exhibits a similar phenomenon, albeit already for smaller $\\rho$ and which less pronounced standard deviation due to lower precision solutions. We do not have a final explanation of why ALM performs slightly better for smaller $\\rho$ in this setting. One possible reason could be the large coherence $\\nu$ of the ground truth in this real data setting considered, in which case Theorem 4.3 would be compatible with the need of more samples for successful reconstruction.\n\n> 3. Time complexity of the MatrixIRLS  $O(n^3)$ due to SVD? Maximal problem size to be solved via MatrixIRLS within an hour?\n\nThank you for pointing out the omission of the computational discussion of Step 7. We would like to stress that it is _not_ true that we need full SVDs for the weight operator update step, but only the $r_k$ singular triplets. Based on the update rule for the smoothing $\\epsilon$, it holds that $r_k \\geq \\tilde{r}$, but in many cases, empirically, $r_k$ coincides with $\\tilde{r}$ throughout the algorithm. For this reason, we used a fast partial SVD method based on a randomized block Krylov iteration whose runtime scale as $O(C r_k log(n))$ [Musco & Musco 2015], where $C$ is the cost of a matrix-vector multiplication involving the matrix to be decomposed. Since we can use a \"tangent space + sparse\" representation of each iterate $X^{(k)}$ to which we apply this, which comes with a matrix-vector multiplication cost of $C= O(r_k n+ r_k^2 + m r_k)$, the cost of Step 7 is essentially linear in $n$. We refer to our global response for the maximal problem size question.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "E0sIs3W0lS", "reviewer": "Reviewer_Jqjh", "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.", "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? \n\nIn 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?  \n\nThe concept of a nu-incoherent matrix appears in Theorems 4.2, 4.5 without earlier explanations. What are these matrices?\n\nThe 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?\n \nThe 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?\n\nIn 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?\n\nLines 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?\n\nLines 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?\n\nThe 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.", "limitations": "This submission seems an incremental improvement of the past work [KV21] with little comparison between the two papers.", "rating": 4, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "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. \n\nProblem 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. \n\nMore 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughts about our submission. Please consider our responses regarding your  assessment:\n\n> (Meaningfulness of rank min. for Problem 1)\n\nAssuming the points matrix $P$ has rank $r$, it follows that the Gram matrix also has rank $r$. When $n \\gg r$, this implies that the rank of the Gram matrix is small. This observation is the motivation behind minimizing the rank. As you noted, directly solving (1) is challenging.  Instead of solving (1) directly, we discuss convex approaches that use a convex surrogate for rank, which are more suitable for optimization. However, these polynomial-time methods are not scalable for large problems. Our proposed method avoids explicitly minimizing the rank and, under the assumptions of our theory, recovers the optimal solution of (1).\nFinally, we would like to mention that a number of prior works derive effective algorithms based on other relaxations of rank minimization.\n\n> \"The rank minimization in (1) and algorithm MatrixILRS appeared under the same name but with slightly different notations in the earlier paper [KV21].\"\n\nIn our manuscript, we clearly mention that the proof strategy is inspired by the paper [KV21], in which a similar algorithm was proposed for low-rank matrix completion (LRMC). However, the considered EDG setup is more challenging due to the non-orthogonality of the sampling basis, which we overcome via Thm. 4.5, which is one reason why guarantees for any non-convex method have not been previously available in the literature.\n\n\n> (Motivation of rank-min for P1) \n\nConsider a quadrilateral with vertices located at $p_1=(-1,1)$, $p_2=(1,2)$, $p_3=(1,-2)$, and $p_4=(-1,-1)$. We know the lengths of the sides but not the length of the diagonals. Ignoring rank minimization, this problem can be formulated as an SDP feasibility problem using the relations $X_{i,i}+X_{j,j}-X_{i,j}=D_{i,j}$ where {(i,j)} are the indices corresponding to the available entries of the distance matrix. Solving this using CVX yields the rank $4$ matrix\n$$\nX=\n\\begin{pmatrix}\n 1.431  &  0.431 &   -1.294 &   -0.569\\\\\\\\\n 0.431 &   4.431 &   -3.569 &   -1.294\\\\\\\\\n -1.294 &  -3.569 &    4.431 &  0.431\\\\\\\\\n -0.569 &  -1.294 &    0.431 &   1.431\\\\\\\\\n\\end{pmatrix}\n$$\nThis example illustrates that, when distances are missing, the feasibility problem can admit higher rank solutions i.e., it is \"easier\" to satisfy the distance constraints in higher dimensions. To find low-rank solutions, we can employ approaches that are based on factorizing the Gram matrix as $PP^T$. Doing so for this problem, with rank=2, yields\n$$\n\\begin{pmatrix}\n 1 &  0 &   0 &  -1\\\\\\\\\n 0 &  4 &  -4 &   0\\\\\\\\\n 0 & -4 &   4 &   0\\\\\\\\\n-1 &  0 &   0 &   1\n\\end{pmatrix}\n$$\nThis not the true Gram matrix, but it satisfies the given distance constraints, indicating that no unique solution to P1 exists. However, if we assume the distance between \\(p_1\\) and \\(p_3\\) is known and restrict the rank to 2, then among various initializations, the one with the lowest objective function accurately identifies the underlying quadrilateral up to rigid motion and translation.\n> \"In Def $3.2$...\"\n\nYes, $w_{\\alpha}$ is a matrix of size $n\\times n$. The measurement operator is based on the trace inner product \n$\n\\langle w_{\\alpha_l}, X \\rangle =  \\sum_{i,j}    w_{\\alpha_l}(i,j) X(i,j)\n$.\n> (coherence $\\nu$)\n\nWe have introduced the notion of coherence in the Definition 4.1, the $\\nu$-incoherent matrices in Theorem 4.2 and 4.5 refer to those matrices which have a coherence of $\\nu$ (Definition 4.1). We will add an appropriate reference to earlier occurrences of this notion.\n> (Prob. space)\n\nWe use the probability space with the discrete sample space of all subsets of cardinality m of the set if integers between $1$ and $n(n-1)/2$, equipped with the uniform distribution (sampling without replacement). The probability lower bound for the statement is $1-\\frac{2}{n^{2}}$ (see proof of Thm. 4.3).\n>\"In Theorem 4.3, can mu be large enough...\"\n\nNo, the initialization condition on the $k$-th iterate $X^{(k)}$ is formulated such that in the statement of Thm. 4.3, the inequality you are referring to will be strict (cf. the proof in Appendix D), given the specific value of $\\mu$. For the Gaussian experiment for Figure 5, in the case of $r=5$ and $\\rho=2$, for example, the resulting value will be $\\mu \\approx 2.56\\cdot 10^{6}$. This leads to a relatively small theoretically certified \"basin of quadratic convergence\" if one wants to apply Thm 4.3. with the constants provided. However, we note that, first, Thm 4.3 is unique in the literature for this problem as it applies for the minimal sample complexity of $O(\\nu n r log(n))$.\n>\"Lines 251-252 say that \"an adaptation ...\"\n\nConsider the expansion of a low-rank matrix \\(X\\) in an orthogonal basis \\(\\{w_{\\alpha}\\}\\): \n$$\nX = \\sum_{\\alpha} \\langle X, w_{\\alpha} \\rangle w_{\\alpha}.\n$$\nThe standard low-rank matrix recovery analysis can be reformulated as the problem of finding a low-rank matrix given a few of the expansion coefficients $\\{\\langle X, w_{\\alpha} \\rangle\\}$. In contrast, in the EDG setting, the natural basis considered is no longer orthogonal, making the above expansion invalid. The proof approach relies on a dual basis expansion, and the specific challenging steps involve showing bounds related to a modified sampling operator. These bounds depend on the linear-algebraic properties of the basis and the dual basis.\n> \"The biggest concern is line 82 saying...\"\n\nAs the reviewer points out, not every random symmetric matrix corresponds to a set of points; positive definiteness is required to realize such points. Under the assumptions of our main theorem, the proposed algorithm converges to the true Gram matrix of rank \n$r$, which is both symmetric and positive definite. We then obtain the configuration of the points through an r-truncated eigendecomposition.\n\nWe would appreciate if you consider raising your rating if we resolved your concerns. Thank you!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EpoIqtC9iS", "reviewer": "Reviewer_fWZw", "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.", "questions": "1.\tThere are some vertical space issues, like Line 286 for Section 5. \n2.\tCan the authors briefly discuss the main challenges for global convergence?", "limitations": "Discussed in the supplementary material. I suspect the file in the supplementary zip file should be the main submitted file.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "The related work is discussed comprehensively. The method and theory seem solid. Experiments are convincing.", "weaknesses": "1.\tThere are quite a few typos or undefined notation that make some of the paragraphs hard to read. For example:\n\n  a.\tLine 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).\n\n  b.\tLine 158, $\\sigma_i(\\cdot)$ is not defined, tho I can guess the meaning.\n\n  c.\tLine 165: $X^{(k)}$ should be $X$. \n\n  d.\tEq (5) gives the update from k to k+1, while Eq (6) gives the rule from k-1 to k.\n\n  e.\tEq(9), at the end, there is a missing comma.\n\n2.\tFigure 2 looks great, but it will be even better if we can observe the claimed rate $O(\\nu rn\\log n)$ empirically.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your careful feedback.\n\nWe appreciate your pointers regarding typos and your presentation suggestions. We will refer to the definition of the coherence $\\nu$ at the first occurrence in the paper.\n\n> Figure 2 looks great, but it will be even better if we can observe the claimed rate $O(\\nu r n \\log(n))$  empirically.\n\nThank you for the feedback. We would like to mention that even for related, simpler problems such as the low-rank matrix completion problem, there is little empirical exploration of a related sample complexity phase transition available for any algorithm (only for the more generic Gaussian measurements, such an analysis was done in [Donoho, Gavish, Montanari, PNAS 2013]. The sample complexity order of $O(\\nu r n \\log(n))$ should be seen as a sharp worst-case bound, but both in practice as well as for our data generation protocols (Gaussian or ill-conditioned data), it is unclear if this dependence on factors $\\log(n)$ or coherence parameter $\\nu$ is visible in reconstruction experiments. Since we defined the oversampling factor $\\rho = m / (n r - r*(r-1)/2)$ as quotient between sample number $m$ and the degrees of freedom of a rank-r p.s.d. matrix, a success rate of $100%$ for $n=500$, $r=5$ at $\\rho = 2$ for MatrixIRLS (see Figure 1) shows that recovery is well possible at $m = 4980 < 15537 \\approx n r \\log(n) \\leq \\nu n r \\log(n)$ (it always holds that $\\nu \\geq 1$) in many cases.\n\n> Can the authors briefly discuss the main challenges for global convergence?\n\nA major challenge for the global convergence theory of the proposed method is that main theorem, Thm. 4.3, applies only if the method is initialized close enough to the ground truth. The theory of similar IRLS algorithms for other problems (see papers [DDFG10,MF10,KV21]) shares this limitation, and therefore is not unique to our method. The challenge for applying classical optimization theory tools to the proposed scheme is rooted in the non-convexity of the (smoothed) log-det objective as well as in the non-constant smoothing: While MatrixIRLS can be considered as a descent method due to a majorization property of the quadratic function implicitly defined by the weight operator with respect to the $\\epsilon$-smoothed log-det objective, the $\\epsilon$-smoothing _changes_ at each iteration (cf. Algorithm 1), which slightly changes the underlying functional to be minimized at each iteration. Obtaining a global convergence statement for a scheme like Algorithm 1 would therefore constitute solving a major open problem in the theory of \"non-convex\" IRLS algorithms.\n\n\nIf we were able to adequately address your concerns, we kindly would ask you to consider adjusting your rating accordingly. Thank you!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We appreciate the reviewers' constructive and very detailed feedback to our submission. A point-by-point response and clarification regarding their comments have been addressed separately to each reviewer, however, we highlight some key points below, many of which are supported by additional experiments whose results can be seen in the attached PDF.

**Runtime on Real Data and Scalability**

Certainly, it is important that the algorithmic runtime does not become prohibitive for relevant problem instances. We have provided in Table 1 in the attached PDF the reported reconstruction times for each of the four algorithms applied to the 1BPM Protein data of Subsection 5.3 (with $n=3672$ datapoints) in a low-data regime with oversampling factor of $\rho=3$. 

It can be seen that MatrixIRLS is with $7.08$ minutes around $3$ times faster than ALM, which needed $23.4$ minutes until convergence. While these times certainly depend on the precise choice of stopping criteria for each algorithm (we used the ones indicated in Appendix E.2), this shows that the proposed method is competitive in terms of clock time.
In order to understand the scalability of the proposed algorithm, we have provided the time of completion of MatrixIRLS in the table Table 2. The first two rows shows that if we fixed the oversampling factor($\rho$) as $3$, then we are able to recover the points in the magnitude of $10^4$, is just $13.7$ minutes. So to further test the scalability, we also looked at the time to completion when less number of samples are provided ($\rho = 2.5$). In that setup $n = 10000$ takes $57.5$ minutes to recover with high precision. We will include such a comparison in the final version of the paper.

**Robustness to Parameter Choices**

 In order to compare the robustness with respect to the choice of the rank estimate (called $\tilde{r}$ for MatrixIRLS) for each of the four considered algorithms, we ran experiments over $8$ independent instances where the underlying rank estimate provided in the algorithm ($\tilde{r}$) is different from the actual rank ($r$) of the problem. For $n = 500$ and $r=5$ in a setup as in Figure 1 of the submission, we report in Figure 2 of the attached PDF that the median recovery error of MatrixIRLS only slightly deteriorates for $\tilde{r} \in \{6,7, 10\}$, and has a slight robustness advantage compared to ALM, whereas RieEDG performs significantly worse. None of the algorithms succeeds if $\tilde{r}< r$ is chosen.

In many geometry reconstruction problems, however, there is a natural rank estimate choice based on the dimension of the geometry ($r=2$ for 2D problems, $r=3$ for 3D problems), which makes $\tilde{r}$ easy to choose. If the dimensionality of the points to be embedded is not known, our experience suggests that when in doubt, a slightly higher $\tilde{r}$ than the true dimension (up to factor $2$ overestimation) will still lead to good results.  

We conducted additional experiments exploring the empirical performance of the considered algorithms in the case of ill-conditioned ground truth Gram matrices with $\kappa = 10^5$, considering now also $n=500$ and different choices of $r \in \{2,3,4,5\}$ as in the setting of Figure 1 of the submitted manuscript (Gaussian ground truth) and different oversampling factors $\rho$. The results can be found in Figure 1 of the attached PDF. It can be observed that RieEDG and ScaledSGD struggle considerably in this setting, necessitating more than $\rho= 3.5$ for reasonable reconstruction rates. On the other hand, the significant advantage of MatrixIRLS compared to ALM (reconstruction already with $\rho=1.5$ vs. with $\rho=2$ for MatrixIRLS vs. ALM) remains consistent for these different parameter choices.

**Challenges for Global Convergence**

A major challenge for the global convergence theory of the proposed method is that main theorem, Thm. 4.3, applies only if the method is initialized close enough to the ground truth. The theory of similar IRLS algorithms for other problems (see papers [DDFG10,MF10,KV21]) shares this limitation, and therefore is not unique to our method. The challenge for applying classical optimization theory tools to the proposed scheme is rooted in the non-convexity of the (smoothed) log-det objective as well as in the non-constant smoothing (see reply to Reviewer fWZw for more details, as well as the discussion about the choice of $\mu$ in reply to Reviewer Jqjh).

--------
Due to lack of space, we provide below also an answer to one of the questions of Reviewer Jqjh:
> "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?"

Thank you for pointing this out. Rigid motions and translation preserve the distance matrix of an underlying set of points. In contrast, scaling does not. Given that, we only consider the Procrustes analysis without uniform scaling to remain consistent with the problem formulation. If we differentiate the objective with respect to the translation and find the closed form of the optimal translation as a function of the rotation, it can be shown that this optimal objective, for any choice of rotation, is equivalent to an objective whereby we first center the points at the origin. Specifically, we can equivalently consider the objective
$$ 
\underset{Q}{\min} ||QX_c-Y_c||_F,
 $$
where $X_c$ and $Y_c$ are centered at the origin. In terms of computation, the Procrustes analysis involves the SVD of a matrix of size $r \times r$ that costs $O(r^3)$, and matrix multiplication that costs $O(nr^2)$. Hence, the complexity is linear in the number of points.

Meta-review: The submission studies the recovery of a low-rank Euclidean distance matrix from a subset of its entries. This problem has applications in sensor positioning, protein folding, and related areas. The paper studies an iterative reweighed least squares algorithm, which solves a sequence of weighted least squares completion problems. It proves that this method converges locally, with a linear rate. In particular, if the observed distances are sampled uniformly at random, and the number of observations is at least n r log n times the coherence of the target matrix, then IRLS converges linearly within a certain schatten-infinity neighborhood of the truth. In experiments, the IRLS approach shows advantages in handling ill-conditioned data — a challenging case for nonconvex factorization-type methods. 

Reviewers produced a generally positive evaluation of the paper: while there has been quite a bit of theoretical work on nonconvex low-rank recovery, including analyses of both factorization and iterative least squares methods, the paper has novelty within the literature on nonconvex *euclidean distance matrix* reconstruction. The paper is crisply written. The main limitation of the theory is that it does not comprise a complete recovery result, since convergence is local in nature. One device for achieving a recovery result is to couple the local analysis with spectral initialization; doing so would help to contextualize the convergence guarantee (i.e., is the radius large enough to ensure near optimal sample complexity for this hybrid method). Overall, the problem makes a solid contribution to the literature on nonconvex low-rank recovery.
Decision: Accept (poster)