  The sparse dictionary coding framework represents signals as a linear
combination of a few predefined dictionary atoms. It has been employed for
images, time series, graph signals and recently for 2-way (or 2D)
spatio-temporal data employing jointly temporal and spatial dictionaries. Large
and over-complete dictionaries enable high-quality models, but also pose
scalability challenges which are exacerbated in multi-dictionary settings.
Hence, an important problem that we address in this paper is: How to scale
multi-dictionary coding for large dictionaries and datasets?
  We propose a multi-dictionary atom selection technique for low-rank sparse
coding named LRMDS. To enable scalability to large dictionaries and datasets,
it progressively selects groups of row-column atom pairs based on their
alignment with the data and performs convex relaxation coding via the
corresponding sub-dictionaries. We demonstrate both theoretically and
experimentally that when the data has a low-rank encoding with a sparse subset
of the atoms, LRMDS is able to select them with strong guarantees under mild
assumptions. Furthermore, we demonstrate the scalability and quality of LRMDS
in both synthetic and real-world datasets and for a range of coding
dictionaries. It achieves 3X to 10X speed-up compared to baselines, while
obtaining up to two orders of magnitude improvement in representation quality
on some of the real world datasets given a fixed target number of atoms.
