# Structured Low-Rank Matrix Factorization: Global Optimality, Algorithms, and Applications

arXiv: https://arxiv.org/abs/1708.07850 · HTML: https://mlsanity.com/paper/1708.07850/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Aug 2017.

## Built on by (most cited first, 16 of 16)

- [Exploring Deep Neural Networks via Layer-Peeled Model: Minority Collapse in Imbalanced Training](https://mlsanity.com/paper/2101.12699/) (2021)
- [Imbalance Trouble: Revisiting Neural-Collapse Geometry](https://mlsanity.com/paper/2208.05512/) (2022)
- [Structured Graph Learning for Scalable Subspace Clustering: From Single-view to Multi-view](https://mlsanity.com/paper/2102.07943/) (2021)
- [Local Dense Logit Relations for Enhanced Knowledge Distillation](https://mlsanity.com/paper/2507.15911/) (2025)
- [Convergence Error Analysis of Reflected Gradient Langevin Dynamics for Globally Optimizing Non-Convex Constrained Problems](https://mlsanity.com/paper/2203.10215/) (2022)
- [Nonconvex Linear System Identification with Minimal State Representation](https://mlsanity.com/paper/2504.18791/) (2025)
- [Self-paced Principal Component Analysis](https://mlsanity.com/paper/2106.13880/) (2021)
- [Wave-Informed Matrix Factorization with Global Optimality Guarantees](https://mlsanity.com/paper/2107.09144/) (2021)
- [Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms](https://mlsanity.com/paper/2301.08015/) (2023)
- [Recovering Simultaneously Structured Data via Non-Convex Iteratively Reweighted Least Squares](https://mlsanity.com/paper/2306.04961/) (2023)
- [Robust Matrix Factorization with Grouping Effect](https://mlsanity.com/paper/2106.13681/) (2021)
- [Robust Manifold Nonnegative Tucker Factorization for Tensor Data Representation](https://mlsanity.com/paper/2211.03934/) (2022)
- [Wave Physics-informed Matrix Factorizations](https://mlsanity.com/paper/2312.13584/) (2023)
- [On subdifferential chain rule of matrix factorization and beyond](https://mlsanity.com/paper/2410.05022/) (2024)
- [Adaptive Stain Normalization for Cross-Domain Medical Histology](https://mlsanity.com/paper/2510.06592/) (2025)
- [Sparse Network Inference under Imperfect Detection and its Application to Ecological Networks](https://mlsanity.com/paper/2604.18820/) (2026)

## Abstract (arXiv)

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.