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.

本文研究了一种适用于大规模数据集且通过使用特定形式的正则化来捕获因素中的额外结构的矩阵分解技术，该技术将已知的正则化器（如总变化和核范数）作为特定情况。 尽管所得到的优化问题是非凸的，但我们证明如果因素的大小足够大，在某些条件下，任何因素的局部最小值都可以得到全局最小值。我们还提供了一些实用的算法来解决矩阵分解问题，并导出了给定近似解的距离与全局最优解之间的距离范围。在大数据集上，神经钙成像视频分割和高光谱压缩恢复的示例显示了我们的方法的优势。

结构化低秩矩阵分解：全局最优、算法和应用