Matrix Completion in Group Testing: Bounds and Simulations

• URL: http://arxiv.org/abs/2501.13780v2
• Date: Tue, 09 Sep 2025 04:06:50 GMT
• Title: Matrix Completion in Group Testing: Bounds and Simulations
• Authors: Trung-Khang Tran, Thach V. Bui,
• Abstract summary: The goal of group testing is to identify a small number of defective items within a large population.<n>In this work, we address the case where some entries of $mM$ are missing, yielding a missing measurement matrix $mG$.<n>Our aim is to reconstruct $mM$ from $mG$ using available samples and their outcome vectors.
• Score: 2.721477719641864
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Spectral Estimation with Free Decompression [47.81955761814048]
  We introduce a novel method of "free decompression" to estimate the spectrum of very large (impalpable) matrices.<n>Our method can be used to extrapolate from the empirical spectral densities of small submatrices to infer the eigenspectrum of extremely large (impalpable) matrices.
  arXiv  Detail & Related papers  (2025-06-13T17:49:25Z)
• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery [8.722715843502321]
  We provide for the first time, linear convergence rates independent of the rank of the sought asymmetric matrix in the presence of gross corruptions.<n>By applying our approach to (robust) matrix sensing, we highlight its merits when the measurement operator satisfies a mixed-norm restricted isometry property.
  arXiv  Detail & Related papers  (2024-10-22T08:58:44Z)
• Efficient Matrix Factorization Via Householder Reflections [2.3326951882644553]
  We show that the exact recovery of the factors $mathbfH$ and $mathbfX$ from $mathbfY$ is guaranteed with $Omega$ columns in $mathbfY$. We hope the techniques in this work help in developing alternate algorithms for dictionary learning.
  arXiv  Detail & Related papers  (2024-05-13T11:13:49Z)
• Statistical Inference For Noisy Matrix Completion Incorporating Auxiliary Information [3.9748528039819977]
  This paper investigates statistical inference for noisy matrix completion in a semi-supervised model. We apply an iterative least squares (LS) estimation approach in our considered context. We show that our method only needs a few iterations, and the resulting entry-wise estimators of the low-rank matrix and the coefficient matrix are guaranteed to have normal distributions.
  arXiv  Detail & Related papers  (2024-03-22T01:06:36Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  We study matrix estimation problems arising in reinforcement learning (RL) with low-rank structure. In low-rank bandits, the matrix to be recovered specifies the expected arm rewards, and for low-rank Markov Decision Processes (MDPs), it may for example characterize the transition kernel of the MDP. We show that simple spectral-based matrix estimation approaches efficiently recover the singular subspaces of the matrix and exhibit nearly-minimal entry-wise error.
  arXiv  Detail & Related papers  (2023-10-10T17:06:41Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  We propose a natural algorithm that involves imputing the missing values of the matrix $XTX$. We evaluate our algorithm on one-sided recovery of synthetic data and low-coverage genome sequencing.
  arXiv  Detail & Related papers  (2023-06-06T22:35:16Z)
• A General Algorithm for Solving Rank-one Matrix Sensing [15.543065204102714]
  The goal of matrix sensing is to recover a matrix $A_star in mathbbRn times n$, based on a sequence of measurements. In this paper, we relax that rank-$k$ assumption and solve a much more general matrix sensing problem.
  arXiv  Detail & Related papers  (2023-03-22T04:07:26Z)
• A Nearly-Optimal Bound for Fast Regression with $\ell_\infty$ Guarantee [16.409210914237086]
  Given a matrix $Ain mathbbRntimes d$ and a tensor $bin mathbbRn$, we consider the regression problem with $ell_infty$ guarantees. We show that in order to obtain such $ell_infty$ guarantee for $ell$ regression, one has to use sketching matrices that are dense. We also develop a novel analytical framework for $ell_infty$ guarantee regression that utilizes the Oblivious Coordinate-wise Embedding (OCE) property
  arXiv  Detail & Related papers  (2023-02-01T05:22:40Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• Test Set Sizing Via Random Matrix Theory [91.3755431537592]
  This paper uses techniques from Random Matrix Theory to find the ideal training-testing data split for a simple linear regression. It defines "ideal" as satisfying the integrity metric, i.e. the empirical model error is the actual measurement noise. This paper is the first to solve for the training and test size for any model in a way that is truly optimal.
  arXiv  Detail & Related papers  (2021-12-11T13:18:33Z)
• Low-rank Matrix Recovery With Unknown Correspondence [62.634051913953485]
  We show that it is possible to recover $M$ via solving a nuclear norm minimization problem under a proper low-rank condition on $M$, with provable non-asymptotic error bound for the recovery of $M$. Experiments on simulated data, the MovieLens 100K dataset and Yale B database show that $textM3textO achieves state-of-the-art performance over several baselines and can recover the ground-truth correspondence with high accuracy.
  arXiv  Detail & Related papers  (2021-10-15T09:27:50Z)
• Causal Matrix Completion [15.599296461516984]
  Matrix completion is the study of recovering an underlying matrix from a sparse subset of noisy observations. Traditionally, it is assumed that the entries of the matrix are "missing completely at random"
  arXiv  Detail & Related papers  (2021-09-30T14:17:56Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors [54.936314353063494]
  We provide recovery guarantees for a correlation-based optimization algorithm for robust 1-bit compressive sensing. We make use of a practical iterative algorithm, and perform numerical experiments on image datasets to corroborate our results.
  arXiv  Detail & Related papers  (2021-08-08T05:28:06Z)
• Chi-square and normal inference in high-dimensional multi-task regression [7.310043452300736]
  The paper proposes chi-square and normal methodologies for the unknown coefficient matrix $B*$ of size $ptimes T$ in a Multi-Task (MT) linear model.
  arXiv  Detail & Related papers  (2021-07-16T11:19:49Z)
• Support Recovery of Sparse Signals from a Mixture of Linear Measurements [48.556633593447465]
  Recovery of support of a sparse vector from simple measurements is a widely studied problem. We consider generalizations of this problem: mixtures of linear regressions, and mixtures of linear classifiers. We provide algorithms that use a number of measurements in $k, log n$ and quasi-polynomial in $ell$ to recover the support of all the unknown vectors in the mixture.
  arXiv  Detail & Related papers  (2021-06-10T17:48:13Z)
• Rank-One Measurements of Low-Rank PSD Matrices Have Small Feasible Sets [26.42912954945887]
  We study the role of the constraint set in determining the solution to low-rank, positive semidefinite (PSD) matrix sensing problems. We demonstrate practical implications by applying conic projection methods for PSD matrix recovery without incorporating low-rank regularization.
  arXiv  Detail & Related papers  (2020-12-17T17:23:27Z)
• Leveraged Matrix Completion with Noise [84.20092979053119]
  We show that we can provably recover an unknown $ntimes n$ matrix of rank $r$ from just about $mathcalO(nrlog2 (n))$ entries. Our proofs are supported by a novel approach that phrases sufficient optimality conditions based on the Golfing Scheme.
  arXiv  Detail & Related papers  (2020-11-11T16:25:45Z)
• Adversarial Robust Low Rank Matrix Estimation: Compressed Sensing and Matrix Completion [2.0257616108612373]
  We deal with matrix compressed sensing, including lasso as a partial problem, and matrix completion. We propose a simple unified approach based on a combination of the Huber loss function and the nuclear norm penalization.
  arXiv  Detail & Related papers  (2020-10-25T02:32:07Z)
• The Average-Case Time Complexity of Certifying the Restricted Isometry Property [66.65353643599899]
  In compressed sensing, the restricted isometry property (RIP) on $M times N$ sensing matrices guarantees efficient reconstruction of sparse vectors. We investigate the exact average-case time complexity of certifying the RIP property for $Mtimes N$ matrices with i.i.d. $mathcalN(0,1/M)$ entries.
  arXiv  Detail & Related papers  (2020-05-22T16:55:01Z)
• Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion [101.83262280224729]
  We develop a relative error bound for nuclear norm regularized matrix completion. We derive a relative upper bound for recovering the best low-rank approximation of the unknown matrix.
  arXiv  Detail & Related papers  (2015-04-26T13:12:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.