【NeurIPS2023】矩阵压缩通过随机低秩和低精度分解

矩阵在各个学科领域都非常有用，因为它们提供了一个方便的框架来有结构地组织和处理数据。然而，现代矩阵可能涉及数十亿的元素，这使得它们的存储和处理在计算资源和内存使用方面都非常要求。尽管如此大，但这种矩阵往往大约是低秩的。我们提出了一个算法，利用这种结构得到任何矩阵A的低秩分解为A ≈ LR，其中L和R是低秩因子。L和R中的元素总数可能远小于A中的。此外，L和R的条目被量化为低精度格式，从而通过给我们一个低秩和低精度的分解来压缩A。我们的算法首先通过随机草图其列来计算A的范围空间的近似基，然后对构成此基的向量进行量化。然后，它计算A的列到这个量化基的近似投影。我们推导出我们算法的近似误差的上界，并分析目标秩和量化位预算的影响。压缩比和近似精度之间的权衡允许根据特定应用要求灵活地选择这些参数。我们通过图像压缩、图像和文本嵌入的最近邻分类以及压缩LlaMa-7b的层来实证地展示了我们算法的效果。我们的结果表明，我们可以实现如每个矩阵坐标一位的激进压缩比，同时超越或维持传统压缩技术的性能。