Sparse JL Transform Analyses Overview
A comprehensive overview of the Sparse JL Transform, discussing concepts such as embedding high-dimensional spaces into lower dimensions, matrix construction, dimension reduction, and distributional lemma. Explore the purpose, fast transform techniques, and practical applications of the transformation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Simple Analyses of the Sparse JL Transform MICHAEL B. COHEN, T. S. JAYRAM AND JELANI NELSON, 2018 OVERVIEW BY SHARON STEIN DROPS.DAGSTUHL.DE/OPUS/VOLLTEXTE/2018/8305/ 1
Recap JL Lemma A set of points in a high-dimensional space can be embedded into a space of much lower dimension in such a way that distances between the points are nearly preserved ?1 ? ?1 = ?1 ? ?2 = ?2 ?2 ? ??? ????????? ? ???? ????????? 2
Recap JL Lemma we constructed a matrix of gaussians and showed that it can act as a linear map for the dimension reduction ?(??) 3
The Purpose Significantly reduce the compute time of L?. ? ?? ? ? ?? Haven't we seen that already? 4
Recap Fast JL Transform 1 In 2006, Ailon and Chazelle showed that There is a map which takes ?(? log ? + ?3)time to multiply by a vector. 5
Recap Fast JL Transform 2 And we have proved in class (lectures 6-7) there is a map which takes ?(?log? + ?) time to multiply (when the dimension m is a little bigger). 6
Recap Fast JL Transform 2 The proof is based on constructing a map ? = ??? made from: Sparse: ? is a sampling matrix (one non-zero each row) Structured: ? is a Hadamard matrix Sparse: ? is a diagonal matrix 7
Recap - Distributional JL Lemma For any 0 < ?,? < 1 and a positive integer ?, there exists a distribution over L ? ? ?s.t. for ? = ?(? 2log1 ?)and any unit vector ? ? : 2 1 > ? < ? ? ??2 2 ? 2> ? < ? ? ??2 8
Overview 9
How? Construct a matrix with ?(? ??) non-zero entries Where are the non-zero entries? What is their value? 10
Proof Outline Assuming we constructed a matrix L ? ? ? 2 1 Define: Z = ??2 Then, by Markov s inequality, for any ? 0, ? > ? < ? ? ? ?? ? 11
To Do Construct a matrix to fit the conditions Bound the q moment of Z, ? ?q 12
Rademacher distribution A Rademacher random variable X: 12 12 P ? = ? = ? = 1, ?.? ? = 1, ?.? 14
Sparse JL Transform in order to determine the placement for the non- zeros, we ll use Bernoulli random variables In order to determine the value of the non-zeros, we ll use Rademacher random variables 15
Sparse JL Transform (2) Pick a random L ? ? ? that satisfies: ? ??,?= ???,???,? where ? = ? ? ? . Bernoulli Rademacher Determines the value of the non-zeros Determines the placement for the non-zeros 16
SJLT Condition 1 To limit the compute time, we need exactly ? non-zero entries per column: 0 0 0 0 0 0 0 0 0 ? 0 0 0 0 0 0 0 ??,?= ? 0 < ? < ?: 0 0 0 0 0 ?=? 0 0 0 0 0 0 0 0 0 0 0 Example: m = 6, s = 2 17
SJLT Condition 2 For all ? ? ,i ? , ? ? ??,? are distributed as ????????? ? ? This results in ??,? = 18
SJLT Remark Are the ??,? independent? They can't be fully independent. Recall condition 1: exactly ? non-zero entries per column ? ??,?= ? ?=1 19
SJLT Condition 3 ? ? ? , ??)|?| ?( ?,? ????,?) (?,?)??? ??,? = ( Notice that when the ??,? are fully independent, the above equation is an equality By this condition, they are almost independent 20
SJLT Remark In order to simplify, we will assume that the ??,? are fully independent. Why can we do that? Every time we ll use the independency, the actual proof used condition 3 instead. 21
The Proof 22
Remember Z equals double vertical line cap L x double vertical line sub 2 squared minus 1 Z = ??2 2 1 23
? ??? ? 1 ???= ? i=1 ??,???,??? 2 ? 1? ?= ??? ??,???,??i ?=1 ? ?=1 ? = ?? ( ??,???,???,???,?????) ?=? ?,? 24
? (2) ??? 2= ??2 ? ? 1? ??,???,???,???,????? + ?=1 ? ? ? ? 1? ??,?2??,?2??2 = ?=1 ?=1 = ? = ??= ? 25
Representation of Z 2 1 = Z = ??2 ? ? 1? ??,???,???,???,????? ?=1 ? ? ? ? = 0 26
Reminders 12 ?,?|??,?|2) Frobenius Norm: ??= ( Operator Norm: for a symmetric matrix ?, ? = the largest absolute value of an eigenvalue of ?. 27
Hanson-Wright Inequality let ?1, ,?? = ? be independent Rademacher s and ? ? ? ?. For any ? 0: ??= ? (??|???? ? ???? |?) ? ??+ ? ? 28
Hanson-Wright Inequality (1) ??= ? (??|???? ? ???? |?) ? ??+ ? ? 29
Zs Quadratic form In order to use the Hanson-Wright inequality, we can express ? = ????. Where ? ?? ? ?? is a block diagonal matrix. There are ? blocks, each ? ? ?. Where in the ?? block ??, ?? ?,?= for ? ?, ?? ?,?= 0 for all ?. 1 ???,???,????? 30
Use Hanson-Wright By Hanson-Wright: 1?= ? ??|?|? ? ??+ ? ? 32
Use Hanson-Wright (2) ??over both sides: Take ?? | |? 1? 1?= ? (?? ? ????|?|? ? ??+ ? ? ) 33
Use Hanson-Wright ??satisfies the triangle inequality : Fact: ?? | |? 1? ??= ? (?? ? ????|?|? ? ??+ ? ? ) ?? ??) ?) ?) ?( ?(?? ?? + ?(?? ? Note that in order to bound Z s moment, we only need to bound A s norms. 34
Bounding Zs Moment Claim 1: ?? ? ? ?) (?? ?? ? Claim 2: ?? ? ?? ?) (?? ? 35
Bounding Zs Moment (1) By Markov: ? ? > ? < ? ? ? ?? ? ? O( ?(?? ?? 1? 1?)? ?) ?) + ?(?? ? By Claims: 1 ? + ?1 ? ? O( ? ?)? 36
Bounding Zs Moment (2) ?2 ? 1 ? Set: ? = log By the definition of : = ?2 ? ?0 ? For some constant ?0. 37
Bounding Zs Moment (3) ? ? > ? < ? ?2 ? 1 ? ? 1 ?+ ?0 = ? ? ? ?0 ? ? ? ?? ? = ? ? ? ? ? ? ?0+ ?0 ?0+ ?0 ? 38
Bounding Zs Moment (2) ? ? > ? log1 log1 1 ? ? ? < ? ?0+ ?0 ? 39
Proofing the Claims In order to complete the proof, all there is left to do, is to proof claim 1 and 2. Which means we need to bound A s norms. 40
Bounding the operator norm Since ? is block-diagonal, its eigenvalues are the eigenvalues of each block. 1 ? For a block ??, write ?? = ?? is diagonal with (??)?,?= ??,???2, and (??)?,?= ??,???,?????. ?? ??. 41
Bounding the operator norm (2) By the triangle inequality: 1 ? ?? ?? + ?? 2 1 ?? ? 42
Bounding the operator norm (2) . Define ? ? ?where ??= ??,??? Then, ??= ???. 2 ?2 2= 1 ?? = ?2 2? ?= ? ?? ?? 43
Lemma 2 Let 1 ? ?. For ? distributed as ???????? ?,? . ? if ??< ?, ??= ? ?? ?( ??) 44
Lemma 2 explained Since ???????? ?,? variables could be represented as a sum of ? ?????????(?) variables. 45
Lemma 2 explained (2) Then, when calculating ? ?? we get a polynomial of ?? with a degree ? 46
Bounding the Frobenius norm Remember: ?? ?,?= ?? ?,?= 0 for all ? 1 ???,???,?????for ? ? Then: 2?? 2 ( ?=1 2= ? 1 ?? ?2 ? ??? ??,???,?) 47
Bounding the Frobenius norm (2) Suppose ??1,?, ,???,?= 1 for a distinct ?. Then ?=1 ??,???,?= ?=1 ? ? ???,? this sum is distributed as ????????(?,?/?) And then by lemma 2, ? ? ) ?2 ??= ? ?( ??,???,? ? = ? ? ?=1 48
Bounding the Frobenius norm (3) 1? ? q ?? = ? ??= 2 ?) ?) 2 ?( ?? ?? = ?( ?? 2 1 2 12 ? ? ? By the triangle 1 ?2 ? ? inequality we get ?? 1? ) 2?? 2 2?? 2?( ?? ??,???,? ?? ??,???,? ?=1 ? 2 ? ? ?=1 ?? = ? = = ? ? 49
Bounding the Frobenius norm (4) ?? ?) ?( ?? ? 1? ? ? ?( ?) 50
