Convex relaxations for permutation problems
From MaRDI portal
Abstract: Seriation seeks to reconstruct a linear order between variables using unsorted, pairwise similarity information. It has direct applications in archeology and shotgun gene sequencing for example. We write seriation as an optimization problem by proving the equivalence between the seriation and combinatorial 2-SUM problems on similarity matrices (2-SUM is a quadratic minimization problem over permutations). The seriation problem can be solved exactly by a spectral algorithm in the noiseless case and we derive several convex relaxations for 2-SUM to improve the robustness of seriation solutions in noisy settings. These convex relaxations also allow us to impose structural constraints on the solution, hence solve semi-supervised seriation problems. We derive new approximation bounds for some of these relaxations and present numerical experiments on archeological data, Markov chains and DNA assembly from shotgun gene sequencing data.
Recommendations
- Continuation methods for approximate large scale object sequencing
- Optimal rates of statistical seriation
- Graph-Based Representations in Pattern Recognition
- A Spectral Algorithm for Seriation and the Consecutive Ones Problem
- Seriation in the presence of errors: a factor 16 approximation algorithm for \(l_{\infty }\)-fitting Robinson structures to distances
Cites work
- \(\ell ^2_2\) spreading metrics for vertex ordering problems
- A New Value Iteration method for the Average Cost Dynamic Programming Problem
- A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
- A spectral algorithm for envelope reduction of sparse matrices
- A Spectral Algorithm for Seriation and the Consecutive Ones Problem
- Abundance matrices and seriation in archaeology
- An Analysis of Spectral Envelope Reduction via Quadratic Assignment Problems
- An improved approximation ratio for the minimum linear arrangement problem
- An Investigation of Interior-Point Algorithms for the Linear Transportation Problem
- Approximating orthogonal matrices by permutation matrices
- Approximating the bandwidth via volume respecting embeddings
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Divide-and-conquer approximation algorithms via spreading metrics
- Elements of Information Theory
- Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
- Geometric algorithms and combinatorial optimization
- scientific article; zbMATH DE number 3168330 (Why is no real title available?)
- scientific article; zbMATH DE number 4070633 (Why is no real title available?)
- scientific article; zbMATH DE number 47363 (Why is no real title available?)
- scientific article; zbMATH DE number 1489799 (Why is no real title available?)
- scientific article; zbMATH DE number 3393603 (Why is no real title available?)
- Incidence matrices and interval graphs
- Introductory lectures on convex optimization. A basic course.
- Moment inequalities for sums of random matrices and their applications in optimization
- New Approximation Techniques for Some Linear Ordering Problems
- On complexity of matrix scaling
- On the consecutive ones property
- Quick approximation to matrices and applications
- Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
- Semidefinite programming relaxations for the quadratic assignment problem
- Seriation and matrix reordering methods: An historical overview
- Smallest compact formulation for the permutahedron
- Sums of random symmetric matrices and quadratic optimization under orthogonality constraints
- The quadratic assignment problem
- The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure
- Weak Recovery Conditions from Graph Partitioning Bounds and Order Statistics
Cited in
(20)- Optimal rates of statistical seriation
- New special cases of the quadratic assignment problem with diagonally structured coefficient matrices
- The unit-capacity constrained permutation problem
- The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure
- Permutatorial optimization via the permutahedron
- Reconstruction of line-embeddings of graphons
- Domain permutation reduction for constraint satisfaction problems
- The seriation problem in the presence of a double Fiedler value
- L_p-norm regularization algorithms for optimization over permutation matrices
- ADM-CLE approach for detecting slow variables in continuous time Markov chains and dynamic data
- Permutation Problems and Channelling Constraints
- An Optimal Algorithm for Strict Circular Seriation
- Similarity-first search: a new algorithm with application to Robinsonian matrix recognition
- Spectral graph matching and regularized quadratic relaxations. I: Algorithm and Gaussian analysis
- Convex solution of a permutation problem
- Localization in 1D non-parametric latent space models from pairwise affinities
- Continuation methods for approximate large scale object sequencing
- \texttt{PQser:} a Matlab package for spectral seriation
- Minimax optimal seriation in polynomial time
- Topology-driven antenna clustering for distributed massive MIMO receivers
This page was built for publication: Convex relaxations for permutation problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3456867)
