We propose a simple and efficient approach to learning sparse models. Our approach consists of (1) projecting the data into a lower dimensional space, (2) learning a dense model in the lower dimensional space, and then (3) recovering the sparse model in the original space via compressive sensing. We apply this approach to Non-negative Matrix Factorization (NMF), tensor decomposition and linear classification---showing that it obtains $10\times$ compression with negligible loss in accuracy on real data, and obtains up to $5\times$ speedups. Our main theoretical contribution is to show the following result for NMF: if the original factors are sparse, then their projections are the sparsest solutions to the projected NMF problem. This explains why our method works for NMF and shows an interesting new property of random projections: they can preserve the solutions of non-convex optimization problems such as NMF.

本文考虑在通过随机投影压缩的数据上准确高效地计算低秩矩阵或张量分解的问题。我们研究了在压缩域内执行分解并从恢复(压缩)因子中重构原始高维因子的方法，在矩阵和张量设置中，我们建立了这种自然方法能够证明恢复原始因子的条件。我们对合成数据进行了实验，证实了压缩因式分解在真实世界的基因表达和脑电时间序列数据集中的实际适用性，并支持这些理论结果。

压缩因式分解: 快速而准确地低秩分解压缩感知数据