Nonnegative Matrix Factorization
Lee, D., and S. Seung. "Learning the Parts of Objects by Nonnegative Matrix Factorization." Nature 401 (1999): 788–91.
Vavasis, S. "On the Complexity of Nonnegative Matrix Factorization." SIAM Journal on Optimization (2009).
Arora, S., R. Ge, et al. "Computing a Nonnegative Matrix Factorization—Provably." Symposium on Theory of Computing (2012).
Arora, S., R. Ge, et al. "Learning Topic Models—Going Beyond SVD." Foundations of Computer Science (2012).
Arora, S., R. Ge, et al. "A Practical Algorithm for Topic Modeling with Provable Guarantees." International Conference on Machine Learning (2013).
Balcan, M., A. Blum, et al. "Clustering under Approximation Stability." Journal of the ACM 60, no. 2 (2013). (See discussion)
Tensor Decompositions
Hillar, C., and L. Lim. "Most Tensor Problems are NP-hard." Journal of the ACM (2013).
Mossel, E., and S. Roch. "Learning Nonsingular Phylogenies and Hidden Markov Models." The Annals of Applied Probability 16, no. 2 (2006): 583–614.
Anandkumar, A., D. Foster, et al. "A Spectral Algorithm for Latent Dirichlet Allocation." Neural Information Processing System (2012).
Anandkumar, A., R. Ge, et al. "A Tensor Spectral Approach to Learning Mixed Membership Community Models." Conference on Learning Theory (2013).
Goyal, N., S. Vempala, et al. "Fourier PCA and Robust Tensor Decomposition." Symposium on Theory of Computing (2014).
Feige, U., and J. Kilian. "Heuristics for Semirandom Graph Problems." Journal of Computing and System Sciences 63, no. 4 (2001): 639–71. (See discussion)
Sparse Coding
Olshausen, B., and D. Field. "Emergence of Simple-cell Receptive Field Properties by Learning a Sparse Code for Natural Images." Nature 381, (1996): 607–09.
Spielman, D., H. Wang, et al. "Exact Recovery of Sparsely-used Dictionaries." Conference on Learning Theory (2012).
Arora, S., R. Ge, et al. "Simple, Efficient, and Neural Algorithms for Sparse Coding." Manuscript (2015).
Barak, B., J. Kelner, et al. "Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method." Manuscript (2014).
Geman, S., and D. Geman. 
"Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images." (PDF - 4.3MB) Pattern Analysis and Machine Intelligence (1984). (See discussion)
Learning Mixture Models
Dempster, A., N. Laird, et al. "Maximum Likelihood from Incomplete Data via the EM Algorithm." Journal of Royal Statistical Society 39, no. 1 (1977): 1–38.
Dasgupta, S. "Learning Mixtures of Gaussians." Foundations of Computer Science (1999): 634–44.
Arora, S., and R. Kannan. "Learning Mixtures of Separated Nonspherical Gaussians." The Annals of Applied Probability 15, no. 1A (2005): 69–92.
Kalai, A., A. Moitra, et al. "Efficiently Learning Mixtures of Two Gaussians." (PDF) Symposium on Theory of Computing (2010).
Moitra, A., and G. Valiant. "Settling the Polynomial Learnability of Mixtures of Gaussians." Foundations of Computer Science (2010).
Belkin, M., and K. Sinha. "Polynomial Learning of Distribution Families." Foundations of Computer Science (2010).
Bhaskara, A., M. Charikar, et al. "Smoothed Analysis of Tensor Decompositions." Symposium on Theory of Computing (2014). (See discussion)
Linear Inverse Problems
Candes, E., and B. Recht. "Exact Matrix Completion via Convex Optimization." Foundations of Computational Mathematics 9, no. 6 (2009): 717–72.
Chandrasekaran, V., P. Parrilo, et al. "The Convex Geometry of Linear Inverse Problems." Foundations of Computational Mathematics 12, no. 6 (2012): 805–49.
Jain, P., P. Netrapalli, et al. "Low-rank Matrix Completion using Alternating Minimization." Symposium on Theory of Computing (2012).
Hardt, M. "Understanding Alternating Minimization for Matrix Completion." Foundations of Computational Mathematics (2014).
Barak, B., and A. Moitra. "Tensor Prediction, Rademacher Complexity and Random 3-XOR." Manuscript (2015).
Berthet, Q., and P. Rigollet. "Computational Lower Bounds for Sparse PCA." Conference on Learning Theory (2013). (See discussion)
Chandrasekaran, V., and M. Jordan. "Computational and Statistical Tradeoffs via Convex Relaxation." Proceedings of the National Academy of Sciences of the United States of America 110, no. 13 (2013): E1181–90. (See discussion)