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

Related publications (32)

COMPUTING FUNCTIONS OF SYMMETRIC HIERARCHICALLY SEMISEPARABLE MATRICES

The aim of this work is to develop a fast algorithm for approximating the matrix function f(A) of a square matrix A that is symmetric and has hierarchically semiseparable (HSS) structure. Appearing in a wide variety of applications, often in the context of ...

2024

Spectral Estimators for High-Dimensional Matrix Inference

Farzad Pourkamali

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

EPFL2024

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

Daniel Kressner, Alice Cortinovis

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

Siam Publications2024

Randomized low-rank approximation and its applications

Ulf David Persson

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

EPFL2024

IMPROVED VARIANTS OF THE HUTCH plus plus ALGORITHM FOR TRACE ESTIMATION

Daniel Kressner, Alice Cortinovis, Ulf David Persson

This paper is concerned with two improved variants of the Hutch++ algorithm for estimating the trace of a square matrix, implicitly given through matrix-vector products. Hutch++ combines randomized low-rank approximation in a first phase with stochastic tr ...

SIAM PUBLICATIONS2022

RANDOMIZED JOINT DIAGONALIZATION OF SYMMETRIC

Daniel Kressner, Haoze He

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

Siam Publications2024

Sparse random hypergraphs: non-backtracking spectra and community detection

Ludovic Théo Stephan

We consider the community detection problem in a sparse q-uniform hypergraph G, assuming that G is generated according to the Hypergraph Stochastic Block Model (HSBM). We prove that a spectral method based on the non-backtracking operator for hypergraphs w ...

OXFORD UNIV PRESS2024

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

Alice Cortinovis

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

EPFL2022

Building on Efficient Foundations: Effectively Training LLMs with Structured Feedforward Layers

Xiuying Wei, Caglar Gulcehre, Skander Moalla

State-of-the-art results in large language models (LLMs) often rely on scale, which becomes computationally expensive. This has sparked a research agenda to reduce these models' parameter counts and computational costs without significantly impacting their ...

2024

Iterative refinement of Schur decompositions

Daniel Kressner, Zvonimir Bujanovic

The Schur decomposition of a square matrix A is an important intermediate step of state-of-the-art numerical algorithms for addressing eigenvalue problems, matrix functions, and matrix equations. This work is concerned with the following task: Compute a (m ...

SPRINGER2023

DIVIDE-AND-CONQUER METHODS FOR FUNCTIONS OF MATRICES WITH BANDED OR HIERARCHICAL LOW-RANK STRUCTURE\ast

Daniel Kressner, Stefano Massei, Alice Cortinovis

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

SIAM PUBLICATIONS2022

Optimal denoising of rotationally invariant rectangular matrices

Lenka Zdeborová, Florent Gérard Krzakala, Emanuele Troiani, Vittorio Erba

In this manuscript we consider denoising of large rectangular matrices: given a noisy observation of a signal matrix, what is the best way of recovering the signal matrix itself? For Gaussian noise and rotationally-invariant signal priors, we completely ch ...

2022

Statistical limits of dictionary learning: Random matrix theory and the spectral replica method

Nicolas Macris, Jean François Emmanuel Barbier

We consider increasingly complex models of matrix denoising and dictionary learning in the Bayes-optimal setting, in the challenging regime where the matrices to infer have a rank growing linearly with the system size. This is in contrast with most existin ...

AMER PHYSICAL SOC2022

On Randomized Trace Estimates for Indefinite Matrices with an Application to Determinants

Daniel Kressner, Alice Cortinovis

Randomized 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 ...

2022

Tangent functional connectomes uncover more unique phenotypic traits

Mingkui Wang, Enrico Amico

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

CELL PRESS2023

A mathematical theory for mass lumping and its generalization with applications to isogeometric analysis

Annalisa Buffa, Yannis Dirk Voet, Espen Sande

Explicit time integration schemes coupled with Galerkin discretizations of time-dependent partial differential equations require solving a linear system with the mass matrix at each time step. For applications in structural dynamics, the solution of the li ...

2023

Robust Differentiable SVD

Pascal Fua, Mathieu Salzmann, Wei Wang, Yinlin Hu, Zheng Dang

Eigendecomposition of symmetric matrices is at the heart of many computer vision algorithms. However, the derivatives of the eigenvectors tend to be numerically unstable, whether using the SVD to compute them analytically or using the Power Iteration (PI) ...

2021

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

Mihai Adrian Ionescu, Ali Saeidi, Luca Capua, Yann Christophe Sprunger

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

IEEE2023

Further results on latent discourse models and word embeddings

Youssef Allouah

We discuss some properties of generative models for word embeddings. Namely, (Arora et al., 2016) proposed a latent discourse model implying the concentration of the partition function of the word vectors. This concentration phenomenon led to an asymptotic ...

Microtome Publishing2021

Construction of optimal spectral methods in phase retrieval

Lenka Zdeborová, Florent Gérard Krzakala

We consider the phase retrieval problem, in which the observer wishes to recover a n-dimensional real or complex signal X⋆ from the (possibly noisy) observation of |ΦX⋆|, in which Φ is a matrix of size m×n. We consider a \emph{high-dimensional} setting whe ...

2021