论文标题
通过矩阵缩放查找霍尔阻滞剂
Finding Hall blockers by matrix scaling
论文作者
论文摘要
对于给定的非负矩阵$ a =（a_ {ij}）$，矩阵缩放问题询问是否可以将$ a $缩放到双向随机矩阵$ d_1ad_2 $ for某些阳性对角线矩阵$ d_1，d_2 $。美元通过该算法，$ a $在且仅当与$ a $相关的两部分图具有完美匹配时，将限制为限制的双随机矩阵收敛。该属性可以决定在给定的两部分图$ g $中存在完美匹配，该属性与$ 0,1 $ -Matrix $ a_g $ .linial，Samorodnitsky和Wigderson一起标识，并且Wigderson显示$ o（n^2 \ log n）$ iTerations $ a_g $ iTerations $ a_g $ iTerations $ a_g $ iTeration $ a_g $ ncluct $ a_g $ decluct $ a_g $ ncluct $ a_g $ n $ g $ ncution $ g $是否具有完美匹配的匹配。这里$ n $是$ g $的颜色类别之一中的顶点。在本文中，我们显示了此结果的扩展：如果$ g $没有完美的匹配，则多项式的sindhorn迭代数字标识了霍尔阻止器 - 一个顶点子集$ x $，neighl enken nekinbors $γ（x）$ with $ | x | > |γ（x）| $。具体来说，我们表明$ o（n^2 \ log n）$迭代可以识别一个霍尔阻滞剂，并且进一步的多项式迭代还可以识别所有参数厅阻滞剂$ x $的最大化$（1-λ）| x | - λ|γ（x）| $ for $λ\在[0,1] $中。前者的结果基于对sindhorn算法的解释，作为对几何编程的交替最小化。后者是一种解释为KL-Divergence的交替最小化（Csiszár和Tusnády1984，Gietl和Reffel 2013）及其对非估算矩阵的限制行为（AAS 2014）。我们还将沉没的限制与参数网络流，多咪要的主要分区以及双分部分图的Dulmage-Mendelsohn分解。
For a given nonnegative matrix $A=(A_{ij})$, the matrix scaling problem asks whether $A$ can be scaled to a doubly stochastic matrix $D_1AD_2$ for some positive diagonal matrices $D_1,D_2$.The Sinkhorn algorithm is a simple iterative algorithm, which repeats row-normalization $A_{ij} \leftarrow A_{ij}/\sum_{j}A_{ij}$ and column-normalization $A_{ij} \leftarrow A_{ij}/\sum_{i}A_{ij}$ alternatively. By this algorithm, $A$ converges to a doubly stochastic matrix in limit if and only if the bipartite graph associated with $A$ has a perfect matching. This property can decide the existence of a perfect matching in a given bipartite graph $G$, which is identified with the $0,1$-matrix $A_G$.Linial, Samorodnitsky, and Wigderson showed that $O(n^2 \log n)$ iterations for $A_G$ decide whether $G$ has a perfect matching. Here $n$ is the number of vertices in one of the color classes of $G$. In this paper, we show an extension of this result:If $G$ has no perfect matching, then a polynomial number of the Sinkhorn iterations identifies a Hall blocker -- a vertex subset $X$ having neighbors $Γ(X)$ with $|X| > |Γ(X)|$. Specifically, we show that $O(n^2 \log n)$ iterations can identify one Hall blocker, and that further polynomial iterations can also identify all parametric Hall blockers $X$ of maximizing $(1-λ) |X| - λ|Γ(X)|$ for $λ\in [0,1]$.The former result is based on an interpretation of the Sinkhorn algorithm as alternating minimization for geometric programming. The latter is on an interpretation as alternating minimization for KL-divergence (Csiszár and Tusnády 1984, Gietl and Reffel 2013) and its limiting behavior for a nonscalable matrix (Aas 2014). We also relate the Sinkhorn limit with parametric network flow, principal partition of polymatroids, and the Dulmage-Mendelsohn decomposition of a bipartite graph.
