## 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." *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)