Associative Memory via a Sparse Recovery Model

Arya Mazumdar, Ankit Singh RawatNeurIPS 2015 · OpenReview

This paper by Arya Mazumdar and Ankit Singh Rawat presents a novel bridge between two historically distinct fields: neural associative memories (like Hopfield networks) and sparse recovery (compressed sensing). By reframing the act of "remembering" as a sparse denoising problem, the authors demonstrate how to achieve exponential storage capacity with robust error correction using biologically plausible algorithms.

The Challenge of Associative Memory

Associative memory is the ability of a system to store a set of patterns and retrieve the correct one when presented with a noisy or partial version. For decades, the Hopfield Network has been the standard model. However, Hopfield networks face a frustrating trade-off between capacity and robustness. If you want to store many patterns (exponential in the number of neurons $n$), the network usually becomes extremely sensitive to noise. Traditional binary Hopfield networks can only store about $O(n / \log n)$ patterns if they are expected to correct a linear number of errors.

The core challenge is to design a system that has high capacity (stores many patterns), high robustness (corrects many errors), and is neurally feasible (the "recall" process uses local computations that neurons could actually perform).

A New Approach: Recall as Sparse Recovery

The authors shift the perspective from "storing patterns in weights" to "learning the constraints of a subspace."

Instead of traditional Hebbian learning, the authors propose learning a set of linear constraints that every valid message in the dataset must satisfy. Mathematically, they find a matrix $\mathbf{B}$ such that for any valid message $\mathbf{x}$, the product $\mathbf{Bx} = 0$.

When a noisy query $\mathbf{y} = \mathbf{x} + \mathbf{e}$ is received (where $\mathbf{e}$ is a sparse error vector), the system computes the "syndrome" $\mathbf{r} = \mathbf{By}$. Since $\mathbf{Bx} = 0$, it follows that $\mathbf{r} = \mathbf{Be}$. This is the classic setup for compressed sensing: recovering a sparse signal $\mathbf{e}$ from a small number of linear measurements $\mathbf{r}$. The most elegant insight here is treating the noise as the signal to be recovered. By solving for the error vector $\mathbf{e}$ and subtracting it from the query $\mathbf{y}$, the system "recalls" the original pattern $\mathbf{x}$.

Neurally Feasible Algorithms

To ensure the model is biologically relevant, the authors focus on iterative algorithms like Iterative Soft Thresholding (IST) and the Bregman Iterative (BI) algorithm. These algorithms only require matrix-vector multiplications and coordinate-wise thresholding.

Bipartite graph representation of the neural associative memory model.

As shown above, these operations can be mapped directly onto a bipartite graph of "message nodes" and "constraint nodes," allowing each node to perform simple calculations based only on information from its immediate neighbors.

Key Insights and Results

By leveraging the Restricted Isometry Property (RIP) and the Null-Space Property from compressed sensing, the authors prove that it is possible to break the traditional capacity ceiling. The system can store a super-polynomial or even exponential number of patterns in a network of size $O(n)$. Furthermore, unlike previous models that only work for random noise, this sparse recovery approach provides guarantees against adversarial errors—specific, worst-case patterns of corruption.

The paper establishes strong theoretical bounds using random models:

  • Sub-Gaussian Model: In a network of size $O(n)$, it is possible to store $\sim \exp(n^{3/4})$ vectors and correctly recall them even if $O(n^{1/4})$ coordinates are corrupted.
  • Random Orthonormal Basis Model: The system can store $\exp(r)$ vectors and correct $O((n-r)/\log^6 n)$ errors.
Simulation results comparing the neurally feasible Bregman Iterative (BI) algorithm with the Primal-Dual (PD) solver across different noise and matrix conditions.

In synthetic experiments with $n=1000$ neurons, the neurally feasible Bregman Iterative (BI) algorithm performed almost identically to the computationally expensive Primal-Dual (PD) linear programming solver across various noise and matrix conditions. This proves that the "biological" version of the algorithm doesn't sacrifice much accuracy for its efficiency.

Limitations and Future Work

While groundbreaking, the model has a few limitations:

  • Low-Dimensionality Assumption: The model assumes the dataset belongs to a low-dimensional subspace. If the data is full-rank (occupies the entire space), the null space becomes trivial, and the model cannot function.
  • Learning Complexity: While the recall phase is fast and iterative, the learning phase (finding the optimal null space with low coherence) involves solving a Quadratically Constrained Quadratic Problem (QCQP), which may be difficult to scale or implement neurally.
  • Real-World Data: The current work focuses on random synthetic models. Future research is needed to see how these linear constraints perform on highly structured real-world data like natural images or semantic embeddings.

Summary updated

Abstract

An associative memory is a structure learned from a dataset $\mathcal{M}$ of vectors (signals) in a way such that, given a noisy version of one of the vectors as input, the nearest valid vector from $\mathcal{M}$ (nearest neighbor) is provided as output, preferably via a fast iterative algorithm. Traditionally, binary (or $q$-ary) Hopfield neural networks are used to model the above structure. In this paper, for the first time, we propose a model of associative memory based on sparse recovery of signals. Our basic premise is simple. For a dataset, we learn a set of linear constraints that every vector in the dataset must satisfy. Provided these linear constraints possess some special properties, it is possible to cast the task of finding nearest neighbor as a sparse recovery problem. Assuming generic random models for the dataset, we show that it is possible to store super-polynomial or exponential number of $n$-length vectors in a neural network of size $O(n)$. Furthermore, given a noisy version of one of the stored vectors corrupted in near-linear number of coordinates, the vector can be correctly recalled using a neurally feasible algorithm.
BibTeX
@inproceedings{mazumdar2015associative,
  author = {Arya Mazumdar and Ankit Singh Rawat},
  title = {{Associative Memory via a Sparse Recovery Model}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=By-Ildb_-S},
}
Figure