This workshop will survey recent progress in numerical linear algebra, such as, the modern approaches to low-rank approximation, least squares problems, linear systems and spectral estimation. Topics of interest include sparse and structured matrix computations, fast deterministic and randomized algorithms, complexity analysis, and the growing role of numerical linear algebra in computational mathematics, data science, and optimization.
We are happy to welcome the EMS Distinguished Lecturer Volker Mehrmann as a participant in our workshop!
Organizers
Aalto University
Princeton University
University of Manchester
Speakers
Semi-plenary speakers
University of Pisa
EPFL
Caltech
KU Leuven
Invited speakers
University of California, Berkeley
University of Huelva
Scuola Normale Superiore Pisa
Charles University
University of Cambridge
Universidad Carlos III de Madrid
University of California, San Diego
University of Mons
EPFL
UT Austin
TU Berlin
Virginia Tech
University of Oxford
Aalto University
University of Pisa
University of Pisa
North Carolina State University
University of Manchester
Thursday, 16 July
14:00-14:30
Ioana Dumitriu (University of California, San Diego)
The Baik-Ben Arous-Peche (BBP) phenomenon in random matrix theory refers to the possibility of recovering a low-rank signal in the presence of dense noise, through spectral methods. Roughly speaking, the BBP phenomenon offers a rigorous framework for Principal Component Analysis (PCA). Inspired by real-life applications, we examine a doubly-sparse model where both the noise and the signal have relatively few nonzero entries (and different density parameters), and show how the BBP phenomenon remains true in this context. Specifically, above the signal-to-noise threshold, the model develops outlier eigenvalues whose eigenvectors correlate to the signal vectors; below the threshold, no such outlier eigenvalues will be present. Our results are broad and cover low-rank additive noise. This is joint work with JD Flynn and Zhichao Wang.
14:30-15:00
Erin Carson (Charles University)
Mixed-precision algorithms have launched an era in which efficiency and accuracy are no longer mutually exclusive. Rather than rely entirely on high-precision formats like double (64-bit) precision, mixed-precision algorithms apply lower precisions such as single (32-bit) or half (16-bit) precision whenever possible, reserving higher precision only for critical steps. Doing so can drastically reduce memory requirements, improve performance, and lessen energy consumption on modern computer hardware without sacrificing accuracy or stability. In this talk, we discuss the challenges of using low/mixed precision, and present five cases, common in scientific applications, where using mixed precision makes sense.
15:00-15:30 semi-plenary talk
Joel A. Tropp (Caltech)
Tensor network methods have become a leading technology for computations with exponentially large data. These data structures make it possible to store and manipulate vectors and matrices far outside the reach of traditional dense or sparse linear algebra methods.
This talk introduces random tensor networks as a dimension reduction tool for exponentially large, tensor-structured data. Under suitable assumptions, tensor networks populated with independent Gaussian entries can emulate the behavior of exponentially large Gaussian random vectors, while using only a vanishing fraction of the storage. These results lead to tensor network analogs of core randomized linear algebra algorithms for low-rank approximation and trace estimation. Examples from quantum many-body physics illustrate how these algorithms scale well past the limits of conventional dimension reduction techniques. No prior knowledge of tensor networks is assumed.
Joint work with Chris Camaño, Ethan Epperly, and Raphael Meyer.
15:30-16:00 semi-plenary talk
Nick Vannieuwenhoven (KU Leuven)
An additive tensor decomposition of a tensor consists of a sum of elementary tensors. These decompositions arise in a wide range of data analysis applications. Notwithstanding their importance, decomposing a tensor into its elementary constituents remains a challenging problem, even in the absence of noise.
In this talk, we present an algorithmic framework for tensor mining that is ultimately based only on standard numerical linear algebra. It applies to a variety of additive decompositions, such as canonical polyadic (CP), block term, Chow, Grassmann, and Waring decompositions, provided the decomposition length is not too large.
The essential steps of this tensor mining framework are as follows. First, we place the high-order input tensor into an appropriate third-order mold by reshaping. Second, we cut off the right number of matrix slices from this remolded third-order tensor by random projections. Third, we apply Brooksbank-Kassabov-Wilson chiseling to these matrix slices to extract the projected elementary tensor components.
This talk is based on joint works with Tim Seynnaeve, Daniele Taufer, and David Thorsteinsson.
16:00-16:30 Coffee Break
16:30-17:00
Leonardo Robol (University of Pisa)
LSQR and LSMR are iterative methods, based on the Golub–Kahan bidiagonalization algorithm, widely used for large-scale linear least squares problems. FLSQR and FLSMR are flexible variants of LSQR and LSMR, respectively, based on a flexible Golub-Kahan (Arnoldi-like) factorization algorithm, which naturally allow modifications of the solution approximation subspace and/or handling inexact matrix-vector multiplications with the (transpose of the) coefficient matrix, thereby enabling to enforce prior information into the computed solution. The goal of this talk is to introduce sFLSQR and sFLSMR, i.e., sketched variants of FLSQR and FLSMR, respectively, where randomization becomes particularly effective, as it allows to recover short recurrences for the solution approximation, and to deal with approximate transposes.
We explore applications to large-scale inverse problems, showing the ability of the new randomized solvers to alleviate computational bottlenecks while preserving reconstruction quality. We present a theoretical analysis of sFLSQR and sFLSMR and numerical experiments. We show that the choice of the best algorithms depends on the noise level of the problem, and moving from sFLSQR to sFLSMR can significantly improve the quality of the sketched solution when the noise is large.
17:00-17:30
Gustav Conradie (University of Cambridge)
Koopman-based models lift nonlinear dynamics on a finite-dimensional state space to an infinite-dimensional function space, allowing for a global linearization of the dynamics. By considering the functions which correspond to the state coordinates, we can use the Koopman operator to predict the original dynamics. Standard methods like DMD or EDMD correspond to a Galerkin approximation of the Koopman operator, which converges in a large subspace limit. While convergence of this limit is known, less studied is the rate of convergence, and in particular a posteriori error bounds, which tell us how close our forecasts are to the true dynamics. In this talk we will discuss new algorithms which compute rigorous error bounds for forecasts using the Koopman operator, both in the classical L^2 setting and the kernelized setting, which allows for pointwise rather than norm error bounds. We also introduce a framework for computing the expected errors in forecasts using randomized methods involving Gaussian processes, and extend techniques for measuring subspace angles to the infinite-dimensional setting to produce a novel dimension reduction tool for Koopman operators. We will discuss applications to systems including cavity fluid flows and orbital dynamics.
17:30-18:00
Daniel Kressner (EPFL)
Randomized methods in numerical linear algebra, such as the randomized SVD and the Girard-Hutchinson estimator, usually employ isotropic random vectors. When the matrix under consideration arises from the discretization of an infinite-dimensional problem, such as an integral equation, the use of isotropic random vectors may raise concerns about whether the results obtained by randomized matrix computations have a meaningful infinite-dimensional limit. In a series of works, partly motivated by applications to operator learning, Boulle and Townsend, as well as Zvonek, Horning, and Townsend, addressed these concerns by imposing regularity on the random vectors/fields through a Gaussian process with a non-identity covariance operator K. While the non-isotropy introduced by K makes it possible to incorporate prior information and to define a meaningful limit of the random vectors, an unfortunate choice may lead to unfavorable performance, significant bias, and large constants in the error bounds. In this work, we introduce novel infinite-dimensional extensions of the randomized SVD and the Girard-Hutchinson estimator that do not require such a choice and enjoy error bounds matching those in the finite-dimensional case. Our extension is based on a different viewpoint on existing randomized methods: isotropic random vectors are used only implicitly, through the application of the matrix or operator to the random vector. This allows us to show how the usual randomized methods applied to discretizations converge to our infinite-dimensional extensions as the discretization is refined. This talk is based on joint work with David Persson and Andre Uschmajew, as well as Zvonimir Bujanovic and Hrvoje Olic.
18:00-18:30
Oleg Balabanov (University of California, Berkeley)
Many methods in scientific computing and machine learning lead to large-scale linear systems and least-squares problems whose associated operators exhibit a relatively small number of dominant spectral components. Examples arise in kernel methods, Gaussian process models, neural-network training, PDE-constrained inverse problems, and second-order optimization. Efficient iterative solvers for these problems require preconditioners that can deflate dominant spectral components while supporting matrix-free implementations and adapting to operator structure, including sparsity, matrix shape, symmetry, definiteness, and spectral tails or gaps.
We introduce RandRAND, a class of randomized preconditioners based on randomized range deflation. RandRAND deflates dominant spectral components through efficient orthogonal projections onto random subspaces, without computing explicit eigenpairs or low-rank factorizations. We present RandRAND preconditioners for several problem classes and establish high-probability guarantees showing that they reduce operator’s condition number while preserving the spectral structure relevant to fast Krylov convergence. We also discuss extensions that reuse deflation subspaces across sequences of related linear systems.
RandRAND preconditioners admit basis-less implementations using fast randomized transforms, reducing both computational cost and memory requirements. To avoid costly orthogonalization, we use novel randomized Q-less QR factorizations or represent projections through tall least-squares problems solved with refinement and second-level preconditioning. These strategies balance construction and application costs while maintaining numerical robustness.
Friday, 17 July
14:00-14:30
Arvind Saibaba (North Carolina State University)
Rank-revealing factorizations such as Businger-Golub column pivoted QR and Gu-Eisenstat strong-revealing QR factorizations are well-studied in the numerical linear algebra community. In this talk, we view these factorizations through the lens of submodularity, which codifies the property of diminishing returns. We show that Businger-Golub column pivoted QR is a greedy algorithm and Gu-Eisenstat strong-revealing QR factorization is a 1-interchange algorithm for volume maximization. This gives rise to new bounds for these algorithms and a new way of studying column subset selection.
14:30-15:00
Agnieszka Miedlar (Virginia Tech)
In this talk, we introduce a unified framework for nonlinear Krylov subspace methods (nlKrylov) to solve systems of nonlinear equations. Building on classical GCR-like/type linear Krylov solvers such as GMRESR, we generalize these approaches to nonlinear problems via nested algorithmic structures. Extensive numerical experiments validate the theoretical insights and demonstrate the robustness and efficiency of our proposed algorithms.
15:00-16:00 special talk
Volker Mehrmann (TU Berlin)
The iterative solution of large-scale problems subject to non-symmetric matrices or operators arising in discretizations of (port-)Hamiltonian partial differential equations. We consider problems governed by an operator with symmetric part that is positive (semi-)definite. Prior work has shown that the structure and sparsity of the associated linear system enables Krylov subspace solvers such as the generalized minimal residual method (GMRES) or short recurrence variants such as Widlund’s or Rapoport’s method using the symmetric part, or an approximation of it, as preconditioner. In this work, we analyze the resulting condition numbers, which are crucial for fast convergence of these methods, for various partial differential equations (PDEs) arising in diffusion phenomena, fluid dynamics, and elasticity. We show that preconditioning with the symmetric part leads to a condition number uniform in the mesh size in case of elliptic and parabolic PDEs where the precondition system is a bounded operator. Further, we employ the tailored Krylov subspace methods in optimal control by means of a condensing approach and a constraint preconditioner for the optimality system. We illustrate the results by various large-scale numerical examples and discuss efficient evaluations of the preconditioner, such as incomplete Cholesky factorization or the algebraic multigrid method.
We also present multilayer approximate nullspace methods that optimally exploit the resulting matrix structure. Joint work with Manuel Schaller and Martin Stoll and partly with Murat Manguoglu.
16:00-16:30 Coffee Break
16:30-17:00
Yuji Nakatsukasa (University of Oxford)
The quest for an algorithm that solves an nxn linear system Ax=b in O(n^2) time complexity, or O(n^2 poly(1/epsilon)) when solving up to epsilon relative error, is a long-standing open problem in numerical linear algebra and theoretical computer science.
There are two predominant paradigms for measuring relative error: forward error (i.e., distance from the output to the optimum solution) and backward error (i.e., distance to the nearest problem solved by the output). In most prior studies, convergence of iterative linear system solvers is measured via various notions of forward error, and as a result, depends heavily on the conditioning of the input. Yet, the numerical analysis literature has long advocated for backward error as the more practically relevant notion of approximation. In this work, we show that — surprisingly — the classical and simple Richardson iteration incurs at most 1/k (relative) backward error after k iterations on any positive semidefinite (PSD) linear system, irrespective of its condition number. This universal convergence rate implies an O(n^2/epsilon) complexity algorithm for solving a PSD linear system to epsilon backward error, and we establish similar or better complexity when using a variety of Krylov solvers beyond Richardson. Then, by directly minimizing backward error over a Krylov subspace, we attain an even faster O(1/k^2) universal rate, and we turn this into an efficient algorithm, MINBERR, with complexity O(n^2/sqrt(epsilon)). We extend this approach via normal equations to solving general linear systems, for which we empirically observe O(1/k) convergence. We report strong numerical performance of our algorithms on benchmark problems.The quest for an algorithm that solves an $n\times n$ linear system Ax=b in O(n^2) time complexity, or O(n^2 poly(1/epsilon)) when solving up to epsilon relative error, is a long-standing open problem in numerical linear algebra and theoretical computer science.
17:00-17:30
Per-Gunnar Martinsson (UT Austin)
Randomized algorithms for matrix computations are often remarkably efficient, but in practical computations a central question is not only how to compress or solve quickly, but also how to certify the accuracy of a particular computation using only quantities available at runtime. This talk begins with recent work on a posteriori error estimation for randomized low-rank approximation, with emphasis on inexpensive certificates of accuracy, adaptive rank determination, and the reliable use of fast but potentially riskier randomized embeddings. These ideas also play a central role in sketch recycling and rank-adaptive CUR methods such as IterativeCUR.
The second part of the talk turns to structured matrix computations. Many dense operators arising in scientific computing admit hidden structure that allows much faster compression, matrix-vector multiplication, or inversion than would be possible for an unstructured matrix. The talk will discuss how randomized sampling and a posteriori error estimation can be combined in this setting to compress global operators reliably. A central theme is how to exploit the fact that, in many applications, the matrix is a discretization of a continuum operator, so that analytic structure from the underlying problem can be brought to bear on both the design of randomized algorithms and the certification of their accuracy.
17:30-18:00
Nicolas Gillis (University of Mons)
Low-rank matrix factorizations, such as principal component analysis (PCA) and nonnegative matrix factorization (NMF), are among the most widely used tools for dimensionality reduction and unsupervised learning. Given a data matrix, X, they seek two smaller matrices, W and H, such that W*H approximates X. Their success relies on the assumption that data can be well approximated by a low-dimensional linear model. However, many real-world data sets exhibit nonlinear structures that cannot be captured adequately by linear factorizations. In this talk, I will discuss recent advances in nonlinear matrix decompositions (NMDs), a class of models introduced by Saul (SIAM J. Math. Data Sci., 2021). NMDs replace the linear model W*H by a nonlinear transformation f(W*H), where the function f(.) is applied element-wise. I will present several examples of such models, including (i) the ReLU transform, f(x) = max(0,x), which reveals intriguing connections between sparse and low-rank matrices, (ii) the component-wise square, f(x) = x^2, which relates to Hadamard decompositions and probabilistic representations, and (iii) clipping transforms, of the form f(x)=min(b,max(x,a)), which are useful for recommender systems and data affected by measurement saturation. I will discuss some of the theoretical and algorithmic challenges they raise, and illustrate their potential through several real-world applications.
18:00-18:30
Giovanni Barbarino (University of Huelva)
Minimum-volume nonnegative matrix factorization (min-vol NMF) has been used successfully in many applications, such as hyperspectral imaging, chemical kinetics, spectroscopy, topic modeling, and audio source separation. However, its robustness to noise has been a long-standing open problem. In this paper, we prove that min-vol NMF identifies the groundtruth factors in the presence of noise under a condition referred to as the expanded sufficiently scattered condition which requires the data points to be sufficiently well scattered in the latent simplex generated by the basis vectors.
Saturday, 18 July
14:00-14:30 semi-plenary talk
Laura Grigori (EPFL)
We discuss recent advances in randomized algorithms for solving large-scale linear and multilinear algebra problems that combine dimensionality reduction with mixed-precision arithmetic. By embedding relevant subspaces through sketching, these methods can exploit optimized kernels and mixed precision while providing numerical guarantees with high probability. We first describe communication optimal algorithms for several sketching operators, ranging from dense to sparse and structured transforms. We then focus on randomized techniques for solving linear systems and eigenvalue problems, together with their use in scientific applications such as
material science. These developments are being incorporated into RandMixPack, a library developed in our group for GPU and CPU architectures.
14:30-15:00 semi-plenary talk
Alice Cortinovis (University of Pisa)
Galton-Watson processes are classical stochastic models for the evoulution of a population in which individuals reproduce independently according to a fixed offspring distribution. While the Kesten-Stigum theorem characterizes the almost sure limit of suitably normalized supercritical Galton-Watson branching processes (which plays an important role in branching-process theory), its density is generally not available in closed form, and must be computed numerically. Our approach is based on a nonlinear Poincaré-type functional equation satisfied by the Laplace-Stieltjes transform of the limit distribution. Its discretization is combined with a moment-matching procedure to obtain accurate approximations within a class of linear combinations of Laguerre polynomials with exponential damping. This strategy leads naturally to finite-dimensional linear algebra problems involving structured matrices. Numerical experiments illustrate the effectiveness of the method for several offspring distributions and demonstrate the accuracy of the reconstructed densities.
15:00-15:30
Federico Poloni (University of Pisa)
We describe some recent advances in structured matrix nearness problems: the prototypical problem is the one of finding the nearest singular matrix to a given matrix A, in the Frobenius norm, preserving a certain linear structure, for instance sparsity or Toeplitz-ness.
The problem has an unexpected
By introducing the left and/or right kernel vector as optimization variables, the problem becomes simpler and can be solved using standard optimization tools. However, regularization and the presence of spurious solutions are issues that need special consideration.
15:30-16:00
Frolian Dopico (Universidad Carlos III de Madrid)
We present an algorithm for approximating a given matrix polynomial of degree d by a matrix polynomial of prescribed rank and degree at most d. The method builds on recent advances in the theory of generic factorizations of matrix polynomials with bounded rank and degree. We also give a specialized treatment of the case of matrix pencils (degree one matrix polynomials), motivated by its particular theoretical and practical importance. Lastly, numerical experiments are reported to assess the performance of the proposed approach and to compare it with existing methods.
This is a joint work with S. Das, A. Dmytryshyn, and M. Gulliksson.
16:00-16:30 Coffee Break
16:30-17:00
Michele Benzi (Scuola Normale Superiore Pisa)
Using basic facts from the theory of (matrix) Lie groups and algebras, we show that many of the classical matrix splittings used to construct stationary iterative methods and preconditioners for Krylov subspace methods can be interpreted as linearizations of matrix factorizations. Moreover, we show that new matrix splittings are obtained when we specialize these splittings to some of the classical matrix groups and their Lie and Jordan algebras. As an example, we derive structured variants of the HSS (Hermitian and skew-Hermitian splitting) iteration, and provide sufficient conditions for their convergence.
This is joint work with Milo Viviani (Scuola Normale Superiore).
17:00-17:30
Vanni Noferini (Aalto University)
In his book “Functions of Matrices: Theory and Computation”, Nick Higham posed the following question (Research Problem 3.11): Determine the Jordan form of the Fréchet derivative of f at X in terms of that of X. By polynomial interpolation, one can show that it suffices to solve the problem for polynomial functions f. More generally, one can consider formal Fréchet derivatives of polynomials f with coefficients over an algebraically close field of characteristics 0. I call this slight generalization of Higham’s Problem 3.11 the Fréchet-Jordan problem. More generally, given an algebraically closed field $\mathbb{F}$ of characteristic 0 and two square matrices $X \in \mathbb{F}^{m \times m}, Y \in \mathbb{F}^{n \times n}$, one can consider matrices of the form $$P(X,Y)=\sum_{i,j} a_{ij} X^i \otimes Y^j, \qquad a_{ij} \in \mathbb{F}.$$ and study the Jordan form of $P$ in terms of that of $X$ and $J$. I call this the bivariate Jordan problem, and one can show that the Fréchet-Jordan problem is a special case. In this talk, I plan to give a partial solution of the bivariate Jordan problem under a Zariski generic assumption. A general solution appears very difficult, and I will present some bounds and partial results. Moreover, I will give a full solution of the Fréchet-Jordan problem, even when the generic assumption does not hold. Generically, my solution can be described in closed form, but in some special cases it describes the sought Jordan form in terms of the ranks of certain integer Toeplitz matrices. These latter matrices are often, but not always, full rank; I will pose as a related new open problem the characterization of when exactly they are rank deficient, including some partial results. If time permits, I will also discuss some nontrivial connections between this problem and some recent deep results in commutative algebra.
17:30-18:00
Francoise Tisseur (University of Manchester)
We present a mixed-precision preconditioned one-sided Jacobi algorithm that uses low precision to compute the preconditioner, applies it in high precision, and computes the singular value decomposition using the one-sided Jacobi algorithm at working precision. Our analysis yields smaller relative forward error bounds for the computed singular values than those of standard SVD algorithms. We present and analyse two approaches for constructing effective preconditioners. Our numerical experiments support the theoretical results and demonstrate that our algorithm achieves smaller relative forward errors than the LAPACK routines DGESVJ and DGEJSV, as well as the MATLAB svd function, particularly for ill-conditioned matrices. Timing tests show that our approach accelerates the convergence of the Jacobi iterations and that the dominant cost arises from a single high-precision matrix-matrix multiplication. With improved software or hardware support for this bottleneck, our algorithm would be faster than the LAPACK one-sided Jacobi algorithm DGESVJ and comparable in speed to the state-of-the-art preconditioned one-sided Jacobi algorithm DGEJSV, but much more accurate.
Posters
Jonas Bresch
(TU Berlin)
The maximization of the (generalized) Rayleigh quotient is a central problem in numerical linear algebra. Conventional algorithms for its computation typically rely on matrix-adjoint products, making them sensitive to errors arising from adjoint mismatches. To address this issue, we introduce a stochastic zeroth-order Riemannian algorithm that maximizes the generalized Rayleigh quotient without requiring adjoint or matrix inverse computations. Moreover, the construction can be translated to other quantities as for example $|A|$ and $|A – V|$, where only evaluations of the linear map $x \mapsto A x$, respectively $y \mapsto V^*y$ are available. Those are of interest in inverse problems and uncertainty quantification. We provide theoretical convergence guarantees showing that the iterates converge to the set of global maximizers of the (generalized) Rayleigh quotient at a sublinear rate with probability one. Our theoretical results are supported by numerical experiments, which demonstrate the excellent performance of the proposed method compared to state-of-the-art algorithms. Further generalizations are possible for Ky-Fan norm and sum, the application for SVDs and LDAs, and extensions for more general optimization problems using iterative, weighted least square subproblems.
Alexandra Dache
(University of Mons)
Multilayer networks allow the modeling of interactions between the same entities across different contexts, such as temporal observations, varying settings, or interactions of different types. They consist of several graphs, one per layer, defined over the same set of nodes. The goal of community detection in multilayer networks is to identify groups of nodes exhibiting similar connectivity patterns, which may vary across layers. We propose a method based on a joint nonnegative symmetric matrix trifactorization for community detection in multilayer networks, where each graph is approximated by a nonnegative symmetric matrix trifactorization. Our approach enforces constraints on the factor matrices so that communities are disjoint and shared across layers, while allowing each layer to have its own connectivity patterns and node degrees. This flexibility enables the model to capture both local and global structural variations across layers.We also develop a scalable algorithm to efficiently solve this problem. We evaluate the proposed method against state-of-the-art approaches across various multilayer network settings. Experimental results demonstrate that our model accurately detects communities in diverse and challenging scenarios, including networks with heterogeneous degrees and varying structural patterns.
Leia Greenberg
(Tel Aviv University)
Reduced Rank Regression (RRR) is a widely used method for multi-response regression. However, RRR assumes a linear relationship between features and responses. While linear models are useful and often provide a good approximation, many real-world problems involve more complex relationships that cannot be adequately captured by simple linear interactions. One way to model such relationships is via multilinear transformations. We introduce Higher Order Reduced Rank Regression (HORRR), an extension of RRR that leverages multilinear transformations, and as such is capable of capturing nonlinear interactions in multi-response regression. HORRR employs tensor representations for the coefficients and a Tucker decomposition to impose multilinear rank constraints as regularization akin to the rank constraints in RRR. Encoding these constraints as a manifold allows us to use Riemannian optimization to solve HORRR problems. We theoretically and empirically analyze the use of Riemannian optimization for solving HORRR problems. We show that the stationary points of this optimization problem correspond to generalized eigenpairs in both the matrix and higher-order cases. Empirically, HORRR demonstrates robust performance, achieving low relative recovery errors on synthetic datasets across varying noise levels. Furthermore, when applied to a multi-class classification task using the MNIST dataset, HORRR achieves accuracy comparable to exact kernel-based methods using a polynomial kernel, while utilizing significantly less storage.
Plamen Koev
(San Jose State University)
We will present new algorithms for performing virtually all computations with totally nonnegative matrices to high relative accuracy regardless of whether the matrix is singular generalizing the results of [3] for nonsingular totally nonnegative matrices. The algorithms achieve high relative accuracy by completely avoiding subtractions and thus preserving the high relative accuracy. The matrix computations include the inverse, the eigenvalues, the SVD [2], the Schur complement, a submatrix, as well as any minor.
The new algorithms also include for the first time the computation of the singular vectors to high relative accuracy. It also completes computations in the nonsingular case, such as submatrices (and the properties thereof) which can be singular even when the initial matrix isn’t.
Joint work with J. Delgado, A. Marco, J.M. Pena, J.J. Martines, R. Viana.
References
[1] J. Delgado, P. Koev, A. Marco, J.M. Pena, J.J. Martines, R. Viana, Accurate Computations with Totally
Nonnegative Matrices of Any Rank. Numer. Math. (2026), submitted.
[2] Koev, P. Accurate eigenvalues and exact zero Jordan blocks of totally nonnegative matrices. Numer. Math.
141, 693–713 (2019).
[3] Plamen Koev Accurate Computations with Totally Nonnegative Matrices SIAM Journal on Matrix Analysis
and Applications 2007 29:3, 731-751.
Mikhail Lepilov
(Rensselaer Polytechnic Institute)
Due to the size of many kernel matrices that arise in applications, it is often necessary to work with their low-rank approximations in order to efficiently perform many computations. Low-rank matrix decompositions to such matrices may be quickly obtained by exploiting the analytic structure of the underlying kernel, for example by using Taylor expansions or an integral representation; such ideas trace back to the fast multipole method. However, there is often a gap between the theoretical epsilon-rank of a given kernel matrix, explicitly obtained using its eigenvalue decomposition, and the existing analytic decompositions of the same rank. In this work, we aim to bridge this gap by exploring the proxy point method, which approximates complex-analytic kernel matrices using a discretized contour integral representation. In particular, we combine this approach with a judicious choice of conformal map applied to the set of points at which the kernel is evaluated in order to obtain near-optimal analytic approximations. We apply this new method to some well-studied kernel matrices, such as the Hilbert and Cauchy matrices, in order to compare it with existing analytic methods and with the best available theoretical bounds. In the process, we demonstrate a new asymptotically-optimal solution to the Zolotarev sign problem on certain subsets of the complex plane.
Xiang Lu
(University of Chicago)
It is well known that Grassmannians admit an involution matrix model: a k-dimensional subspace corresponds to an orthogonal projection P, and the transformation Q=2P-I produces an involution whose +1-eigenspace is that subspace and whose -1-eigenspace is its orthogonal complement. In this way Grassmannians may be viewed as families of structured involutions.
In this work, we show that the special orthogonal, special unitary, and symplectic groups admit factorizations in terms of such Grassmannian involutions. Namely, every matrix in SO(n) can be written as the product of two Grassmannian involutions, while every matrix in SU(n) and Sp(2n) can be written as the product of four, with each factor having prescribed trace. This leads to new structured matrix factorizations of special orthogonal, special unitary, and symplectic groups.
In the SO(n) and SU(n) cases, we go beyond existence and characterize which dimensions of the Grassmannian factors yield decompositions of the whole group. The proofs are partly constructive and yield practical algorithms for finding the decompositions.
Fabio Matti
(EPFL)
We propose a novel method for reconstructing noisy outputs generated by one-dimensional linear time-invariant systems. Our approach estimates the system’s finite impulse response (FIR) using a kernel-based formulation combined with maximum likelihood estimation (MLE). We jointly approximate the two terms involved in the MLE objective function, namely the inverse quadratic form y^T (λ I + A)^-1 y and the log-determinant log(det(λ I + A)), where A is a certain positive semidefinite matrix with fast matrix-vector products and λ > 0 is a regularization parameter. Rather than approximating these two terms separately, as in classical approaches, we construct a single augmented Krylov subspace for A from which we simultaneously extract approximations for both terms of the MLE objective. A major benefit of the augmentation is the accelerated convergence of the approximations of the inverse quadratic form, in a manner analogous to preconditioning. Thanks to the shift-invariance of Krylov subspaces, the extracted approximations can be used to evaluate the MLE objective for many values of the parameter λ at little additional cost. This, along with the combined evaluation of the two terms, significantly accelerates the maximum likelihood estimation compared to classical methods. We provide theoretical guarantees for the approximations and demonstrate their benefits through multiple numerical experiments.
Keiichi Morikuni
(University of Tsukuba)
Complex moments consisting of contour integrals extract the desired eigencomponents from input vectors. This study extends a projection method using complex moments for regular eigenvalue problems to the singular ones of linear matrix pencils, in particular in the presence of singular Kronecker blocks. We establish conditions such that the method gives all finite eigenvalues in a prescribed domain in the complex plane and the corresponding eigenvectors, defined using equivalence classes by Dopico and Noferini, 2020. We show that quadratic palindromic matrix polynomials arising from singular Kronecker blocks are regular and have the same number of eigenvalues in and outside the specified domain in the complex plane. Perturbation with rank equal to the number of eigenvalues lying in the specified domain is added to the complex moments. We assure that the proposed method determines the eigenvalues in the specified domain, provided that the number of eigenvalues of interest plus the size of the singular blocks is not larger than the product of the order of complex moments and the number of input vectors. Numerical experiments verify these points. This is joint work with Akira Imakura.
Lauri Nyman
(University of Manchester)
This poster considers the theoretical convergence of flexible GMRES. While convergence of standard GMRES is well studied, there exist few results of similar nature for flexible GMRES. The aim of this work is to discuss and fill in this gap. In addition, we report on experiences of using these ideas in the context of randomized sketching.
Haesun Park
(Georgia Institute of Technology)
A co-embedding method based on constrained low-rank approximation is proposed to achieve seamless knowledge fusion across multi-view datasets. By mapping disparate data types into a common subspace, the method maintains critical semantic relationships for downstream analytics, such as clustering. An advantage of our approach is its inductive capability; by utilizing pre-computed basis vectors, the model effectively embeds new data points on the fly. We validate our framework using a document-author-keyword network and a healthcare case study involving patient records and portal interaction logs, demonstrating significant efficacy in multi-type data integration.
Louise Schaub
(University of Wuppertal)
Low-rank approximations of large symmetric positive definite matrices are a cornerstone of computational mathematics, with central roles in numerical linear algebra, statistics, and machine learning. Pivoted Cholesky factorizations provide an efficient incremental approach for constructing such approximations, typically relying on greedy or randomized pivot rules that select indices based on residual diagonal entries.
In many modern applications, the target matrix does not appear in isolation but enters a nonlinear matrix functional that ultimately determines computational or statistical performance. A prominent example is Gaussian process regression, where low-rank kernel approximations are embedded within the variational free energy, a functional combining log-determinant, data-fit, and residual variance terms. Classical residual-based pivoting, however, aligns naturally with only the last component of this objective and is implicitly designed to reduce algebraic approximation error, which does not always correlate with inference accuracy.
In this work, we present a novel objective-aware pivot selection rule for pivoted Cholesky factorizations by maximizing the exact incremental improvement of the variational free energy arising in Gaussian process regression under Cholesky-consistent rank-one updates. The resulting per-pivot criterion admits a closed-form expression and can be evaluated efficiently using low-rank update identities. This preserves the incremental structure and computational efficiency of standard pivoted Cholesky methods. Numerical experiments show that, particularly at small to moderate target ranks, objective-aware pivoting yields consistently better variational objective values and improved predictive performance compared to classical greedy and randomized pivoting.
Nian Shao
(EPFL)
Given a holomorphic matrix-valued function, the poles of its sketched resolvent are generically its eigenvalues. Once a high-quality rational approximation of the sketched resolvent is obtained, the poles of this approximation typically lie close to those eigenvalues, providing a flexible framework for solving both linear and nonlinear eigenvalue problems.
In this poster, we present a nonlinear eigensolver based on polefinding applied to a rational approximation of the sketched resolvent. In particular, we address the following three theoretical questions:
Can all spectral information be recovered robustly from the sketched resolvent?
Will the poles of a rational approximation obtained via AAA converge to those of the sketched resolvent, given that AAA only guarantees accuracy at the sample points?
Is the polefinding procedure for a barycentric rational form via a generalized eigenproblem backward and forward stable?
We provide affirmative answers to all three questions by analyzing the effects of block probing and zooming in. Numerical experiments demonstrate the sharpness of our theoretical results.
This poster is based on joint work with Yuji Nakatsukasa at University of Oxford.
Matvei Zhukov
(Aalto University)
In the poster, I will present a new method of computing the nearest normal matrix to a given matrix. For a complex-valued square matrix A of size n, the nearest normal matrix is the normal matrix B which minimizes the Frobenius norm of the difference A – B. We show that this optimization problem is equivalent to minimizing a certain function over the manifold of unitary matrices U(n). The novel algorithm is based on the spectral theorem for normal matrices, and yields competitive results, by combining it with existing algorithms of optimization over Riemannian manifolds. Additionally, we discuss the structured version of the problem of finding a nearest real normal matrix to a given real matrix using Riemannian optimization. The setting of real matrices poses additional complications, which include non-differentiability of the target function. We present an algorithm solving this optimization problem.
