Structured Low-Rank Matrix Factorization: Global Optimality, Algorithms,
  and Applications
  Recently, convex formulations of low-rank matrix factorization problems have
received considerable attention in machine learning. However, such formulations
often require solving for a matrix of the size of the data matrix, making it
challenging to apply them to large scale datasets. Moreover, in many
applications the data can display structures beyond simply being low-rank,
e.g., images and videos present complex spatio-temporal structures that are
largely ignored by standard low-rank methods. In this paper we study a matrix
factorization technique that is suitable for large datasets and captures
additional structure in the factors by using a particular form of
regularization that includes well-known regularizers such as total variation
and the nuclear norm as particular cases. Although the resulting optimization
problem 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 global
minimizer. A few practical algorithms are also provided to solve the matrix
factorization problem, and bounds on the distance from a given approximate
solution of the optimization problem to the global optimum are derived.
Examples in neural calcium imaging video segmentation and hyperspectral
compressed recovery show the advantages of our approach on high-dimensional
datasets.
