**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Fast deterministic and randomized algorithms for low-rank approximation, matrix functions, and trace estimation

Abstract

In this thesis we propose and analyze algorithms for some numerical linear algebra tasks: finding low-rank approximations of matrices, computing matrix functions, and estimating the trace of matrices.In the first part, we consider algorithms for building low-rank approximations of a matrix from some rows or columns of the matrix itself. We prove a priori error bounds for a greedy algorithm for cross approximation and we develop a faster and more efficient variant of an existing algorithm for column subset selection. Moreover, we present a new deterministic polynomial-time algorithm that gives a cross approximation which is quasi-optimal in the Frobenius norm. The second part of the thesis is concerned with matrix functions. We develop a divide-and-conquer algorithm for computing functions of matrices that are banded, hierarchically semiseparable, or have some other off-diagonal low-rank structure. An important building block of our approach is an existing algorithm for updating the function of a matrix that undergoes a low-rank modification (update), for which we present new convergence results. The convergence analysis of our divide-and-conquer algorithm is related to polynomial or rational approximation of the function.In the third part we consider the problem of approximating the trace of a matrix which is available indirectly, through matrix-vector multiplications. We analyze a stochastic algorithm, the Hutchinson trace estimator, for which we prove tail bounds for symmetric (indefinite) matrices. Then we apply our results to the computation of the (log)determinants of symmetric positive definite matrices.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (10)

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning), achieving automation eventually.

Low-rank approximation

In mathematics, low-rank approximation is a minimization problem, in which the cost function measures the fit between a given matrix (the data) and an approximating matrix (the optimization variable), subject to a constraint that the approximating matrix has reduced rank. The problem is used for mathematical modeling and data compression. The rank constraint is related to a constraint on the complexity of a model that fits the data. In applications, often there are other constraints on the approximating matrix apart from the rank constraint, e.

Greedy algorithm

A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time. For example, a greedy strategy for the travelling salesman problem (which is of high computational complexity) is the following heuristic: "At each step of the journey, visit the nearest unvisited city.

Related MOOCs (9)

Algebra (part 1)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Algebra (part 1)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.

Algebra (part 2)

Un MOOC francophone d'algèbre linéaire accessible à tous, enseigné de manière rigoureuse et ne nécessitant aucun prérequis.