Low Rank Multi-Dictionary Selection at Scale

稀疏字典编码框架将信号表示为少量预定义字典原子的线性组合。它已被用于图像、时间序列、图信号，并最近用于同时使用时间和空间字典的2维时空数据。大型且超完备的字典可实现高质量模型，但也带来了可扩展性挑战，尤其是在多字典设置中更加严重。因此，本文解决的一个重要问题是：如何为大型字典和数据集扩展多字典编码？我们提出了一种名为LRMDS的低秩稀疏编码多字典原子选择技术。为了实现对大型字典和数据集的可扩展性，它逐步选择基于数据对齐的行列原子对组，并通过相应的子字典执行凸松弛编码。我们在理论和实验上都证明，当数据具有低秩编码和稀疏原子子集时，LRMDS能够在温和的假设下提供强有力的选择保证。此外，我们在合成和真实数据集上展示了LRMDS的可扩展性和质量，并使用一系列编码字典。与基准相比，它在速度上实现了3倍至10倍的提升，同时在一些真实数据集上在固定目标原子数的情况下获得了达两个数量级的表示质量提高。

本文试图解决如何在大规模字典和数据集的情况下扩展多字典编码的问题。

本文提出了一种名为LRMDS的多字典原子选择技术，通过逐步选择与数据对齐的行列原子对并通过相应的子字典执行凸松弛编码来实现可扩展性。当数据具有低秩编码和一小部分原子时，LRMDS能够在温和的假设下提供强有力的保证。

实验结果表明，在一定数量的原子下，LRMDS在一些真实世界数据集上实现了两个数量级的表示质量提升，并且相比基线实现了3倍至10倍的加速。论文还提供了开源代码。

最近的相关研究包括：《Multi-Dictionary Learning for Sparse Coding: A Comparative Study》、《Multi-Dictionary Sparse Coding for Image Classification》等。