Worst-case low-rank approximations

Anya Fries; Markus Reichstein; David Blei; Jonas Peters

stat.MLMar 11, 2026

Worst-case low-rank approximations

Authors: Anya Fries, Markus Reichstein, David Blei, Jonas Peters

Organizations: Seminar for Statistics, ETH Zürich, Zürich, Switzerland · Max Planck Institute for Biogeochemistry, Jena, Germany · Department of Computer Science and Department of Statistics, Columbia University, New York, USA

Abstract

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.

Figures & tables

Figure 1: Proportion of explained variance by $\mathtt{poolPCA}$ and $\mathtt{norm}\textrm{-}\mathtt{maxRegret}$ in the FLUXNET example on source (left) and target (right) regions (for one specific split). Unlike $\mathtt{poolPCA}$ , which optimizes a pooled explained variance, $\mathtt{norm}\textrm{-}\mathtt{maxRegret}$ optimizes a worst-case criterion over the source domains, which, here, yields a worst-case improvement of 7.8%. Section 3.1 proves that this choice comes with a worst-case improvement over a larger class of target domains, too. Indeed, in this example, the worst-case explained variance over the target domains improves by 25.8%. (Over 20 different splits, the median relative increase in worst-case improvements equal 25.6% and 16.6% for source and target domains, respectively; the median decrease in average performance for source domains equals 7.5%; see Section 6.1 for more details.)

Figure 2: Visualization of possible solutions to the rank-1 approximation problem in a specific example. The figure shows contour plots of two distributions $\mathcal{N}(0,\Sigma_{1})$ (green) and $\mathcal{N}(0,\Sigma_{2})$ (orange), together with their supports (shaded planes). The methods $\mathtt{poolPCA}$ , $\mathtt{sepPCA}$ , $\mathtt{minPCA}$ , and $\mathtt{maxRegret}$ describe different ways to aggregate over different source domains in the objective function (see Section 2.2 for details); their solutions are denoted by $V^{\textrm{pool}}$ , $V^{\textrm{sep}}$ , $V^{\textrm{minPCA}}$ , and $V^{\textrm{maxRegret}}$ , respectively (the values in parentheses indicate the pooled and worst-case explained variance). For example, $V^{\textrm{pool}}$ and $V^{\textrm{sep}}$ explain $0\%$ of variance in the worst-case domain, as they are orthogonal to the support of that domain. In contrast, $V^{\textrm{minPCA}}$ maximizes the worst case explained variance (resulting in 36%) and $V^{\textrm{maxRegret}}$ explains at least 24% of variance in each domain. Details are provided in Example 1 .

		Objective function
Normalized		Explained variance		Reconstruction error		Regret
		(Def. 2 )		(Def. 3 )		(Def. 4 )
	No	$\mathtt{minPCA}$	$\neq$	$\mathtt{maxRCS}$	$\neq$	$\mathtt{maxRegret}$	$\neq$
		$\neq$		$\neq$		$\neq$
	Yes	$\mathtt{norm}\textrm{-}\mathtt{minPCA}$	$=$	$\mathtt{norm}\textrm{-}\mathtt{maxRCS}$	$\neq$	$\mathtt{norm}\textrm{-}\mathtt{maxRegret}$	$\neq$

Table 1: The six worst-case PCA formulations considered in this work: three objectives (explained variance, reconstruction error, and regret) combined with two normalization choices (normalized vs. unnormalized). The symbols

=

and

\neq

indicate whether the solutions coincide (see Theorem 6 ). The equality holds if the methods are applied to the full (and usually unknown) distribution or to its empirical counterpart.

Figure 5: Finite-sample performance of $\mathtt{maxRCS}$ ; see Section 5.1.3 . Left : Difference in worst-case loss (reconstruction error) over the convex hull of the population covariance matrices between empirical and population $\mathtt{maxRCS}$ . Right : Analogous difference between between empirical $\mathtt{maxRCS}$ and empirical $\mathtt{poolPCA}$ . Negative values indicate that $\mathtt{maxRCS}$ attains lower worst-case error than $\mathtt{poolPCA}$ . Across sample sizes, $\mathtt{maxRCS}$ outperforms $\mathtt{poolPCA}$ .

Figure 6: Regret may be preferable under heterogeneous noise; see Section 5.1.4 . Left : As suggested by the population theory, solutions to

\mathtt{maxRCS}

and

\mathtt{maxRegret}

are almost identical in the noiseless case. With heterogeneous noise,

\mathtt{maxRegret}

behaves similarly as if the data were noiseless. Right : When

k

is strictly smaller than the rank of the covariance matrices, solutions to

\mathtt{maxRCS}

and

\mathtt{maxRegret}

differ in the noiseless case. Nevertheless, under heterogeneous noise,

\mathtt{maxRegret}

can still be preferable over

\mathtt{maxRCS}

even if the evaluation criteria is reconstruction error.

Figure 7: Worst-case inductive matrix completion with partially observed source domains (90% missing entries; regime (ii)). Left: Difference in average and worst-case test reconstruction error between $\mathtt{maxMC}$ and $\mathtt{poolMC}$ . In line with Theorem 14 (which covers the population case and allows for some $\epsilon$ deviation), $\mathtt{maxMC}$ generally improves worst-case performance; in terms of average error, it incurs only minor changes. Right: Worst-case difference as the proportion of missing target entries varies, for different heterogeneity levels $(\alpha,\beta)$ . $\mathtt{maxMC}$ achieves lower median worst-case error than $\mathtt{poolMC}$ , with larger gains under stronger domain heterogeneity.

Panel of Figure 8 — Figure 8: Left : Map of FLUXNET sites, colored by TransCom region. Right : Relative difference in worst-case proportion of explained variance between $\mathtt{poolPCA}$ and $\mathtt{maxRegret}$ , $\mathtt{norm}\textrm{-}\mathtt{maxRegret}$ , $\mathtt{norm}\textrm{-}\mathtt{maxRCS}$ , and $\mathtt{avgcovPCA}$ , evaluated on held-out target regions over 20 random train–test splits. Positive values indicate improved worst-case performance relative to pooled PCA. The worst-case objectives generally improve robustness, with $\mathtt{norm}\textrm{-}\mathtt{maxRegret}$ achieving the strongest gains in median worst-case proportion of explained variance.

Figure 9: Comparison of dimensionality reduction methods on ecosystem function data across continents. Left : Proportion of variance explained on the pooled dataset. Centre : Worst-case proportion of variance explained across continents. Right : Loadings of the top three principal components for

\mathtt{poolPCA}

and

\mathtt{norm}\textrm{-}\mathtt{maxRCS}

\mathtt{norm}\textrm{-}\mathtt{maxRCS}

improves worst-case proportion of explained variance with negligible loss in average performance, while largely retaining the physical interpretability of the principal axes.

Appendix figures & tables7 assets

Supplementary material from the paper’s appendix.

Appendix

Figure B.i: Comparison of projected gradient descent (PGD; used in our experiments) with the optimization schemes of Wang et al. (2025) (StablePCA) and Tantipongpipat et al. (2019) (MW and SDP) for solving $\mathtt{minPCA}$ . Results are shown for $(p,E)\in\{(10,5),(10,50),(50,5)\}$ where $p$ is the number of features and $E$ is the number of domains. Top row : median difference in minimum explained variance relative to that of PGD ( negative values indicate that PGD explains more variance in the worst case) as a function of the number of components $k$ . Bottom row : runtime in seconds for each algorithm. Shaded regions represent the 25%-75% quantiles. PGD attains similar objective values to both baselines, with acceptable runtime.

Figure B.ii: Comparison of PGD, StablePCA, MW, and SDP for solving $\mathtt{maxRegret}$ for $(p,E)=(10,5)$ . PGD achieves comparable (or better) maximum regret values (positive values indicate that PGD performs better, i.e., has a lower worst-case regret).

Figure B.iii: Worst-case inductive matrix completion with fully observed source domains; regime (i). Left: Difference in average and worst-case test reconstruction error between $\mathtt{maxMC}$ and $\mathtt{poolMC}$ . In line with Theorem 14 (which covers the population case and allows for some $\epsilon$ deviation), $\mathtt{maxMC}$ generally improves worst-case performance; in terms of average error, it incurs only minor changes. Right: Worst-case difference as the proportion of missing target entries varies, for different heterogeneity levels $(\alpha,\beta)$ . $\mathtt{maxMC}$ achieves lower median worst-case error than $\mathtt{poolMC}$ , with larger gains under stronger domain heterogeneity.

Figure C.i: Scree plots for each TransCom region (shown in different colours). In Section 6.1 , we use rank-2 approximations.

Figure C.ii: Relative difference in worst-case proportion of explained variance between

\mathtt{poolPCA}

and, from top to bottom,

\mathtt{maxRegret}

\mathtt{norm}\textrm{-}\mathtt{maxRegret}

\mathtt{norm}\textrm{-}\mathtt{maxRCS}

, and

\mathtt{avgcovPCA}

. Positive values indicate improved worst-case performance relative to

\mathtt{poolPCA}

. Results are shown for 20 random region splits, evaluated on the source and target regions across varying numbers of principal components. Apart from the rank-one case, the worst-case objectives exhibit improved robustness or similar behavior to

\mathtt{poolPCA}

Variable	Description
GPP ${}_{\textrm{sat}}$	Maximum gross CO 2 uptake at light saturation
NEP ${}_{\textrm{max}}$	Maximum net ecosystem productivity
ET ${}_{\textrm{max}}$	Maximum evapotranspiration
EF	Evaporative fraction
EF ${}_{\textrm{ampl}}$	EF amplitude
GS ${}_{\textrm{max}}$	Maximum dry canopy surface conductance

Appendix

Table 2: Ecosystem functional properties used in the reanalysis of Migliavacca et al. (2021) .

Figure C.iii: Comparison of dimensionality reduction methods on the ecosystem function dataset. Left : Proportion of variance explained on the pooled dataset. Right : Worst-case proportion of variance explained across continents. Methods that account for domain heterogeneity outperform

\mathtt{poolPCA}

in the worst-case continent, with

\mathtt{norm}\textrm{-}\mathtt{maxRCS}

most closely matching pooled average performance.

Low-Rank Approximation

Low-rank approximation represents matrices, tensors, and model computations with fewer components to reduce storage and computation while preserving useful structure.

See all 93 papers

Inference and Uncertainty Quantification for Streaming $r$ -PCA
Aug 18, 2026Haoshu Xu, Hongzhe LiPrincipal Component Analysis
University of Pennsylvania
Lifting PCA in the Wasserstein Space
Oct 21, 2026Jérémie Bigot, Clément BonetPrincipal Component Analysis Optimal Transport
Institut de Mathématiques de Bordeaux, Université de Bordeaux, CNRS (UMR 5251) · CMAP, Ecole Polytechnique, Institut Polytechnique de Paris, CNRS (UMR 7641)
Scale-Calibrated Median-of-Means for Robust Distributed Principal Component Analysis
May 20, 2026Kisung YouPrincipal Component Analysis
Department of Mathematics, Baruch College · Department of Mathematics, The Graduate Center, City University of New York

Aug 18, 2026J/K move · Enter open · S save

Inference and Uncertainty Quantification for Streaming $r$ -PCA

Haoshu Xu, Hongzhe Li

University of Pennsylvania

Principal Component Analysis

Open paper AskPDF arXiv

We address two open questions in streaming PCA via Oja's algorithm: sharp operator-norm convergence for general rank under sub-Gaussian data, and distributional inference for the resulting subspace estimator. Existing convergence analyses, even in the rank-one case, either assume bounded data or leave non-vanishing remainder terms that prevent adaptation to a polynomially vanishing tail spectrum, while existing distributional results are confined to the rank-one case. Our convergence theory removes these remainder terms and yields a sharp rate. In the dense-tail spiked covariance regime, this rate matches the minimax rate up to logarithmic factors. More generally, we prove a matching lower bound, up to logarithmic factors, across both dense-tail and sparse-tail regimes under a mild nondegeneracy condition. The analysis yields a linearization of Oja's iterates, which in turn enables a high-dimensional Gaussian approximation for the general-rank subspace estimation error with an explicit limiting covariance. We also establish a row-wise Gaussian approximation over convex sets for the aligned difference, recovering prior rank-one results as special cases. For practical inference, we develop an online multiplier bootstrap algorithm and prove its consistency. Beyond streaming PCA, our techniques contribute to Gaussian approximation and bootstrap inference for nonconvex stochastic approximation.

Abstract

Low-Rank Approximation

Explore similar work

Inference and Uncertainty Quantification for Streaming rrr-PCA

Lifting PCA in the Wasserstein Space

Scale-Calibrated Median-of-Means for Robust Distributed Principal Component Analysis

Inference and Uncertainty Quantification for Streaming $r$ -PCA