ผลต่างระหว่างรุ่นของ "Sgt/lecture9"

จาก Theory Wiki
ไปยังการนำทาง ไปยังการค้นหา
 
(ไม่แสดง 10 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน)
แถว 74: แถว 74:
 
ที่ approximate <math>K_{n,n}</math> นั่นคือ
 
ที่ approximate <math>K_{n,n}</math> นั่นคือ
 
:<math>(1-\epsilon)\frac{d}{n}K_{n,n} \preceq G \preceq (1+\epsilon)\frac{d}{n}K_{n,n}</math>
 
:<math>(1-\epsilon)\frac{d}{n}K_{n,n} \preceq G \preceq (1+\epsilon)\frac{d}{n}K_{n,n}</math>
 +
 +
นั่นคือ eigenvalue <math>\lambda_1\leq\lambda_2\leq\cdots\leq\lambda_{2n}</math> ของ Laplacian ของกราฟ G มีคุณสมบัติดังนี้
 +
<math>\lambda_1 = 0\ ,\ \lambda_{2n} = 2d\ ,\ |\lambda_i-d|\leq \epsilon d\ ;\ 1 < i < 2n</math>
 +
 +
เราสามารถสร้างกราฟที่มีคุณสมบัติตามต้องการได้โดยการสร้าง double-cover ของ expander graph โดยนิยามดังนี้
 +
 +
กราฟ H เป็น double-cover ของกราฟ G เมื่อ H เป็นกราฟที่มีจำนวนโหนดและเส้นเชื่อมเป็นสองเท่าของ G โดยสำหรับทุกโหนด u ของ G
 +
กราฟ H จะมีโหนด <math>u_0,u_1</math>
 +
 +
และสำหรับเส้นเชื่อม <math>(u,v)</math> ใน G จะมีเส้นเชื่อมใน H สองเส้น <math>(u_0,v_1),(u_1,v_0)</math> และการบ้านในสัปดาห์นี้คือ การพิสูจน์ข้อความด้านล่าง
 +
{{กล่องทฤษฎีบท|ให้ H เป็น double-cover ของ G จะได้ว่าสำหรับทุก eigenvalue <math>\lambda_i</math> ของ Laplacian ของ G จะได้ว่า
 +
Laplacian ของ H จะมี eigenvalue ที่มีค่าเท่ากับ <math>\lambda_i</math> และ <math>|2d - \lambda_i|</math>}}
 +
 +
ในสัปดาห์นี้ เราพูดถึงทฤษฎีบทเพิ่มอีกสองทฤษฎีบท
 +
 +
{{กล่องทฤษฎีบท|ให้ <math>G = (U \cup V,E)</math> เป็น d-regular bipartite graph ที่ approximate <math>\frac{d}{n}K_{n,n}</math>
 +
 +
จะได้ว่าสำหรับเซต <math>S \subset U</math> และ <math>T \subset V</math> ใดใด
 +
:<math>\Bigl|\ |E(S,T)| - \frac{d}{n}|S| |T|\Bigr|\ \leq\ \epsilon d\sqrt{|S| |T|}</math>}}
 +
 +
และจากทฤษฎีบทด้านบนเราได้ทฤษฎีบทนี้
 +
 +
{{กล่องทฤษฎีบท|ให้ <math>|S| = \sigma n</math> และ <math>|T| = \tau n</math> ดีกรีเฉลี่ยของ <math>G(S \cup T)</math> มีค่าไม่เกิน <math>\frac{2d\sigma\tau}{\sigma + \tau} + \epsilon d</math> }}

รุ่นแก้ไขปัจจุบันเมื่อ 10:56, 22 เมษายน 2558

Spectral Graph Theory

  1. บทนำและทบทวนพีชคณิตเชิงเส้น (ณัฐวุฒิ)
  2. คุณสมบัติของ Eigenvalue ต่อกราฟ (ธานี,ณัฐวุฒิ)
  3. คุณสมบัติของ Eigenvalue ต่อกราฟ[2] (ภัทร)
  4. คุณสมบัติของ Eigenvalue ลำดับที่สองบนกราฟต่างๆ (ธานี)
  5. Cheeger Inequality (ศุภชวาล)
  6. การทดลอง Cheeger Inequality และ Effective Resistance (ธานี)
  7. Random Walks และ Psuedo Random Generator (ศุภชวาล)
  8. Psuedo Random Generator[2] (ภัทร)
  9. Coding Theory และ Expander code (ธานี)
  10. Expander graph from Linear coding (ภัทร)
  11. Chebyshev polynomial (ศุภชวาล)
  12. Preconditioning (ธานี)

แก้ไขกล่องนี้แก้ไขสารบัญ

บันทึกคำบรรยายวิชา Spectral graph theory นี้ เป็นบันทึกที่นิสิตเขียนขึ้น เนื้อหาโดยมากยังไม่ผ่านการตรวจสอบอย่างละเอียด การนำไปใช้ควรระมัดระวัง

Coding Theory

เราต้องการส่งข้อมูลขนาด m บิท แต่ระหว่างการส่งอาจจะเกิดความผิดพลาดทำให้บางบิทไม่ถูกต้อง จึงมีการคิดการส่งเพื่อให้สามารถตรวจจับ / แก้ไขความผิดพลาดได้ โดยส่งข้อมูลที่ encode แล้วและมีขนาด n บิท นั่นคือ

Hamming Code คือการ encode ข้อมูลขนาด 4 บิทไปเป็นข้อมูล 7 บิท โดยสามารถรับประกันได้ว่า ถ้าข้อมูลผิดพลาดไปไม่เกิน 1 บิท จะสามารถตรวจจับและแก้ไขได้ โดยให้ข้อมูลอยู่ที่บิทที่ 3,5,6,7 และ ให้

1.บิทที่ 4 เป็น XOR ของบิทที่ 5,6,7

2.บิทที่ 2 เป็น XOR ของบิทที่ 3,6,7

3.บิทที่ 1 เป็น XOR ของบิทที่ 3,5,7

ให้ แทนบิทที่ i เราสามารถตรวจจับ/แก้ไขความผิดพลาดไม่เกินหนึ่งบิทได้ดังนี้

a = XOR XOR XOR , b = XOR XOR XOR , c = XOR XOR XOR

ถ้า a,b,c ไม่เท่ากับศูนย์ บิทที่ผิดพลาดคือบิทที่

ซึ่งการสร้าง codeword แบบใดๆนั้นจะมีค่าสองค่าที่ใช้บอกความ"ดี" ของการสร้างนั้นๆ ได้แก่ ค่าอัตราส่วนระหว่างความยาว message ต่อความยาว codeword (เรียกว่า rate)

และค่า Hamming Distance คือจำนวนบิทที่แตกต่างกันที่น้อยที่สุดของคู่ codeword ใดๆ ซึ่งเป็น upperbound ของ จำนวนบิทที่สามารถ correction ได้

เช่น การสร้าง codeword หนึ่งๆ มี Hamming distance เป็น d การสร้างแบบนั้นจะไม่สามารถ correct message ที่ผิดพลาดเกิน d/2 บิทได้ และนิยาม minimum relative distance คือค่า d/n (Hamming distance ต่อความยาว codeword)

เราจะเรียกกระบวนการสร้าง codeword หนึ่งๆว่า asymtotically good ถ้า ไม่ว่า message จะมีความยาวเพิ่มขึ้นอย่างไร ค่า rate และ minimum relative distance จะมากกว่าค่าคงที่ค่าหนึ่งเสมอ

Random Linear Code

ในส่วนนี้ เราจะแสดงให้เห็นว่าถ้าหากเราเขียน message ให้อยู่ในรูปเวคเตอร์ v และสุ่มเมทริกซ์ M ขึ้นมาเพื่อเป็นเมทริกซ์ที่ใช้สร้าง codeword แล้ว

ด้วยความน่าจะเป็นที่สูง เมทริกซ์นั้นจะมีคุณสมบัติ asymtotically good

สุ่มเมทริกซ์ขนาด n แถว m หลัก จะได้ว่าสำหรับค่า d ใดๆ ความน่าจะเป็นที่เมทริกซ์นั้นจะสร้าง codeword ขนาด n สำหรับ message ขนาด m ที่มี minimum distance อย่างน้อย d มีไม่น้อยกว่า


การพิจารณาค่า distance ต่ำสุด เราสามารถ simplify ได้โดยการพิจารณาว่า สำหรับ message ในรูปเวคเตอร์ b ไม่เท่ากับศูนย์ใดๆ จำนวนบิทที่เป็นค่า 1 มีน้อยที่สุดกี่บิท

พิจารณาแต่ละค่าใน Mb เราพบว่าค่านั้นๆ จะเป็น 0 ด้วยความน่าจะเป็น 1/2 เนื่องจาก M สุ่มแบบ uniform ดังนั้น ความน่าจะเป็นที่ Mb สำหรับ fixed b จะมีบิทที่เป็น 1 ไม่เกิน d บิทนั้น มีค่าเท่ากับ

และสำหรับทุก b เราใช้ union bound จึงได้ว่าความน่าจะเป็นที่ สุ่ม M ใดๆแล้ว ทำให้ทุก Mb สำหรับทุก message b มีบิท 1 น้อยกว่า d บิท มีค่าไม่ต่ำกว่า
จึงได้ตามที่ต้องการ
Littlebox.png

Reed-Solomon Code

อีกหนึ่งตัวอย่างของการทำ Error Correcting คือ Reed-Solomon Code

สำหรับจำนวนเฉพาะ p หนึ่งๆ และ message ขนาด m และนิยามฟังก์ชันพหุนาม

และ code word ขนาด n คือ

Reed-Solomon code จะ correct error ได้ p หน่วย

สังเกตุว่าหน่วยย่อยของ Reed-Solomon ไม่ใช่บิท เนื่องจาก correct ที่ระดับ element

หากจะใช้หน่วยเป็นบิท จะต้องแทน element ด้วย บิท และจะ correct ได้เพียง p บิท

Expander Code

ให้ แทน complete bipartite graph เราต้องการสร้าง d-regular graph G ที่ approximate นั่นคือ

นั่นคือ eigenvalue ของ Laplacian ของกราฟ G มีคุณสมบัติดังนี้

เราสามารถสร้างกราฟที่มีคุณสมบัติตามต้องการได้โดยการสร้าง double-cover ของ expander graph โดยนิยามดังนี้

กราฟ H เป็น double-cover ของกราฟ G เมื่อ H เป็นกราฟที่มีจำนวนโหนดและเส้นเชื่อมเป็นสองเท่าของ G โดยสำหรับทุกโหนด u ของ G กราฟ H จะมีโหนด

และสำหรับเส้นเชื่อม ใน G จะมีเส้นเชื่อมใน H สองเส้น และการบ้านในสัปดาห์นี้คือ การพิสูจน์ข้อความด้านล่าง

ให้ H เป็น double-cover ของ G จะได้ว่าสำหรับทุก eigenvalue ของ Laplacian ของ G จะได้ว่า Laplacian ของ H จะมี eigenvalue ที่มีค่าเท่ากับ และ

ในสัปดาห์นี้ เราพูดถึงทฤษฎีบทเพิ่มอีกสองทฤษฎีบท

ให้ เป็น d-regular bipartite graph ที่ approximate

จะได้ว่าสำหรับเซต และ ใดใด

และจากทฤษฎีบทด้านบนเราได้ทฤษฎีบทนี้

ให้ และ ดีกรีเฉลี่ยของ มีค่าไม่เกิน