# Associative Memories to Accelerate Approximate Nearest Neighbor Search
## 3 Search Problems with Sparse Patterns
Therefore, \(\left|\mathbb{E}\left[f^{(3)}(\zeta_{1})\,\sigma_{k}^{3}-\mathbb{E}f^{(3)}( \zeta_{2})\,\xi_{k}^{3}\right]\right|\) is of order \(t^{2}e^{t/\sqrt{c}}\), i.e., for fixed \(t\) of constant order, and:  
\[\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}))\]0  
where \(\mathcal{O}_{t}\) denotes an upper bound by a constant that may depend on \(t\). This notation (and the implied crude way to deal with the \(t\)-dependence) is justified, because from the next line on, we will just concentrate on \(t\) values that are smaller than \(\frac{1}{2}\). For those, \(\frac{c^{2}e^{t/\sqrt{c}}}{\sqrt{c}}\leq\frac{1}{\sqrt{c}}\). Moreover, we have for \(t\) smaller than \(1/2\) by Gaussian integration:  
\[\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}))\]1  
Therefore, writing:  
\[\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}))\]2  
We obtain:  
\[\left( \begin{array}{c}t\frac{x_{p}^{2}-\frac{c^{2}}{2t}}{\mathbb{E}[e^{\sqrt {\frac{c^{2}}{2}}}]}\\ \sqrt{\frac{c^{2}}{2t}}\end{array} \right)^{k}\leq e^{-\frac{k}{2}\log(1-2t)} \left(1+e^{\frac{1}{2}\log(1-2t)}\mathcal{O}_{t}(\frac{1}{\sqrt{c}})\right)^{ k}.\]  
In a similar fashion, we can also bound:  
\[\left( \begin{array}{c}-t\frac{x_{p}^{2}-\frac{c^{2}}{2t}}{\sqrt{\frac{c^{2} }{2t}}}\\ \sqrt{\frac{c^{2}}{2t}}\end{array} \right)^{k-1}\leq e^{-\frac{k-1}{2}\log(1+2t )}\bigg{(}1+e^{\frac{1}{2}\log(1+2t)}\mathcal{O}_{t}(\frac{1}{\sqrt{c}})\bigg{)} ^{k-1},\]  
where now, we make use of \(\mathbb{E}[e^{-t\xi^{2}}]=\frac{1}{\sqrt{1+2t}}\) instead of (1). Hence, by [PERSON] expansion of the logarithm altogether, we obtain:  
\[\mathbb{P}(\sum_{\mu=1}^{k}(X_{\mu}-\frac{c^{2}}{d})^{2}-\sum_{\mu=k+1}^{2k-1 }(X_{\mu}-\frac{c^{2}}{d})^{2}\geq\frac{c^{2}}{2})\quad\leq e^{-t\frac{d}{2}} e^{2 tt^{2}+\mathcal{O}(t+t^{2}\frac{k}{\sqrt{c}}+kt^{4})}. \tag{2}\]  
Note that we will always assume that \(c\to\infty\) such that \(\frac{k}{\sqrt{c}}\) is negligible with respect to \(k\). Now, we choose \(t=\frac{d}{8k}\). This, in particular, ensures that \(t\) converges to zero for large dimensions and therefore especially that (1) can be applied; we obtain that asymptotically:  
\[\mathbb{P}(\sum_{\mu=1}^{k}(X_{\mu}-\frac{c^{2}}{d})^{2}-\sum_{\mu=k+1}^{2k-1 }(X_{\mu}-\frac{c^{2}}{d})^{2}\geq\frac{c^{2}}{2})\leq e^{-\frac{1}{3}\frac{c^ {2}}{2t}}. \tag{3}\]  
Indeed, keeping the leading order term from the \(\mathcal{O}\)-expression in (2) with our choice of \(t\), we obtain that asymptotically:  
\[\mathbb{P}(\sum_{\mu=1}^{k}(X_{\mu}-\frac{c^{2}}{d})^{2}-\sum_{\mu=k+1}^{2k-1 }(X_{\mu}-\frac{c^{2}}{d})^{2}\geq\frac{c^{2}}{2})\leq e^{-\frac{1}{32}\frac{ c^{2}}{t}+\mathcal{O}(\frac{d}{8})}=e^{-\frac{1}{32}\frac{c^{2}}{t}(1+\mathcal{O}(\frac{d}{8 }))}.\]As \(d\ll k\), the term \((1+\mathcal{O}(\frac{d^{2}}{k^{3}}))\) will get arbitrarily close to one; hence, (3) follows. However, the right-hand side of (3) goes to zero, whenever \(d^{2}\gg k\). Hence, for \(d\ll k\ll d^{2}\), we obtain that the method works fine if \(c\ll d\), \(c\ll\left(\frac{d^{7}}{k^{3}}\right)^{\frac{1}{5}}\) and \(q\ll e^{\frac{1}{33}\frac{d^{2}}{k}}\), which are our last conditions. In a very similar fashion, we can treat the case of an input pattern that is a corrupted version of one of the vectors in the database. **Corollary 1**. : _Assume that the input pattern \(x^{0}\) has a macroscopic overlap with one of the patterns in the database, i.e., \(\sum_{l=1}^{d}x_{l}^{0}x_{l}^{u}=\alpha c\), for a \(\alpha\in(0,1)\), and \(x^{0}\) has \(c\) entries equal to one and \(d-c\) indices equal to zero. The algorithm described above works asymptotically correctly, i.e., with an error probability that converges to zero, and is efficient if:_  
1. \(d\ll k\ll d^{2}\)_,_
2.