Sparse Metric Repair: If It Ain't Broke, Don't Fix It

on YouTube ↗33m

" summary

Problem: a symmetric nonnegative distance matrix violates triangle inequalities; goal is to find a perturbation P so D+P is a metric while minimizing the L0 sparsity (change as few pairwise distances as possible). Key claim: decrease-only = Floyd‑Warshall gives the sparsest and L1‑closest repair; increase‑only is combinatorially hard and a lexicographic greedy (IOMR) can be correct but has worst‑case approximation ~n. Experiments show reweighted L1 often works well, heuristics run much faster than convex solvers, and final broken triangles drop below 1% on tested data; detection and subcubic time remain unlikely (n^3 barrier).

AI-written summary · about

" chapters (17)

1. 0:00Intro
2. 0:52Definitions
3. 2:24Motivation: Data cleaning
4. 4:04Metric Repair Formally
5. 5:29Traditional Techniques
6. 7:55Sparse Matrix Repair: Optimistic data cleaning
7. 8:25methods: convex relaxation
8. 10:26The real problem with convex methods....
9. 11:54Three Repair Scenarios: Constrain P
10. 15:13Decrease Only Metric Repair: Sparse Guarantees
11. 16:12Working around cubic constraints
12. 16:42Increase Only Metric Repair: Algorithms
13. 22:03General metric repair problem
14. 22:32Examples, experiments
15. 26:28Arbitrarily Perturbed Path Metric of Erdös-Renyi Graph
16. 27:40Experimental Observations
17. 28:17So what's next?