# Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Oct 2013.

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

- [Bipartite mixed membership distribution-free model. A novel model for community detection in overlapping bipartite weighted networks](https://mlsanity.com/paper/2211.00912/) (2022)
- [A useful criterion on studying consistent estimation in community detection](https://mlsanity.com/paper/2109.14950/) (2021)
- [Improved Algorithm and Bounds for Successive Projection](https://mlsanity.com/paper/2403.11013/) (2024)
- [On the Robustness of the Successive Projection Algorithm](https://mlsanity.com/paper/2411.16195/) (2024)
- [Directed mixed membership stochastic blockmodel](https://mlsanity.com/paper/2101.02307/) (2021)
- [Non-negative matrix factorization algorithms generally improve topic model fits](https://mlsanity.com/paper/2105.13440/) (2021)
- [Directed degree corrected mixed membership model and estimating community memberships in directed networks](https://mlsanity.com/paper/2109.07826/) (2021)
- [Mixed membership distribution-free model](https://mlsanity.com/paper/2112.04389/) (2021)
- [Mixed membership estimation for categorical data with weighted responses](https://mlsanity.com/paper/2310.10989/) (2023)
- [Overlapping and nonoverlapping models](https://mlsanity.com/paper/2111.01392/) (2021)
- [Two to Five Truths in Non-Negative Matrix Factorization](https://mlsanity.com/paper/2305.05389/) (2023)
- [Robustness of Minimum-Volume Nonnegative Matrix Factorization under an Expanded Sufficiently Scattered Condition](https://mlsanity.com/paper/2511.04291/) (2025)
- [Hyperspectral Image Data Reduction for Endmember Extraction](https://mlsanity.com/paper/2512.10506/) (2025)

## Abstract (arXiv)

Nonnegative matrix factorization (NMF) under the separability assumption can provably be solved efficiently, even in the presence of noise, and has been shown to be a powerful technique in document classification and hyperspectral unmixing. This problem is referred to as near-separable NMF and requires that there exists a cone spanned by a small subset of the columns of the input nonnegative matrix approximately containing all columns. In this paper, we propose a preconditioning based on semidefinite programming making the input matrix well-conditioned. This in turn can improve significantly the performance of near-separable NMF algorithms which is illustrated on the popular successive projection algorithm (SPA). The new preconditioned SPA is provably more robust to noise, and outperforms SPA on several synthetic data sets. We also show how an active-set method allow us to apply the preconditioning on large-scale real-world hyperspectral images.