Convex Relaxations for Permutation Problems

on YouTube ↗47m

" summary

Claims that spectral ordering via the Fiedler vector spectral ordering recovers seriation exactly for noiseless R-matrices, and that seriation equals a two-sum quadratic objective that is NP-hard in general. Method builds a convex relaxation over doubly stochastic relaxation matrices, adds a small concave penalty and linear side constraints to encode pairwise order information, then samples monotone projections to recover permutations. Results: spectral step handles large data (example: 250,000 reads in 2 seconds), QP finishes on blocks of size ~100–200 and improves accuracy when structural constraints are added; spectral fails once noise exceeds the spectral gap.

AI-written summary · about

" chapters (19)

1. 0:00Intro
2. 0:35CI Asian
3. 3:10Why is this important
4. 5:08spectral solution
5. 5:30spectral clustering
6. 7:50additional structural information
7. 11:43cut matrices
8. 16:05why do we care
9. 17:25the convex hull
10. 18:35the objective
11. 22:38the hack
12. 25:38linear constraints
13. 28:23metrics
14. 30:13historical examples
15. 32:03numerical results
16. 33:18Markov chains
17. 35:15Numerical information
18. 37:03DNA
19. 41:17Conclusion