/2
Proof.Withoutlossofgenerality,weassume wk =1for1≤k≤N.Pr[Xi=1|Xj=1]=Pr[hwi(a)=hwi(b)|Xj=1]=Pr[hvi Σi 1wkwTvi(a)=hvi Σi 1wkwTvi(b)|hwj(a)=kkk=1k=1hwj(b)].Since{w1,...wi 1}isauniformlyrandomorthonormalbasisofarandomsubspaceuni-formlydistributedonGrassmannmanifold,byexchangingtheindexjand1wehavethatequalsPr[hvi Σi 1wkwTvi(a)=hvi Σi 1wkwTvi(b)|hw1(a)=hw1(b)]=Pr[Xi=1|X1=1].k=1kk=1k
Lemma6.For{Xi}de nedinTheorem1,wehavePr[Xi=1|Xj=1]=Pr[X2=1|X1=1],
θa,b1≤j<i≤N≤d.Givenθa,b∈(0,π
],wehavePr[X2=1|X1=1]<.
Theproofofthislemmaislong,thusweprovideitintheAppendix(insupplementary le).
Theorem2.Giventwovectorsa,b∈Rdandrandomvariables{Xi}de nedasinTheorem1,denotep2,1=Pr[X2=1|X1=1],andSX=ΣNi=1XiwhichistheHammingdistancebetween
Nθpθa,bNθtheN-Super-Bitsofaandb,for1<N≤d,thenVar[SX]=a,b+N(N 1)2,1 (a,b)2.Proof.ByLemma6,Pr[Xi=1|Xj=1]=Pr[X2=1|X1=1]=p2,1when1≤j<i≤N.
pθa,b,forany1≤j<ThereforePr[Xi=1,Xj=1]=Pr[Xi=1|Xj=1]Pr[Xj=1]=2,1
2222i≤N.ThereforeVar[SX]=E[SX] E[SX]2=ΣNi=1E[Xi]
+2Σj<iE[XiXj] NE[X1]=
Nθa,bNθNθpθa,bNθ+2Σj<iPr[Xi=1,Xj=1] (a,b)2=a,b+N(N 1)2,1 (a,b)2.Corollary2.DenoteVar[SBLSHN,K]asthevarianceoftheHammingdistanceproducedbySBLSH,where1≤N≤distheSuper-Bitdepth,andK=N×Listhecodelength.ThenVar[SBLSHN,K]=L×Var[SBLSHN,N].Furthermore,givenθa,b∈(0,π
],ifK=N1×L1=
N2×L2and1≤N2<N1≤d,thenVar[SBLSHN1,K]<Var[SBLSHN2,K].
Proof.Sincev1,v2,...,vKareindependentlysampled,andw1,w2,...,wKareproducedbyorthog-onalizingeveryNvectors,theHammingdistancesproducedbydifferentN-Super-Bitsareinde-pendent,thusVar[SBLSHN,K]=L×Var[SBLSHN,N].
a,bThereforeVar[SBLSHN1,K]=L1×(1
a,b+N1(N1 1)2,1 (1
a,b)2)=a,b+K(N1 θθa,bpθa,bπ2 KN1(a,b1)2,1
).ByLemma6,whenθa,b∈(0,],forN1>N2>1,0≤p2,1<.
KθθThereforeVar[SBLSHN1,K] Var[SBLSHN2
,K]=a,b(N1 N2)(p2,1 a,b
)<0.For
Kθa,bθN1>N2=1,Var[SBLSHN1,K] Var[SBLSHN2,K]=(N1 1)(p2,1 a,b
)<0NθpθNθKθ
Corollary3.DenoteVar[SRPLSHK]asthevarianceoftheHammingdistanceproducedbySRP-LSH,where
K=N×L
isthecodelengthandLisapositiveinteger,1<N≤d.Ifθa,b∈(0,π
],
thenVar[SRPLSHK]>Var[SBLSHN,K].
Proof.ByCorollary2,Var[SRPLSHK]=Var[SBLSH1,K]>Var[SBLSHN,K].
2.2.1Numericalveri cation
Figure2:ThevarianceofSRP-LSHandSBLSHagainsttheangleθa,btoestimate.
InthissubsectionweverifynumericallythebehaviorofthevariancesofbothSRP-LSHandSBLSHfordifferentanglesθa,b∈(0,π].ByTheorem2,thevarianceofSBLSHiscloselyrelatedtop2,1de nedinTheorem2.Werandomlygenerate30pointsinR10,whichinvolves435angles.Foreachangle,wenumericallyapproximatep2,1usingsamplingmethod,wherethesamplenumberis1000.We xK=N=d,andplotthevariancesVar[SRPLSHN]andVar[SBLSHN,N]againstvariousanglesθa,b.Figure2showsthatwhenθa,b∈(0,π/2],SBLSHhasamuchsmallervariance