  Approximating invariant subspaces of generalized eigenvalue problems (GEPs)
is a fundamental computational problem at the core of machine learning and
scientific computing. It is, for example, the root of Principal Component
Analysis (PCA) for dimensionality reduction, data visualization, and noise
filtering, and of Density Functional Theory (DFT), arguably the most popular
method to calculate the electronic structure of materials. For a Hermitian
definite GEP $HC=SC\Lambda$, let $\Pi_k$ be the true spectral projector on the
invariant subspace that is associated with the $k$ smallest (or largest)
eigenvalues. Given $H,$ $S$, an integer $k$, and accuracy
$\varepsilon\in(0,1)$, we show that we can compute a matrix $\widetilde\Pi_k$
such that $\lVert\Pi_k-\widetilde\Pi_k\rVert_2\leq \varepsilon$, in $O\left(
n^{\omega+\eta}\mathrm{polylog}(n,\varepsilon^{-1},\kappa(S),\mathrm{gap}_k^{-1})
\right)$ bit operations in the floating point model with probability $1-1/n$.
Here, $\eta>0$ is arbitrarily small, $\omega\lesssim 2.372$ is the matrix
multiplication exponent, $\kappa(S)=\lVert S\rVert_2\lVert S^{-1}\rVert_2$, and
$\mathrm{gap}_k$ is the gap between eigenvalues $k$ and $k+1$. To the best of
our knowledge, this is the first end-to-end analysis achieving such
"forward-error" approximation guarantees with nearly $O(n^{\omega+\eta})$ bit
complexity, improving classical $\widetilde O(n^3)$ eigensolvers, even for the
regular case $(S=I)$. Our methods rely on a new $O(n^{\omega+\eta})$ stability
analysis for the Cholesky factorization, and a new smoothed analysis for
computing spectral gaps, which can be of independent interest. Ultimately, we
obtain new matrix multiplication-type bit complexity upper bounds for PCA
problems, including classical PCA and (randomized) low-rank approximation.
