Matrix Completion in Group Testing: Bounds and Simulations

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:=(yij) ∈ 0, 1t × s, mM:=(mij) ∈ 0,1t × n, mX:=(xij) ∈ 0,1n × s, and matrix mG ∈ 0,1 t × n be a matrix generated from matrix mM by erasing some entries in mM. Suppose mY:=mM odot mX, where an entry yij:=bigveek=1n (mikwedge xkj), 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.