# Worst-case low-rank approximations

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 42 references that are in the map.
- First posted on arXiv 11 Mar 2026.

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

- [Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization](https://mlsanity.com/paper/1911.08731/) (2019)
- [Certifying Some Distributional Robustness with Principled Adversarial Training](https://mlsanity.com/paper/1710.10571/) (2017)
- [Variance-based regularization with convex objectives](https://mlsanity.com/paper/1610.02581/) (2016)
- [The Price of Fair PCA: One Extra Dimension](https://mlsanity.com/paper/1811.00103/) (2018)
- [Provable Inductive Matrix Completion](https://mlsanity.com/paper/1306.0626/) (2013)
- [Maximin effects in inhomogeneous large-scale data](https://mlsanity.com/paper/1406.0596/) (2014)
- [Efficient Fair Principal Component Analysis](https://mlsanity.com/paper/1911.04931/) (2019)
- [Statistical Inference for Maximin Effects: Identifying Stable Associations across Multiple Studies](https://mlsanity.com/paper/2011.07568/) (2020)
- [Magging: maximin aggregation for inhomogeneous large-scale data](https://mlsanity.com/paper/1409.2638/) (2014)
- [Fair Principal Component Analysis and Filter Design](https://mlsanity.com/paper/2002.06557/) (2020)
- [Fair principal component analysis (PCA): minorization-maximization algorithms for Fair PCA, Fair Robust PCA and Fair Sparse PCA](https://mlsanity.com/paper/2305.05963/) (2023)
- [Towards a Fairer Non-negative Matrix Factorization](https://mlsanity.com/paper/2411.09847/) (2024)
- [Sparse outlier-robust PCA for multi-source data](https://mlsanity.com/paper/2407.16299/) (2024)

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

- [Anchor PCA](https://mlsanity.com/paper/2606.06233/) (2026)

## Abstract (arXiv)

Real-world data in health, economics, and environmental sciences are often collected across heterogeneous domains (such as hospitals, regions, or time periods). In such settings, distributional shifts can make standard PCA unreliable, in that, for example, the leading principal components may explain substantially less variance in unseen domains than in the training domains. Existing approaches (such as FairPCA) have proposed to consider worst-case (rather than average) performance across multiple domains. This work develops a unified framework, called wcPCA, applies it to other objectives (resulting in the novel estimators such as norm-minPCA and norm-maxregret, which are better suited for applications with heterogeneous total variance) and analyzes their relationship. We prove that for all objectives, the estimators are worst-case optimal not only over the observed source domains but also over all target domains whose covariance lies in the convex hull of the (possibly normalized) source covariances. We establish consistency and asymptotic worst-case guarantees of empirical estimators. We extend our methodology to matrix completion, another problem that makes use of low-rank approximations, and prove approximate worst-case optimality for inductive matrix completion. Simulations and two real-world applications on ecosystem-atmosphere fluxes demonstrate marked improvements in worst-case performance, with only minor losses in average performance.