Research map / Learning theory and algorithms / Matrix and tensor methods
Sample-Efficient Geometry Reconstruction from Euclidean Distances using Non-Convex Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes MatrixIRLS, an iteratively reweighted least squares method for Euclidean distance geometry from minimal random distance samples, with local quadratic convergence and a tangent-space RIP for symmetric rank-r matrices.
Problem
Recovering point configurations from a minimal number of observed pairwise Euclidean distances (incomplete Euclidean distance geometry), where convex nuclear-norm relaxations are computationally heavy and data-inefficient and few non-convex methods have guarantees.
Approach
Applies a MatrixIRLS variant with smoothed log-det objectives to the Gram-matrix rank minimization formulation, using a dual basis for the non-orthogonal distance measurement basis to prove a tangent-space RIP and local quadratic convergence at the optimal sample complexity O(nr log n).
Key results
- MatrixIRLS achieves comparable success to ALM and outperforms RieEDG and ScaledSGD in phase transition experiments, requiring fewer distance samples.
- On ill-conditioned data MatrixIRLS reaches relative error about 1e-8 in around 35 iterations, while other methods stay above 1e-3 after 100000 iterations.
- On 1BPM protein (n=3672, r=3) with oversampling factor 3, MatrixIRLS finishes in 7.08 minutes with relative error 2.7e-12, versus 23.4 minutes for ALM.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MatrixIRLS instead of ALM | 1BPM protein reconstruction · 1BPM protein, rho=3 | relative error: $5.6\times10^{-6}$ -> $2.7\times10^{-12}$ | Helped |
| Use MatrixIRLS instead of ALM | 1BPM protein reconstruction · 1BPM protein, rho=3 | time until convergence (mins): 23.4 -> 7.08 | Helped |
| Use MatrixIRLS instead of RieEDG | 1BPM protein reconstruction · 1BPM protein, rho=3 | relative error: $5.6\times10^{-2}$ -> $2.7\times10^{-12}$ | Helped |
| Use MatrixIRLS instead of ScaledSGD | 1BPM protein reconstruction · 1BPM protein, rho=3 | relative error: $2.4\times10^{-2}$ -> $2.7\times10^{-12}$ | Helped |
| Use MatrixIRLS rather than ScaledSGD or RieEDG | Synthetic Gaussian distance reconstruction · Gaussian synthetic data, ranks 2 to 5 | recovery success probability | Helped |
| Use MatrixIRLS rather than ScaledSGD or RieEDG | 1BPM protein reconstruction · Protein 1BPM | recovery success probability | Mixed |
Surprising findings
- For the 1BPM protein, ALM has superior performance for oversampling factors between 1 and 1.5, per the supplementary limitations.
- Per-iteration runtime of MatrixIRLS is larger than other non-convex methods, though it needs under a tenth of their iterations.
Limitations
- Convergence guarantee is only local, requiring initialization near the ground truth.
- Per-iteration runtime is higher than other non-convex methods.
- ALM is superior on the protein data for oversampling factors between 1 and 1.5.
Experimental setup
Datasets: synthetic Gaussian point configurations 1BPM protein structure from Protein Data Bank US cities data
Benchmarks: synthetic Gaussian Gram matrices (n=500) ill-conditioned synthetic data (n=400, kappa=1e5) 1BPM protein (n=3672, r=3) US cities data
Metrics: success probability relative Procrustes distance runtime (minutes) oversampling factor
Baselines: ALM ScaledSGD RieEDG
Builds on: MatrixIRLS nuclear norm minimization for EDG Burer-Monteiro factorization Riemannian optimization for EDG
Closest papers by meaning
- Euclidean Embedding of Data Using Local Distances (NeurIPS 2026 · similarity 0.88)
- Efficient, Sparse Representation of Manifold Distance Matrices for Classical Scaling (CVPR 2018 · similarity 0.87)
- MetricEmbedding: Accelerate Metric Nearness by Tropical Inner Product (ICML 2025 · similarity 0.86)
- Geometric Mean Metric Learning (ICML 2016 · similarity 0.86)
- Euclidean distance compression via deep random features (NeurIPS 2024 · similarity 0.84)
- Learning Distances from Data with Normalizing Flows and Score Matching (ICML 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.