اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدA review of matrix scaling and Sinkhorns normal form for matrices and positive maps
57
0
0.0
(
0
)
تأليف
Martin Idel
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Given a nonnegative matrix $A$, can you find diagonal matrices $D_1,~D_2$ such that $D_1AD_2$ is doubly stochastic? The answer to this question is known as Sinkhorns theorem. It has been proved with a wide variety of methods, each presenting a variety of possible generalisations. Recently, generalisations such as to positive maps between matrix algebras have become more and more interesting for applications. This text gives a review of over 70 years of matrix scaling. The focus lies on the mathematical landscape surrounding the problem and its solution as well as the generalisation to positive maps and contains hardly any nontrivial unpublished results.
قيم البحث
اقرأ أيضاً
Given a totally positive matrix, can one insert a line (row or column) between two given lines while maintaining total positivity? This question was first posed and solved by Johnson and Smith who gave an algorithm that results in one possible line i
nsertion. In this work we revisit this problem. First we show that every totally positive matrix can be associated to a certain vertex-weighted graph in such a way that the entries of the matrix are equal to sums over certain paths in this graph. We call this graph a scaffolding of the matrix. We then use this to give a complete characterization of all possible line insertions as the strongly positive solutions to a given homogeneous system of linear equations.
Sinkhorn proved that every entry-wise positive matrix can be made doubly stochastic by multiplying with two diagonal matrices. In this note we prove a recently conjectured analogue for unitary matrices: every unitary can be decomposed into two diagon
al unitaries and one whose row- and column sums are equal to one. The proof is non-constructive and based on a reformulation in terms of symplectic topology. As a corollary, we obtain a decomposition of unitary matrices into an interlaced product of unitary diagonal matrices and discrete Fourier transformations. This provides a new decomposition of linear optics arrays into phase shifters and canonical multiports described by Fourier transformations.
Stochastic matrices and positive maps in matrix algebras proved to be very important tools for analysing classical and quantum systems. In particular they represent a natural set of transformations for classical and quantum states, respectively. Here
we introduce the notion of pseudo-stochastic matrices and consider their semigroup property. Unlike stochastic matrices, pseudo-stochastic matrices are permitted to have matrix elements which are negative while respecting the requirement that the sum of the elements of each column is one. They also allow for convex combinations, and carry a Lie group structure which permits the introduction of Lie algebra generators. The quantum analog of a pseudo-stochastic matrix exists and is called a pseudo-positive map. They have the property of transforming a subset of quantum states (characterized by maximal purity or minimal von Neumann entropy requirements) into quantum states. Examples of qubit dynamics connected with diamond sets of stochastic matrices and pseudo-positive maps are dealt with.
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 scali
ng, 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 $widetilde{A}inmathbb{R}^{Mtimes N}$ 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 $widetilde{A}$ around those of $A = mathbb{E}[widetilde{A}]$. This result is employed to bound the convergence rate of the scaling factors of $widetilde{A}$ to those of $A$, as well as the concentration of the scaled version of $widetilde{A}$ around the scaled version of $A$ in operator norm, as $M,Nrightarrowinfty$. When the entries of $widetilde{A}$ 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 $mathcal{O}(sqrt{log N / N})$ with high probability. We demonstrate our results in several simulations.
A matrix $A$ is totally positive (or non-negative) of order $k$, denoted $TP_k$ (or $TN_k$), if all minors of size $leq k$ are positive (or non-negative). It is well-known that such matrices are characterized by the variation diminishing property tog
ether with the sign non-reversal property. We do away with the former, and show that $A$ is $TP_k$ if and only if every submatrix formed from at most $k$ consecutive rows and columns has the sign non-reversal property. In fact this can be strengthened to only consider test vectors in $mathbb{R}^k$ with alternating signs. We also show a similar characterization for all $TN_k$ matrices - more strongly, both of these characterizations use a single vector (with alternating signs) for each square submatrix. These characterizations are novel, and similar in spirit to the fundamental results characterizing $TP$ matrices by Gantmacher-Krein [Compos. Math. 1937] and $P$-matrices by Gale-Nikaido [Math. Ann. 1965]. As an application, we study the interval hull $mathbb{I}(A,B)$ of two $m times n$ matrices $A=(a_{ij})$ and $B = (b_{ij})$. This is the collection of $C in mathbb{R}^{m times n}$ such that each $c_{ij}$ is between $a_{ij}$ and $b_{ij}$. Using the sign non-reversal property, we identify a two-element subset of $mathbb{I}(A,B)$ that detects the $TP_k$ property for all of $mathbb{I}(A,B)$ for arbitrary $k geq 1$. In particular, this provides a test for total positivity (of any order), simultaneously for an entire class of rectangular matrices. In parallel, we also provide a finite set to test the total non-negativity (of any order) of an interval hull $mathbb{I}(A,B)$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
