Compressed Factorization: Fast and Accurate LowRank Factorization of CompressivelySensed Data
[edit]
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:56905700, 2019.
Abstract
What learning algorithms can be run directly on compressivelysensed data? In this work, we consider the question of accurately and efficiently computing lowrank 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 highdimensional 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 wellknown 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 nonconvex, NPHard problems like nonnegative matrix factorization. We support these theoretical results with experiments on synthetic data and demonstrate the practical applicability of compressed factorization on realworld gene expression and EEG time series datasets.
Related Material


