# Exponentially Convergent Algorithms for Supervised Matrix Factorization

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 61 references that are in the map.
- First posted on arXiv 18 Nov 2023.

## Builds on (most cited first, 13 of 13)

- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Low-rank Solutions of Linear Matrix Equations via Procrustes Flow](https://mlsanity.com/paper/1507.03566/) (2015)
- [Accelerating Ill-Conditioned Low-Rank Matrix Estimation via Scaled Gradient Descent](https://mlsanity.com/paper/2005.08898/) (2020)
- [Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach](https://mlsanity.com/paper/1609.03240/) (2016)
- [A Convergent Gradient Descent Algorithm for Rank Minimization and Semidefinite Programming from Random Linear Measurements](https://mlsanity.com/paper/1506.06081/) (2015)
- [Stochastic Majorization-Minimization Algorithms for Large-Scale Optimization](https://mlsanity.com/paper/1306.4650/) (2013)
- [Finding Low-Rank Solutions via Non-Convex Matrix Factorization, Efficiently and Provably](https://mlsanity.com/paper/1606.03168/) (2016)
- [A Unified Computational and Statistical Framework for Nonconvex Low-Rank Matrix Estimation](https://mlsanity.com/paper/1610.05275/) (2016)
- [UCB-based Algorithms for Multinomial Logistic Regression Bandits](https://mlsanity.com/paper/2103.11489/) (2021)
- [Supervised Dictionary Learning and Sparse Representation-A Review](https://mlsanity.com/paper/1502.05928/) (2015)
- [Supervised PCA: A Multiobjective Approach](https://mlsanity.com/paper/2011.05309/) (2020)
- [Structure-Aware Classification using Supervised Dictionary Learning](https://mlsanity.com/paper/1609.09199/) (2016)

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

- [A latent linear model for nonlinear coupled oscillators on graphs](https://mlsanity.com/paper/2311.14910/) (2023)
- [Supervised Deep Multimodal Matrix Factorization for Interpretable Brain Network Analysis](https://mlsanity.com/paper/2605.13312/) (2026)

## Abstract (arXiv)

Supervised matrix factorization (SMF) is a classical machine learning method that simultaneously seeks feature extraction and classification tasks, which are not necessarily a priori aligned objectives. Our goal is to use SMF to learn low-rank latent factors that offer interpretable, data-reconstructive, and class-discriminative features, addressing challenges posed by high-dimensional data. Training SMF model involves solving a nonconvex and possibly constrained optimization with at least three blocks of parameters. Known algorithms are either heuristic or provide weak convergence guarantees for special cases. In this paper, we provide a novel framework that 'lifts' SMF as a low-rank matrix estimation problem in a combined factor space and propose an efficient algorithm that provably converges exponentially fast to a global minimizer of the objective with arbitrary initialization under mild assumptions. Our framework applies to a wide range of SMF-type problems for multi-class classification with auxiliary features. To showcase an application, we demonstrate that our algorithm successfully identified well-known cancer-associated gene groups for various cancers.