# Certifiably Optimal Low Rank Factor Analysis

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2016.

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

- [Sparse Plus Low Rank Matrix Decomposition: A Discrete Optimization Approach](https://mlsanity.com/paper/2109.12701/) (2021)
- [A new perspective on low-rank optimization](https://mlsanity.com/paper/2105.05947/) (2021)
- [Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps](https://mlsanity.com/paper/2402.15409/) (2024)
- [Detecting adversaries in Crowdsourcing](https://mlsanity.com/paper/2110.04117/) (2021)
- [Optimal Ensemble Construction for Multi-Study Prediction with Applications to COVID-19 Excess Mortality Estimation](https://mlsanity.com/paper/2109.09164/) (2021)
- [Prescriptive PCA: Dimensionality Reduction for Two-stage Stochastic Optimization](https://mlsanity.com/paper/2306.02223/) (2023)
- [On Minimum Trace Factor Analysis -- An Old Song Sung to a New Tune](https://mlsanity.com/paper/2402.02459/) (2024)
- [ℓ0 factor analysis](https://mlsanity.com/paper/2411.08468/) (2024)
- [Improved Approximation Algorithms for Orthogonally Constrained Problems Using Semidefinite Optimization](https://mlsanity.com/paper/2501.02942/) (2025)
- [Compact Lifted Relaxations for Low-Rank Optimization](https://mlsanity.com/paper/2603.20228/) (2026)

## Abstract (arXiv)

Factor Analysis (FA) is a technique of fundamental importance that is widely used in classical and modern multivariate statistics, psychometrics and econometrics. In this paper, we revisit the classical rank-constrained FA problem, which seeks to approximate an observed covariance matrix (boldsymbolSigma), by the sum of a Positive Semidefinite (PSD) low-rank component (boldsymbolTheta) and a diagonal matrix (boldsymbolPhi) (with nonnegative entries) subject to boldsymbolSigma - boldsymbolPhi being PSD. We propose a flexible family of rank-constrained, nonlinear Semidefinite Optimization based formulations for this task. We introduce a reformulation of the problem as a smooth optimization problem with convex compact constraints and propose a unified algorithmic framework, utilizing state of the art techniques in nonlinear optimization to obtain high-quality feasible solutions for our proposed formulation. At the same time, by using a variety of techniques from discrete and global optimization, we show that these solutions are certifiably optimal in many cases, even for problems with thousands of variables. Our techniques are general and make no assumption on the underlying problem data. The estimator proposed herein, aids statistical interpretability, provides computational scalability and significantly improved accuracy when compared to current, publicly available popular methods for rank-constrained FA. We demonstrate the effectiveness of our proposal on an array of synthetic and real-life datasets. To our knowledge, this is the first paper that demonstrates how a previously intractable rank-constrained optimization problem can be solved to provable optimality by coupling developments in convex analysis and in discrete optimization.