  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 $\mu_i$. Our goal is to recover the
linear subspace shared by $\mu_1,\ldots,\mu_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 $\mu_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.
