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

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

In this thesis we will present and analyze randomized algorithms for numerical linear algebra problems. An important theme in this thesis is randomized low-rank approximation. In particular, we will study randomized low-rank approximation of matrix functio ...

This work is concerned with the computation of the action of a matrix function f(A), such as the matrix exponential or the matrix square root, on a vector b. For a general matrix A, this can be done by computing the compression of A onto a suitable Krylov ...

A key challenge across many disciplines is to extract meaningful information from data which is often obscured by noise. These datasets are typically represented as large matrices. Given the current trend of ever-increasing data volumes, with datasets grow ...

Multiple tensor-times-matrix (Multi-TTM) is a key computation in algorithms for computing and operating with the Tucker tensor decomposition, which is frequently used in multidimensional data analysis. We establish communication lower bounds that determine ...

Given a family of nearly commuting symmetric matrices, we consider the task of computing an orthogonal matrix that nearly diagonalizes every matrix in the family. In this paper, we propose and analyze randomized joint diagonalization (RJD) for performing t ...

The increasing complexity of transformer models in artificial intelligence expands their computational costs, memory usage, and energy consumption. Hardware acceleration tackles the ensuing challenges by designing processors and accelerators tailored for t ...

Spectral algorithms are some of the main tools in optimization and inference problems on graphs. Typically, the graph is encoded as a matrix and eigenvectors and eigenvalues of the matrix are then used to solve the given graph problem. Spectral algorithms ...

This paper introduces a novel method for data-driven robust control of nonlinear systems based on the Koopman operator, utilizing Integral Quadratic Constraints (IQCs). The Koopman operator theory facilitates the linear representation of nonlinear system d ...

We introduce an algorithm to reconstruct a mesh from discrete samples of a shape's Signed Distance Function (SDF). A simple geometric reinterpretation of the SDF lets us formulate the problem through a point cloud, from which a surface can be extracted wit ...

This paper offers a new algorithm to efficiently optimize scheduling decisions for dial-a-ride problems (DARPs), including problem variants considering electric and autonomous vehicles (e-ADARPs). The scheduling heuristic, based on linear programming theor ...

Sample efficiency is a fundamental challenge in de novo molecular design. Ideally, molecular generative models should learn to satisfy a desired objective under minimal calls to oracles (computational property predictors). This problem becomes more apparen ...

Sylvester matrix equations are ubiquitous in scientific computing. However, few solution techniques exist for their generalized multiterm version, as they now arise in an increasingly large number of applications. In this work, we consider algebraic parame ...

Functional connectomes (FCs) containing pairwise estimations of functional couplings between pairs of brain regions are commonly represented by correlation matrices. As symmetric positive definite matrices, FCs can be transformed via tangent space projecti ...

State-of-the-art Artificial Intelligence (AI) algorithms, such as graph neural networks and recommendation systems, require floating-point computation of very large matrix multiplications over sparse data. Their execution in resource-constrained scenarios, ...

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

The locally optimal block preconditioned conjugate gradient (LOBPCG) algorithm is a popular approach for computing a few smallest eigenvalues and the corresponding eigenvectors of a large Hermitian positive definite matrix A. In this work, we propose a mix ...

Phase transitions in non-Hermitian systems are at the focus of cutting edge theoretical and experimental research. On the one hand, parity-time- (PT-) and anti-PT-symmetric physics have gained ever-growing interest, due to the existence of non-Hermitian sp ...

This 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 in ...

In this paper we demonstrate ultra-high sensitivity silicon nanowires pH and protein sensing on the same Silicon nanowire array platform by using a constant current method and monitoring the drain voltage as function of analyte concentration. The injected ...

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

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

Chat with Graph Search

Randomized low-rank approximation and its applications

SPEEDING UP KRYLOV SUBSPACE METHODS FOR COMPUTING f(A)b VIA RANDOMIZATION

Spectral Estimators for High-Dimensional Matrix Inference

COMMUNICATION LOWER BOUNDS AND OPTIMAL ALGORITHMS FOR MULTIPLE TENSOR-TIMES-MATRIX COMPUTATION

RANDOMIZED JOINT DIAGONALIZATION OF SYMMETRIC

Accelerator-driven Data Arrangement to Minimize Transformers Run-time on Multi-core Architectures

The Power of Two Matrices in Spectral Algorithms for Community Recovery

Koopman-based Data-driven Robust Control of Nonlinear Systems Using Integral Quadratic Constraints

Reach For the Arcs: Reconstructing Surfaces from SDFs via Tangent Points

A ride time-oriented scheduling algorithm for dial-a-ride problems

Augmented Memory: Sample-Efficient Generative Molecular Design with Reinforcement Learning

Preconditioning techniques for generalized Sylvester matrix equations

Tangent functional connectomes uncover more unique phenotypic traits

A 16-bit Floating-Point Near-SRAM Architecture for Low-power Sparse Matrix-Vector Multiplication

Approximation Algorithms for Allocation and Network Design

A mixed precision LOBPCG algorithm

Emergent non-Hermitian localization phenomena in the synthetic space of zero-dimensional bosonic systems

Improved ParaDiag via low-rank updates and interpolation

Ultra-High Sensitivity Silicon Nanowire Array Biosensor Based on a Constant-Current Method for Continuous Real-Time pH and Protein Monitoring in Interstitial Fluid

Results on Sparse Integer Programming and Geometric Independent Sets