pith. sign in

arxiv: 2508.00091 · v3 · submitted 2025-07-31 · 🧮 math.OC · cs.CG· cs.LG

Provable Non-Convex Euclidean Distance Matrix Completion: Geometry, Reconstruction, and Robustness

Chandler Smith , HanQin Cai , Abiy Tasissa This is my paper

Pith reviewed 2026-05-19 01:29 UTC · model grok-4.3

classification 🧮 math.OC cs.CGcs.LG
keywords euclidean distance matrix completionriemannian optimizationlow-rank matrix completionrestricted isometry propertynon-convex optimizationsensor network localizationmolecular conformation
0
0 comments X

The pith

Riemannian gradient descent on rank-r Gram matrices recovers point configurations from partial distances with linear convergence when sampling exceeds a bound set by incoherence and rank.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper tackles recovering point positions from incomplete pairwise distances by recasting the task as low-rank completion of the associated Gram matrix. Optimization proceeds via Riemannian gradient descent directly on the manifold of fixed-rank positive semidefinite matrices. The main theorem establishes local linear convergence with high probability under a Bernoulli observation model once the sampling probability reaches order nu squared times r squared log n over n, where nu captures an EDMC-specific notion of incoherence. A separate one-step hard-thresholding initialization is shown to succeed at a milder sampling rate of order nu r to the three-halves times log to the three-fourths n over n to the one-fourth. The analysis centers on verifying a restricted isometry property for the symmetric linear operator that encodes the distance measurements through a non-orthogonal dual basis expansion.

Core claim

By encoding observed distances as expansion coefficients in a non-orthogonal basis and optimizing over the space of rank-r Gram matrices, the authors show that Riemannian gradient descent converges linearly to the true low-rank solution with high probability, provided the sampling probability p satisfies p ≥ O(ν² r² log(n)/n). This holds under a Bernoulli model for which distances are observed. The proof relies on establishing a restricted isometry property for the associated symmetric linear operator through analysis of a second-order degenerate U-statistic. Initialization via one-step hard thresholding succeeds under the milder condition p ≥ O(ν r^{3/2} log^{3/4}(n)/n^{1/4}).

What carries the argument

Riemannian gradient descent on the manifold of rank-r positive semidefinite matrices, with the central analytic step being the restricted isometry property of the symmetric linear operator induced by the dual basis expansion of the observed distances.

Load-bearing premise

The true point configuration produces a Gram matrix that is exactly rank-r and whose incoherence parameter with respect to the distance operator remains bounded.

What would settle it

A configuration of points whose Gram matrix is exactly rank-r with bounded incoherence, yet Riemannian gradient descent fails to converge to the correct solution even when distances are observed at a probability meeting or exceeding the stated bound.

Figures

Figures reproduced from arXiv: 2508.00091 by Abiy Tasissa, Chandler Smith, HanQin Cai.

Figure 1
Figure 1. Figure 1: Visualizing the rows of U that lead to the lowest incoherence parameter. Next, we aim to state the incoherence condition in terms of the points. Using (13) and noting the relation in (3), and recalling that X = UΛU ⊤ with matrix Λ := diag (λ1 · · · λr), ui = Λ−1/2pi . Note that classical MDS only recovers a point cloud up to rotation, and that the vectors pi referred to here are those recovered through MDS… view at source ↗
Figure 2
Figure 2. Figure 2: Example of a set of points with the highest incoherence parameter. [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 8.6
Figure 8.6. Figure 8.6: 1 in [56]). 5 Theoretical Analysis In this section, we will provide the main results of this work, which are the local convergence and recovery guarantees for Algorithm 1, presented in Theorems 5.4 and 5.6. Prior to this, we formally state our incoherence assumptions, expanding upon the assumption first described in Section 3: Assumption 5.1 (Incoherence assumption). Let X ∈ R n×n be a rank-r matrix with… view at source ↗
Figure 3
Figure 3. Figure 3: This diagram is a schematic of the overall proof of convergence for Algorithm [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Reconstruction of the synthetic datasets referenced in Table [PITH_FULL_IMAGE:figures/full_fig_p020_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Oversampling ratio ρ versus dimension r for 100 points on the uniform distribution on S r−1 . Each parameter was tested 100 times. -2 -1.8 -1.6 -1.4 -1.2 -1 Noise Exponent (log10( )) 1 1.5 2 2.5 3 3.5 4 4.5 5 Oversampling Rate 0 50 100 150 200 250 300 350 400 450 500 [PITH_FULL_IMAGE:figures/full_fig_p021_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Oversampling ratio ρ versus noise level 10γ for 100 points drawn i.i.d. from Unif(S 2 ). Each parameter was tested 500 times. ratio ρ ∈ [1, 5]. We set the success threshold at 10−2 relative difference, a relaxed value from previous experiments due to the addition of noise [PITH_FULL_IMAGE:figures/full_fig_p021_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: A diagram of a simple first-order retraction method on [PITH_FULL_IMAGE:figures/full_fig_p055_7.png] view at source ↗
read the original abstract

The problem of recovering the configuration of points from their partial pairwise distances, referred to as the Euclidean Distance Matrix Completion (EDMC) problem, arises in a broad range of applications, including sensor network localization, molecular conformation, and manifold learning. In this paper, we propose a Riemannian optimization framework for solving the EDMC problem by formulating it as a low-rank matrix completion task over the space of positive semi-definite Gram matrices. The available distance measurements are encoded as expansion coefficients in a non-orthogonal basis, and optimization over the Gram matrix implicitly enforces geometric consistency through nonnegativity and the triangle inequality, a structure inherited from classical multidimensional scaling. Under a Bernoulli sampling model for observed distances, we prove that Riemannian gradient descent on the manifold of rank-$r$ matrices locally converges linearly with high probability when the sampling probability satisfies $p\geq O(\nu^2 r^2\log(n)/n)$, where $\nu$ is an EDMC-specific incoherence parameter. Furthermore, we provide an initialization candidate using a one-step hard thresholding procedure that yields convergence, provided the sampling probability satisfies $p \geq O(\nu r^{3/2}\log^{3/4}(n)/n^{1/4})$. A key technical contribution of this work is the analysis of a symmetric linear operator arising from a dual basis expansion in the non-orthogonal basis, which requires analysis of a second order degenerate U-statistic to establish an optimal restricted isometry property in the presence of coupled terms. Empirical evaluations on synthetic data demonstrate that our algorithm achieves competitive performance relative to state-of-the-art methods. Moreover, we provide a geometric interpretation of matrix incoherence tailored to the EDMC setting and provide robustness guarantees for our method.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper formulates Euclidean Distance Matrix Completion (EDMC) as low-rank matrix completion over the manifold of positive semi-definite Gram matrices and develops a Riemannian gradient descent algorithm. Under a Bernoulli sampling model, it claims local linear convergence with high probability when the sampling probability satisfies p ≥ O(ν² r² log(n)/n), where ν is an EDMC-specific incoherence parameter. It also supplies a one-step hard-thresholding initialization that succeeds for p ≥ O(ν r^{3/2} log^{3/4}(n)/n^{1/4}), analyzes a symmetric linear operator via second-order degenerate U-statistics to obtain a restricted isometry property, provides a geometric interpretation of incoherence, and reports competitive empirical performance on synthetic data together with robustness guarantees.

Significance. If the central convergence claim holds under the stated assumptions, the work supplies a provable non-convex method for EDMC with sampling rates that improve on generic matrix completion bounds by exploiting the geometric structure of Gram matrices and the dual-basis expansion. The technical handling of the non-orthogonal basis through a symmetric operator and second-order U-statistic analysis constitutes a genuine contribution. The geometric definition of the incoherence parameter ν and the robustness results are also useful for applications such as sensor localization and molecular conformation. The result would be strengthened by explicit control on ν.

major comments (2)
  1. [Main convergence theorem / RIP analysis] Main convergence theorem (abstract and implied in the RIP section): the local linear convergence rate is stated for p ≥ O(ν² r² log(n)/n) only after treating the EDMC-specific incoherence parameter ν as a fixed constant that enables the restricted isometry property for the symmetric linear operator. The manuscript supplies a geometric definition of ν but does not derive an a priori bound showing ν = O(1) (or any explicit dependence on minimal point separation, ambient dimension, or n) for generic point configurations. If ν grows even mildly with n or r, the hidden factors render the claimed threshold super-linear and undermine the optimality statement.
  2. [RIP / U-statistic analysis] U-statistic concentration argument (second-order degenerate U-statistic section): the restricted isometry property for the symmetric linear operator induced by the dual basis expansion is obtained via concentration of a second-order U-statistic. The derivation appears to invoke post-hoc incoherence assumptions on the coupled terms without an explicit lemma controlling their scaling; verification of the precise constants and the transition from the Bernoulli model to the EDMC geometry would be needed to confirm the stated sampling rate.
minor comments (2)
  1. [Empirical evaluations] The empirical section describes results as “competitive” on synthetic data but provides no quantitative tables, error metrics, or direct comparisons with specific baselines; adding these would improve reproducibility.
  2. [Notation and definitions] Notation for the incoherence parameter ν should be introduced once with its geometric definition and then used consistently in all theorem statements and the abstract.

Simulated Author's Rebuttal

2 responses · 1 unresolved

We thank the referee for their detailed and constructive report. We respond to the major comments point-by-point below, indicating the revisions we will make to the manuscript.

read point-by-point responses

  1. Referee: [Main convergence theorem / RIP analysis] Main convergence theorem (abstract and implied in the RIP section): the local linear convergence rate is stated for p ≥ O(ν² r² log(n)/n) only after treating the EDMC-specific incoherence parameter ν as a fixed constant that enables the restricted isometry property for the symmetric linear operator. The manuscript supplies a geometric definition of ν but does not derive an a priori bound showing ν = O(1) (or any explicit dependence on minimal point separation, ambient dimension, or n) for generic point configurations. If ν grows even mildly with n or r, the hidden factors render the claimed threshold super-linear and undermine the optimality statement.

    Authors: We agree that an explicit discussion of ν's scaling would strengthen the result. The current manuscript defines ν geometrically and treats it as a fixed, problem-dependent constant (standard in incoherence analyses). In revision we will add a remark providing conditions under which ν = O(1), e.g., when points satisfy a minimal separation of Ω(1). This keeps the sampling rate near-optimal for typical EDMC instances while noting that ν can grow for pathological clustered configurations. revision: yes

  2. Referee: [RIP / U-statistic analysis] U-statistic concentration argument (second-order degenerate U-statistic section): the restricted isometry property for the symmetric linear operator induced by the dual basis expansion is obtained via concentration of a second-order U-statistic. The derivation appears to invoke post-hoc incoherence assumptions on the coupled terms without an explicit lemma controlling their scaling; verification of the precise constants and the transition from the Bernoulli model to the EDMC geometry would be needed to confirm the stated sampling rate.

    Authors: The concentration analysis for the second-order degenerate U-statistic, including control of coupled terms via the dual-basis expansion and EDMC geometry, appears in the appendix. We will add an explicit lemma in the main text that states the scaling bounds on the incoherence parameters of the coupled terms, verifies the constants from the concentration inequalities, and explicitly shows the transition from the Bernoulli model to the RIP for the symmetric operator. revision: yes

standing simulated objections not resolved
  • An unconditional a priori bound on ν = O(1) for completely arbitrary point configurations without any separation or geometric assumptions.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via external concentration and geometric definitions

full rationale

The paper establishes local linear convergence of Riemannian gradient descent on the rank-r manifold under a Bernoulli sampling model by analyzing the restricted isometry property of a symmetric linear operator induced by dual basis expansion of observed distances. This RIP is proved using concentration of a second-order degenerate U-statistic, yielding the sampling threshold p ≥ O(ν² r² log(n)/n) where ν is an explicitly defined EDMC-specific incoherence parameter arising from the geometry of the underlying Gram matrix and point configuration. The initialization via one-step hard thresholding follows a similar but weaker bound. No step reduces by construction to a fitted input, self-citation chain, or self-definitional equivalence; the central claims rest on standard manifold optimization techniques and probabilistic concentration bounds that are independent of the target result and externally verifiable.

Axiom & Free-Parameter Ledger

2 free parameters · 2 axioms · 0 invented entities

The central claim rests on the low-rank Gram matrix model, the Bernoulli observation model, and the boundedness of the EDMC incoherence parameter; no new physical entities are postulated.

free parameters (2)
  • rank r
    The algorithm and theorem are stated for a fixed known rank r of the Gram matrix; this is a modeling choice that must be selected or estimated.
  • incoherence parameter ν
    ν is defined specifically for the EDMC setting and appears in the sampling threshold; its value is not derived but treated as a problem-dependent constant.
axioms (2)
  • domain assumption The underlying configuration admits a rank-r positive semidefinite Gram matrix satisfying the observed distances.
    Invoked when formulating EDMC as low-rank matrix completion over the PSD cone.
  • domain assumption The sampling of distances follows an independent Bernoulli model with probability p.
    Used to establish the high-probability restricted isometry property via U-statistic concentration.

pith-pipeline@v0.9.0 · 5854 in / 1615 out tokens · 25019 ms · 2026-05-19T01:29:13.235430+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

106 extracted references · 106 canonical work pages · 3 internal anchors

  1. [1]

    Improving localization accuracy for autonomous driving in snow- rain environments,

    M. Aldibaja, N. Suganuma, and K. Yoneda, “Improving localization accuracy for autonomous driving in snow- rain environments,” in 2016 IEEE/SICE International Symposium on System Integration (SII) . IEEE, 2016, pp. 212–217

    work page 2016

  2. [2]

    Multi-sensor localization and navigation for remote manipulation in smoky areas,

    J. V. Marti, J. Sales, R. Marin, and P. Sanz, “Multi-sensor localization and navigation for remote manipulation in smoky areas,” International Journal of Advanced Robotic Systems , vol. 10, no. 4, p. 211, 2013

    work page 2013

  3. [3]

    Exploring the limits of precision and accuracy of protein structures determined by nuclear magnetic resonance spectroscopy,

    G. M. Clore, M. A. Robien, and A. M. Gronenborn, “Exploring the limits of precision and accuracy of protein structures determined by nuclear magnetic resonance spectroscopy,” Journal of molecular biology , vol. 231, no. 1, pp. 82–102, 1993

    work page 1993

  4. [4]

    Localization systems for wireless sensor networks,

    A. Boukerche, H. A. Oliveira, E. F. Nakamura, and A. A. Loureiro, “Localization systems for wireless sensor networks,” IEEE wireless Communications , vol. 14, no. 6, pp. 6–12, 2007

    work page 2007

  5. [5]

    A review on localization in wireless sensor networks,

    J. Kuriakose, S. Joshi, R. Vikram Raju, and A. Kilaru, “A review on localization in wireless sensor networks,” Advances in signal processing and intelligent recognition systems , pp. 599–610, 2014

    work page 2014

  6. [6]

    Semidefinite programming based algorithms for sensor network localization,

    P. Biswas, T.-C. Lian, T.-C. Wang, and Y. Ye, “Semidefinite programming based algorithms for sensor network localization,” ACM Transactions on Sensor Networks (TOSN) , vol. 2, no. 2, pp. 188–220, 2006

    work page 2006

  7. [7]

    Sensor network localization, euclidean distance matrix completions, and graph realization,

    Y. Ding, N. Krislock, J. Qian, and H. Wolkowicz, “Sensor network localization, euclidean distance matrix completions, and graph realization,” Optimization and Engineering , vol. 11, no. 1, pp. 45–66, 2010

    work page 2010

  8. [8]

    Distance-based formulations for the position analysis of kinematic chains,

    N. Rojas, “Distance-based formulations for the position analysis of kinematic chains,” Ph.D. dissertation, Universitat Politècnica de Catalunya, 2012

    work page 2012

  9. [9]

    Distance geometry in active structures,

    J. M. Porta, N. Rojas, and F. Thomas, “Distance geometry in active structures,” Mechatronics for Cultural Heritage and Civil Engineering , pp. 115–136, 2018

    work page 2018

  10. [10]

    A global geometric framework for nonlinear dimensionality reduction,

    J. B. Tenenbaum, V. De Silva, and J. C. Langford, “A global geometric framework for nonlinear dimensionality reduction,” science, vol. 290, no. 5500, pp. 2319–2323, 2000

    work page 2000

  11. [11]

    Molecular conformations from distance matrices,

    W. Glunt, T. Hayden, and M. Raydan, “Molecular conformations from distance matrices,” Journal of Com- putational Chemistry , vol. 14, no. 1, pp. 114–120, 1993

    work page 1993

  12. [12]

    Applications of multidimensional scaling to molecular conformation,

    M. W. Trosset, “Applications of multidimensional scaling to molecular conformation,” 1997

    work page 1997

  13. [13]

    Using a distributed sdp approach to solve simulated protein molecular conformation problems,

    X. Fang and K.-C. Toh, “Using a distributed sdp approach to solve simulated protein molecular conformation problems,” in Distance Geometry. Springer, 2013, pp. 351–376

    work page 2013

  14. [14]

    A branch-and-prune algorithm for the molecular distance geometry problem,

    L. Liberti, C. Lavor, and N. Maculan, “A branch-and-prune algorithm for the molecular distance geometry problem,” International Transactions in Operational Research , vol. 15, no. 1, pp. 1–17, 2008

    work page 2008

  15. [15]

    Quantitatively visualizing bipartite datasets,

    T. Einav, Y. Khoo, and A. Singer, “Quantitatively visualizing bipartite datasets,” Physical Review X , vol. 13, no. 2, p. 021002, 2023. 22

    work page 2023

  16. [16]

    Multidimensional scaling: I. theory and method,

    W. S. Torgerson, “Multidimensional scaling: I. theory and method,” Psychometrika, vol. 17, no. 4, pp. 401–419, 1952

    work page 1952

  17. [17]

    Discussion of a set of points in terms of their mutual distances,

    G. Young and A. S. Householder, “Discussion of a set of points in terms of their mutual distances,” Psychome- trika, vol. 3, no. 1, pp. 19–22, 1938

    work page 1938

  18. [18]

    W. S. Torgerson, Theory and methods of scaling. Wiley, 1958

    work page 1958

  19. [19]

    Some distance properties of latent root and vector methods used in multivariate analysis,

    J. C. Gower, “Some distance properties of latent root and vector methods used in multivariate analysis,” Biometrika, vol. 53, no. 3-4, pp. 325–338, 1966

    work page 1966

  20. [20]

    Euclidean distance matrices: essential theory, algo- rithms, and applications,

    I. Dokmanic, R. Parhizkar, J. Ranieri, and M. Vetterli, “Euclidean distance matrices: essential theory, algo- rithms, and applications,” IEEE Signal Processing Magazine , vol. 32, no. 6, pp. 12–30, 2015

    work page 2015

  21. [21]

    A novel low-rank matrix completion approach to estimate missing entries in euclidean distance matrices,

    N. Moreira, L. Duarte, C. Lavor, and C. Torezzan, “A novel low-rank matrix completion approach to estimate missing entries in euclidean distance matrices,” 2017

    work page 2017

  22. [22]

    A rank minimization heuristic with application to minimum order system approximation,

    M. Fazel, H. Hindi, and S. P. Boyd, “A rank minimization heuristic with application to minimum order system approximation,” in American Control Conference, 2001. Proceedings of the 2001 , vol. 6. IEEE, 2001, pp. 4734–4739

    work page 2001

  23. [23]

    Decoding by linear programming,

    E. J. Candes and T. Tao, “Decoding by linear programming,” IEEE transactions on information theory , vol. 51, no. 12, pp. 4203–4215, 2005

    work page 2005

  24. [24]

    Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information,

    E. J. Candès, J. Romberg, and T. Tao, “Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information,” IEEE Transactions on information theory , vol. 52, no. 2, pp. 489–509, 2006

    work page 2006

  25. [25]

    Exact matrix completion via convex optimization,

    E. J. Candès and B. Recht, “Exact matrix completion via convex optimization,” Foundations of Computational mathematics, vol. 9, no. 6, pp. 717–772, 2009

    work page 2009

  26. [26]

    Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization,

    B. Recht, M. Fazel, and P. A. Parrilo, “Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization,” SIAM review , vol. 52, no. 3, pp. 471–501, 2010

    work page 2010

  27. [27]

    Note on sampling without replacing from a finite collection of matrices

    D. Gross and V. Nesme, “Note on sampling without replacing from a finite collection of matrices,” arXiv preprint arXiv:1001.2738 , 2010

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  28. [28]

    Exact reconstruction of euclidean distance geometry problem using low-rank matrix completion,

    A. Tasissa and R. Lai, “Exact reconstruction of euclidean distance geometry problem using low-rank matrix completion,” IEEE Transactions on Information Theory , vol. 65, no. 5, pp. 3124–3144, 2018

    work page 2018

  29. [29]

    Solving partial differential equations on manifolds from incomplete interpoint distance,

    R. Lai and J. Li, “Solving partial differential equations on manifolds from incomplete interpoint distance,” SIAM Journal on Scientific Computing , vol. 39, no. 5, pp. A2231–A2256, 2017

    work page 2017

  30. [30]

    Sensor network localization via riemannian conjugate gradient and rank reduction,

    Y. Li and X. Sun, “Sensor network localization via riemannian conjugate gradient and rank reduction,” IEEE Transactions on Signal Processing , vol. 72, pp. 1910–1927, 2024

    work page 1910

  31. [31]

    Low-rank matrix completion in a general non-orthogonal basis,

    A. Tasissa and R. Lai, “Low-rank matrix completion in a general non-orthogonal basis,” Linear Algebra and its Applications, vol. 625, pp. 81–112, 2021

    work page 2021

  32. [32]

    Localization of iot networks via low-rank matrix completion,

    L. T. Nguyen, J. Kim, S. Kim, and B. Shim, “Localization of iot networks via low-rank matrix completion,” IEEE Transactions on Communications , vol. 67, no. 8, pp. 5833–5847, 2019

    work page 2019

  33. [33]

    Euclidean distance matrix completion via asymmetric projected gradient descent,

    Y. Li and X. Sun, “Euclidean distance matrix completion via asymmetric projected gradient descent,” 2025. [Online]. A vailable: https://arxiv.org/abs/2504.19530

    work page arXiv 2025

  34. [34]

    Sample-efficient geometry reconstruction from euclidean distances using non-convex optimization,

    I. Ghosh, A. Tasissa, and C. Kümmerle, “Sample-efficient geometry reconstruction from euclidean distances using non-convex optimization,” in Advances in Neural Information Processing Systems , A. Globerson, L. Mackey, D. Belgrave, A. Fan, U. Paquet, J. Tomczak, and C. Zhang, Eds., vol. 37. Curran Associates, Inc., 2024, pp. 77 226–77 268. [Online]. A vaila...

    work page 2024

  35. [35]

    The power of convex relaxation: Near-optimal matrix completion,

    E. J. Candès and T. Tao, “The power of convex relaxation: Near-optimal matrix completion,” IEEE Trans- actions on Information Theory , vol. 56, no. 5, pp. 2053–2080, 2010. 23

    work page 2053

  36. [36]

    Rank minimization via online learning,

    R. Meka, P. Jain, C. Caramanis, and I. S. Dhillon, “Rank minimization via online learning,” in Proceedings of the 25th International Conference on Machine learning , 2008, pp. 656–663

    work page 2008

  37. [37]

    Mixed-projection conic optimization: A new paradigm for modeling rank constraints,

    D. Bertsimas, R. Cory-Wright, and J. Pauphilet, “Mixed-projection conic optimization: A new paradigm for modeling rank constraints,” Operations Research, vol. 70, no. 6, pp. 3321–3344, 2022

    work page 2022

  38. [38]

    A simpler approach to matrix completion,

    B. Recht, “A simpler approach to matrix completion,” The Journal of Machine Learning Research , vol. 12, pp. 3413–3430, 2011

    work page 2011

  39. [39]

    Recovering low-rank matrices from few coefficients in any basis,

    D. Gross, “Recovering low-rank matrices from few coefficients in any basis,” Information Theory, IEEE Transactions on, vol. 57, no. 3, pp. 1548–1566, 2011

    work page 2011

  40. [40]

    A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization,

    S. Burer and R. D. Monteiro, “A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization,” Mathematical Programming, vol. 95, no. 2, pp. 329–357, 2003

    work page 2003

  41. [41]

    Low-rank matrix completion using alternating minimization,

    P. Jain, P. Netrapalli, and S. Sanghavi, “Low-rank matrix completion using alternating minimization,” in Proceedings of the forty-fifth annual ACM symposium on Theory of computing , 2013, pp. 665–674

    work page 2013

  42. [42]

    Understanding alternating minimization for matrix completion,

    M. Hardt, “Understanding alternating minimization for matrix completion,” Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS , pp. 651–660, 12 2014

    work page 2014

  43. [43]

    Provable non-convex phase retrieval with outliers: Median truncated Wirtinger flow,

    H. Zhang, Y. Chi, and Y. Liang, “Provable non-convex phase retrieval with outliers: Median truncated Wirtinger flow,” in International conference on machine learning . PMLR, 2016, pp. 1022–1031

    work page 2016

  44. [44]

    Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization,

    S. J. Optim, Y. Chen, Y. Chi, J. Fan, and Y. Yan, “Noisy matrix completion: Understanding statistical guarantees for convex relaxation via nonconvex optimization,” SIAM J Optim , vol. 30, pp. 3098–3121, 2020. [Online]. A vailable: https://doi.org/10.1137/19M1290000

    work page doi:10.1137/19m1290000 2020

  45. [45]

    Fast federated low rank matrix completion,

    A. A. Abbasi, S. Moothedath, and N. Vaswani, “Fast federated low rank matrix completion,” in 2023 59th Annual Allerton Conference on Communication, Control, and Computing (Allerton) . IEEE, 2023, pp. 1–6

    work page 2023

  46. [46]

    Efficient federated low rank matrix completion,

    A. A. Abbasi and N. Vaswani, “Efficient federated low rank matrix completion,” IEEE Transactions on Information Theory , 2025

    work page 2025

  47. [47]

    Phase retrieval using alternating minimization,

    P. Netrapalli, P. Jain, and S. Sanghavi, “Phase retrieval using alternating minimization,” Advances in Neural Information Processing Systems , vol. 26, 2013

    work page 2013

  48. [48]

    Wright and Y

    J. Wright and Y. Ma, High-Dimensional Data Analysis with Low-Dimensional Models: Principles, Computa- tion, and Applications . Cambridge University Press, 2022

    work page 2022

  49. [49]

    Foucart and H

    S. Foucart and H. Rauhut, A Mathematical Introduction to Compressive Sensing , ser. Applied and Numerical Harmonic Analysis. Springer New York, 2013. [Online]. A vailable: https://books.google.com/books?id= zb28BAAAQBAJ

    work page 2013

  50. [50]

    A dual basis approach to multidimensional scaling: spectral analysis and graph regularity,

    S. Lichtenberg and A. Tasissa, “A dual basis approach to multidimensional scaling: spectral analysis and graph regularity,” 2023

    work page 2023

  51. [51]

    Riemannian optimization for euclidean distance geometry,

    C. Smith, S. Lichtenberg, H. Cai, and A. Tasissa, “Riemannian optimization for euclidean distance geometry,” OPT2023: 15th Annual Workshop on Optimization for Machine Learning , 2023

    work page 2023

  52. [52]

    Vershynin, Introduction to the non-asymptotic analysis of random matrices

    R. Vershynin, Introduction to the non-asymptotic analysis of random matrices . Cambridge University Press, 2012, p. 210–268

    work page 2012

  53. [53]

    Cambridge Series in Statistical and Probabilistic Mathematics

    ——, High-Dimensional Probability: An Introduction with Applications in Data Science , ser. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018

    work page 2018

  54. [54]

    Guarantees of riemannian optimization for low rank matrix completion

    K. Wei, J.-F. Cai, T. F. Chan, and S. Leung, “Guarantees of riemannian optimization for low rank matrix completion. ”Inverse Problems & Imaging , vol. 14, no. 2, 2020

    work page 2020

  55. [55]

    Low-rank matrix completion in a general non-orthogonal basis,

    A. Tasissa and R. Lai, “Low-rank matrix completion in a general non-orthogonal basis,” Linear Algebra and its Applications, vol. 625, pp. 81–112, 2021. [Online]. A vailable: www.elsevier.com/locate/laa

    work page 2021

  56. [56]

    G. H. Golub and C. F. Van Loan, Matrix Computations - 4th Edition . Philadelphia, PA: Johns Hopkins University Press, 2013. [Online]. A vailable: https://epubs.siam.org/doi/abs/10.1137/1.9781421407944 24

    work page doi:10.1137/1.9781421407944 2013

  57. [57]

    The approximation of one matrix by another of lower rank,

    C. Eckart and G. Young, “The approximation of one matrix by another of lower rank,” Psychometrika, vol. 1, no. 3, pp. 211–218, 1936

    work page 1936

  58. [58]

    Diland: An algorithm for distributed sensor localization with noisy distance measurements,

    U. A. Khan, S. Kar, and J. M. Moura, “Diland: An algorithm for distributed sensor localization with noisy distance measurements,” IEEE Transactions on Signal Processing , vol. 58, no. 3, pp. 1940–1947, 2009

    work page 1940

  59. [59]

    Perturbation analysis of the euclidean distance matrix optimization problem and its numerical implications,

    S. Guo, H.-D. Qi, and L. Zhang, “Perturbation analysis of the euclidean distance matrix optimization problem and its numerical implications,” Computational Optimization and Applications , vol. 86, no. 3, pp. 1193–1227, 2023

    work page 2023

  60. [60]

    Semidefinite programming approaches for sensor network localization with noisy distance measurements,

    P. Biswas, T.-C. Liang, K.-C. Toh, Y. Ye, and T.-C. Wang, “Semidefinite programming approaches for sensor network localization with noisy distance measurements,” IEEE transactions on automation science and engineering , vol. 3, no. 4, pp. 360–371, 2006

    work page 2006

  61. [61]

    Robust node localization for rough and extreme deployment environments,

    A. Tasissa and W. Dargie, “Robust node localization for rough and extreme deployment environments,”

    work page

  62. [62]

    A vailable: https://arxiv.org/abs/2507.03856

    [Online]. A vailable: https://arxiv.org/abs/2507.03856

    work page arXiv

  63. [63]

    Structured sampling for robust euclidean distance geometry,

    C. Kundu, A. Tasissa, and H. Cai, “Structured sampling for robust euclidean distance geometry,” in 2025 59th Annual Conference on Information Sciences and Systems (CISS) . IEEE, Mar. 2025, p. 1–6. [Online]. A vailable:http://dx.doi.org/10.1109/CISS64860.2025.10944739

    work page doi:10.1109/ciss64860.2025.10944739 2025

  64. [64]

    A dual basis approach for structured robust euclidean distance geometry,

    ——, “A dual basis approach for structured robust euclidean distance geometry,” 2025. [Online]. A vailable: https://arxiv.org/abs/2505.18414

    work page arXiv 2025

  65. [65]

    Low-rank matrix completion by Riemannian optimization—extended version,

    B. Vandereycken, “Low-rank matrix completion by Riemannian optimization—extended version,” 2012

    work page 2012

  66. [66]

    Fixed-rank matrix factorizations and riemannian low-rank optimization,

    B. Mishra, G. Meyer, S. Bonnabel, and R. Sepulchre, “Fixed-rank matrix factorizations and riemannian low-rank optimization,” 2013

    work page 2013

  67. [67]

    Low-rank matrix completion via preconditioned optimization on the grassmann manifold,

    N. Boumal and P.-A. Absil, “Low-rank matrix completion via preconditioned optimization on the grassmann manifold,” Absil / Linear Algebra and its Applications , vol. 475, p. 201, 2015. [Online]. A vailable: www.elsevier.com/locate/laahttp://dx.doi.org/10.1016/j.laa.2015.02.0270024-3795/

    work page doi:10.1016/j.laa.2015.02.0270024-3795/ 2015

  68. [68]

    SET: an algorithm for consistent matrix completion

    W. Dai and O. Milenkovic, “Set: an algorithm for consistent matrix completion,” 2010. [Online]. A vailable: https://arxiv.org/abs/0909.2705

    work page internal anchor Pith review Pith/arXiv arXiv 2010

  69. [69]

    Matrix completion from a few entries,

    R. H. Keshavan, A. Montanari, and S. Oh, “Matrix completion from a few entries,” IEEE Transactions on Information Theory , vol. 56, no. 6, pp. 2980–2998, 2010

    work page 2010

  70. [70]

    Matrix completion from noisy entries,

    ——, “Matrix completion from noisy entries,” Journal of Machine Learning Research , vol. 11, no. Jul, pp. 2057–2078, 2010

    work page 2057

  71. [71]

    Solving euclidean distance matrix completion problems via semidefinite programming,

    A. Y. Alfakih, A. Khandani, and H. Wolkowicz, “Solving euclidean distance matrix completion problems via semidefinite programming,” Computational optimization and applications , vol. 12, no. 1-3, pp. 13–30, 1999

    work page 1999

  72. [72]

    Semidefinite programming for ad hoc wireless sensor network localization,

    P. Biswas and Y. Ye, “Semidefinite programming for ad hoc wireless sensor network localization,” in Proceed- ings of the 3rd international symposium on Information processing in sensor networks , 2004, pp. 46–54

    work page 2004

  73. [73]

    A distributed sdp approach for large-scale noisy anchor-free graph realization with applications to molecular conformation,

    P. Biswas, K.-C. Toh, and Y. Ye, “A distributed sdp approach for large-scale noisy anchor-free graph realization with applications to molecular conformation,” SIAM Journal on Scientific Computing , vol. 30, no. 3, pp. 1251– 1277, 2008

    work page 2008

  74. [74]

    An sdp-based divide-and-conquer algorithm for large-scale noisy anchor-free graph realization,

    N.-H. Z. Leung and K.-C. Toh, “An sdp-based divide-and-conquer algorithm for large-scale noisy anchor-free graph realization,” SIAM Journal on Scientific Computing , vol. 31, no. 6, pp. 4351–4372, 2010

    work page 2010

  75. [75]

    Protein structure by semidefi- nite facial reduction,

    B. Alipanahi, N. Krislock, A. Ghodsi, H. Wolkowicz, L. Donaldson, and M. Li, “Protein structure by semidefi- nite facial reduction,” in Research in Computational Molecular Biology: 16th Annual International Conference, RECOMB 2012, Barcelona, Spain, April 21-24, 2012. Proceedings 16 . Springer, 2012, pp. 1–11

    work page 2012

  76. [76]

    An evaluation of computational strategies for use in the determination of protein structure from distance constraints obtained by nuclear magnetic resonance,

    T. F. Havel, “An evaluation of computational strategies for use in the determination of protein structure from distance constraints obtained by nuclear magnetic resonance,” Progress in biophysics and molecular biology , vol. 56, no. 1, pp. 43–78, 1991. 25

    work page 1991

  77. [77]

    Distance geometry optimization for protein structures,

    J. J. Moré and Z. Wu, “Distance geometry optimization for protein structures,” Journal of Global Optimization, vol. 15, pp. 219–234, 1999

    work page 1999

  78. [78]

    G. M. Crippen, T. F. Havel et al. , Distance geometry and molecular conformation . Research Studies Press Taunton, 1988, vol. 74

    work page 1988

  79. [79]

    Distance geometry: Theory, algorithms, and chemical applications,

    T. F. Havel, “Distance geometry: Theory, algorithms, and chemical applications,” Encyclopedia of Computa- tional Chemistry , vol. 120, pp. 723–742, 1998

    work page 1998

  80. [80]

    Recent advances on the discretizable molecular distance geometry problem,

    C. Lavor, L. Liberti, N. Maculan, and A. Mucherino, “Recent advances on the discretizable molecular distance geometry problem,” European Journal of Operational Research , vol. 219, no. 3, pp. 698–706, 2012

    work page 2012

Showing first 80 references.