# Low Rank Multi-Dictionary Selection at Scale

arXiv: https://arxiv.org/abs/2406.06960 · HTML: https://mlsanity.com/paper/2406.06960/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 41 references that are in the map.
- First posted on arXiv 11 Jun 2024.

## Builds on (most cited first, 5 of 5)

- [Graph signal processing for machine learning: A review and new perspectives](https://mlsanity.com/paper/2007.16061/) (2020)
- [A survey of sparse representation: algorithms and applications](https://mlsanity.com/paper/1602.07017/) (2016)
- [Screening Tests for Lasso Problems](https://mlsanity.com/paper/1405.4897/) (2014)
- [Temporal Graph Signal Decomposition](https://mlsanity.com/paper/2106.13517/) (2021)
- [Fast greedy algorithms for dictionary selection with generalized sparsity constraints](https://mlsanity.com/paper/1809.02314/) (2018)

## Built on by (most cited first, 1 of 1)

- [Multi-Dictionary Learning for Low Rank Sparse Coding](https://mlsanity.com/paper/2509.10033/) (2025)

## Abstract (arXiv)

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.