I'm probably missing a trivial answer, but somehow I can't find it.
Given symmetric matrix $A \in \mathbb R^{n \times n}$, what's the complexity of diagonalizing the matrix, i.e. finding diagonal $\Lambda = diag(\lambda_1, \ldots, \lambda_n)$ and orthogonal $Q \in \mathbb R^{n \times n}$ such that $$\|A - Q^{-1} \Lambda Q\| < \epsilon \|A\|?$$ Here I use the operator norm. You can assume that the largest eigenvalue of $A$ is bounded by constants from both above and below. You can assume that all eigenvalues are different (it can also be achieved by perturbing $A$).
Basically, I have $f(x) = x^\top A x$, and I need to guarantee that the function doesn't excessively change after diagonalization.
Eigenvalues can be approximated efficiently using e.g. shifted QR algorithm. For the eigenspaces, The complexity of the matrix eigenproblem claims to find them, but I'm confused about what their result is: the main theorem only talks about approximating eigenvalues. What exactly they mean by "associated eigenspaces" is unclear to me: both from the definition point of view (since the eigenvalues are only found approximately, they almost surely don't have the eigenspaces) and from the approximation point of view. Other papers also don't seem to show a concrete answer (again, maybe I misinterpret the results).
