# Subspace Recovery from Heterogeneous Data with Non-isotropic Noise

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 37 references that are in the map.
- First posted on arXiv 24 Oct 2022.

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

- [Exploiting Shared Representations for Personalized Federated Learning](https://mlsanity.com/paper/2102.07078/) (2021)
- [Few-Shot Learning via Learning the Representation, Provably](https://mlsanity.com/paper/2002.09434/) (2020)
- [The Benefit of Multitask Representation Learning](https://mlsanity.com/paper/1505.06279/) (2015)
- [On the Theory of Transfer Learning: The Importance of Task Diversity](https://mlsanity.com/paper/2006.11650/) (2020)
- [Provable Meta-Learning of Linear Representations](https://mlsanity.com/paper/2002.11684/) (2020)
- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [Meta-learning for mixed linear regression](https://mlsanity.com/paper/2002.08936/) (2020)
- [Heteroskedastic PCA: Algorithm, Optimality, and Applications](https://mlsanity.com/paper/1810.08316/) (2018)
- [On Polynomial Time Methods for Exact Low Rank Tensor Completion](https://mlsanity.com/paper/1702.06980/) (2017)
- [Efficient Aggregated Kernel Tests using Incomplete U-statistics](https://mlsanity.com/paper/2206.09194/) (2022)
- [Tight and Robust Private Mean Estimation with Few Users](https://mlsanity.com/paper/2110.11876/) (2021)
- [Sample Efficient Linear Meta-Learning by Alternating Minimization](https://mlsanity.com/paper/2105.08306/) (2021)
- [High-dimensional principal component analysis with heterogeneous missingness](https://mlsanity.com/paper/1906.12125/) (2019)
- [Asymmetry Helps: Eigenvalue and Eigenvector Analyses of Asymmetrically Perturbed Low-Rank Matrices](https://mlsanity.com/paper/1811.12804/) (2018)
- [Tackling small eigen-gaps: Fine-grained eigenvector estimation and inference under heteroscedastic noise](https://mlsanity.com/paper/2001.04620/) (2020)
- [User-Level Private Learning via Correlated Sampling](https://mlsanity.com/paper/2110.11208/) (2021)
- [Finite Sample Guarantees for PCA in Non-Isotropic and Data-Dependent Noise](https://mlsanity.com/paper/1709.06255/) (2017)
- [Fast Robust Subspace Tracking via PCA in Sparse Data-Dependent Noise](https://mlsanity.com/paper/2006.08030/) (2020)

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

- [Learning from Similar Linear Representations: Adaptivity, Minimaxity, and Robustness](https://mlsanity.com/paper/2303.17765/) (2023)
- [Federated Representation Learning in the Under-Parameterized Regime](https://mlsanity.com/paper/2406.04596/) (2024)
- [On the Benefits of Public Representations for Private Transfer Learning under Distribution Shift](https://mlsanity.com/paper/2312.15551/) (2023)
- [How Many Domains Suffice for Domain Generalization? A Tight Characterization via the Domain Shattering Dimension](https://mlsanity.com/paper/2506.16704/) (2025)
- [Differentially private sliced inverse regression in the federated paradigm](https://mlsanity.com/paper/2306.06324/) (2023)
- [Learning with Shared Representations: Statistical Rates and Efficient Algorithms](https://mlsanity.com/paper/2409.04919/) (2024)
- [When More Data Doesn't Help: Limits of Adaptation in Multitask Learning](https://mlsanity.com/paper/2601.20774/) (2026)
- [Estimation of Models with Limited Data by Leveraging Shared Structure](https://mlsanity.com/paper/2310.02864/) (2023)
- [Meta-learning of shared linear representations beyond well-specified linear regression](https://mlsanity.com/paper/2501.18975/) (2025)
- [Subspace Recovery in Winsorized PCA: Insights into Accuracy and Robustness](https://mlsanity.com/paper/2502.16391/) (2025)
- [GeoERM: Geometry-Aware Multi-Task Representation Learning on Riemannian Manifolds](https://mlsanity.com/paper/2505.02972/) (2025)
- [Robust and Adaptive Spectral Method for Representation Multi-Task Learning with Contamination](https://mlsanity.com/paper/2509.06575/) (2025)
- [On the Power of Source Screening for Learning Shared Feature Extractors](https://mlsanity.com/paper/2602.16125/) (2026)
- [Near-optimal and Efficient First-Order Algorithm for Multi-Task Learning with Shared Linear Representation](https://mlsanity.com/paper/2605.00473/) (2026)

## Abstract (arXiv)

Recovering linear subspaces from data is a fundamental and important task in statistics and machine learning. Motivated by heterogeneity in Federated Learning settings, we study a basic formulation of this problem: the principal component analysis (PCA), with a focus on dealing with irregular noise. Our data come from n users with user i contributing data samples from a d-dimensional distribution with mean μi. Our goal is to recover the linear subspace shared by μ1,ldots,μn using the data points from all users, where every data point from user i is formed by adding an independent mean-zero noise vector to μi. If we only have one data point from every user, subspace recovery is information-theoretically impossible when the covariance matrices of the noise vectors can be non-spherical, necessitating additional restrictive assumptions in previous work. We avoid these assumptions by leveraging at least two data points from each user, which allows us to design an efficiently-computable estimator under non-spherical and user-dependent noise. We prove an upper bound for the estimation error of our estimator in general scenarios where the number of data points and amount of noise can vary across users, and prove an information-theoretic error lower bound that not only matches the upper bound up to a constant factor, but also holds even for spherical Gaussian noise. This implies that our estimator does not introduce additional estimation error (up to a constant factor) due to irregularity in the noise. We show additional results for a linear regression problem in a similar setup.