Publications related to Fast deterministic and randomized algorithms for low-rank approximation, matrix functions, and trace estimation

On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices

Daniel Kressner, Stefano Massei, Alice Cortinovis

The problem of finding a k x k submatrix of maximum volume of a matrix A is of interest in a variety of applications. For example, it yields a quasi-best low-rank approximation constructed from the rows and columns of A. We show that such a submatrix can a ...

ELSEVIER SCIENCE INC2020

Quantitative lower bounds on the Lyapunov exponent from multivariate matrix inequalities

Marius Christopher Lemm

The Lyapunov exponent characterizes the asymptotic behavior of long matrix products. Recognizing scenarios where the Lyapunov exponent is strictly positive is a fundamental challenge that is relevant in many applications. In this work we establish a novel ...

2020

Sub-Matrix Factorization for Real-Time Vote Prediction

Patrick Thiran, Matthias Grossglauser, Victor Kristof

We address the problem of predicting aggregate vote outcomes (e.g., national) from partial outcomes (e.g., regional) that are revealed sequentially. We combine matrix factorization techniques and generalized linear models (GLMs) to obtain a flexible, effic ...

2020

Rational Krylov for Stieltjes matrix functions: convergence and pole selection

Stefano Massei

Evaluating the action of a matrix function on a vector, that is

x=f(\mathcal M)v

, is an ubiquitous task in applications. When

\mathcal M

is large, one usually relies on Krylov projection methods. In this paper, we provide effective choices for the pole ...

2019

hm-toolbox: Matlab software for HODLR and HSS matrices

Daniel Kressner, Stefano Massei

Matrices with hierarchical low-rank structure, including HODLR and HSS matrices, constitute a versatile tool to develop fast algorithms for addressing large-scale problems. While existing software packages for such matrices often focus on linear systems, t ...

2019

MATHICSE Technical Report: Block Krylov subspace methods for functions of matrices II: Modified block FOM

Kathryn Dianne Lund

We analyze an expansion of the generalized block Krylov subspace framework of [Electron.\ Trans.\ Numer.\ Anal., 47 (2017), pp. 100-126]. This expansion allows the use of low-rank modifications of the matrix projected onto the block Krylov subspace and con ...

MATHICSE2019

MATHICSE Technical Report : On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices

Daniel Kressner, Stefano Massei, Alice Cortinovis

The problem of finding a

k\times k

submatrix of maximum volume of a matrix A is of interest in a variety of applications. For example, it yields a quasi-best low-rank approximation constructed from the rows and columns of A. We show that such a submatrix ...

MATHICSE2019

Multi-panel, on-single-chip Memristive Biosensing

Giovanni De Micheli, Sandro Carrara, Danilo Demarchi, Ioulia Tzouvadaki, Abuduwaili Tuoheti

Memristive biosensors have demonstrated excellent capabilities for ultrasensitive bio-detection. In the present work, memristive biosensing chips are designed, fabricated and implemented in a for the first time presented multi-panel on-chip detection for d ...

2019

Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization

Sebastian Urban Stich

We present the first accelerated randomized algorithm for solving linear systems in Euclidean spaces. One essential problem of this type is the matrix inversion problem. In particular, our algorithm can be specialized to invert positive definite matrices i ...

2018

Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization

Sebastian Urban Stich

We present the first accelerated randomized algorithm for solving linear systems in Euclidean spaces. One essential problem of this type is the matrix inversion problem. In particular, our algorithm can be specialized to invert positive definite matrices i ...

NEURAL INFORMATION PROCESSING SYSTEMS (NIPS)2018

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

Graph Chatbot

Chat with Graph Search

On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices

Quantitative lower bounds on the Lyapunov exponent from multivariate matrix inequalities

Sub-Matrix Factorization for Real-Time Vote Prediction

Rational Krylov for Stieltjes matrix functions: convergence and pole selection

hm-toolbox: Matlab software for HODLR and HSS matrices

MATHICSE Technical Report: Block Krylov subspace methods for functions of matrices II: Modified block FOM

MATHICSE Technical Report : On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices

Multi-panel, on-single-chip Memristive Biosensing

Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization

Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization

hm-toolbox: Matlab software for HODLR and HSS matrices

Quantitative lower bounds on the Lyapunov exponent from multivariate matrix inequalities

MATHICSE Technical Report : On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices

Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization

On maximum volume submatrices and cross approximation for symmetric semidefinite and diagonally dominant matrices

Rational Krylov for Stieltjes matrix functions: convergence and pole selection

Multi-panel, on-single-chip Memristive Biosensing

MATHICSE Technical Report: Block Krylov subspace methods for functions of matrices II: Modified block FOM

Accelerated Stochastic Matrix Inversion: General Theory and Speeding up BFGS Rules for Faster Second-Order Optimization

Sub-Matrix Factorization for Real-Time Vote Prediction