Exemplary methods and apparatus are disclosed that implement super-sparse image/video compression by storing image dictionary elements within a cross-bar resistive random access memory (ReRAM) array (or other suitable cross-bar NVM array). In illustrative examples, each column of the cross-bar ReRAM array stores the values for one dictionary element (such as one 4×4 dictionary element). Methods and apparatus are described for training (configuring) the cross-bar ReRAM array to generate and store the dictionary elements by sequentially applying patches from training images to the array using an unstructured Hebbian training procedure. Additionally, methods and apparatus are described for compressing an input image by applying patches from the input image to the ReRAM array to read out cross-bar column indices identifying the columns storing the various dictionary elements that best fit the image. This may be done in parallel using a set of ReRAM arrays.