# Associative Memories to Accelerate Approximate Nearest Neighbor Search
## 4 Dense, Unbiased Patterns  
Contrary to the previous section, we will now treat the situation where the patterns are not sparse and do not have a bias. This is best modeled by choosing \(x^{\mu}\in\{-1,1\}^{d}\) for some (large) \(d\). We will now assume that the \(x^{\mu},\mu=1,\ldots,n\) are i.i.d. and have i.i.d. coordinates such that:  
\[\mathbb{P}(x^{\mu}_{l}=1)=\frac{1}{2}=\mathbb{P}(x^{\mu}_{l}=-1)\]  
for all \(l=1,\ldots,d\) and all \(\mu=1,\ldots,n\). Again, we will suppose that there is an \(x^{\mu}\) such that \(d_{H}(x^{\mu},x^{0})\) is macroscopically large. To illustrate the ideas, we start with the situation that \(x^{0}=x^{1}\). Again, we will also partition the patterns into equal-sized classes \(\mathcal{X}^{1},\ldots X^{q}\), with \(|\mathcal{X}^{i}|=k\) for all \(i=1,\ldots,q\) and compute:  
\[s(\mathcal{X}^{i},x^{0})=\sum_{\mu:x^{\mu}\in\mathcal{X}^{i}}\sum_{l,m=1}^{d}x ^{0}_{l}x^{\mu}_{m}x^{\mu}_{l}x^{\mu}_{m}\]  
to compute the overlap of a class \(i\) with the query pattern. We will prove:  
Theorem 4.2: _Assume that the query pattern is equal to one of the patterns in the database. The algorithm described above works asymptotically correctly and is efficient if:_  
1. \(d\ll k\ll d^{2}\)_, i.e.,_ \(\frac{k}{d^{2}}\to 0\) _and_ \(\frac{k}{d}\to\infty\)_, and either_
2. \(qe^{-\frac{1}{8}\frac{d^{2}}{k}}\to 0\) _if_ \(d^{4}\ll k^{3}\)_,_
3. _or_ \(q\exp\left(-\frac{d^{2}}{k^{2}}\right)\to 0\) _if_ \(k\leq Cd^{\frac{4}{3}}\)_, for some_ \(C>0\)_._  
Proof. : Without loss of generality, we may again suppose that \(x^{0}=x^{1}\) and now that \(x^{0}_{l}=x^{1}_{l}\equiv 1\) for all \(l=1,\ldots,d\), since otherwise, we can flip the spins of all coordinates and all images, where this is not the case (recall that the \(x^{\mu}_{l}\) are all unbiased i.i.d., such that flipping the spins does not change their distribution). Then, the above expression simplifies to:  
\[s(\mathcal{X}^{i},x^{0})=\sum_{\mu:x^{\mu}\in\mathcal{X}^{i}}\sum_{l,m=1}^{d} x^{\mu}_{l}x^{\mu}_{m}.\]  
Especially:  
\[s(\mathcal{X}^{1},x^{0})=d^{2}+\sum_{ \begin{subarray}{c}x^{\mu}\in\mathcal{X }^{1}\\ \mu\
eq 1\end{subarray} }\sum_{l,m=1}^{d}x^{\mu}_{l}x^{\mu}_{m}.\]  
Again, we want to know for which parameters:  
\[\mathbb{P}(\exists i\geq 2:s(\mathcal{X}^{i},x^{0})\geq s(\mathcal{X}^{1},x^{ 0}))\to 0\qquad\text{as}\quad d\to\infty.\]  
Trivially,  
\[\mathbb{P}(\exists i\geq 2:s(\mathcal{X}^{i},x^{0})\geq s(\mathcal{X}^{1},x^{ 0}))\leq q\mathbb{P}(s(\mathcal{X}^{2},x^{0})\geq s(\mathcal{X}^{1},x^{0})).\]  
By the exponential Chebyshev inequality, we obtain for any \(t>0\):  
\[\mathbb{P}(s(\mathcal{X}^{2},x^{0})\geq s(\mathcal{X}^{1},x^{0}))= \mathbb{P}(\sum_{\mu:x^{\mu}\in\mathcal{X}^{2}}\sum_{l,m=1}^{d}x^{\mu}_{l}x^{ \mu}_{m}-\sum_{ \begin{subarray}{c}x^{\mu}\in\mathcal{X}^{1}\\ \
u\
eq 1\end{subarray} }\sum_{l,m=1}^{d}x^{\
u}_{l}x^{\
u}_{m}\geq d^{2})\] \[\leq e^{-td^{2}}(\mathbb{E}\exp(t\sum_{l,m=1}^{d}x^{\mu}_{l}x^{\mu}_{m} ))^{k}(\mathbb{E}\exp(-t\sum_{l,m=1}^{d}x^{\
u}_{l}x^{\
u}_{m}))^{k-1}.\]  
We first choose \(\varepsilon_{d}=k^{-1/4}\tilde{\varepsilon}_{d}\) for some small \(\tilde{\varepsilon}_{d}\) converging to zero as \(d\) goes to infinity, such that the first factor on the right-hand side converges to one. Then, we choose \(k\) and \(d\) such that the third term on the right-hand side converges to one. This is true if:  
\[\frac{1}{2}\log(1+2 td)-\frac{\varepsilon_{d}^{2}}{2t\sqrt{d}}+\log(k)\to-\infty.\]  
Anticipating our choices of \(t\) and \(d\) such that \(dt\) goes to zero, we get the condition \(-\frac{k^{-1/4}\varepsilon_{d}^{2}}{2t\sqrt{d}}+\log(k)\to-\infty\) as \(d\) and \(k\) go to zero. Now, we always suppose that \(d\ll k\). With these choices, we obtain that:  
\[\mathbb{P}(s(\mathcal{X}^{2},x^{0})\geq s(\mathcal{X}^{1},x^{0}))\leq e^{-td^ {2}}e^{-\frac{k-1}{2}\log(1+2 dt)}e^{-\frac{k}{2}\log(1-2 dt)}\approx e^{-td^{2 }}e^{-\frac{k}{2}\log(1-4d^{2}t^{2})}\]  
Now, we differentiate two cases.