Holographic Reduced Representation
Holographic Reduced Representation
**Holographic Reduced Representations** are a simple mechanism to represent an associative array of key-value pairs in a fixed-size vector. Each individual key-value pair is the same size as the entire associative array; the array is represented by the sum of the pairs. Concretely, consider a complex vector key $r = (a\_{r}[1]e^{iφ\_{r}[1]}, a\_{r}[2]e^{iφ\_{r}[2]}, \dots)$, which is the same size as the complex vector value x. The pair is "bound" together by element-wise complex multiplication, which multiplies the moduli and adds the phases of the elements:

$$ y = r \otimes x $$

$$ y =  \left(a\_{r}[1]a\_{x}[1]e^{i(φ\_{r}[1]+φ\_{x}[1])}, a\_{r}[2]a\_{x}[2]e^{i(φ\_{r}[2]+φ\_{x}[2])}, \dots\right) $$

Given keys $r\_{1}$, $r\_{2}$, $r\_{3}$ and input vectors $x\_{1}$, $x\_{2}$, $x\_{3}$, the associative array is:

$$c = r\_{1} \otimes x\_{1} + r\_{2} \otimes x\_{2} + r\_{3} \otimes x\_{3} $$

where we call $c$ a memory trace. Define the key inverse:

$$ r^{-1} = \left(a\_{r}[1]^{−1}e^{−iφ\_{r}[1]}, a\_{r}[2]^{−1}e^{−iφ\_{r}[2]}, \dots\right) $$

To retrieve the item associated with key $r\_{k}$, we multiply the memory trace element-wise by the vector $r^{-1}\_{k}$. For example: 

$$ r\_{2}^{−1} \otimes c = r\_{2}^{-1} \otimes \left(r\_{1} \otimes x\_{1} + r\_{2} \otimes x\_{2} + r\_{3} \otimes x\_{3}\right) $$

$$ r\_{2}^{−1} \otimes c = x\_{2} + r^{-1}\_{2} \otimes \left(r\_{1} \otimes x\_{1} + r\_{3} \otimes x3\right) $$

$$ r\_{2}^{−1} \otimes c = x\_{2} + noise $$

The product is exactly $x\_{2}$ together with a noise term. If the phases of the elements of the key vector are randomly distributed, the noise term has zero mean.

Source: [Associative LSTMs](https://arxiv.org/pdf/1602.03032.pdf)