Scaling positive random matrices: concentration and asymptotic convergence

DOI10.1214/22-ECP502MaRDI QIDQ2679643zbMATH OpenOpenAlexFDO

Authors Boris Landa

Publication date 23 January 2023

Published in Electronic Communications in Probability (Search for Journal in Brave)

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

zbMATH Keywords

concentration inequalitydoubly stochastic matrixmatrix balancingmatrix scaling

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Large deviations (60F10)

Abstract: It is well known that any positive matrix can be scaled to have prescribed row and column sums by multiplying its rows and columns by certain positive scaling factors (which are unique up to a positive scalar). This procedure is known as matrix scaling, and has found numerous applications in operations research, economics, image processing, and machine learning. In this work, we investigate the behavior of the scaling factors and the resulting scaled matrix when the matrix to be scaled is random. Specifically, letting $widetildeAinmathbb{R}^{MimesN}$ be a positive and bounded random matrix whose entries assume a certain type of independence, we provide a concentration inequality for the scaling factors of $widetildeA$ around those of $A=mathbbE[widetildeA]$. This result is employed to bound the convergence rate of the scaling factors of $widetildeA$ to those of $A$, as well as the concentration of the scaled version of $widetildeA$ around the scaled version of $A$ in operator norm, as $M,Nightarrowinfty$. When the entries of $widetildeA$ are independent, $M=N$, and all prescribed row and column sums are $1$ (i.e., doubly-stochastic matrix scaling), both of the previously-mentioned bounds are $mathcalO(sqrtlogN/N)$ with high probability. We demonstrate our results in several simulations.

Recommendations

• Matrix scaling limits in finitely many iterations
• Scaling of symmetric matrices by positive diagonal congruence
• Scaling Matrices to Prescribed Row and Column Maxima
• A Symmetry Preserving Algorithm for Matrix Scaling
• On the rate of convergence of deterministic and randomized RAS matrix scaling algorithms

Cites work

• A Comparative Study of Algorithms for Matrix Balancing
• A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
• Asymptotics for semidiscrete entropic optimal transport
• Central limit theorems for entropy-regularized optimal transport on finite spaces and statistical applications
• Concerning nonnegative matrices and doubly stochastic matrices
• Convergence of entropic schemes for optimal transport and gradient flows
• Diagonal Equivalence to Matrices with Prescribed Row and Column Sums
• Doubly stochastic normalization of the Gaussian kernel is robust to heteroskedastic noise
• Empirical regularized optimal transport: statistical theory and applications
• High-dimensional probability. An introduction with applications in data science
• Manifold learning with bi-stochastic kernels
• On information plus noise kernel random matrices
• Scaling of matrices to achieve specified row and column sums
• Spectral Convergence of Diffusion Maps: Improved Error Bounds and an Alternative Normalization
• Stability of entropic optimal transport and Schrödinger bridges
• Symmetrizing smoothing filters
• The collected works of Wassily Hoeffding. Ed. by N. I. Fisher and P. K. Sen
• The DAD Theorem for Arbitrary Row Sums
• The diagonal equivalence of a nonnegative matrix to a stochastic matrix
• The Sinkhorn–Knopp Algorithm: Convergence and Applications

Cited in

(3)

• On concentration of high-dimensional matrices with randomly signed entries
• Spectral analysis of matrix scaling and operator scaling
• The Dyson equalizer: adaptive noise stabilization for low-rank signal detection and recovery

This page was built for publication: Scaling positive random matrices: concentration and asymptotic convergence

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