Convex Relaxations for Permutation Problems
Talkat Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013) · 2013-09-16..09-19
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)
- 0:00Intro
- 0:35CI Asian
- 3:10Why is this important
- 5:08spectral solution
- 5:30spectral clustering
- 7:50additional structural information
- 11:43cut matrices
- 16:05why do we care
- 17:25the convex hull
- 18:35the objective
- 22:38the hack
- 25:38linear constraints
- 28:23metrics
- 30:13historical examples
- 32:03numerical results
- 33:18Markov chains
- 35:15Numerical information
- 37:03DNA
- 41:17Conclusion