Approximating orthogonal matrices by permutation matrices

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

Authors: 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

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
• scientific article; zbMATH DE number 2197982
• Approximating a symmetric matrix

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

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)