Matrix Completion in Group Testing: Bounds and Simulations
The main goal of group testing is to identify a small number of defective items in a large population of items. A test on a subset of items is positive if the subset contains at least one defective item and negative otherwise. In non-adaptive design, all tests can be tested simultaneously and represented by a measurement matrix in which a row and a column represent a test and an item, respectively. An entry in row $i$ and column $j$ is 1 if item $j$ belongs to the test $i$ and is 0 otherwise. Given an unknown set of defective items, the objective is to design a measurement matrix such that, by observing its corresponding outcome vector, the defective items can be recovered efficiently. The basic trait of this approach is that the measurement matrix has remained unchanged throughout the course of generating the outcome vector and recovering defective items. In this paper, we study the case in which some entries in the measurement matrix are erased, called \emph{the missing measurement matrix}, before the recovery phase of the defective items, and our objective is to fully recover the measurement matrix from the missing measurement matrix. In particular, we show that some specific rows with erased entries provide information aiding the recovery while others do not. Given measurement matrices and erased entries follow the Bernoulli distribution, we show that before the erasing event happens, sampling sufficient sets of defective items and their corresponding outcome vectors can help us recover the measurement matrix from the missing measurement matrix.
Code (0)
등록된 구현이 없습니다.
Tasks
Matrix CompletionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
A Probably Approximately Correct Analysis of Group Testing Algorithms
We consider the problem of identifying the defectives from a population of items via a non-adaptive group testing framework with a random pooling-matrix design. We analyze the sufficient number of tests needed for approx…
Factor Group-Sparse Regularization for Efficient Low-Rank Matrix Recovery
This paper develops a new class of nonconvex regularizers for low-rank matrix recovery. Many regularizers are motivated as convex relaxations of the matrix rank function. Our new factor group-sparse regularizers are moti…
Low-Rank Matrix CompletionMatrix CompletionNonconvex Matrix Completion with Linearly Parameterized Factors
Techniques of matrix completion aim to impute a large portion of missing entries in a data matrix through a small portion of observed ones. In practice including collaborative filtering, prior information and special str…
Collaborative FilteringMatrix CompletionInformation-theoretic Bounds on Matrix Completion under Union of Subspaces Model
In this short note we extend some of the recent results on matrix completion under the assumption that the columns of the matrix can be grouped (clustered) into subspaces (not necessarily disjoint or independent). This m…
ClusteringMatrix CompletionMultiple Testing of Linear Forms for Noisy Matrix Completion
Many important tasks of large-scale recommender systems can be naturally cast as testing multiple linear forms for noisy matrix completion. These problems, however, present unique challenges because of the subtle bias-an…
Matrix CompletionRecommendation Systemsvalid