Matrix Completion in Group Testing: Bounds and Simulations
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911143399784448 |
|---|---|
| author | Tran, Trung-Khang Bui, Thach V. |
| author_facet | Tran, Trung-Khang Bui, Thach V. |
| contents | The goal of group testing is to identify a small number of defective items within a large population. In the non-adaptive setting, tests are designed in advance and represented by a measurement matrix $\mM$, where rows correspond to tests and columns to items. A test is positive if it includes at least one defective item. Traditionally, $\mM$ remains fixed during both testing and recovery. In this work, we address the case where some entries of $\mM$ are missing, yielding a missing measurement matrix $\mG$. Our aim is to reconstruct $\mM$ from $\mG$ using available samples and their outcome vectors.
The above problem can be considered as a problem intersected between Boolean matrix factorization and matrix completion, called the matrix completion in group testing (MCGT) problem, as follows. Given positive integers $t,s,n$, let $\mY:=(y_{ij}) \in \{0, 1\}^{t \times s}$, $\mM:=(m_{ij}) \in \{0,1\}^{t \times n}$, $\mX:=(x_{ij}) \in \{0,1\}^{n \times s}$, and matrix $\mG \in \{0,1 \}^{t \times n}$ be a matrix generated from matrix $\mM$ by erasing some entries in $\mM$. Suppose $\mY:=\mM \odot \mX$, where an entry $y_{ij}:=\bigvee_{k=1}^n (m_{ik}\wedge x_{kj})$, and $\wedge$ and $\vee$ are AND and OR operators. Unlike the problem in group testing whose objective is to find $\mX$ when given $\mM$ and $\mY$, our objective is to recover $\mM$ given $\mY,\mX$, and $\mG$.
We first prove that the MCGT problem is NP-complete. Next, we show that certain rows with missing entries aid recovery while others do not. For Bernoulli measurement matrices, we establish that larger $s$ increases the higher the probability that $\mM$ can be recovered. We then instantiate our bounds for specific decoding algorithms and validate them through simulations, demonstrating superiority over standard matrix completion and Boolean matrix factorization methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_13780 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Matrix Completion in Group Testing: Bounds and Simulations Tran, Trung-Khang Bui, Thach V. Information Theory Machine Learning The goal of group testing is to identify a small number of defective items within a large population. In the non-adaptive setting, tests are designed in advance and represented by a measurement matrix $\mM$, where rows correspond to tests and columns to items. A test is positive if it includes at least one defective item. Traditionally, $\mM$ remains fixed during both testing and recovery. In this work, we address the case where some entries of $\mM$ are missing, yielding a missing measurement matrix $\mG$. Our aim is to reconstruct $\mM$ from $\mG$ using available samples and their outcome vectors. The above problem can be considered as a problem intersected between Boolean matrix factorization and matrix completion, called the matrix completion in group testing (MCGT) problem, as follows. Given positive integers $t,s,n$, let $\mY:=(y_{ij}) \in \{0, 1\}^{t \times s}$, $\mM:=(m_{ij}) \in \{0,1\}^{t \times n}$, $\mX:=(x_{ij}) \in \{0,1\}^{n \times s}$, and matrix $\mG \in \{0,1 \}^{t \times n}$ be a matrix generated from matrix $\mM$ by erasing some entries in $\mM$. Suppose $\mY:=\mM \odot \mX$, where an entry $y_{ij}:=\bigvee_{k=1}^n (m_{ik}\wedge x_{kj})$, and $\wedge$ and $\vee$ are AND and OR operators. Unlike the problem in group testing whose objective is to find $\mX$ when given $\mM$ and $\mY$, our objective is to recover $\mM$ given $\mY,\mX$, and $\mG$. We first prove that the MCGT problem is NP-complete. Next, we show that certain rows with missing entries aid recovery while others do not. For Bernoulli measurement matrices, we establish that larger $s$ increases the higher the probability that $\mM$ can be recovered. We then instantiate our bounds for specific decoding algorithms and validate them through simulations, demonstrating superiority over standard matrix completion and Boolean matrix factorization methods. |
| title | Matrix Completion in Group Testing: Bounds and Simulations |
| topic | Information Theory Machine Learning |
| url | https://arxiv.org/abs/2501.13780 |