1,721,037 research outputs found
Low-rank approximation in the Frobenius norm by column and row subset selection
Full text linkA CUR approximation of a matrix A is a particular type of low-rank approximation A approx CUR, where C and R consist of columns and rows of A, respectively. One way to obtain such an approximation is to apply column subset selection to A and AT . In this work, we describe a numerically robust and much faster variant of the column subset selection algorithm proposed by Deshpande and Rademacher, which guarantees an error close to the best approximation error in the Frobenius norm. For cross approximation, in which U is required to be the inverse of a submatrix of A described by the intersection of C and R, we obtain a new algorithm with an error bound that stays within a factor k + 1 of the best rank-k approximation error in the Frobenius norm. To the best of our knowledge, this is the first deterministic polynomial-time algorithm for which this factor is bounded by a polynomial in k. Our derivation and analysis of the algorithm is based on derandomizing a recent existence result by Zamarashkin and Osinsky. To illustrate the versatility of our new column subset selection algorithm, an extension to low multilinear rank approximations of tensors is provided as well. © 2020 Society for Industrial and Applied Mathematics
Low rank ODEs for Hamiltonian matrix nearness problems
No full textFor a Hamiltonian matrix with purely imaginary
eigenvalues, we aim to determine the nearest
Hamiltonian matrix such that some or all eigenvalues leave the imaginary
axis.
Conversely, for a Hamiltonian matrix with all eigenvalues lying off
the imaginary axis, we look for a nearest Hamiltonian matrix that has
a pair of imaginary eigenvalues. The Hamiltonian matrices can be allowed to be complex or restricted to be real. Such Hamiltonian matrix nearness
problems are motivated by applications such as the analysis of passive
control systems. They
are closely related to the problem of determining extremal
points of Hamiltonian pseudospectra. We obtain a characterization of
optimal perturbations, which turn out to be of low rank and are
attractive stationary points of low-rank differential equations that
we derive. We use a two-level approach, where in the inner level we determine extremal points of the Hamiltonian \eps-pseudospectrum for a given \eps by following the low-rank differential equations into a stationary point, and on the outer level we optimize for~\eps. This permits us to give fast algorithms - exhibiting quadratic convergence - for solving the considered Hamiltonian matrix
nearness problems
Computing extremal points of symplectic pseudospectra and solving symplectic matrix nearness problems.
No full textWe study differential equations that lead to extremal points in symplectic pseudospectra. In a two-level approach, where on the inner level we compute extremizers of the symplectic \eps-pseudospectrum for a given \eps and on the outer level we optimize over \eps,
this is used to solve symplectic matrix nearness problems such as the following:
For a symplectic matrix with eigenvalues of unit modulus, we aim to determine the nearest complex symplectic matrix such that some or all eigenvalues leave the complex unit circle. Conversely, for a symplectic matrix with all eigenvalues lying off the unit circle, we consider the problem of computing the nearest symplectic matrix that has an eigenvalue on the unit circle
On Randomized Trace Estimates for Indefinite Matrices with an Application to Determinants
Full text linkRandomized trace estimation is a popular and well-studied technique that approximates the trace of a large-scale matrix B by computing the average of x(T) Bx for many samples of a random vector X. Often, B is symmetric positive definite (SPD) but a number of applications give rise to indefinite B. Most notably, this is the case for log-determinant estimation, a task that features prominently in statistical learning, for instance in maximum likelihood estimation for Gaussian process regression. The analysis of randomized trace estimates, including tail bounds, has mostly focused on the SPD case. In this work, we derive new tail bounds for randomized trace estimates applied to indefinite B with Rademacher or Gaussian random vectors. These bounds significantly improve existing results for indefinite B, reducing the number of required samples by a factor n or even more, where n is the size of B. Even for an SPD matrix, ourwork improves an existing result by Roosta-Khorasani and Ascher (Found Comput Math, 15(5):1187-1212, 2015) for Rademacher vectors. This work also analyzes the combination of randomized trace estimates with the Lanczos method for approximating the trace of f(B). Particular attention is paid to the matrix logarithm, which is needed for log-determinant estimation. We improve and extend an existing result, to not only cover Rademacher but also Gaussian random vectors.ANCHPThis is an Open Access article under the terms of the Creative Commons Attribution Licens
Divide-and-Conquer Methods for Functions of Matrices with Banded or Hierarchical Low-Rank Structure
Full text linkThis work is concerned with approximating matrix functions for banded matrices, hierarchically semiseparable matrices, and related structures. We develop a new divide-and-conquer method based on (rational) Krylov subspace methods for performing low-rank updates of matrix functions. Our convergence analysis of the newly proposed method proceeds by establishing relations to best polynomial and rational approximation. When only the trace or the diagonal of the matrix function is of interest, we demonstrate---in practice and in theory---that convergence can be faster. For the special case of a banded matrix, we show that the divide-and-conquer method reduces to a much simpler algorithm, which proceeds by computing matrix functions of small submatrices. Numerical experiments confirm the effectiveness of the newly developed algorithms for computing large-scale matrix functions from a wide variety of applications
Improved ParaDiag via low-rank updates and interpolation
Full text linkThis work is concerned with linear matrix equations that arise from the space-time discretization of time-dependent linear partial differential equations (PDEs). Such matrix equations have been considered, for example, in the context of parallel-in-time integration leading to a class of algorithms called ParaDiag. We develop and analyze two novel approaches for the numerical solution of such equations. Our first approach is based on the observation that the modification of these equations performed by ParaDiag in order to solve them in parallel has low rank. Building upon previous work on low-rank updates of matrix equations, this allows us to make use of tensorized Krylov subspace methods to account for the modification. Our second approach is based on interpolating the solution of the matrix equation from the solutions of several modifications. Both approaches avoid the use of iterative refinement needed by ParaDiag and related space-time approaches in order to attain good accuracy. In turn, our new algorithms have the potential to outperform, sometimes significantly, existing methods. This potential is demonstrated for several different types of PDEs
Compress-and-restart block Krylov subspace methods for Sylvester matrix equations
Full text linkBlock Krylov subspace methods (KSMs) comprise building blocks in many state-of-the-art solvers for large-scale matrix equations as they arise, for example, from the discretization of partial differential equations. While extended and rational block Krylov subspace methods provide a major reduction in iteration counts over polynomial block KSMs, they also require reliable solvers for the coefficient matrices, and these solvers are often iterative methods themselves. It is not hard to devise scenarios in which the available memory, and consequently the dimension of the Krylov subspace, is limited. In such scenarios for linear systems and eigenvalue problems, restarting is a well-explored technique for mitigating memory constraints. In this work, such restarting techniques are applied to polynomial KSMs for matrix equations with a compression step to control the growing rank of the residual. An error analysis is also performed, leading to heuristics for dynamically adjusting the basis size in each restart cycle. A panel of numerical experiments demonstrates the effectiveness of the new method with respect to extended block KSMs
Low-rank updates of matrix functions II: Rational Krylov methods
Full text linkThis work develops novel rational Krylov methods for updating a large-scale matrix function ƒ(A) when A is subject to low-rank modifications. It extends our previous work in this context on polynomial Krylov methods, for which we present a simplified convergence analysis. For the rational case, our convergence analysis is based on an exactness result that is connected to work by Bernstein and Van Loan on rank-one updates of rational matrix functions. We demonstrate the usefulness of the derived error bounds for guiding the choice of poles in the rational Krylov method for the exponential function and Markov functions. Low-rank updates of the matrix sign function require additional attention; we develop and analyze a combination of our methods with a squaring trick for this purpose. A curious connection between such updates and existing rational Krylov subspace methods for Sylvester matrix equations is pointed out
Quasi-Optimal Sampling to Learn Basis Updates for Online Adaptive Model Reduction with Adaptive Empirical Interpolation
No full textTraditional model reduction derives reduced models from large-scale systems in a one-time computationally expensive offline (training) phase and then evaluates reduced models in an online phase to rapidly predict system outputs; however, this offline/online splitting means that reduced models can be expected to faithfully predict outputs only for system behavior that has been incorporated into the reduced models during the offline phase. This work considers model reduction with the online adaptive empirical interpolation method (AADEIM) that adapts reduced models in the online phase to system behavior that was not anticipated in the offline phase by deriving updates from a few samples of the states of the large-scale systems. The contribution of this work is an analysis of the AADEIM sampling strategy for deciding which parts of the large-scale states to sample to learn reduced-model updates. The analysis shows that the AADEIM sampling strategy is optimal up to a factor 2. Numerical results demonstrate the theoretical results by comparing the quasi-optimal AADEIM sampling strategy to other sampling strategies on various examples
- …
