Source author record

Maike Meier

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.NA Numerical Analysis

Catalog footprint

Research overview

2works

2topics

1close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2024arXiv

Fast randomized numerical rank estimation for numerically low-rank matrices

Matrices with low-rank structure are ubiquitous in scientific computing. Choosing an appropriate rank is a key step in many computational algorithms that exploit low-rank structure. However, estimating the rank has been done largely in an ad-hoc fashion in large-scale settings. In this work we develop a randomized algorithm for estimating the numerical rank of a (numerically low-rank) matrix. The algorithm is based on sketching the matrix with random matrices from both left and right; the key fact is that with high probability, the sketches preserve the orders of magnitude of the leading singular values. We prove a result on the accuracy of the sketched singular values and show that gaps in the spectrum are detected. For an $m\times n$ $(m\geq n)$ matrix of numerical rank $r$ , the algorithm runs with complexity $O(mn\log n+r^3)$ , or less for structured matrices. The steps in the algorithm are required as a part of many low-rank algorithms, so the additional work required to estimate the rank can be even smaller in practice. Numerical experiments illustrate the speed and robustness of our rank estimator.

preprint2022arXiv

Randomized algorithms for Tikhonov regularization in linear least squares

We describe two algorithms to efficiently solve regularized linear least squares systems based on sketching. The algorithms compute preconditioners for $\min \|Ax-b\|^2_2 + λ\|x\|^2_2$ , where $A\in\mathbb{R}^{m\times n}$ and $λ>0$ is a regularization parameter, such that LSQR converges in $\mathcal{O}(\log(1/ε))$ iterations for $ε$ accuracy. We focus on the context where the optimal regularization parameter is unknown, and the system must be solved for a number of parameters $λ$ . Our algorithms are applicable in both the underdetermined $m\ll n$ and the overdetermined $m\gg n$ setting. Firstly, we propose a Cholesky-based sketch-to-precondition algorithm that uses a `partly exact' sketch, and only requires one sketch for a set of $N$ regularization parameters $λ$ . The complexity of solving for $N$ parameters is $\mathcal{O}(mn\log(\max(m,n)) +N(\min(m,n)^3 + mn\log(1/ε)))$ . Secondly, we introduce an algorithm that uses a sketch of size $\mathcal{O}(\text{sd}_λ(A))$ for the case where the statistical dimension $\text{sd}_λ(A)\ll\min(m,n)$ . The scheme we propose does not require the computation of the Gram matrix, resulting in a more stable scheme than existing algorithms in this context. We can solve for $N$ values of $λ_i$ in $\mathcal{O}(mn\log(\max(m,n)) + \min(m,n)\,\text{sd}_{\minλ_i}(A)^2 + Nmn\log(1/ε))$ operations.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.