論文の概要: Matrix Completion in Group Testing: Bounds and Simulations

• arxiv url: http://arxiv.org/abs/2501.13780v2
• Date: Tue, 09 Sep 2025 04:06:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-10 14:38:26.743683
• Title: Matrix Completion in Group Testing: Bounds and Simulations
• Title（参考訳）: グループテストにおけるマトリックス補完:境界とシミュレーション
• Authors: Trung-Khang Tran, Thach V. Bui,
• Abstract要約: グループテストの目標は、少数の欠陥項目を集団内で特定することである。 この研究では、$mM$のいくつかのエントリが欠落している場合に対処し、測定行列 $mG$ が欠落する。 我々の目標は、利用可能なサンプルと結果ベクトルを使用して$mM$を$mG$から再構築することである。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: グループテストの目標は、少数の欠陥項目を集団内で特定することである。 非適応的な設定では、テストは事前に設計され、測定行列$\mM$で表される。 テストは、少なくとも1つの欠陥項目を含む場合、陽性である。 伝統的に、$\mM$はテストとリカバリの両方で固定されている。 この研究では、$\mM$ のいくつかのエントリが欠落している場合に対処し、測定行列 $\mG$ が欠落する。 我々の目標は、利用可能なサンプルと結果ベクトルを使用して$\mM$を$\mG$から再構築することです。 上記の問題はブール行列分解と行列完備化の間に交わされる問題であり、群検定(MCGT)問題における行列完備化(英語版)と呼ばれる。 正の整数 $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}$は、$\mM$のいくつかのエントリを消去することによって生成される行列である。 for $\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 operator。 グループテストの問題は、$\mM$と$\mY$が与えられたときに$\mX$を見つけることであるが、我々の目標は$\mM$が$\mY、\mX$が$\mG$を回収することである。 MCGT問題はNP完全であることを最初に証明する。 次に、欠落したエントリを持つ行がリカバリに役立ち、他の行はリカバリに役立ちません。 ベルヌーイ測度行列の場合、より大きい$s$は、$\mM$を回収できる確率を高くする。 次に、特定の復号アルゴリズムのバウンダリをインスタンス化し、シミュレーションにより検証し、標準的な行列補完法やブール行列分解法よりも優れていることを示す。

関連論文リスト

• Spectral Estimation with Free Decompression [47.81955761814048]
  非常に大きな(可逆な)行列のスペクトルを推定する「自由減圧」の新たな手法を提案する。 提案手法は, 極大(非可逆)行列の固有スペクトルを推定するために, 小型サブマトリクスの実験的スペクトル密度から外挿することができる。
  論文  参考訳（メタデータ） (2025-06-13T17:49:25Z)
• Guarantees of a Preconditioned Subgradient Algorithm for Overparameterized Asymmetric Low-rank Matrix Recovery [8.722715843502321]
  非対称行列のランクに依存しない線形収束率を, 粗悪な汚職の存在下で初めて提供する。 この手法を(ロバスト)マトリクスセンシングに適用することにより、測定演算子が混合ノルム制限等尺性を満たす場合の利点を明らかにする。
  論文  参考訳（メタデータ） (2024-10-22T08:58:44Z)
• Statistical Inference For Noisy Matrix Completion Incorporating Auxiliary Information [3.9748528039819977]
  本稿では,半教師付きモデルにおける雑音行列補完の統計的推測について検討する。 検討した文脈において,反復最小二乗(LS)推定手法を適用した。 提案手法は数回の反復しか必要とせず、結果として得られる低ランク行列と係数行列のエントリーワイズ推定器は正規分布を持つことが保証されている。
  論文  参考訳（メタデータ） (2024-03-22T01:06:36Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  低ランク構造を持つ強化学習(RL)における行列推定問題について検討した。 低ランク帯では、回収される行列は期待される腕の報酬を指定し、低ランクマルコフ決定プロセス(MDP)では、例えばMDPの遷移カーネルを特徴付ける。 簡単なスペクトルベースの行列推定手法は,行列の特異部分空間を効率よく復元し,ほぼ最小の入力誤差を示すことを示す。
  論文  参考訳（メタデータ） (2023-10-10T17:06:41Z)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  行列の欠落値を$XTX$で計算する自然アルゴリズムを提案する。 合成データの一方の回収と低被覆ゲノムシークエンシングについて,本アルゴリズムの評価を行った。
  論文  参考訳（メタデータ） (2023-06-06T22:35:16Z)
• Test Set Sizing Via Random Matrix Theory [91.3755431537592]
  本稿ではランダム行列理論の手法を用いて、単純な線形回帰に対して理想的なトレーニング-テストデータ分割を求める。 それは「理想」を整合性計量を満たすものとして定義し、すなわち経験的モデル誤差は実際の測定ノイズである。 本論文は,任意のモデルのトレーニングとテストサイズを,真に最適な方法で解決した最初の論文である。
  論文  参考訳（メタデータ） (2021-12-11T13:18:33Z)
• Causal Matrix Completion [15.599296461516984]
  マトリックス完備化(Matrix completion)は、ノイズ観測のスパース部分集合から基礎となる行列を復元する研究である。 伝統的に、行列の成分は「ランダムに完全に欠落している」と仮定される。
  論文  参考訳（メタデータ） (2021-09-30T14:17:56Z)
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors [54.936314353063494]
  我々は,ロバストな1ビット圧縮センシングのための相関に基づく最適化アルゴリズムのリカバリ保証を提供する。 我々は,実用的な反復アルゴリズムを用いて,画像データセットの数値実験を行い,結果の相関付けを行う。
  論文  参考訳（メタデータ） (2021-08-08T05:28:06Z)
• Support Recovery of Sparse Signals from a Mixture of Linear Measurements [48.556633593447465]
  簡単な測定からスパースベクトルの支持を回復することは、広く研究されている問題である。 この問題の一般化を考える:線形回帰の混合と線形分類器の混合である。 我々は$k, log n$ および quasi-polynomial を $ell$ で多くの測定値を用いて、混合中の未知ベクトルの全てのサポートを回復するアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2021-06-10T17:48:13Z)
• Rank-One Measurements of Low-Rank PSD Matrices Have Small Feasible Sets [26.42912954945887]
  低ランク正正半定値(psd)行列センシング問題に対する解決定における制約集合の役割について検討した。 低ランク正則化を含まずにpsd行列の復元に円錐射影法を適用して実用的意義を示す。
  論文  参考訳（メタデータ） (2020-12-17T17:23:27Z)
• Leveraged Matrix Completion with Noise [84.20092979053119]
  未知の$ntimes n$ matrix of rank $r$ from just $mathcalO(nrlog2 (n))$ entry. 我々の証明は、ゴルフスキームに基づく十分な最適条件を記述する新しいアプローチによって支持されている。
  論文  参考訳（メタデータ） (2020-11-11T16:25:45Z)
• Adversarial Robust Low Rank Matrix Estimation: Compressed Sensing and Matrix Completion [2.0257616108612373]
  部分的な問題としてラッソを含む行列圧縮センシングと行列補完を扱う。 本稿では,ハマー損失関数と核ノルムのペナル化を組み合わせた単純な統一手法を提案する。
  論文  参考訳（メタデータ） (2020-10-25T02:32:07Z)
• Relative Error Bound Analysis for Nuclear Norm Regularized Matrix Completion [101.83262280224729]
  我々は、原子核ノルム正規化行列補完に対する相対誤差を開発する。 未知行列の最適低ランク近似を回復するための相対上界を導出する。
  論文  参考訳（メタデータ） (2015-04-26T13:12:16Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。