1.1 Problem Statement

1.2 Results and Techniques

Eigenvalue Gaps, \(\kappa _V\), and Pseudospectral Shattering. The key probabilistic result of the paper is that a random complex Gaussian perturbation of any matrix yields a nearby matrix with large minimum eigenvalue gap and small \(\kappa _V\).

The proof of Theorem 1.4 appears in Sect. 3.1. The key idea is to first control \(\kappa _V(X)\) using [9] and then observe that for a matrix with small \(\kappa _V\), two eigenvalues of X near a complex number z imply a small second-least singular value of \(z-X\), which we are able to control.

In Sect. 3.2 we develop the notion of pseudospectral shattering, which is implied by Theorem 1.4 and says roughly that the pseudospectrum consists of n components that lie in separate squares of an appropriately coarse grid in the complex plane. This is useful in the analysis of the spectral bisection algorithm in Sect. 5.

The main new idea in the proof of Theorem 1.5 is to control the evolution of the pseudospectra \(\Lambda _{\epsilon _k}(A_k)\) of the iterates with appropriately decreasing (in k) parameters \(\epsilon _k\), using a sequence of carefully chosen shrinking contour integrals in the complex plane. The pseudospectrum provides a richer induction hypothesis than scalar quantities such as condition numbers, and allows one to control all quantities of interest using the holomorphic functional calculus. This technique is introduced in Sects. 4.1 and 4.2, and carried out in finite arithmetic in Sect. 4.3, yielding Theorem 1.5.

Diagonalization by Spectral Bisection. Given an algorithm for computing the sign function, there is a natural and well-known approach to the eigenproblem pioneered in [11]. The idea is that the matrices \((I\pm \mathrm {sgn}(A))/2\) are spectral projectors onto the invariant subspaces corresponding to the eigenvalues of A in the left and right open half planes, so if some shifted matrix \(z + A\) or \(z + iA\) has roughly half its eigenvalues in each half plane, the problem can be reduced to smaller subproblems appropriate for recursion.

The two difficulties in carrying out the above approach are: (a) efficiently computing the sign function (b) finding a balanced splitting along an axis that is well-separated from the spectrum. These are nontrivial even in exact arithmetic, since the iteration (8) converges slowly if (b) is not satisfied, even without roundoff error. We use Theorem 1.4 to ensure that a good splitting always exists after a small Gaussian perturbation of order \(\delta \), and Theorem 1.5 to compute splittings efficiently in finite precision. Combining this with well-understood techniques such as rank-revealing QR factorization, we obtain the following theorem, whose proof appears in Sect. 5.1.

Since there is a correspondence in terms of the condition number between backward and forward approximations, and as it is customary in numerical analysis, our discussion revolves around backward approximation guarantees. For convenience of the reader, we write down below the explicit guarantees that one gets by using (4) and invoking \(\mathsf {EIG}\) with accuracy \(\frac{\delta }{6n \kappa _{\mathrm {eig}}}\).

1.3 Related Work

Minimum Eigenvalue Gap. The minimum eigenvalue gap of random matrices has been studied in the case of Hermitian and unitary matrices, beginning with the work of Vinson [64], who proved an \(\Omega (n^{-4/3})\) lower bound on this gap in the case of the Gaussian Unitary Ensemble (GUE) and the Circular Unitary Ensemble (CUE). Bourgade and Ben Arous [3] derived exact limiting formulas for the distributions of all the gaps for the same ensembles. Nguyen, Tao, and Vu [50] obtained non-asymptotic inverse polynomial bounds for a large class of non-integrable Hermitian models with i.i.d. entries (including Bernoulli matrices).

In a different direction, Aizenman et al. proved an inverse-polynomial bound [1] in the case of an arbitrary Hermitian matrix plus a GUE matrix or a Gaussian orthogonal ensemble (GOE) matrix, which may be viewed as a smoothed analysis of the minimum gap. Theorem 3.6 may be viewed as a non-Hermitian analogue of the last result.

In the non-Hermitian case, Ge [33] obtained an inverse polynomial bound for i.i.d. matrices with real entries satisfying some mild moment conditions, and [55]⁵ proved an inverse polynomial lower bound for the complex Ginibre ensemble. Theorem 3.6 may be seen as a generalization of these results to non-centered complex Gaussian matrices.

Smoothed Analysis and Free Probability. The study of numerical algorithms on Gaussian random matrices (i.e., the case \(A=0\) of smoothed analysis) dates back to [25, 29, 56, 65]. The powerful idea of improving the conditioning of a numerical computation by adding a small amount of Gaussian noise was introduced by Spielman and Teng in [59], in the context of the simplex algorithm. Sankar, Spielman, and Teng [54] showed that adding real Gaussian noise to any matrix yields a matrix with polynomially bounded condition number; [9] can be seen as an extension of this result to the condition number of the eigenvector matrix, where the proof crucially requires that the Gaussian perturbation is complex rather than real. The main difference between our results and most of the results on smoothed analysis (including [2]) is that our running time depends logarithmically rather than polynomially on the size of the perturbation.

The broad idea of regularizing the spectral instability of a nonnormal matrix by adding a random matrix can be traced back to the work of Śniady [58] and Haagerup and Larsen [37] in the context of Free Probability theory.

In the special case of Hermitian matrices, Higham [38] established efficient reductions between the sign function and the polar decomposition. Byers and Xu [16] proved backward stability of a certain scaled version of the Newton iteration for Hermitian matrices, in the context of computing the polar decomposition. Higham and Nakatsukasa [49] (see also the improvement [48]) proved backward stability of a different iterative scheme for computing the polar decomposition, and used it to give backward stable spectral bisection algorithms for the Hermitian eigenproblem with \(O(n^3)\)-type complexity.

Non-Hermitian Eigenproblem. Floating Point Arithmetic. The eigenproblem has been thoroughly studied in the numerical analysis community, in the floating point model of computation. While there are provably fast and accurate algorithms in the Hermitian case (see the next subsection) and a large body of work for various structured matrices (see, e.g., [13]), the general case is not nearly as well-understood. As recently as 1997, J. Demmel remarked in his well-known textbook [26]: “\(\ldots \) the problem of devising an algorithm [for the non-Hermitian eigenproblem] that is numerically stable and globally (and quickly!) convergent remains open.”

As far as we are aware, there are no other published provably polynomial-time algorithms for the general eigenproblem. The two standard references for diagonalization appearing most often in theoretical computer science papers do not meet this criterion. In particular, the widely cited work by Pan and Chen [51] proves that one can compute the eigenvalues of A in \(O(n^\omega + n\log \log (1/\delta ))\) (suppressing logarithmic factors) arithmetic operations by finding the roots of its characteristic polynomial, which becomes a bound of \(O(n^{\omega +1}a+n^2\log (1/\delta )\log \log (1/\delta ))\) bit operations if the characteristic polynomial is computed exactly in rational arithmetic and the matrix has entries of bit length a. However that paper does not give any bound for the amount of time taken to find approximate eigenvectors from approximate eigenvalues, and states this as an open problem.⁹

Finally, the important work of Demmel et al. [22] (see also the followup [6]), which we rely on heavily, does not claim to provably solve the eigenproblem either—it bounds the running time of one iteration of a specific algorithm, and shows that such an iteration can be implemented numerically stably, without proving any bound on the number of iterations required in general.

Hermitian Eigenproblem. For comparison, the eigenproblem for Hermitian matrices is much better understood. We cannot give a complete bibliography of this huge area, but mention one relevant landmark result: the work of Wilkinson [66], who exhibited a globally convergent diagonalization algorithm, and the work of Dekker and Traub [21] who quantified the rate of convergence of Wilkinson’s algorithm and from which it follows that the Hermitian eigenproblem can be solved with backward error \(\delta \) in \(O(n^3+n^2\log (1/\delta ))\) arithmetic operations in exact arithmetic.¹⁰ We refer the reader to [52,  §8.10] for the simplest and most insightful proof of this result, due to Hoffman and Parlett [41]

There has also recently been renewed interest in this problem in the theoretical computer science community, with the goal of bringing the runtime close to \(O(n^\omega )\): Louis and Vempala [45] show how to find a \(\delta \)-approximation of just the largest eigenvalue in \(O(n^\omega \log ^4(n)\log ^2(1/\delta ))\) bit operations, and Ben-Or and Eldar [12] give an \(O(n^{\omega +1}\mathrm {polylog}(n))\)-bit-operation algorithm for finding a \(1/\mathrm {poly}(n)\)-approximate diagonalization of an \(n\times n\) Hermitian matrix normalized to have \(\Vert A\Vert \le 1\).

Reader Guide. This paper contains a lot of parameters and constants. On first reading, it may be good to largely ignore the constants not appearing in exponents and to keep in mind the typical setting \(\delta =1/\mathrm {poly}(n)\) for the accuracy, in which case the important auxiliary parameters \(\omega , 1-\alpha , \epsilon , \beta , \eta \) are all \(1/\mathrm {poly}(n)\), and the machine precision is \(\log (1/{\textbf {u }})=\mathrm {polylog}(n)\).

2.1 Spectral Projectors and Holomorphic Functional Calculus

Since every spectral projector P commutes with M, its range agrees exactly with an invariant subspace of M. We will often find it useful to choose some region of the complex plane bounded by a simple closed positively oriented rectifiable curve \(\Gamma \), and compute the spectral projector onto the invariant subspace spanned by those eigenvectors whose eigenvalues lie inside \(\Gamma \). Such a projector can be computed by a contour integral analogous to the above.

Recall that if f is any function, and M is diagonalizable, then we can meaningfully define \(f(M) := V f(D) V^{-1}\), where f(D) is simply the result of applying f to each element of the diagonal matrix D. The holomorphic functional calculus gives an equivalent definition that extends to the case when M is non-diagonalizable. As we will see, it has the added benefit that bounds on the norm of the resolvent of M can be converted into bounds on the norm of f(M).

2.2 Pseudospectrum and Spectral Stability

The \(\epsilon \)-pseudospectrum of a matrix is defined in (5). Directly from this definition, we can relate the pseudospectra of a matrix and a perturbation of it.

It is also immediate that \(\Lambda (M) \subset \Lambda _\epsilon (M)\), and in fact a stronger relationship holds as well:

In this paper we will repeatedly use that assumptions about the pseudospectrum of a matrix can be turned into stability statements about functions applied to the matrix via the holomorphic functional calculus. Here we describe an instance of particular importance.

2.3 Finite-Precision Arithmetic

Throughout the paper, we will take the pedagogical perspective that our algorithms are games played between the practitioner and an adversary who may additively corrupt each operation. In particular, we will include explicit error terms (always denoted by \(E_{(\cdot )}\)) in each appropriate step of every algorithm. In many cases we will first analyze a routine in exact arithmetic—in which case the error terms will all be set to zero—and subsequently determine the machine precision \({\textbf {u }}\) necessary so that the errors are small enough to guarantee convergence.

2.4 Sampling Gaussians in Finite Precision

For various parts of the algorithm, we will need to sample from normal distributions. For our model of arithmetic, we assume that the complex normal distribution can be sampled up to machine precision in O(1) arithmetic operations. To be precise, we assume the existence of the following sampler:

Note that, since the Gaussian distribution has unbounded support, one should only expect the sampler \(\mathsf {N}(\sigma )\) to have a relative error guarantee of the sort \(|{\widetilde{G}} - G| \le c_{\mathsf {N}}\sigma |G| \cdot {\textbf {u }}\). However, as it will become clear below, we only care about realizations of Gaussians satisfying \(|G|<R\), for a certain prespecified \(R>0\), and the rare event \(|G|>R\) will be accounted for in the failure probability of the algorithm. So, for the sake of exposition we decided to omit the |G| in the bound on \(|{\widetilde{G}}-G|\).

We will only sample \(O(n^2)\) Gaussians during the algorithm, so this sampling will not contribute significantly to the runtime. Here as everywhere in the paper, we will omit issues of underflow or overflow. Throughout this paper, to simplify some of our bounds, we will also assume that \(c_{\mathsf {N}}\ge 1\).

2.5 Black-box Error Assumptions for Multiplication, Inversion, and QR

Our algorithm uses matrix–matrix multiplication, matrix inversion, and QR factorization as primitives. For our analysis, we must therefore assume some bounds on the error and runtime costs incurred by these subroutines. In this section, we first formally state the kind of error and runtime bounds we require, and then discuss some implementations known in the literature that satisfy each of our requirements with modest constants.

Our definitions are inspired by the definition of logarithmic stability introduced in [22]. Roughly speaking, they say that implementing the algorithm with floating point precision \({\textbf {u }}\) yields an accuracy which is at most polynomially or quasipolynomially in n worse than \({\textbf {u }}\) (possibly also depending on the condition number in the case of inversion). Their definition has the property that while a logarithmically stable algorithm is not strictly speaking backward stable, it can attain the same forward error bound as a backward stable algorithm at the cost of increasing the bit length by a polylogarithmic factor. See Section 3 of their paper for a precise definition and a more detailed discussion of how their definition relates to standard numerical stability notions.

The above definitions can be instantiated with traditional \(O(n^3)\)-complexity algorithms for which \(\mu _{\mathsf {MM}}, \mu _\mathsf {QR}, \mu _{\mathsf {INV}}\) are all O(n) and \(c_\mathsf {INV}=1\) [39]. This yields easily implementable practical algorithms with running times depending cubically on n.

In order to achieve \(O(n^\omega )\)-type efficiency, we instantiate them with fast-matrix-multiplication-based algorithms and with \(\mu (n)\) taken to be a low-degree polynomial [22]. Specifically, the following parameters are known to be achievable.

We remark that for specific existing fast matrix multiplication algorithms such as Strassen’s algorithm, specific small values of \(\mu _\mathsf {MM}(n)\) are known (see [23] and its references for details), so these may also be used as a black box, though we will not do this in this paper.

3.1 Smoothed Analysis of Gap and Eigenvector Condition Number

As is customary in the literature, we will refer to an \(n\times n\) random matrix \(G_n\) whose entries are independent complex Gaussians drawn from \(\mathcal {N}(0,1_\mathbb {C}/n)\) as a normalized complex Ginibre random matrix. To be absolutely clear, and because other choices of scaling are quite common, we mean that \(\mathbb {E}G_{i,j} = 0\) and \(\mathbb {E}|G_{i,j}|^2 = 1/n\).

In the course of proving Theorem 1.4, we will need to bound the probability that the second-smallest singular value of an arbitrary matrix with small Ginibre perturbation is atypically small. We begin with a well-known lower tail bound on the singular values of a Ginibre matrix alone.

As in several of the authors’ earlier work [9], we can transfer this result to case of a Ginibre perturbation via a remarkable coupling result of P. Śniady.

We will need as well the main theorem of [9], which shows that the addition of a small complex Ginibre to an arbitrary matrix tames its eigenvalue condition numbers.

Our final lemma before embarking on the proof in earnest shows that bounds on the j-th smallest singular value and eigenvector condition number are sufficient to rule out the presence of j eigenvalues in a small region. For our particular application, we will take \(j=2\).

We now present the main tail bound that we use to control the minimum gap and eigenvector condition number.

A specific setting of parameters in Theorem 3.6 immediately yields Theorem 1.4.

Since it is of independent interest in random matrix theory, we record the best bound on the gap alone that is possible to extract from the theorem above.

3.2 Shattering

Propositions 2.2 and 2.3 in the preliminaries together tell us that if the \(\epsilon \)-pseudospectrum of an \(n\times n\) matrix A has n connected components, then each eigenvalue of any size-\(\epsilon \) perturbation \({\widetilde{A}}\) will lie in its own connected component of \(\Lambda _\epsilon (A)\). The following key definitions make this phenomenon quantitative in a sense which is useful for our analysis of spectral bisection.

As a warm-up for more sophisticated arguments later on, we give here an easy consequence of the shattering property.

The theorem below quantifies the extent to which perturbing by a Ginibre matrix results in a shattered pseudospectrum. See Fig. 1 for an illustration in the case where the initial matrix is poorly conditioned. In general, not all eigenvalues need move so far upon such a perturbation, in particular if the respective \(\kappa _i\) are small.

Finally, we show that the shattering property is retained when the Gaussian perturbation is added in finite precision rather than exactly. This also serves as a pedagogical warm-up for our presentation of more complicated algorithms later in the paper: we use E to represent an adversarial roundoff error (as in step 2), and for simplicity neglect roundoff error completely in computations whose size does not grow with n (such as steps 3 and 4, which set scalar parameters).

4.1 Circles of Apollonius

It has been known since antiquity that a circle in the plane may be described as the set of points with a fixed ratio of distances to two focal points. By fixing the focal points and varying the ratio in question, we get a family of circles named for the Greek geometer Apollonius of Perga. We will exploit several interesting properties enjoyed by these Circles of Apollonius in the analysis below.

More precisely, we analyze the Newton iteration map \(g\) in terms of the family of Apollonian circles whose foci are the points \(\pm 1 \in \mathbb {C}\). For the remainder of this section we will write \(m(z) = \tfrac{1 - z}{1 + z}\) for the Möbius transformation taking the right half-plane to the unit disk, and for each \(\alpha \in (0,1)\) we denote by

$$\begin{aligned} \mathsf {C}^{+}_{\alpha } = \left\{ z \in \mathbb {C}: |m(z)| \le \alpha \right\} , \quad \mathsf {C}^{-}_{\alpha } = \{ z \in {\mathbb {C}} : |m(z)|^{-1} \le \alpha \} \end{aligned}$$

the closed region in the right (respectively left) half-plane bounded by such a circle. Write \(\partial \mathsf {C}^{+}_{\alpha }\) and \(\partial \mathsf {C}^{-}_{\alpha }\) for their boundaries, and \(\mathsf {C}_{\alpha } = \mathsf {C}^{+}_{\alpha } \cup \mathsf {C}^{-}_{\alpha }\) for their union. See Fig. 2 for an illustration.

It follows from Observation 4.1 that under repeated application of the Newton map g, any point in the right or left half-plane converges to \(+1\) or \(-1\), respectively.

4.2 Exact Arithmetic

In this section, we set \(A_0 := A\) and \(A_{k+1} := g(A_k)\) for all \(k \ge 0\). In the case of exact arithmetic, Observation 4.1 implies global convergence of the Newton iteration when A is diagonalizable. For the convenience of the reader, we provide this argument (due to [53]) below.

The above analysis becomes useless when trying to prove the same statement in the framework of finite arithmetic. This is due to the fact that at each step of the iteration the roundoff error can make the eigenvector condition numbers of the \(A_k\) grow. In fact, since \(\kappa _V(A_k)\) is sensitive to infinitesimal perturbations whenever \(A_k\) has a multiple eigenvalue, it seems difficult to control it against adversarial perturbations as the iteration converges to \(\mathrm {sgn}(A_k)\) (which has very high multiplicity eigenvalues). A different approach, also due to [53], yields a proof of convergence in exact arithmetic even when A is not diagonalizable. However, that proof relies heavily on the fact that \(m(A_N)\) is an exact power of \(m(A_0)\), or more precisely, it requires the sequence \(A_k\) to have the same generalized eigenvectors, which is again not the case in the finite arithmetic setting.

Therefore, a robust version, tolerant to perturbations, of the above proof is needed. To this end, instead of simultaneously keeping track of the eigenvector condition number and the spectrum of the matrices \(A_k\), we will just show that for certain \(\epsilon _k > 0\), the \(\epsilon _k\)-pseudospectra of these matrices are contained in a certain shrinking region dependent on k. This invariant is inherently robust to perturbations smaller than \(\epsilon _k\), unaffected by clustering of eigenvalues due to convergence, and allows us to bound the accuracy and other quantities of interest via the functional calculus. For example, the following lemma shows how to obtain a bound on \(\Vert A_N- \mathrm {sgn}(A)\Vert \) solely using information from the pseudospectrum of \(A_N\).

The lemma below is instrumental in determining the sequences \(\alpha _k, \epsilon _k\).

Lemma 4.4 will also be useful in bounding the condition numbers of the \(A_k\), which is necessary for the finite arithmetic analysis.

Another direct application of Lemma 4.4 yields the following.

We are now ready to prove the main result of this section, a pseudospectral version of Proposition 4.2.

4.3 Finite Arithmetic

Finally, we turn to the analysis of \(\mathsf {SGN}\) in finite arithmetic. By making the machine precision small enough, we can bound the effect of roundoff to ensure that the parameters \(\alpha _k\), \(\epsilon _k\) are not too far from what they would have been in the exact arithmetic analysis above. We will stop the iteration before any of the quantities involved become prohibitively small, so we will only need \(\mathrm {polylog}(1-\alpha _0, \epsilon _0, \beta )\) bits of precision, where \(\beta \) is the accuracy parameter.

In exact arithmetic, recall that the Newton iteration is given by \(A_{k+1} = g(A_{k}) = \frac{1}{2} (A_k + A_k^{-1}).\) Here we will consider the finite arithmetic version \(\mathsf {G}\) of the Newton map \(g\), defined as \(\mathsf {G}(A) := g(A)+E_A\) where \(E_A\) is an adversarial perturbation coming from the roundoff error. Hence, the sequence of interest is given by \({\widetilde{A}}_0 := A\) and \({\widetilde{A}}_{k+1} := \mathsf {G}({\widetilde{A}}_k)\) .

In this subsection we will prove the following theorem concerning the runtime and precision of \(\mathsf {SGN}\). Our assumptions on the size of the parameters \(\alpha _0, \beta , \mu _{\mathsf {INV}}(n)\) and \(c_\mathsf {INV}\) are in place only to simplify the analysis of constants; these assumptions are not required for the execution of the algorithm.

Later on, we will need to call \(\mathsf {SGN}\) on a matrix with shattered pseudospectrum; the lemma below calculates acceptable parameter settings for shattering so that the pseudospectrum is contained in the required pair of Apollonian circles, satisfying the hypothesis of Theorem 4.9.

The proof of Theorem 4.9 will proceed as in the exact arithmetic case, with the modification that \(\epsilon _k\) must be decreased by an additional factor after each iteration to account for roundoff. At each step, we set the machine precision \({\textbf {u }}\) small enough so that the \(\epsilon _k\) remain close to what they would be in exact arithmetic. For the analysis we will introduce an explicit auxiliary sequence \(e_k\) that lower bounds the \(\epsilon _k\), provided that \({\textbf {u }}\) is small enough.

The proof of this lemma is deferred to “Appendix A”.

We now show that the conclusion of Lemma 4.12 still holds if we replace \(\epsilon _i\) everywhere in the hypothesis by \(e_i\), which is an explicit function of \(\epsilon _0\) and \(\alpha _0\) defined in Lemma 4.12. Note that we do not know \(\epsilon _i \ge e_i\) a priori, so to avoid circularity we must use a short inductive argument.

We would like to apply Lemma 4.14 to ensure \(\Vert \widetilde{A_N} - \mathrm {sgn}(A) \Vert \) is at most \(\beta \), the desired accuracy parameter. The upper bound (38) in Lemma 4.14 is the sum of two terms; we will make each term less than \(\beta /2\). The bound for the second term will yield a sufficient condition on the number of iterations N. Given that, the bound on the first term will then give a sufficient condition on the machine precision \({\textbf {u }}\). This will be the content of Lemmas 4.16 and 4.17.

We start with the second term. The following preliminary lemma will be useful:

The proof is deferred to “Appendix A”.

Now we move to the first term in the bound of Lemma 4.14.

Matching the statement of Theorem 4.9, we give a slightly cleaner sufficient condition on N that implies the hypothesis on N appearing in the above lemmas. The proof is deferred to “Appendix A”.

Taking the logarithm of the machine precision yields the number of bits required:

This completes the proof of Theorem 4.9. Finally, we may prove the theorem advertised in Sect. 1.

5.1 Proof of Theorem 5.5

A key stepping-stone in our proof will be the following elementary result controlling the spectrum, pseudospectrum, and eigenvectors after perturbing a shattered matrix.

The algorithm \(\mathsf {EIG}\) works by recursively reducing to subinstances of smaller size, but requires a pseudospectral guarantee to ensure speed and stability. We thus need to verify that the pseudospectrum does not deteriorate too substantially when we pass to a sub-problem.

Initial lemmas in hand, let us begin to analyze the algorithm. At several points we will make an assumption on the machine precision in the margin. These will be collected at the end of the proof, where we will verify that they follow from the precision hypothesis of Theorem 5.5.

Correctness.

Everything is now in place to show that, if every call to \(\mathsf {DEFLATE}\) succeeds, \(\mathsf {EIG}\) has the advertised accuracy guarantees. After we show this, we will lower bound this success probability and compute the running time.

Running Time and Failure Probability. Let’s begin with a simple lemma bounding the depth of \(\mathsf {EIG}\)’s recursion tree.

On each new call to \(\mathsf {EIG}\) the grid only decreases in size, so the initial assumption is sufficient. Finally, we need that every matrix passed to \(\mathsf {SPLIT}\) throughout the course of the algorithm has norm at most 4. Lemma 5.11 shows that if \(\Vert A\Vert \le 4\) and has its \(\epsilon \)-pseudospectrum shattered, then \(\Vert \widetilde{A_{\pm }} - A_{\pm }\Vert \le \epsilon /5\), and since \(\Vert A_{\pm }\Vert = \Vert A\Vert \), this means \(\Vert \widetilde{A_{\pm }}\Vert \le \Vert A\Vert + \epsilon /5\). Thus each time we pass to a subproblem, the norm of the matrix we pass to \(\mathsf {EIG}\) (and thus to \(\mathsf {SPLIT}\)) increases by at most an additive \(\epsilon /5\), where \(\epsilon \) is the input to the outermost call to \(\mathsf {EIG}\). Since \(\epsilon \) decreases by a factor of 4/5 on each recursion step, this means that by the end of the algorithm the norm of the matrix passed to \(\mathsf {EIG}\) will increase by at most an additive \((\epsilon + (4/5)\epsilon + (4/5)^2 \epsilon + \cdots )/5 = \epsilon \le 1/2\). Thus we will be safe if our initial matrix has norm at most 3.5, as assumed.

Required Bits of Precision. We will need the following bound on the norms of all spectral projectors.