Introduction to matrix and tensor factorization models and related stochastic nonconvex and constrained optimization algorithms

Abstract. Matrix/tensor factorization models such as principal component analysis , nonnegative matrix factorization, and CANDECOM/PARAFAC tensor decomposition provide powerful framework for dimension reduction and interpretable feature extraction, which are important in analyzing high-dimensional data that comes in large volume. Their diverse applications include image denoising and reconstruction, dictionary learning, topic modeling, and network data analysis. Fitting such factorization models to training data gives rise to various nonconvex and constrained optimization algorithms. Moreover, such models can be trained efficiently for streaming data using stochastic/online versions of such algorithms. After introducing matrix/tensor factorization models and their applications in various contexts, we survey some well-known nonconvex constrained optimization algorithms such as block coordinate descent and projected gradient descent. We also discuss some recent developments in general stochastic optimization algorithms such as stochastic proximal gradient descent and stochastic regularized majorization-minimization and their convergence and complexity guarantees under general Markovian streaming data.