What learning algorithms can be run directly on compressively-sensed data? In
this work, we consider the question of accurately and efficiently computing
low-rank matrix or tensor factorizations given data compressed via random
projections. We examine the approach of first performing factorization in the
compressed domain, and then reconstructing the original high-dimensional
factors from the recovered (compressed) factors. In both the matrix and tensor
settings, we establish conditions under which this natural approach will
provably recover the original factors. While it is well-known that random
projections preserve a number of geometric properties of a dataset, our work
can be viewed as showing that they can also preserve certain solutions of
non-convex, NP-Hard problems like non-negative matrix factorization. We support
these theoretical results with experiments on synthetic data and demonstrate
the practical applicability of compressed factorization on real-world gene
expression and EEG time series datasets.

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