Approximating orthogonal matrices by permutation matrices

DOI10.4310/PAMQ.2006.V2.N4.A3zbMATH Open1131.15026arXivmath/0510612MaRDI QIDQ866456FDOQ866456

Alexander Barvinok

Publication date: 20 February 2007

Published in: Pure and Applied Mathematics Quarterly (Search for Journal in Brave)

Abstract: Motivated in part by a problem of combinatorial optimization and in part by analogies with quantum computations, we consider approximations of orthogonal matrices U by ``non-commutative convex combinations A of permutation matrices of the type A=sum A_sigma sigma, where sigma are permutation matrices and A_sigma are positive semidefinite nxn matrices summing up to the identity matrix. We prove that for every nxn orthogonal matrix U there is a non-commutative convex combination A of permutation matrices which approximates U entry-wise within an error of c n^{-1/2}ln n and in the Frobenius norm within an error of c ln n. The proof uses a certain procedure of randomized rounding of an orthogonal matrix to a permutation matrix.

Full work available at URL: https://arxiv.org/abs/math/0510612

zbMATH Keywords

combinatorial optimizationorder statisticspermutation matricesGaussian measurepositive semidefinite matricesorthogonal matricesFrobenius normmeasure concentrationquantum computations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Hermitian, skew-Hermitian, and related matrices (15B57) Order statistics; empirical distribution functions (62G30) Combinatorial optimization (90C27) Positive matrices and their generalizations; cones of matrices (15B48) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60)

Cited In (3)

• The method of permissible basis matrices
• Orthogonal matrix and its application in Bloom's threshold scheme
• Convex Relaxations for Permutation Problems

   Recommendations

• An approximate orthogonalization technique for arbitrary rectangular matrices 👍 👎
• Permutation matrices whose convex combinations are orthostochastic 👍 👎
• An iterative algorithm for approximate orthogonalisation of symmetric matrices 👍 👎
• Rational orthogonal approximations to orthogonal matrices 👍 👎
• Extension of an approximate orthogonalization algorithm to arbitrary rectangular matrices 👍 👎
• Orthogonal polynomial matrices and computation of matrix Padé approximates 👍 👎
• On Perhermitian Matrices 👍 👎
• Approximating Matrices with Multiple Symmetries 👍 👎
• Title not available (Why is that?) 👍 👎
• Approximating a symmetric matrix 👍 👎

This page was built for publication: Approximating orthogonal matrices by permutation matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q866456)