分離行列

数学において、論理行列はd -分離行列および/またはd -分離行列として記述されることがあります。これらの概念は、非適応型群検定という数学の分野において極めて重要な役割を果たします。

数学の文献では、d分離行列は重ね合わせコード^{[ 1 ]}またはd被覆フリー族^{[ 2 ]}とも呼ばれる。

陳と黄（2006）によると、^{[ 3 ]}

• 2 つのd列セットのブール値の合計が同じにならない場合、行列はd分離可能と言われます。
• 2 つのd以下の列のセットが同じブール値の合計を持たない場合、その行列は - 分離可能 (つまり、上線付きのd )であると言われます。${\displaystyle {\overline {d}}}$
• d列のどのセットもブール値の合計が他の単一の列のスーパーセットにならない場合、その行列はd分離であると言われます。

以下の関係は「よく知られている」ものである：^{[ 3 ]}

• すべての-分離行列は-分離行列でもある。^{[ 3 ]}${\displaystyle {\overline {d+1}}}$ ${\displaystyle d}$
• すべての-分離行列は-分離可能でもある。^{[ 3 ]}${\displaystyle d}$ ${\displaystyle {\overline {d}}}$
• すべての- 分離可能な行列は、- 分離可能でもあります (定義により)。${\displaystyle {\overline {d}}}$ ${\displaystyle d}$

具体的な例

次の行列は2分離可能です。これは、各列のペアの和が異なるためです。例えば、最初の2列のブール和（つまり、ビットごとのOR ）は です。この和は、行列内の他のどの列のペアの和としても得られません。 ${\displaystyle 6\times 8}$ ${\displaystyle 110000\lor 001100=111100}$

ただし、列 1、2、3 (つまり) の合計が列 1、4、5 の合計に等しいため、この行列は 3 分離可能ではありません。 ${\displaystyle 111111}$

この行列も-分離可能ではありません。なぜなら、列 1 と 8（つまり ）の和が列 1 のみの和に等しいからです。実際、すべての列がゼロである行列は、任意の に対して -分離可能になるはずがありません。 ${\displaystyle {\overline {2}}}$ ${\displaystyle 110000}$ ${\displaystyle {\overline {d}}}$ ${\displaystyle d\geq 1}$

${\displaystyle \quad \left[{\begin{array}{cccccccc}1&0&0&1&1&0&0&0\\1&0&0&0&1&0&1&0&0\\0&1&0&0&1&0&0&1&0&0\\0&1&0&0&1&0&0&1&0&0\\0&1&0&1&0&0&1&0&0\\\end{array}}\right]}$

次の行列は- 分離可能 (したがって 2 分離) ですが、3 分離ではありません。 ${\displaystyle 6\times 4}$ ${\displaystyle {\overline {3}}}$

${\displaystyle \quad \left[{\begin{array}{cccc}1&0&0&1\\1&0&1&0\\0&1&1&0\\0&1&0&0\\0&1&0&0\\0&0&0&1\\\end{array}}\right]}$

この行列から 3 列以下の列を選択する方法は 15 通りあり、それぞれの選択によってブール値の合計は異なります。

列	ブール値の合計		列	ブール値の合計
なし	000000		2,3	011110
1	110000		2,4	101101
2	001100		3,4	111011
3	011010		1、2、3	111110
4	100001		1,2,4	111101
1,2	111100		1,3,4	111011
1,3	111010		2,3,4	111111
1,4	110001

ただし、列 2、3、4 (つまり) の合計は列 1 (つまり ) のスーパーセットであるため、この行列は 3 分離しません。 ${\displaystyle 111111}$ ${\displaystyle 110000}$

d分離性のグループ検定への応用

非適応型グループ検定問題は、任意の商品集合に対して、その集合に不良品が含まれているかどうかを判定できる検定法が存在することを前提としています。n個の商品（そのうちd個は不良品）のバッチに含まれる不良品をすべて正確に特定できる一連のグループ分けを考え出すことが求められます。

行と列を持つ - 分離可能な行列は、不良品の数が正確にd 個であることがわかっている場合に、 t検定を使用してn個のバッチ内の不良品を見つける方法を簡潔に説明します。 ${\displaystyle d}$ ${\displaystyle t}$ ${\displaystyle n}$

行と列を持つ -分離行列(または、より一般的には任意の-分離行列) は、不良品の数がd以下であることがわかっている場合に、 t検定を使用してn個のバッチ内の不良品を見つける方法を簡潔に説明します。 ${\displaystyle d}$ ${\displaystyle {\overline {d}}}$ ${\displaystyle t}$ ${\displaystyle n}$

実用的な懸念と公表された結果

与えられたnとdに対して、最小のd分離可能行列の行数tは（現在の知識によれば）最小のd分離行列の行数tよりも小さくなる可能性があるが、漸近的にはそれらは互いに定数倍以内である。^{[ 3 ]}さらに、この行列を実際のテストに使用する場合、テスト結果（つまり、 のようなブール和）を欠陥項目のインデックス（つまり、そのブール和を生成する一意の列セット）に「デコード」できるアルゴリズムが必要である。任意のd分離行列に対しては、多項式時間のデコードアルゴリズムが知られており、単純なアルゴリズムは である。^{[ 4 ]}任意のd分離可能だがd分離ではない行列に対しては、最もよく知られているデコードアルゴリズムは指数時間である。^{[ 3 ]}${\displaystyle t\times n}$ ${\displaystyle t\times n}$ ${\displaystyle 111100}$ ${\displaystyle O(nt)}$

PoratとRothschild（2008）は、n列とn行のd分離行列を構築するための決定論的時間アルゴリズムを提示している。^{[ 5 ]}${\displaystyle O(nt)}$ ${\displaystyle \Theta (d^{2}\ln n)}$

参照

• グループテスト
• 連結コード
• 圧縮センシング

参考文献

1. De Bonis, Annalisa; Vaccaro, Ugo (2003). 「一般化重ね合わせ符号の構築と多重アクセスチャネルにおけるグループテストおよび競合解決への応用」.理論計算機科学. 306 ( 1–3 ): 223–243 . doi : 10.1016/S0304-3975(03)00281-0 . MR  2000175 .
2. Paul Erdős ; Péter Frankl ; Zoltán Füredi (1985). 「r個の他の集合の和集合によって覆われる集合がない有限集合の族」(PDF) . Israel Journal of Mathematics . 51 ( 1– 2): 79– 89. doi : 10.1007/BF02772959 . ISSN 0021-2172 . 
3. Hong-Bin Chen; Frank Hwang (2006-12-21). 「d-分離行列、d-分離行列、およびd-分離行列間のミッシングリンクの探究」 .離散応用数学. 155 (5): 662– 664. CiteSeerX 10.1.1.848.5161 . doi : 10.1016/j.dam.2006.10.009 . MR 2303978 .  
4. Piotr Indyk、Hung Q. Ngo、Atri Rudra (2010). 「効率的にデコード可能な非適応型グループテスト」.第21回ACM-SIAM離散アルゴリズムシンポジウム論文集. pp.  1126– 1142. doi : 10.1137/1.9781611973075.91 . hdl : 1721.1/63167 . ISBN 978-0-89871-701-3. ISSN  1071-9040 .
5. Ely Porat; Amir Rothschild (2008). 「明示的非適応型組み合わせ群テストスキーム」.第35回国際オートマトン・言語・プログラミングコロキウム (ICALP) 論文集: 748–759 . arXiv : 0712.3876 . Bibcode : 2007arXiv0712.3876P .

さらに読む

• 必須コーディング理論、第20章
• ディャチコフ、AG、ルイコフ、VV (1982)。選言コードの長さの制限。問題のあるペレダチ情報ii [情報伝達の問題]、18(3)、7–13。
• AG ディシュコフ、AM ラシャド、VV ルイコフ (1989)。重畳された距離コード。問題のある Upravlenija i Teorii Informacii [制御と情報理論の問題]、18(4)、237–250。
• Füredi, Zoltán (1996). 「r-被覆フリー族について」 .組合せ理論ジャーナル. シリーズA. 73 (1): 172– 173. doi : 10.1006/jcta.1996.0012 .