No Magic!

One thing that sometimes confuses people about HRRs is the nature of the inverse operation.

For example, if we have a binding of two vectors, say A*B (where '*' is a circular convolution operations in HRRs), then how can we recover A (or B) from this binding, and exactly what information is stored in the binding?

The short answer is “there is no magic!” -- the amount of information stored in a binding is the same as the amount of information stored in the vector A or B.

This means that just given the binding alone, it is impossible to discover that is is constructed out of A and B (because then the binding would have had twice as much information as A and B).

However, given the binding A*B and one of the vectors, say A, it is possible to reconstruct the other member of the binding, i.e., B. This can be done using the “convolution inverse”, which can be written A*.

The convolution inverse (called “involution” in HRRs) is actually just a permutation of the elements of the vector – in ordinary HRRs it keeps the first element in place and reverses the order of the remaining elements. In terms of matrix linear algebra, the matrix corresponding to the convolution inverse of vector A is the transpose of the matrix corresponding to vector A.

Note that we assume that the “cue” vector (that we are using to decode the binding) is in fact part of the binding. It is also possible to use a a different cue vector, say C, to try to decode the binding A*B. If we do that, we get the vector C* * A*B, which is a just another vector. To identify that this is actually a nonsense vector, we need to have some way of identifying “valid” vectors. This is the one of the function of the “cleanup memory” in HRRs.