# Multi-Dictionary Learning for Low Rank Sparse Coding

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 53 references that are in the map.
- First posted on arXiv 12 Sep 2025.

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

- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [A survey of sparse representation: algorithms and applications](https://mlsanity.com/paper/1602.07017/) (2016)
- [Adversarial Robustness of Supervised Sparse Coding](https://mlsanity.com/paper/2010.12088/) (2020)
- [Deep Semantic Dictionary Learning for Multi-label Image Classification](https://mlsanity.com/paper/2012.12509/) (2020)
- [Dictionary Learning with Low-rank Coding Coefficients for Tensor Completion](https://mlsanity.com/paper/2009.12507/) (2020)
- [Sample Complexity of Dictionary Learning and other Matrix Factorizations](https://mlsanity.com/paper/1312.3790/) (2013)
- [Robust Kronecker Component Analysis](https://mlsanity.com/paper/1801.06432/) (2018)
- [Temporal Graph Signal Decomposition](https://mlsanity.com/paper/2106.13517/) (2021)
- [Learning Mixtures of Separable Dictionaries for Tensor Data: Analysis and Algorithms](https://mlsanity.com/paper/1903.09284/) (2019)
- [Sparse Coding with Multi-Layer Decoders using Variance Regularization](https://mlsanity.com/paper/2112.09214/) (2021)
- [Time-Varying Graph Mode Decomposition](https://mlsanity.com/paper/2301.03496/) (2023)
- [Multi-Dictionary Tensor Decomposition](https://mlsanity.com/paper/2309.09717/) (2023)
- [Low Rank Multi-Dictionary Selection at Scale](https://mlsanity.com/paper/2406.06960/) (2024)

## Abstract (arXiv)

Sparse dictionary coding represents signals as linear combinations of a few dictionary atoms. It has been applied to images, time series, graph signals and multi-way spatio-temporal data by jointly employing temporal and spatial dictionaries. Data-agnostic analytical dictionaries, such as the discrete Fourier transform, wavelets and graph Fourier, have seen wide adoption due to efficient implementations and good practical performance. On the other hand, dictionaries learned from data offer sparser and more accurate solutions but require learning of both the dictionaries and the coding coefficients. This becomes especially challenging for multi-dictionary scenarios since encoding coefficients correspond to all atom combinations from the dictionaries. To address this challenge, we propose a low-rank coding model for 2-dictionary scenarios and study its data complexity. Namely, we establish upper and lower bounds on the number of samples needed to learn dictionaries that generalize to unseen samples from the same distribution. We propose an alternating convex optimization solution, called AODL, which employs alternating optimization between the sparse coding matrices and the learned dictionaries. We demonstrate its quality for data reconstruction and missing value imputation in both synthetic and real-world datasets. For a fixed reconstruction quality, AODL learns up to 90% sparser solutions compared to non-low-rank and analytical (fixed) dictionary baselines. In addition, the learned dictionaries reveal interpretable insights into patterns from training samples.