REVIEW 2 major objections 6 minor 23 references
Approximation of the Pseudospectral Abscissa via Eigenvalue Perturbation Theory
T0 review · 2 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The pseudospectral abscissa is governed by a first-order eigenvalue-perturbation formula for small $\epsilon$, with an $O(\epsilon^3)$ refinement for matrices.
desk verdict A solid, honest paper that makes perturbation-theory-based pseudospectral abscissa approximation practical; the local results are rigorous and the global convergence claim is explicitly heuristic, with the failure rate disclosed. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The engine of the paper is the derivative of a simple eigenvalue under perturbation, $\mu'(0;\Delta)=-y^*\Delta T(\mu_0)x/(y^*T'(\mu_0)x)$, whose real part is maximized over unit-norm $\Delta$ by the rank-one update $\Delta T_j=w_j t_j(\mu_0)yx^*\big/\sqrt{\sum_\ell w_\ell^2|t_\ell(\mu_0)|^2}$, with the eigenvectors normalized so that $y^*T'(\mu_0)x$ is real and negative. That gives the $O(\epsilon^2)$ estimate. For matrices, a second-order Taylor expansion in the Frobenius norm, with finite-difference corrections to the eigenvectors, produces the rank-one matrix $\Delta^{\mu_0}_*$ whose rightmost eigenvalue carries the $O(\epsilon^3)$ estimate. The fixed-point iterations are driven by the backward-error identity $\varphi(z)=\sigma_{\min}(T(z))\big/\sqrt{\sum_j w_j^2|t_j(z)|^2}$, the minimal perturbation norm needed to make $z$ an eigenvalue; at each step one forms the minimal perturbation that makes the current point $z$ an eigenvalue and then moves to the rightmost eigenvalue of the perturbed problem. The fixed-point analysis characterizes limits as rbvt points, meaning the smallest singular value is simple, $z$ lies on the boundary of $\Lambda_\epsilon$, and the singular-vector projection $u^*v$ is real and positive.
What would settle it
Take a matrix with a defective repeated eigenvalue at the rightmost spectral position, so the left and right eigenvectors are orthogonal and the perturbation-theory denominator vanishes, and compare the right side of (16), or its matrix specialization, with a direct computation of $\alpha_\epsilon(A)$ for several small $\epsilon$; if the estimate is undefined or does not track $\alpha_\epsilon(A)$ to order $\epsilon^2$, the simplicity assumption is load-bearing. A second check is to record, for the failures reported in Section 7.2.3 at $\epsilon=0.5$ with $N=1$, whether the initializer (40) lies outside the connected component of $\Lambda_\epsilon(A)$ containing the global rightmost point.
Extended reading notes
Core claim
The paper establishes two asymptotic identities. For a regular analytic matrix-valued function $T(\lambda)=\sum_j t_j(\lambda)T_j$ with weighted perturbations, if every eigenvalue is simple and isolated and $\epsilon$ is small enough, then $\alpha_\epsilon(T)=\max_{\mu_0\in\Lambda(T)}\bigl(\operatorname{Re}(\mu_0)+\epsilon\,\sqrt{\sum_j w_j^2|t_j(\mu_0)|^2}\big/|y_{\mu_0}^*T'(\mu_0)x_{\mu_0}|\bigr)+O(\epsilon^2)$, where $x_{\mu_0},y_{\mu_0}$ are unit right and left eigenvectors. For a matrix $A$, using Frobenius-norm perturbations and a finite-difference correction to the eigenvectors, the paper proves $\alpha_\epsilon(A)=\max_{\mu_0\in\Lambda(A)}\alpha(A+\epsilon\,\Delta^{\mu_0}_*)+O(\epsilon^3)$, with $\Delta^{\mu_0}_*$ an explicit rank-one matrix built from the left and right eigenvectors of $\mu_0$ and of $A+h y_{\mu_0}x_{\mu_0}^*$. The paper further shows that the fixed-point maps built from these perturbation directions have a useful property: any nondegenerate limit must be an rbvt point, meaning a right boundary point with a vertical tangent, and the unique global rightmost point is always a fixed point. Numerically, initializing these locally convergent iterations with the perturbation-theory estimates returns the same values as globally convergent criss-cross algorithms on the tested quadratic matrix polynomials and matrices, in a fraction of the time.
Load-bearing premise
The load-bearing premise is that each eigenvalue is distinct and stays distinct under perturbation, with $\epsilon$ small enough that every eigenvalue follows one smooth path; the reported global convergence of the fixed-point iterations also leans on the unproved heuristic that the perturbation-theory starting point lies in the same pseudospectrum region as the global rightmost point.
Editorial extensions
If this is right
- For small $\epsilon$, $\alpha_\epsilon(T)$ can be estimated from one full eigenvalue and eigenvector computation plus a closed-form scalar evaluation per eigenvalue, with no criss-cross or pseudospectral boundary iteration.
- In the matrix case the $O(\epsilon^3)$ formula needs, for each eigenvalue, only one additional eigenvector solve at $A+h y_{\mu_0}x_{\mu_0}^*$ before computing the rightmost eigenvalue of a rank-one-updated matrix; this is the basis of the reported large-scale speedups.
- Theorem 5.1 gives a provable reason the initialization works: when the first-order model is exact, the maximizing eigenvalue and a global rightmost point lie in the same connected component of $\Lambda_\epsilon(T)$.
- If the fixed-point iteration converges to a nondegenerate point, that point is always an rbvt point; a second-derivative check at such a point decides whether it is locally rightmost.
- On the tested quadratic matrix polynomials and on dense and sparse matrices, the initialized iterations match the values returned by globally convergent criss-cross algorithms while using fewer iterations and less runtime.
Reading between the lines
- The first-order metric $\operatorname{Re}\mu_0+\epsilon/|y_{\mu_0}^*x_{\mu_0}|$ could itself be used as a screening function: for large sparse $A$, a Krylov method that targets the few largest values of this metric would bypass the full-spectrum bottleneck the paper identifies in its concluding remarks.
- The rbvt characterization suggests replacing the fixed-point iteration by a Newton-type boundary tracker on the two equations $\sigma_{\min}(T(z))\sqrt{\sum_j w_j^2|t_j(z)|^2}=\epsilon$ and $S(z)=0$, which could converge quadratically instead of linearly.
- The matrix second-order formula is derived with Frobenius-norm perturbations; the same two-term Taylor argument can likely be specialized to structured perturbations such as real, sparse, or banded ones, yielding structured pseudospectral abscissa estimates with the same $O(\epsilon^3)$ order.
- Table 10's restart experiments quantify how often the perturbation-theory initializer misses the global component; an adaptive restart rule based on gaps in the first-order metric, rather than a fixed $N$, would make the heuristic self-certifying.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper develops eigenvalue-perturbation-based approximations and fixed-point iterations for the pseudospectral abscissa. For a general nonlinear eigenvalue problem, a first-order formula with O(ε^2) error is derived (Theorem 2.3, Corollary 2.1), and for the standard eigenvalue problem a second-order formula with claimed O(ε^3) error is given (Theorem 4.2). Two fixed-point iterations (Algorithms 1 and 3) and their matrix specialization (Algorithm 4) are proposed, with fixed-point analyses showing that convergent nondegenerate limits must be rbvt points (Theorems 3.3, 3.4, 4.3). Section 5 discusses initialization using the perturbation formulas, Theorem 5.1 proving that the exact maximizer μ* of R(ε; μ0) lies in a connected component containing a global rightmost point. Numerical experiments on damping problems, stabilization examples, and EigTool matrices compare favorably with criss-cross and Guglielmi–Overton methods, including a 1000-matrix dataset reporting success rates in Table 10. MATLAB implementations are publicly available.
Significance. If the central results hold, the paper provides a cheap and accurate way to estimate global pseudospectral abscissae in the small-ε regime, and a new initialization strategy that appears to make locally convergent fixed-point iterations find the global rightmost point in a vast majority of tested cases. The second-order O(ε^3) formula for matrices is a new contribution. The paper is careful to state its assumptions (simplicity, small ε, nondegeneracy) and does not overclaim a global-convergence theorem. It also ships reproducible MATLAB code and validates against independent implementations (criss-cross, GO), which strengthens the empirical claims. The main weaknesses are the sketch-level derivation of the second-order formula and the unproved component-selection heuristic underlying the practical global claim; both are acknowledged or implicitly present, but need more explicit treatment.
major comments (2)
- [§4.2, Eqs. (33)–(36), Theorem 4.2] The derivation of the O(ε^3) approximation rests on several unquantified approximation steps: the maximizer is claimed to be of the form Δ* = yx* + O(ε), the eigenvector derivatives are replaced by finite differences with step h = O(ε), and the resulting matrix eΔ* is asserted to achieve the maximum up to O(ε^2) in the scaled objective. The text jumps from these approximations to the final O(ε^3) error without proving that the O(ε) errors in eΔ* and in the finite-difference derivative estimates do not propagate into O(ε^2) errors in Re{μ(ε; eΔ*)}. A detailed error analysis, for instance using first-order optimality and Lipschitz continuity of the eigenvector derivatives under the simplicity assumption, is needed to justify the O(ε^3) claim. This is load-bearing for the second-order formula (37) and for the hybrid initialization strategy built on it.
- [§5, Theorem 5.1 vs. Eqs. (39)–(40)] Theorem 5.1 guarantees that an exact maximizer μ* of R(ε; μ0) lies in a connected component of Λε(T) containing a global rightmost point, but the implemented initializer eμ* is the maximizer of the first-order surrogate in (39) or (40), not of R(ε; μ0). No result bounds the distance between eμ* and μ* or ensures that eμ* lands in the same component; the paper's own Table 10 shows failure rates up to 7.5% at ε = 0.5 with N = 1, which is consistent with this gap. Since the paper's practical claim is explicitly only that the method converges in a 'vast majority' of cases, this is not a fatal flaw, but the limitation should be stated openly in Section 5 (rather than left as 'seems plausible') and the abstract/conclusion should be worded to keep the empirical and proven statements distinct.
minor comments (6)
- [Abstract] The phrase 'built on the the perturbation theory ideas' contains a duplicated 'the'.
- [§2.3, proof of Theorem 2.3] In the sentence 'there must be (ΔT1, ..., ΔTκ) ∈ Sε such that z* ∈ Λε(T + ΔT)', the set should be Λ(T + ΔT), the spectrum of the perturbed function, not the ε-pseudospectrum.
- [§5, Theorem 5.1] The notation 'arg max_{μ0∈Λε(T)} R(ε; μ0)' is inconsistent with the domain of R(ε; ·), which is Λ(T); it should read 'arg max_{μ0∈Λ(T)} R(ε; μ0)'.
- [§7.2.2] The word 'Morover' is a typo for 'Moreover'.
- [References] Reference [22] spells the publisher as 'Princetion' (should be 'Princeton'), and reference [5] gives 'John Hopkins' (should be 'Johns Hopkins').
- [Proof of Theorem 3.3] In the interior case, 'Take any vector bv ∈ C' should read 'bv ∈ C^n'; the same notational issue appears with the expansion coefficients c, c2, ..., cn.
Circularity Check
No circularity: the perturbation-theory estimates are derived from first-order eigenvalue expansions and are validated against independent algorithms.
full rationale
The paper's central derivation is self-contained. The first-order estimate in Corollary 2.1 and Theorem 2.3 is obtained by differentiating the perturbed eigenvector equation (equation (10)), maximizing the resulting derivative L'_Delta(0) over the compact perturbation set S (Theorem 2.2), and then proving alpha_epsilon(T) = max_{mu0} R(epsilon; mu0) by elementary set-inclusion arguments that do not presuppose the estimate. The matrix second-order formula in Theorem 4.2 is derived by an explicit Taylor expansion of the analytic eigenvalue function, with the O(epsilon^3) error tracked through equations (33)-(35); no parameter is fitted to alpha_epsilon(A). The numerical validation compares against the independent criss-cross algorithms of Burke-Lewis-Overton and Mehrmann-Mengi and the Guglielmi-Overton fixed-point iteration, and the self-citations ([1], [2], [11]) are software releases, benchmark problems, or a standard singular-value derivative lemma that does not contain the target result. The practical initialization from (39)/(40) is explicitly presented as an empirical heuristic, and the paper reports its failure rates (e.g., Table 10, 7.5% failures at epsilon=0.5 with N=1), so the gap between local convergence and observed global behavior is a stated limitation rather than a circular reduction of the main claims.
Assumptions & free parameters
free parameters (2)
- restart count N =
N=1 default; N=7 used in Table 10
- finite-difference step h =
half machine precision in Remark 4.1
assumptions (7)
- standard math Rouché's theorem
- standard math Analytic implicit function theorem and Rellich's theorem
- domain assumption All eigenvalues of T (or A) are simple and isolated
- domain assumption ε is small enough that [0,ε]⊂U for every eigenvalue, and Assumption 2.1 attainment
- standard math Frobenius-norm and 2-norm pseudospectra of a matrix coincide
- standard math Eckart-Young theorem
- domain assumption Nondegeneracy of fixed points
Cite this review
Pith. "Pith review of Approximation of the Pseudospectral Abscissa via Eigenvalue Perturbation Theory." pith.science (2026). https://pith.science/paper/LVWV3GRX
@misc{pith2026250605535,
author = {Pith},
title = {Pith review of: Approximation of the Pseudospectral Abscissa via Eigenvalue Perturbation Theory},
year = {2026},
howpublished = {\url{https://pith.science/paper/LVWV3GRX}},
note = {Machine review of arXiv:2506.05535}
}
abstract
Reliable and efficient computation of the pseudospectral abscissa in the large-scale setting is still not settled. Unlike the small-scale setting where there are globally convergent criss-cross algorithms, all algorithms in the large-scale setting proposed to date are at best locally convergent. We first describe how eigenvalue perturbation theory can be put in use to estimate the globally rightmost point in the $\epsilon$-pseudospectrum if $\epsilon$ is small. Our treatment addresses both general nonlinear eigenvalue problems, and the standard eigenvalue problem as a special case. For small $\epsilon$, the estimates by eigenvalue perturbation theory are quite accurate. In the standard eigenvalue case, we even derive a formula with an ${\mathcal O}(\epsilon^3)$ error. For larger $\epsilon$, the estimates can be used to initialize the locally convergent algorithms. We also propose fixed-point iterations built on the the perturbation theory ideas for large $\epsilon$ that are suitable for the large-scale setting. The proposed fixed-point iterations initialized by using eigenvalue perturbation theory converge to the globally rightmost point in the pseudospectrum in a vast majority of the cases that we experiment with.
Figures
Figures from the paper (5 more)
Reference graph
Works this paper leans on
-
[1]
W. Ahmed and E. Mengi. LARGE_PSPA: Large-scale computation of the pseudospectral abscissa. https://zenodo.org/records/15442530, 2025
-
[2]
N. Aliyev and E. Mengi. Large-scale minimization of the pseudospectral abscissa.SIAM J. Matrix Anal. Appl., 45(4):2104–2134, 2024
work page 2024
-
[3]
J. V. Burke, A. S. Lewis, and M. L. Overton. Robust stability and a criss-cross algorithm for pseudospectra. IMA J. Numer. Anal., 23(3):359–375, 2003
work page 2003
-
[4]
Y. Genin and P. Van Dooren. Stability radii of polynomial matrices. InProceedings of the 1999 IEEE International Symposium on Computer Aided Control System Design, pages 81–84, 1999
work page 1999
-
[5]
G. H. Golub and C. F. Van Loan.Matrix Computations. John Hopkins University Press, Baltimore, MD, USA, third edition, 1996
work page 1996
-
[6]
N. Guglielmi and G. Lubich. Low-rank dynamics for computing extremal points of real pseu- dospectra. SIAM J. Matrix Anal. Appl., 34:40–66, 2013
work page 2013
-
[7]
N. Guglielmi and M. L. Overton. Fast algorithms for the approximation of the pseudospectral abscissa and pseudospectral radius of a matrix.SIAM J. Matrix Anal. Appl., 32(4):1166–1192, 2011
work page 2011
-
[8]
D. Kressner and B. Vandereycken. Subspace methods for computing the pseudospectral ab- scissa and stability radius.SIAM J. Matrix Anal. Appl., 35(1):292–313, 2014
work page 2014
Show all 23 references
-
[9]
Leibfritz
F. Leibfritz. COMPleib: COnstraint Matrix-optimization Problem library – a collection of test examples for nonlinear semidefinite programs, control system design and related problems. Technical report, Department of Mathematics, University of Trier, 2004
2004
-
[10]
Meerbergen, E
K. Meerbergen, E. Mengi, W. Michiels, and R. Van Beeumen. Computation of pseudospectral abscissa for large-scale nonlinear eigenvalue problems.IMA J. Numer. Anal., 37(4):1831–1863, 2017
2017
-
[11]
Mehrmann and E
V. Mehrmann and E. Mengi. Minimization of the pseudospectral abscissa of a quadratic matrix polynomial. arXiv preprint arXiv:2409.04297 [math.NA], 2024
2024 arXiv
-
[12]
E. Mengi. Measures for Robust Stability and Controllability. Dissertation, New York Univer- sity, 2006
2006
-
[13]
Green, T
W Michiels, K. Green, T. Wagenknecht, and S. Niculescu. Pseudospectra and stability radii for analytic matrix functions with application to time-delay systems.Linear Algebra Appl., 418(1):315–335, 2006
2006
-
[14]
Michiels and N
W. Michiels and N. Guglielmi. An iterative method for computing the pseudospectral abscissa for a class of nonlinear eigenvalue problems.SIAM J. Sci. Comput., 34(4):A2366–A2393, 2012
2012
-
[15]
Nocedal and S
J. Nocedal and S. J. Wright.Numerical Optimization. Springer, New York, NY, USA, 1st edition, 2000
2000
-
[16]
Pappas and D
G. Pappas and D. Hinrichsen. Robust stability of linear systems described by higher-order dynamic equations. IEEE Trans. on Automat. Control, 38(9):1430–1435, 1993. 39
1993
-
[17]
F. Rellich. Perturbation Theory of Eigenvalue Problems. Notes on Mathematics and its Applications. Gordon and Breach, New York, NY, USA, 1969
1969
-
[18]
W. Rudin. Real and Complex Analysis. McGraw-Hill, USA, third edition, 1987
1987
-
[19]
Tisseur and N
F. Tisseur and N. J. Higham. Structured pseudospectra for polynomial eigenvalue problems, with applications. SIAM J. Matrix Anal. Appl., 23(1):187–208, 2001
2001
-
[20]
Tisseur and K
F. Tisseur and K. Meerbergen. The quadratic eigenvalue problem.SIAM Rev., 43(2):235–286, 2001
2001
-
[21]
L. N. Trefethen. Computation of pseudospectra.Acta Numer., 8:247–295, 1999
1999
-
[22]
L. N. Trefethen and M. Embree. Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators. Princetion University Press, Princeton, NJ, 2005
2005
-
[23]
T. G. Wright. EigTool: a graphical tool for nonsymmetric eigenvalue problems. http: //www.comlab.ox.ac.uk/pseudospectra/eigtool/, 2002. 40
2002
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.