Online matrix factorization for Markovian data and applications to Network Dictionary Learning

Online Matrix Factorization (OMF) is a fundamental tool for dictionary learning problems, giving an approximate representation of complex data sets in terms of a reduced number of extracted features. Convergence guarantees for most of the OMF algorithms in the literature assume independence between data matrices, and the case of a dependent data stream remains largely unexplored. In this paper, we show that the well-known OMF algorithm for i.i.d. Furthermore, we extend the convergence result to the case when we can only approximately solve each step of the optimization problems in the algorithm. For applications, we demonstrate dictionary learning from a sequence of images generated by a Markov Chain Monte Carlo (MCMC) sampler. Lastly, by combining online nonnegative matrix factorization and a recent MCMC algorithm for sampling motifs from networks, we propose a novel framework of Network Dictionary Learning, which extracts'network dictionary patches' from a given network in an online manner that encodes main features of the network. We demonstrate this technique on real-world text data. I NTRODUCTION In modern data analysis, a central step is to find a low-dimensional representation to better understand, compress, or convey the key phenomena captured in the data. Matrix factorization provides a powerful setting for one to describe data in terms of a linear combination of factors or atoms. In this setting, we have a data matrix X R d n, and we seek a factorization of X into the product W H for W R d r and H R r n . This problem has gone by many names over the decades, each with different constraints: dictionary learning, factor analysis, topic modeling, component analysis. It has applications in text analysis, image reconstruction, medical imaging, bioinformatics, and many other scientific fields more generally [SGH02, BB05, BBL 07, CWS 11, TN12, BMB 15, RPZ 18]. Each column of the data matrix is approximated by a linear combination of the columns of the dictionary matrix. Online matrix factorization is a problem setting where data are accessed in a streaming manner and the matrix factors should be updated each time. That is, we get draws of X from some distribution π and seek the best factorization such that the expected loss E X πnull null X W H null 2 F null is small. This is a relevant setting in today' s data world, where large companies, scientific instruments, and healthcare systems are collecting massive amounts of data every day . One cannot compute with the entire 1 arXiv:1911.01931v3 There are several algorithms for computing factorizations of various kinds in an online context. Many of them have algorithmic convergence guarantees, however, all these guarantees require that data are sampled at each iteration i.i.d. with respect to previous iterations. In all of the application examples mentioned above, one may make an argument for (nearly) identical distributions, but never for independence.