อัลกอริทึมการส่งข้อความแบบอิงการตรวจสอบในการตรวจจับแบบบีบอัด

อัลก อริทึมการส่งข้อความแบบอิงการตรวจสอบ ( VB-MPAs ) ในการรับรู้แบบบีบอัด ( CS ) ซึ่งเป็นสาขาหนึ่งของการประมวลผลสัญญาณดิจิทัลที่เกี่ยวข้องกับการวัดสัญญาณแบบเบาบางเป็นวิธีการบางอย่างในการแก้ปัญหาการกู้คืนในการรับรู้แบบบีบอัดได้อย่างมีประสิทธิภาพ หนึ่งในเป้าหมายหลักของการรับรู้แบบบีบอัดคือกระบวนการกู้คืน โดยทั่วไปแล้ว กระบวนการกู้คืนในการรับรู้แบบบีบอัดเป็นวิธีการที่ประมาณสัญญาณดั้งเดิมโดยใช้ความรู้เกี่ยวกับสัญญาณที่ถูกบีบอัดและเมทริกซ์การวัด^{[ 1 ]}ในทางคณิตศาสตร์ กระบวนการกู้คืนในการรับรู้แบบบีบอัดคือการค้นหาวิธีแก้ปัญหาที่เบาบางที่สุดที่เป็นไปได้ของระบบสมการเชิงเส้น ที่ไม่สมบูรณ์ ขึ้น อยู่กับลักษณะของเมทริกซ์การวัด สามารถใช้วิธีการสร้างใหม่ที่แตกต่างกันได้ หากเมทริกซ์การวัดเป็นแบบเบาบาง วิธีที่มีประสิทธิภาพวิธีหนึ่งคือการใช้อัลกอริทึมการส่งข้อความสำหรับการกู้คืนสัญญาณ แม้ว่าจะมี วิธี การส่งข้อความที่จัดการกับเมทริกซ์หนาแน่น แต่ลักษณะของอัลกอริทึมเหล่านั้นก็แตกต่างจากอัลกอริทึมที่ทำงานกับเมทริกซ์แบบเบาบางในระดับหนึ่ง^{[ 1 ]}^{[ 2 ]}

ภาพรวม

ปัญหาหลักในกระบวนการกู้คืนข้อมูลใน CS คือการหาคำตอบที่เบาบางที่สุดเท่าที่จะเป็นไปได้สำหรับระบบสมการเชิงเส้นที่ไม่สมบูรณ์ต่อไปนี้ $Ax=y$ ที่ไหน $A$ คือเมทริกซ์การวัด $x$ คือสัญญาณต้นฉบับที่จะกู้คืนและ $y$ เป็นการบีบอัดสัญญาณที่ทราบแล้ว เมื่อเมทริกซ์ $A$ เนื่องจากเมทริกซ์นี้เป็นเมทริกซ์เบาบาง เราจึงสามารถแทนเมทริกซ์นี้ด้วยกราฟสองส่วนได้ $G=(V_{l}\คัพ V_{r},E)$ เพื่อความเข้าใจที่ดียิ่งขึ้น^{[ 2 ]}^{[ 3 ]}^{[ 4 ]}^{[ 5 ]} $V_{l}$ คือเซตของโหนดตัวแปรใน $G$ ซึ่งแสดงถึงชุดขององค์ประกอบของ $x$ และยัง $V_{r}$ คือเซตของโหนดตรวจสอบที่สอดคล้องกับเซตขององค์ประกอบของ $y$ นอกจากนี้ยังมีข้อได้เปรียบอีกด้วย $e=(u,v)$ ระหว่าง $u\in V_{l}$ และ $v\in V_{r}$ หากองค์ประกอบที่สอดคล้องกันใน $A$ มีค่าไม่เป็นศูนย์ กล่าวคือ $A_{v,u}\neq 0$ นอกจากนี้ น้ำหนักของขอบ $w(e)=A_{v,u}$ [ ⁶^{] นี่คือตัวอย่างของเมทริกซ์การ}^วัดแบบเบาบางไบนารีซึ่งน้ำหนักของขอบเป็นศูนย์หรือหนึ่ง

$A=\left[{\begin{array}{cccccccccccc}0&0&1&0&0&0&0&0&1&0&1&0\\0&0&0&1&0&1&0&1&0&0&0&0\\1&0&0&0&0&1&0&0&0&0&1&0\\1&1&1&0&0&0&0&0&0&0&0&0\\0&0&0&1&0&0&1&0&0&0&1&0&0&0&1\\0&0&0&0&0&0&0&0&1&1&1&0&0\\0&1&0&0&1&0&0&0&0&1&0&0\end{array}}\right]$

แนวคิดพื้นฐานเบื้องหลังอัลกอริธึมการส่งข้อความในวิทยาการคอมพิวเตอร์คือการส่งข้อความที่เหมาะสมระหว่างโหนดตัวแปร และตรวจสอบโหนดในลักษณะวนซ้ำเพื่อค้นหาสัญญาณได้อย่างมีประสิทธิภาพ $x$ ข้อความเหล่านี้แตกต่างกันสำหรับโหนดตัวแปรและโหนดตรวจสอบ อย่างไรก็ตาม ลักษณะพื้นฐานของข้อความสำหรับโหนดตัวแปรและโหนดตรวจสอบทั้งหมดจะเหมือนกันในอัลกอริธึมการส่งข้อความตามการตรวจสอบทั้งหมด^{[ 6 ]}ข้อความ $\mu ^{v}(v_{i}):~V_{l}\mapsto \mathbb {R} \times \{0,1\}$ แผ่ออกมาจากโหนดตัวแปร $v_{i}$ ประกอบด้วยค่าของโหนดตรวจสอบและตัวบ่งชี้ที่แสดงว่าโหนดตัวแปรได้รับการตรวจสอบแล้วหรือไม่ นอกจากนี้ยังมีข้อความต่างๆ อีกด้วย $\mu ^{c}(c_{i}):~V_{r}\mapsto \mathbb {R} \times \mathbb {Z} ^{+}$ เกิดจากโหนดตรวจสอบ $c_{i}$ ประกอบด้วยค่าของโหนดตรวจสอบและดีกรีที่เหลือของโหนดตรวจสอบในกราฟ^{[ 6 ]}^{[ 7 ]}

ในแต่ละรอบ โหนดตัวแปรและโหนดตรวจสอบทุกโหนดจะสร้างข้อความใหม่เพื่อส่งไปยังเพื่อนบ้านทั้งหมดโดยอิงจากข้อความที่ได้รับจากเพื่อนบ้านของตนเอง คุณสมบัติเฉพาะที่ของอัลกอริธึมการส่งข้อความนี้ทำให้สามารถนำไปใช้เป็นอัลกอริธึมการประมวลผลแบบขนานได้ และทำให้ความซับซ้อนของเวลาของอัลกอริธึมเหล่านี้มีประสิทธิภาพมาก^{[ 8 ]}

กฎการส่งต่อข้อความ

แหล่งที่มา: ^{[ 9 ]}

กฎทั่วไปของอัลกอริธึมการส่งข้อความแบบอิงการตรวจสอบทั้งหมดคือข้อเท็จจริงที่ว่าเมื่อโหนดตัวแปรได้รับการตรวจสอบแล้ว โหนดตัวแปรนี้สามารถถูกลบออกจากกราฟได้ และอัลกอริธึมสามารถดำเนินการเพื่อแก้ปัญหาส่วนที่เหลือของกราฟได้ อัลกอริธึมการส่งข้อความแบบอิงการตรวจสอบที่แตกต่างกันจะใช้การผสมผสานของกฎการตรวจสอบที่แตกต่างกัน^{[ 6 ]}

กฎการตรวจสอบมีดังต่อไปนี้:

โหนดตรวจสอบศูนย์ (ZCN): ^{[ 8 ]}หากมีโหนดตรวจสอบอย่างน้อยหนึ่งโหนดที่มีค่าเป็นศูนย์ในบริเวณใกล้เคียงของโหนดตัวแปร โหนดตัวแปรนี้ควรได้รับการตรวจสอบด้วยค่าเป็นศูนย์
โหนดตรวจสอบระดับ 1: (D1CN): ^{[ 8 ]}หากมีโหนดตรวจสอบที่มีระดับ 1 อย่างน้อยหนึ่งโหนดในบริเวณใกล้เคียงของโหนดตัวแปร โหนดตัวแปรนั้นควรได้รับการตรวจสอบด้วยค่าที่เลือกแบบสุ่มจากค่าของโหนดตรวจสอบระดับ 1 เหล่านั้น
โหนดตรวจสอบที่เท่ากัน (ECN): ^{[ 8 ]}หากมีโหนดตัวแปรเดียวที่เชื่อมต่อกับโหนดตรวจสอบอย่างน้อยสองโหนดขึ้นไปที่มีค่าไม่เป็นศูนย์เหมือนกัน ค่าของโหนดตัวแปรนั้นควรได้รับการตรวจสอบด้วยค่าทั่วไปของโหนดตรวจสอบเหล่านั้น นอกจากนี้ โหนดตัวแปรอื่นๆ ที่เชื่อมต่อกับโหนดตรวจสอบเหล่านี้เพียงบางส่วน (ไม่ใช่ทั้งหมด) ควรได้รับการตรวจสอบด้วยค่าศูนย์

กฎการส่งข้อความที่ระบุไว้ข้างต้นเป็นกฎพื้นฐานและเป็นกฎเดียวที่ควรใช้ในอัลกอริธึมการส่งข้อความแบบอิงการตรวจสอบใดๆ แสดงให้เห็นว่ากฎง่ายๆ เหล่านี้สามารถกู้คืนสัญญาณต้นฉบับได้อย่างมีประสิทธิภาพหากตรงตามเงื่อนไขบางประการ^{[ 8 ]}^{[ 6 ]}

อัลกอริทึม

มีอัลกอริธึมสี่ตัวที่รู้จักกันในชื่อ VB-MPA ได้แก่ Genie, LM, XH และ SBB ^{[ 6 ]}อัลกอริธึมทั้งหมดนี้ใช้กลยุทธ์เดียวกันในการกู้คืนสัญญาณดั้งเดิม อย่างไรก็ตาม พวกมันใช้การผสมผสานที่แตกต่างกันของกฎการส่งข้อความเพื่อตรวจสอบโหนดตัวแปร

อัลกอริทึม Genie

แหล่งที่มา: ^{[ 6 ]}

อัลกอริทึม Genie เป็นเกณฑ์มาตรฐานในหัวข้อนี้ ประการแรก อัลกอริทึม Genie ถือว่ามีความรู้เกี่ยวกับ เซต สนับสนุนของสัญญาณ กล่าวคือ เซตขององค์ประกอบที่ไม่เป็นศูนย์ของสัญญาณดั้งเดิม ด้วยความรู้นี้ Genie ไม่จำเป็นต้องสนใจโหนดตัวแปรศูนย์ในกราฟ และงานเดียวของอัลกอริทึม Genie คือการกู้คืนค่าขององค์ประกอบที่ไม่เป็นศูนย์ของสัญญาณดั้งเดิม แม้ว่า Genie จะไม่มีประโยชน์ในทางปฏิบัติ แต่ก็สามารถถือได้ว่าเป็นเกณฑ์มาตรฐานของปัญหา โดยเฉพาะอย่างยิ่งในแง่ที่ว่าอัลกอริทึมนี้มีประสิทธิภาพเหนือกว่าอัลกอริทึมอื่นๆ ในหมวดหมู่นี้ และเราสามารถวัดความสำเร็จของอัลกอริทึมหนึ่งๆ ได้โดยการเปรียบเทียบกับอัลกอริทึม Genie

เนื่องจาก Genie ต้องการค้นหาเฉพาะค่าขององค์ประกอบที่ไม่เป็นศูนย์ของสัญญาณเท่านั้น จึงไม่จำเป็นต้องใช้กฎที่รับผิดชอบโหนดตัวแปรที่มีค่าเป็นศูนย์ในอัลกอริธึมนี้ ดังนั้น Genie จึงใช้ D1CN เป็นกฎการตรวจสอบเพียงอย่างเดียว

อัลกอริทึม LM

อัลกอริทึมนี้แตกต่างจากอัลกอริทึม Genie ตรงที่ไม่มีความรู้เกี่ยวกับเซตสนับสนุนของสัญญาณ และใช้ D1CN และ ZCN ร่วมกันเพื่อแก้ปัญหากระบวนการกู้คืนใน CS อันที่จริง ZCN เป็นกฎที่พยายามตรวจสอบโหนดตัวแปรที่มีค่าเป็นศูนย์ และ D1CN รับผิดชอบโหนดตัวแปรที่มีค่าไม่เป็นศูนย์ การใช้งานอัลกอริทึมนี้คือเมื่อไม่มีเมทริกซ์ที่ไม่ใช่ไบนารี ในกรณีดังกล่าว การใช้กฎที่สามจะละเมิดธรรมชาติของความเป็นท้องถิ่นของอัลกอริทึม ปัญหานี้จะได้รับการพิจารณาในอัลกอริทึม SBB ^{[ 6 ]}^{[ 8 ]}

อัลกอริทึม XH

อัลกอริทึมนี้เหมือนกับ LM แต่ใช้ ECN แทน D1CN สำหรับการตรวจสอบโหนดตัวแปรที่ไม่เป็นศูนย์เท่านั้น หากองค์ประกอบที่ไม่เป็นศูนย์ของเมทริกซ์การวัดเป็นไบนารี อัลกอริทึมนี้จะไม่สามารถนำไปใช้ได้อย่างมีประสิทธิภาพ และความเป็นโลคัลของอัลกอริทึมจะถูกละเมิด^{[ 6 ]}

อัลกอริทึม SBB

แหล่งที่มา: ^{[ 6 ]}^{[ 9 ]}

อัลกอริทึมที่มีประสิทธิภาพมากที่สุดในทางปฏิบัติในบรรดาอัลกอริทึมการส่งข้อความตรวจสอบทั้งหมดคืออัลกอริทึม SBB ซึ่งใช้กฎการตรวจสอบทั้งหมดสำหรับการกู้คืนสัญญาณดั้งเดิม ในอัลกอริทึมนี้ D1CN และ ECN มีหน้าที่ตรวจสอบองค์ประกอบที่ไม่เป็นศูนย์ของสัญญาณ และ ZCN และ ECN จะตรวจสอบโหนดตัวแปรศูนย์

รหัสเทียมของ VB-MPA มีดังต่อไปนี้ ในอัลกอริทึมต่อไปนี้ $\mu _{i}$ แสดงถึง $i^{th}$ ส่วนประกอบของข้อความที่ส่งมาจากโหนดตัวแปรและโหนดตรวจสอบ $VN$ อันที่จริงแล้วมันคือตัวแปรที่เก็บป้ายกำกับของโหนดตัวแปรที่ได้รับการตรวจสอบแล้ว $VN'$ นอกจากนี้ยังใช้เพื่อเก็บชุดของโหนดตัวแปรที่ตรวจสอบแล้วในการวนซ้ำครั้งก่อน โดยใช้ตัวแปรทั้งสองนี้เพื่อดูว่ามีความคืบหน้าในจำนวนโหนดตัวแปรที่ตรวจสอบแล้วในอัลกอริทึมหรือไม่ และหากไม่มีความคืบหน้า อัลกอริทึมจะยุติลง^{[ 6 ]}^{[ 9 ]}

1 ฟังก์ชัน VB_MPA( เมทริกซ์การวัด A , เวกเตอร์บีบอัด y ): ^{[ 7 ]} 2  $\mu ^{c}(c):=(y(c),d_{c})~~\forall c\in V_{r}$  // การเริ่มต้นใช้งาน 3  $\mu ^{v}(v):=(0,0)~~\forall v\in V_{l}$  // การเริ่มต้นใช้งาน 4  $VN:=\emptyset$  // การเริ่มต้นใช้งาน 5  $VN':=\{-1\}$  // การเริ่มต้นใช้งาน 6 ในขณะที่( $VN'\neq VN$ ) // ลูปหลัก 7  $VN':=VN$  9 /*============================ ครึ่งรอบที่ 1 ของรอบที่ 1 ============================ */ 10 สำหรับทุกๆ $c\in V_{r}$  11  $value:=y(c)-\sum _{v\in {\mathcal {N}}(c)}{\mu _{2}^{v}(v)\mu _{1}^{v}(v)A(c,v)}$  12  $degree:=d_{c}-\sum _{v\in {\mathcal {N}}(c)}{\mu _{2}^{v}(v)}$  13  $\mu ^{c}(c):=(value,degree)$  14 สิ้นสุดสำหรับ 15 /*============================= รอบครึ่งที่ 2 ของรอบที่ 1 ============================ */ 16 สำหรับทุกๆ $v\in V_{r}\setminus VN$  17 update_rule (v,Algorithm) 18. ถ้าโหนดตัวแปร v ได้รับการตรวจสอบแล้ว 19 เพิ่ม v ลงใน VN 20 จบถ้า 21 จบสำหรับ 22 /*============================= รอบครึ่งที่ 1 ของรอบที่ 2 ============================ */ 23 สำหรับทุกๆ $c\in V_{r}$  24  $value:=y(c)-\sum _{v\in {\mathcal {N}}(c)}{\mu _{2}^{v}(v)\mu _{1}^{v}(v)A(c,v)}$  25  $degree:=d_{c}-\sum _{v\in {\mathcal {N}}(c)}{\mu _{2}^{v}(v)}$  26  $\mu ^{c}(c):=(value,degree)$  27 สิ้นสุดสำหรับ 28 /*============================= รอบที่ 2 ครึ่งรอบที่ 2 ============================ */ 29 สำหรับทุกๆ $v\in V_{l}\setminus VN$  30 ถ้า $\exists c\in {\mathcal {N}}(v):~\mu _{1}^{c}(c)=0$ จากนั้น 31  $\mu ^{v}(v):=(0,1)$  32 เพิ่ม v ลงใน VN 33 จบถ้า 34 จบสำหรับ 35 จบในขณะที่ 36 ส่งคืน $\mu _{1}^{v}(v)~~\forall v\in V_{l}$

ในอัลกอริธึมทั้งหมด ข้อความที่ส่งออกมาจากโหนดตรวจสอบจะเหมือนกัน อย่างไรก็ตาม เนื่องจากกฎการตรวจสอบแตกต่างกันสำหรับอัลกอริธึมต่างๆ ข้อความที่ผลิตโดยโหนดตัวแปรจึงจะแตกต่างกันในแต่ละอัลกอริธึม^{[ 6 ]}อัลกอริธึมที่ให้ไว้ข้างต้นใช้งานได้กับ VB-MPA ทั้งหมด และอัลกอริธึมต่างๆ ใช้กฎที่แตกต่างกันในรอบครึ่งที่ 2 ของรอบที่ 1 และ 2 ตัวอย่างเช่น อัลกอริธึม Genie ใช้กฎ D1CN ในรอบครึ่งที่ 2 ของรอบที่ 1 และในความเป็นจริง รอบครึ่งที่ 2 ของรอบที่ 2 ซึ่งใช้กฎ ZCN นั้นไม่มีประโยชน์ในอัลกอริธึม Genie อัลกอริธึม LM ใช้ D1CN ในรอบครึ่งที่ 2 ของรอบที่ 1 และอัลกอริธึม XH ใช้กฎ ECN ในขั้นตอนนี้แทน D1CN อัลกอริธึม SBB ยังใช้ทั้งกฎ D1CN และ ECN ในรอบครึ่งหลังของรอบที่ 1 กฎทั้งหมดเหล่านี้สามารถนำไปใช้ได้อย่างมีประสิทธิภาพใน ฟังก์ชัน update_ruleในรอบครึ่งหลังของรอบที่ 1

หลักฐานยืนยันความถูกต้อง

แม้ว่าจะไม่มีการรับประกันว่าอัลกอริธึมเหล่านี้จะประสบความสำเร็จในทุกกรณี แต่เราสามารถรับประกันได้ว่าหากโหนดตัวแปรบางส่วนได้รับการตรวจสอบในระหว่างอัลกอริธึมเหล่านี้ ค่าของโหนดตัวแปรเหล่านั้นจะถูกต้องเกือบแน่นอนเพื่อแสดงให้เห็นเช่นนั้น เพียงแค่แสดงให้เห็นว่ากฎการตรวจสอบทั้งหมดทำงานได้อย่างสมบูรณ์แบบและไม่มีการตรวจสอบที่ผิดพลาดก็ เพียงพอแล้ว ^{[ 6 ]}^{[ 8 ]}

ความถูกต้องของ ZCN

ในเชิงพีชคณิต กฎ ZCN กล่าวว่า ถ้าในระบบสมการเชิงเส้นด้านขวาของสมการเป็นศูนย์ ตัวแปรที่ไม่ทราบค่าทั้งหมดในสมการนั้นก็จะเป็น ศูนย์ ด้วยเช่นกันเนื่องจากสมมติว่าสัญญาณดั้งเดิมเป็นสัญญาณเบาบาง (sparse) นอกจากนี้ เรายังต้องสมมติด้วยว่าองค์ประกอบที่ไม่เป็นศูนย์ของสัญญาณนั้นถูกเลือกมาจากการแจกแจงแบบต่อเนื่องสมมติว่ามี $d$ ตัวแปรในสมการนั้น ถ้าบางส่วนของตัวแปรเหล่านั้นอยู่ใน $d-1$ ถ้าองค์ประกอบไม่เป็นศูนย์แล้วองค์ประกอบอื่นๆ ก็จะเป็นศูนย์เช่นกัน $d^{th}$ ค่าของโหนดตัวแปรควรมีค่าเป็นลบเท่ากับผลรวมของค่าเหล่านั้นพอดี $d-1$ โหนดตัวแปร หากเลือกองค์ประกอบที่ไม่เป็นศูนย์ของสัญญาณดั้งเดิมจากการกระจายแบบต่อเนื่องความน่าจะเป็นที่จะเกิดขึ้นจะเป็นศูนย์ ดังนั้นกฎ ZCN จึงทำงานได้อย่างสมบูรณ์แบบ^{[ 6 ]}^{[ 8 ]}

ความถูกต้องของ D1CN

D1CN กล่าวว่า หากโหนดตัวแปรเป็นตัวแปรที่ไม่ทราบค่าเพียงตัวเดียวในสมการ ค่าของตัวแปรนั้นจะเท่ากับด้านขวาของสมการนั้นในความเป็นจริง สมการที่มีตัวแปรที่ไม่ทราบค่าเพียงตัวเดียวคือโหนดตรวจสอบที่มีดีกรีหนึ่ง กล่าวคือ โหนดตรวจสอบที่มีโหนดตัวแปรที่ยังไม่ได้รับการตรวจสอบเพียงโหนดเดียวในบริเวณใกล้เคียง^{[ 6 ]}^{[ 8 ]}

ความถูกต้องของ ECN

กฎนี้มีสองส่วน ส่วนแรกเกี่ยวข้องกับองค์ประกอบที่ไม่เป็นศูนย์ของสัญญาณ ในขณะที่ส่วนที่สองเกี่ยวข้องกับองค์ประกอบที่เป็นศูนย์ของสัญญาณดั้งเดิม สำหรับส่วนแรกนั้น กล่าวว่า ถ้าเรามีสมการสองสมการขึ้นไปที่มีด้านขวา เหมือนกัน และถ้าเรามี ตัวแปรที่ไม่ทราบค่าเพียงตัวเดียว $v$ ถ้าตัวแปรตัวใดตัวหนึ่งเหมือนกันในสมการทั้งหมดเหล่านั้น ค่าของตัวแปรตัวนั้นควรจะเป็นค่าของด้านขวามือของสมการเหล่านั้น นอกจากนี้ ยังระบุว่าตัวแปรอื่นๆ ทั้งหมดในสมการเหล่านั้นควรเป็นศูนย์ สมมติว่าตัวแปรตัวใดตัวหนึ่งในนั้น $v'$ หากไม่ใช่ศูนย์ด้านขวามือของสมการซึ่งประกอบด้วยทั้งสองค่าจะ เป็นศูนย์ $v,v'$ ควรจะเป็น $x(v')+x(v)$ (เพื่อความง่าย ให้สมมติว่าน้ำหนักของขอบทั้งหมดเป็น 1 หรือ 0) นอกจากนี้ เนื่องจากเรารู้ว่า $v$ ถ้าตัวแปรเดียวที่ไม่ซ้ำกันในสมการทั้งหมดนี้ ก็ควรจะมีสมการเดียว $c$ ซึ่ง $v$ มีอยู่และ $v'$ ไม่มีอยู่จริง ในทางกลับกัน เรารู้ว่าด้านขวาของสมการเหล่านี้เหมือนกัน ดังนั้นด้านขวาของสมการ $c$ ควรจะเป็นด้วยเช่นกัน $x(v)+x(v')$ ถ้าเราเอาออก $v'$ จากสมการนี้ ผลรวมของตัวแปรที่ไม่ทราบค่าบางตัวควรจะมีค่าไม่เป็นศูนย์ $x(v')$ เนื่องจากองค์ประกอบที่ไม่เป็นศูนย์ของ $x$ ถูกเลือกแบบสุ่มจากการกระจายแบบต่อเนื่องความน่าจะเป็นที่ผลรวมนี้จะเท่ากับค่าที่แน่นอน $x(v')$ มีค่าเป็นศูนย์ ดังนั้นค่าของ จึง แทบจะแน่นอนว่า เป็นศูนย์ $v$ มีค่าเป็นศูนย์ และตัวแปรอื่นๆ ทั้งหมดในสมการเหล่านี้มีค่าเป็นศูนย์^{[ 6 ]}^{[ 8 ]}^{[ 7 ]}

เหลือเพียงสถานการณ์เดียวสำหรับส่วนที่สองของกฎ ECN เนื่องจากส่วนใหญ่ได้กล่าวถึงไปแล้วในส่วนแรก สถานการณ์นี้คือ เรามีสมการบางสมการที่มีด้านขวามือ เหมือนกัน แต่มีตัวแปรสองตัวขึ้นไปที่เหมือนกันในทุกสมการ ในกรณีนี้ เราไม่สามารถพูดอะไรเกี่ยวกับตัวแปรที่เหมือนกันเหล่านั้นได้ อย่างไรก็ตาม เราสามารถพูดได้ว่าตัวแปรอื่นๆ ทั้งหมดในสมการเหล่านั้นเป็นศูนย์ การพิสูจน์ข้อกล่าวอ้างนี้สามารถทำได้โดยการเปลี่ยนตัวแปรในสมการเหล่านั้น สมมติว่า $v_{1},v_{2},...,v_{q}$ ตัวแปรเหล่านี้เป็นโหนดตัวแปรทั่วไปในสมการเหล่านั้น ถ้าเรากำหนด $v'=v_{1}+v_{2}+...+v_{q}$ จากนั้นปัญหาจะเปลี่ยนไปเป็นส่วนแรกที่เรามีโหนดตัวแปรทั่วไปเพียงโหนดเดียวในสมการทั้งหมดเหล่านั้น ดังนั้น ด้วยเหตุผลเดียวกันกับในส่วนแรก เราจะเห็นว่าโหนดตัวแปรอื่นๆ ที่ไม่ใช่โหนดทั่วไปในสมการทั้งหมดเหล่านั้นสามารถตรวจสอบได้ว่ามีค่าเป็นศูนย์เกือบแน่นอน^{[ 6 ]}^{[ 8 ]}^{[ 7 ]}

เมื่อเลือกองค์ประกอบที่ไม่เป็นศูนย์ของเมทริกซ์การวัดแบบสุ่มจากการกระจายแบบต่อเนื่องจะสามารถแสดงได้ว่าหากโหนดตัวแปรหนึ่งได้รับข้อความเท่ากันหารด้วยน้ำหนักขอบจากเพื่อนบ้าน โหนดตัวแปรนี้จะเป็นตัวแปรที่ไม่ซ้ำกันเพียงตัวเดียวที่เชื่อมต่อกับโหนดตรวจสอบทั้งหมดเหล่านั้น ดังนั้นจึงสามารถใช้กฎโดยใช้วิธีการตัดสินใจแบบโลคอล และโหนดตัวแปรสามารถตรวจสอบตัวเองได้โดยไม่ต้องมีความรู้เพิ่มเติมเกี่ยวกับการเชื่อมต่ออื่นๆ ของโหนดตรวจสอบเหล่านั้น ยิ่งไปกว่านั้น ส่วนที่สองของกฎ ECN ไม่จำเป็นต้องนำไปใช้ เนื่องจากโหนดตัวแปรที่ตรวจสอบแล้วที่ไม่เป็นศูนย์ในกฎ ECN จะถูกลบออกจากกราฟแบบสองส่วนในการวนซ้ำครั้ง ถัดไป และกฎ ZCN จะเพียงพอที่จะตรวจสอบโหนดตัวแปรที่มีค่าเป็นศูนย์ทั้งหมดที่เหลืออยู่จากสมการเหล่านั้นที่มีด้านขวามือ เหมือนกัน โดยสรุปแล้ว เมื่อเลือกองค์ประกอบที่ไม่เป็นศูนย์ของเมทริกซ์การวัดจากการกระจายแบบต่อเนื่องอัลกอริทึม SBB และ XH ที่ใช้กฎ ECN สามารถนำไปใช้ได้อย่างมีประสิทธิภาพ^{[ 6 ]}

การวิเคราะห์เวลาการทำงาน

ลูปย่อยทุกลูปในลูปหลักของอัลกอริทึมสามารถประมวลผลได้บนโปรเซสเซอร์แบบขนานหากเราพิจารณาตัวแปรแต่ละตัวและโหนดตรวจสอบเป็นโปรเซสเซอร์แยกต่างหาก ดังนั้น ลูปย่อยทุกลูปในอัลกอริทึมจึงสามารถประมวลผลได้ในเวลาคงที่ $O(1)$ นอกจากนี้ เนื่องจากอัลกอริทึมจะสิ้นสุดลงเมื่อไม่มีความคืบหน้าในการตรวจสอบโหนดตัวแปร ดังนั้นในกรณีที่เลวร้ายที่สุด หากในแต่ละรอบของการวนซ้ำหลักมีโหนดตัวแปรที่ต้องตรวจสอบเพียงโหนดเดียว จำนวนครั้งสูงสุดที่การวนซ้ำหลักจะทำงานคือ $|V_{l}|$ ดังนั้น อัลกอริทึมทั้งหมดจะถูกดำเนินการในเวลา... $O(|V_{l}|)$ เวลา^[⁷^]

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

6

[ 7 ]

[ 8 ]

[ 9 ]