Recently, convex formulations of low-rank matrix factorization problems havereceived considerable attention in machine learning. However, such formulationsoften require solving for a matrix of the size of the data matrix, making itchallenging to apply them to large scale datasets. Moreover, in manyapplications the data can display structures beyond simply being low-rank,e.g., images and videos present complex spatio-temporal structures that arelargely ignored by standard low-rank methods. In this paper we study a matrixfactorization technique that is suitable for large datasets and capturesadditional structure in the factors by using a particular form ofregularization that includes well-known regularizers such as total variationand the nuclear norm as particular cases. Although the resulting optimizationproblem is non-convex, we show that if the size of the factors is large enough,under certain conditions, any local minimizer for the factors yields a globalminimizer. A few practical algorithms are also provided to solve the matrixfactorization problem, and bounds on the distance from a given approximatesolution of the optimization problem to the global optimum are derived.Examples in neural calcium imaging video segmentation and hyperspectralcompressed recovery show the advantages of our approach on high-dimensionaldatasets.
展开▼