SIAM Journal on Mathematics of Data Science · 2019 · 206 citations · 31 references
ComputingComputer ScienceData ScienceBig Data AnalyticsRecommender SystemsStatistical ModelingApproximation AlgorithmsDimension ReductionDimensionality ReductionLatent Variable ModelingLatent Variable ModelsMatrix FactorizationHigh-dimensional EstimationLow-rank ApproximationLow-rank Matrix Factorization
Matrices of (approximate) low rank are pervasive in data science, appearing in movie preferences, text documents, survey data, medical records, and genomics. While there is a vast literature on how to exploit low rank structure in these datasets, there is less attention paid to explaining why the low rank structure appears in the first place. Here, we explain the effectiveness of low rank models in data science by considering a simple generative model for these matrices: we suppose that each row or column is associated to a (possibly high dimensional) bounded latent variable, and entries of the matrix are generated by applying a piecewise analytic function to these latent variables. These matrices are in general full rank. However, we show that we can approximate every entry of an $m\times n$ matrix drawn from this model to within a fixed absolute error by a low rank matrix whose rank grows as $\mathcal{O}(\log(m+n))$. Hence any sufficiently large matrix from such a latent variable model can be approximated, up to a small entrywise error, by a low rank matrix.
31
Indexing by latent semantic analysis
Scott Deerwester, Susan Dumais, George W. Furnas et al. · Journal of the American Society for Information Science · 1990 · 12.8K citations
Matrix Factorization Techniques for Recommender Systems
Yehuda Koren, Robert Bell, Chris Volinsky · Computer · 2009 · 11.7K citations
Random Features for Large-Scale Kernel Machines
Ali Rahimi, Benjamin Recht · 2007 · 2.7K citations