Approximating orthogonal matrices by permutation matrices

DOI10.4310/PAMQ.2006.V2.N4.A3MaRDI QIDQ866456zbMATH OpenFDO

Authors Alexander Barvinok

Publication date 20 February 2007

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

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

zbMATH Keywords

combinatorial optimizationFrobenius normGaussian measuremeasure concentrationorder statisticsorthogonal matricespermutation matricespositive semidefinite matricesquantum computations

Mathematics Subject Classification ID

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

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.

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

Cited in

(6)

• A characterization of orthogonal permutative matrices of order 4
• Near invariance of the hypercube
• Orthogonal matrix and its application in Bloom's threshold scheme
• The method of permissible basis matrices
• Convex relaxations for permutation problems
• Approximate orthogonality of permutation operators, with application to quantum information

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)