MATHEMATICS
Why randomized Arnoldi needs to restore similarity
A January 2026 preprint repairs a projection problem in randomized Krylov methods. A small example shows why a good basis cannot guarantee familiar convergence.
Research checked
Newest cited publication
A matrix illustration provides linear-algebra background for Arnoldi reductions and the similarity relation examined in the article.
Maschen / Wikimedia Commons. Wikimedia-generated PNG rendering of the SVG; no editorial changes. · Image source · Public domain (released by the creator)
Large scientific calculations often ask a huge matrix a surprisingly narrow question: what are a few of its eigenvalues, or how does a function of that matrix act on one vector? Krylov methods answer by constructing a much smaller space from repeated matrix applications. Randomization can make that construction cheaper, but changing the geometry of the construction can also change the small problem being solved. A January 15, 2026 preprint by Laura Grigori, Daniel Kressner, Nian Shao, and Igor Simunec addresses this distinction directly. Its proposed modification restores a relationship called similarity, recovering the familiar approximations of standard Arnoldi while retaining the attraction of randomized basis construction.
Build a space from repeated actions
Start with a nonzero vector b. Apply A to obtain Ab, then apply it again to obtain A²b. Continuing produces a sequence of candidate directions. Their span is a Krylov space. The useful information is the space, rather than the raw powers, because those powers can rapidly become nearly parallel. An algorithm replaces them with a better basis while tracking how multiplication by A acts within the space and what part escapes it.
For a two coordinate illustration, let A be diagonal with entries one and two and choose b = (1, 1). Then Ab = (1, 2), so the first two vectors already span the plane. A two dimensional exact calculation can recover the whole matrix action. After only one direction, however, the approximation must compress two different stretching factors into one number. This toy setting is small enough to inspect directly. It helps separate approximation caused by limiting the space from errors introduced by constructing and projecting onto that space.
Orthogonality has a computational price
A vector is orthogonal to previous basis directions when its inner products with those directions vanish. Standard orthogonalization computes those inner products using all coordinates. If each vector has a million entries, even the apparently simple task of checking one angle becomes a substantial traversal of memory. Repeating the check against many previous vectors introduces more work and, on distributed machines, communication between processors. Matrix application is not necessarily the only expensive component.
The randomized Gram–Schmidt work of Oleg Balabanov and Laura Grigori develops an alternative based on sketches: shorter random images of the vectors. Their inner products approximately preserve the relevant geometry when the embedding works on the space involved. This is a probabilistic statement with assumptions, not permission to replace a vector by any short list of numbers. A sketch that erases a needed direction cannot support a dependable basis. The question is how much geometry must survive and which downstream calculations rely on exact rather than approximate orthogonality.
A one dimensional projection can already change
Return to A = diag(1, 2) and the direction u = (1, 1). The ordinary Rayleigh quotient is (uᵀAu)/(uᵀu) = 3/2. Now measure inner products using the positive weight matrix W = diag(4, 1). The corresponding quotient is (uᵀWAu)/(uᵀWu) = 6/5. Both calculations use exactly the same direction. Neither calculation suffers from a poorly conditioned collection of basis vectors: there is only one direction. They nevertheless produce different projected eigenvalue estimates.
This constructed example is not a benchmark from the 2026 paper, nor is W presented as a particular random sketch. It isolates the underlying issue of changing an inner product. A well behaved basis is valuable, but it does not force a projection in one geometry to equal a projection in another. Moreover, one by one matrices are similar only when their entries agree. The numbers 1.5 and 1.2 therefore cannot be related merely by changing coordinates inside the small space.
What similarity preserves
Two square matrices H and G are similar when H = T⁻¹GT for some invertible T. They represent the same linear map in different coordinate systems. For example, take G diagonal with entries one and two, and T with rows (1, 1) and (0, 1). Direct multiplication gives H with rows (1, −1) and (0, 2). Its entries differ from G, but its eigenvalues remain one and two. The characteristic polynomial stays unchanged because the inserted factors T and T⁻¹ cancel inside the determinant.
A change of basis in a fixed projected operator is therefore harmless in a specific algebraic sense. A change in the projected operator is different. The January preprint identifies how ordinary randomized Arnoldi can produce a small Hessenberg matrix outside the needed similarity relationship. It restores that relationship by enforcing orthogonality for the final residual direction through an additional least squares problem. That precise repair, rather than an assertion that all randomness is benign, is the central reported development.
Why a boundary direction matters
A small model needs to describe both motion within its chosen space and the part that leaves the space. Think of projecting a velocity onto a plane: the in plane component and the normal component play different roles. If the purported normal component still contains a piece lying in the plane, the bookkeeping changes. The represented action inside the plane can then absorb a piece of what was supposed to be the escaping residual. This geometric picture explains why checking the final direction can matter even if the basis itself remains usable.
For eigenvalue calculations, the projected operator supplies Ritz values, which serve as approximations to eigenvalues of the original matrix. For matrix functions, the small operator appears inside an expression used to approximate f(A)b. A changed small operator can therefore affect more than a diagnostic. The paper establishes equivalence with standard Arnoldi approximations in its stated exact arithmetic setting. Floating point computation, finite sketches, stopping rules, and restarting still require their own care; algebraic identity is not a promise of identical computer bit patterns.
Reading a convergence curve carefully
Imagine a solver whose residual decreases smoothly for several steps, spikes, and then resumes decreasing. That pattern alone does not identify its cause. A restart can discard useful directions, a basis can lose orthogonality, a random embedding can be inadequate, or a monitored quantity can differ from the true error. To interpret the curve, a report should state the actual approximation being formed and compare like quantities at equal subspace dimensions. A smoother picture is evidence to investigate, rather than a theorem about every problem.
The 2025 work of Valeria Simoncini and YiHong Wang studies stabilized Krylov recurrences through randomized sketching and emphasizes the geometry of basis directions and projected problems. It offers a complementary framework rather than the same claim as the January modification. Together, these research directions encourage a useful separation: is the basis well conditioned, does the recurrence describe the intended projection, and does the chosen approximation converge for this matrix? These questions are related, but an affirmative answer to one does not automatically settle the others.
A practical standard of evidence
A useful evaluation should record total time, time spent building the basis, time spent on the final correction, sketch size, random seed policy, attained residual, and failures across repeated runs. If the matrix is accessed through a black box operation, its application cost must also be disclosed. A method that saves orthogonalization may be compelling when that stage dominates and less influential when every matrix application is overwhelmingly expensive. This follows from basic cost accounting, independently of any particular reported experiment.
As of the October 18, 2026 cutoff, the January result is a preprint with analysis and numerical experiments. Its broader importance is conceptual: acceleration should preserve the mathematical object that the application actually needs. Random sketches can preserve enough geometry for a good basis while leaving one projection relationship unresolved. Repairing that relationship provides a sharper route to reliability than simply increasing a sketch until a test happens to look convincing. The best small model must be both cheap to build and faithful to the question being asked.
Sources & further reading
Primary papers, project documentation, and research releases used in this article. Publication dates below refer to the sources themselves.
- Restoring similarity in randomized Krylov methods with applications to eigenvalue problems and matrix functionsarXivPublished Checked
- Randomized Gram-Schmidt process with application to GMRESarXivPublished Checked
- Stabilized Krylov Subspace Recurrences via Randomized SketchingNumerical Linear Algebra with ApplicationsPublished Checked
FOLLOW THE QUESTION
Explore mathematics