Matrix Chernoff bound
For certain applications in linear algebra, it is useful to know properties of the probability distribution of the largest eigenvalue of a finite sum of random matrices. Suppose is a finite sequence of random matrices. Analogous to the well-known Chernoff bound for sums of scalars, a bound on the following is sought for a given parameter t:
The following theorems answer this general question under various assumptions; these assumptions are named below by analogy to their classical, scalar counterparts. All of these theorems can be found in (Tropp 2010), as the specific application of a general result which is derived below. A summary of related works is given.
Matrix Gaussian and Rademacher series
Self-adjoint matrices case
Consider a finite sequence of fixed, self-adjoint matrices with dimension , and let be a finite sequence of independent standard normal or independent Rademacher random variables.
Then, for all ,
where
Rectangular case
Consider a finite sequence of fixed matrices with dimension , and let be a finite sequence of independent standard normal or independent Rademacher random variables. Define the variance parameter
Then, for all ,
Matrix Chernoff inequalities
The classical Chernoff bounds concern the sum of independent, nonnegative, and uniformly bounded random variables. In the matrix setting, the analogous theorem concerns a sum of positive-semidefinite random matrices subjected to a uniform eigenvalue bound.
Matrix Chernoff I
Consider a finite sequence of independent, random, self-adjoint matrices with dimension . Assume that each random matrix satisfies
almost surely.
Define
Then
Matrix Chernoff II
Consider a sequence of independent, random, self-adjoint matrices that satisfy
almost surely.
Compute the minimum and maximum eigenvalues of the average expectation,
Then
The binary information divergence is defined as
for .
Matrix Bennett and Bernstein inequalities
In the scalar setting, Bennett and Bernstein inequalities describe the upper tail of a sum of independent, zero-mean random variables that are either bounded or subexponential. In the matrix case, the analogous results concern a sum of zero-mean random matrices.
Bounded case
Consider a finite sequence of independent, random, self-adjoint matrices with dimension . Assume that each random matrix satisfies
almost surely.
Compute the norm of the total variance,
Then, the following chain of inequalities holds for all :
The function is defined as for .
Consider a sequence of independent and identically distributed random column vectors in . Assume that each random vector satisfies almost surely, and . Then, for all ,[1]
Subexponential case
Consider a finite sequence of independent, random, self-adjoint matrices with dimension . Assume that
for .
Compute the variance parameter,
Then, the following chain of inequalities holds for all :
Rectangular case
Consider a finite sequence ของเมทริกซ์สุ่มอิสระที่มีมิติสมมติว่าเมทริกซ์สุ่มแต่ละตัวเป็นไปตามเงื่อนไขต่อไปนี้
เกือบจะแน่นอน กำหนดพารามิเตอร์ความแปรปรวน
จากนั้น สำหรับทุกคน
ถือครอง
อสมการเมทริกซ์ Azuma, Hoeffding และ McDiarmid
เมทริกซ์ อาซูมะ
อสมการของ Azumaในรูปแบบสเกลาร์ระบุว่ามาร์ติงเกล แบบสเกลาร์ แสดงการกระจุกตัวแบบปกติรอบค่าเฉลี่ย และมาตราส่วนสำหรับการเบี่ยงเบนถูกควบคุมโดยช่วงกำลังสองสูงสุดทั้งหมดของลำดับความแตกต่าง ต่อไปนี้คือส่วนขยายในบริบทของเมทริกซ์
พิจารณาลำดับที่ปรับเปลี่ยนได้แบบจำกัดของเมทริกซ์สมมาตรที่มีมิติและลำดับที่กำหนดไว้ของเมทริกซ์สมมาตรในตัวเองที่ตรงตามเงื่อนไข
แทบจะแน่นอน
คำนวณค่าพารามิเตอร์ความแปรปรวน
จากนั้น สำหรับทุกคน
ค่าคงที่ 1/8 สามารถปรับปรุงให้เป็น 1/2 ได้เมื่อมีข้อมูลเพิ่มเติม กรณีหนึ่งเกิดขึ้นเมื่อแต่ละพจน์บวกมีสมมาตรแบบมีเงื่อนไข ตัวอย่างอื่นต้องอาศัยข้อสมมติฐานว่าการเดินทางไปทำงานแทบจะแน่นอนด้วย.
เมทริกซ์ โฮฟฟ์ดิง
การเพิ่มสมมติฐานว่าพจน์บวกในเมทริกซ์ Azuma เป็นอิสระต่อกัน จะทำให้ได้การขยายอสมการของ Hoeffding ในรูปแบบเมทริก ซ์
พิจารณาลำดับจำกัดประกอบด้วยเมทริกซ์อิสระ สุ่ม และสมมาตรในตัวเอง ที่มีมิติและปล่อยให้เป็นลำดับของเมทริกซ์สมมาตรคงที่ สมมติว่าเมทริกซ์สุ่มแต่ละตัวเป็นไปตามเงื่อนไขต่อไปนี้
แทบจะแน่นอน
จากนั้น สำหรับทุกคน
ที่ไหน
ผลลัพธ์ที่ดีขึ้นนี้ได้รับการกำหนดไว้ใน( Mackey et al. 2012 ) : สำหรับทุก
ที่ไหน
ผลต่างจำกัดของเมทริกซ์ (McDiarmid)
ในบริบทของสเกลาร์อสมการของ McDiarmidให้วิธีการทั่วไปวิธีหนึ่งในการกำหนดขอบเขตของความแตกต่างโดยการประยุกต์ใช้อสมการของ Azumaกับมาร์ติงเกลของ Doobนอกจากนี้ยังมีอสมการความแตกต่างที่มีขอบเขตในรูปแบบเมทริกซ์ด้วย
อนุญาตให้ เป็นกลุ่มของตัวแปรสุ่มอิสระ และให้เป็นฟังก์ชันที่แมปตัวแปรไปยังเมทริกซ์สมมาตรที่มีมิติพิจารณาลำดับต่อไปนี้ของเมทริกซ์สมมาตรคงที่ที่สอดคล้องกับเงื่อนไข
ที่ไหนและครอบคลุมค่าที่เป็นไปได้ทั้งหมดของสำหรับแต่ละดัชนีคำนวณค่าพารามิเตอร์ความแปรปรวน
จากนั้น สำหรับทุกคน
ที่ไหน.
มีการปรับปรุงผลลัพธ์นี้ใน( Paulin, Mackey & Tropp 2013 ) (ดูเพิ่มเติมใน( Paulin, Mackey & Tropp 2016 ) ): สำหรับทุก
ที่ไหนและ
การสำรวจทฤษฎีบทที่เกี่ยวข้อง
ขอบเขตแรกของประเภทนี้ได้มาจาก( Ahlswede & Winter 2003 )โปรดระลึกถึงทฤษฎีบทข้างต้นสำหรับขอบเขต Gaussian และ Rademacher ของเมทริกซ์สมมาตร : สำหรับลำดับจำกัดของเมทริกซ์คงที่แบบสมมาตรที่มีมิติและสำหรับลำดับจำกัดของตัวแปรสุ่มปกติมาตรฐาน อิสระ หรือตัวแปรสุ่มราเดมาเชอร์อิสระ จากนั้น
ที่ไหน
Ahlswede และ Winter จะให้ผลลัพธ์เดียวกัน ยกเว้นว่า...
- .
เมื่อเปรียบเทียบกันแล้วในทฤษฎีบทข้างต้น สลับที่กันได้และกล่าวคือ ค่าดังกล่าวเป็นค่าไอเกนที่ใหญ่ที่สุดของผลรวม ไม่ใช่ผลรวมของค่าไอเกนที่ใหญ่ที่สุด ค่านี้จะไม่มีวันมากกว่าค่าของ Ahlswede–Winter (ตามอสมการสามเหลี่ยมบรรทัดฐาน ) แต่สามารถมีค่าน้อยกว่ามากได้ ดังนั้น ทฤษฎีบทข้างต้นจึงให้ขอบเขตที่แน่นกว่าผลลัพธ์ของ Ahlswede–Winter
ผลงานหลักของ( Ahlswede & Winter 2003 )คือการขยายวิธีการแปลงลาปลาสที่ใช้ในการพิสูจน์ขอบเขตเชอร์นอฟแบบสเกลาร์ (ดู ขอบเขตเชอร์นอฟ # รูปแบบการบวก (ข้อผิดพลาดสัมบูรณ์) ) ไปสู่กรณีของเมทริกซ์สมมาตรในตัวเอง ขั้นตอนการคำนวณแสดงไว้ในการพิสูจน์ด้านล่าง งานวิจัยล่าสุดทั้งหมดในหัวข้อนี้ใช้ขั้นตอนเดียวกันนี้ และความแตกต่างหลักๆ มาจากขั้นตอนต่อมา Ahlswede & Winter ใช้ความไม่เท่าเทียมกันของโกลเด้น-ทอมป์สันในขณะที่ Tropp ( Tropp 2010 )ใช้ ทฤษฎีบท ของLieb
สมมติว่าเราต้องการเปลี่ยนแปลงความยาวของอนุกรม ( n ) และมิติของเมทริกซ์ ( d ) ในขณะที่รักษาด้านขวามือให้คงที่โดยประมาณ n จะต้องเปลี่ยนแปลงไปโดยประมาณตามลอการิทึมของdมีบทความหลายฉบับที่พยายามสร้างขอบเขตโดยไม่ขึ้นอยู่กับมิติ Rudelson และ Vershynin ( Rudelson & Vershynin 2007 )ให้ผลลัพธ์สำหรับเมทริกซ์ที่เป็นผลคูณภายนอกของเวกเตอร์สองตัว ( Magen & Zouzias 2010 ) ให้ผลลัพธ์ที่ไม่ขึ้นอยู่กับมิติสำหรับเมทริกซ์ที่มีอันดับต่ำผลลัพธ์ดั้งเดิมได้มาโดยอิสระจากแนวทางของ Ahlswede–Winter แต่( Oliveira 2010b )พิสูจน์ผลลัพธ์ที่คล้ายกันโดยใช้แนวทางของ Ahlswede–Winter
สุดท้าย Oliveira ( Oliveira 2010a )พิสูจน์ผลลัพธ์สำหรับเมทริกซ์มาร์ติงเกลโดยไม่ขึ้นกับกรอบงาน Ahlswede–Winter Tropp ( Tropp 2011 )ปรับปรุงผลลัพธ์เล็กน้อยโดยใช้กรอบงาน Ahlswede–Winter บทความนี้ไม่ได้นำเสนอผลลัพธ์ทั้งสองนี้
ที่มาและการพิสูจน์
อาลสเวเดและฤดูหนาว
ข้อ โต้แย้ง การแปลงลาปลาสที่พบใน( Ahlswede & Winter 2003 )เป็นผลลัพธ์ที่สำคัญในตัวมันเอง: ให้เป็นเมทริกซ์สมมาตรแบบสุ่ม จากนั้น
เพื่อพิสูจน์เรื่องนี้ ให้แก้ไข . แล้ว
อสมการรองสุดท้ายคืออสมการของมาร์คอฟอสมการสุดท้ายเป็นจริงเนื่องจากเนื่องจากปริมาณทางซ้ายสุดไม่ขึ้นอยู่กับค่าต่ำสุดเหนือยังคงเป็นขีดจำกัดสูงสุดสำหรับมัน
ดังนั้น ภารกิจของเราคือการทำความเข้าใจ อย่างไรก็ตาม เนื่องจากร่องรอยและความคาดหวังต่างก็เป็นเชิงเส้น เราจึงสามารถสลับลำดับกันได้ ดังนั้นจึงเพียงพอที่จะพิจารณาซึ่งเราเรียกว่าฟังก์ชันก่อกำเนิดเมทริกซ์ นี่คือจุดที่วิธีการของ( Ahlswede & Winter 2003 )และ( Tropp 2010 )แตกต่างกัน การนำเสนอต่อไปนี้เป็นไปตาม( Ahlswede & Winter 2003 )
อสมการโกลเด้น-ทอมป์สันบ่งชี้ว่า
- ซึ่งเราได้ใช้ความเป็นเส้นตรงของค่าคาดหวังหลายครั้ง
สมมติเราสามารถหาขอบเขตบนสำหรับโดยการทำซ้ำผลลัพธ์นี้ โดยสังเกตว่า, แล้ว
เมื่อทำซ้ำเช่นนี้ เราจะได้
จนถึงตอนนี้ เราพบขอบเขตที่มีค่าต่ำสุดมากกว่าในทางกลับกัน สิ่งนี้สามารถจำกัดได้ อย่างไรก็ตาม เราสามารถเห็นได้ว่าขอบเขตของ Ahlswede–Winter เกิดขึ้นจากผลรวมของค่าลักษณะเฉพาะที่ใหญ่ที่สุด
ทรอปป์
ผลงานสำคัญของ( Tropp 2010 )คือการประยุกต์ใช้ทฤษฎีบทของ Liebซึ่ง( Ahlswede & Winter 2003 )ได้ประยุกต์ใช้ความไม่เท่าเทียมกันของ Golden–Thompsonบทสรุปของ Tropp มีดังนี้: ถ้าเป็นเมทริกซ์สมมาตรคงที่ และถ้าเมทริกซ์สมมาตรแบบสุ่มนั้น
พิสูจน์: ให้จากนั้นทฤษฎีบทของ Lieb ก็บอกเราว่า
เป็นฟังก์ชันเว้า ขั้นตอนสุดท้ายคือการใช้ความไม่เท่าเทียมของเจนเซ่นเพื่อย้ายค่าคาดหวังเข้าไปภายในฟังก์ชัน:
นี่คือผลลัพธ์หลักของงานวิจัยนี้: คุณสมบัติการบวกย่อยของลอการิทึมของฟังก์ชันก่อกำเนิดเมทริกซ์
คุณสมบัติการบวกย่อยของ log mgf
อนุญาตให้ เป็นลำดับจำกัดของเมทริกซ์สมมาตรแบบสุ่มที่เป็นอิสระต่อกัน แล้วสำหรับทุก ๆ,
หลักฐาน: เพียงแค่ปล่อยก็เพียงพอแล้วเมื่อขยายความนิยาม เราจำเป็นต้องแสดงให้เห็นว่า
เพื่อพิสูจน์ให้เสร็จสมบูรณ์ เราจะใช้กฎของความคาดหวังรวมให้เป็นความคาดหวังที่ขึ้นอยู่กับเงื่อนไขเนื่องจากเราถือว่าทั้งหมดเป็นอิสระต่อกัน
กำหนด.
สุดท้ายนี้ เรามี
โดยที่ในทุกขั้นตอน m เราใช้บทสรุปของ Tropp ร่วมกับ
หางของเจ้านายถูกมัดไว้
ต่อไปนี้เป็นผลลัพธ์โดยตรงจากผลลัพธ์ก่อนหน้า:
ทฤษฎีบททั้งหมดที่กล่าวมาข้างต้นได้มาจากการจำกัดค่านี้ โดยทฤษฎีบทเหล่านั้นประกอบด้วยวิธีการต่างๆ ในการกำหนดขอบเขตของค่าต่ำสุด ขั้นตอนเหล่านี้ง่ายกว่าการพิสูจน์ที่ให้ไว้มาก