On Structural Rank and Resilience of Sparsity Patterns
On Structural Rank and Resilience of Sparsity Patterns
复制标题
DOI：
10.1109/tac.2022.3212013
复制
发表时间：
2021-07
影响因子：
6.8
通讯作者：
M. Belabbas;Xudong Chen;Daniel Zelazo
中科院分区：
文献类型：
--
作者：
M. Belabbas;Xudong Chen;Daniel Zelazo
$\mathbb {R}^{n \times m}$中的稀疏模式，对于$m\geq n$，是矩阵的向量子空间，其允许由$\mathbb {R}^{n \times m}$中的标准基向量组成的基。我们用一个含有$0/\星星$-元素的矩阵来表示稀疏模式，其中$\星星$-元素是任意的真实的数，0-元素等于0。我们说一个稀疏模式具有满结构秩，如果它包含的矩阵的最大秩是$n$。在这篇文章中，我们研究了具有完整结构秩的模式的弹性程度：我们解决了一些问题，例如在不降低结构秩的情况下可以删除多少$\星星$-条目，以及需要添加多少$\星星$-条目才能增加所述弹性程度以达到目标。我们的方法是将这些问题转化为适当定义的二部图上的最大流问题。基于这些翻译，我们提供的算法，解决问题的多项式时间。
A sparsity pattern in $\mathbb {R}^{n \times m}$, for $m\geq n$, is a vector subspace of matrices admitting a basis consisting of canonical basis vectors in $\mathbb {R}^{n \times m}$. We represent a sparsity pattern by a matrix with $0/\star$-entries, where $\star$-entries are arbitrary real numbers and 0-entries are equal to 0. We say that a sparsity pattern has full structural rank if the maximal rank of matrices contained in it is $n$. In this article, we investigate the degree of resilience of patterns with full structural rank: We address questions, such as how many $\star$-entries can be removed without decreasing the structural rank and, reciprocally, how many $\star$-entries one needs to add so as to increase the said degree of resilience to reach a target. Our approach goes by translating these questions into max-flow problems on appropriately defined bipartite graphs. Based on these translations, we provide algorithms that solve the problems in polynomial time.