论文标题
定量组测试和随机矩阵等级
Quantitative Group Testing and the rank of random matrices
论文作者
论文摘要
给定一个随机的bernoulli矩阵$ a \ in \ {0,1 \}^{m \ times n} $，一个整数$ 0 <k <n $和向量$ y：= ax $，其中$ x \ in \ in \ {0,1 \} x $。较小的$ m $ IS更加困难。对于我们感兴趣的参数范围，已知的多项式时间算法需要$ m $的值，该算法大于$ k $。 在这项工作中，我们定义了一个看似更容易的问题，我们称为{\ em subset select}。给定与QGT相同的输入，子集选择中的目标是返回基因$ s \ subseteq [n] $的基数$ m $，因此对于所有$ i \ in [n] $，如果$ x_i = 1 $ then $ i \ in s $。我们表明，如果由$ s $索引的列定义的$ a $的Square subbatrix几乎是完整排名的，则从子集选择问题的解决方案中，我们可以在多项式时间中恢复，则解决方案$ x $ to qgt问题。我们猜想，对于每个多项式时间子集选择算法，所得的输出矩阵将满足所需的等级条件。我们证明了某些类别的算法的猜想。使用此减少，我们提供了一些如何改善已知QGT算法的示例。使用理论分析和仿真，我们证明了修改后的算法解决了QGT问题的$ M $小于原始算法所需的值。
Given a random Bernoulli matrix $ A\in \{0,1\}^{m\times n} $, an integer $ 0< k < n $ and the vector $ y:=Ax $, where $ x \in \{0,1\}^n $ is of Hamming weight $ k $, the objective in the {\em Quantitative Group Testing} (QGT) problem is to recover $ x $. This problem is more difficult the smaller $m$ is. For parameter ranges of interest to us, known polynomial time algorithms require values of $m$ that are much larger than $k$. In this work, we define a seemingly easier problem that we refer to as {\em Subset Select}. Given the same input as in QGT, the objective in Subset Select is to return a subset $ S \subseteq [n] $ of cardinality $ m $, such that for all $ i\in [n] $, if $ x_i = 1 $ then $ i\in S $. We show that if the square submatrix of $A$ defined by the columns indexed by $S$ has nearly full rank, then from the solution of the Subset Select problem we can recover in polynomial-time the solution $x$ to the QGT problem. We conjecture that for every polynomial time Subset Select algorithm, the resulting output matrix will satisfy the desired rank condition. We prove the conjecture for some classes of algorithms. Using this reduction, we provide some examples of how to improve known QGT algorithms. Using theoretical analysis and simulations, we demonstrate that the modified algorithms solve the QGT problem for values of $ m $ that are smaller than those required for the original algorithms.
