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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Chat with Graph Search

COMPUTING FUNCTIONS OF SYMMETRIC HIERARCHICALLY SEMISEPARABLE MATRICES

Spectral Estimators for High-Dimensional Matrix Inference

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

Randomized low-rank approximation and its applications

IMPROVED VARIANTS OF THE HUTCH plus plus ALGORITHM FOR TRACE ESTIMATION

RANDOMIZED JOINT DIAGONALIZATION OF SYMMETRIC

Sparse random hypergraphs: non-backtracking spectra and community detection

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

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

Iterative refinement of Schur decompositions

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

Optimal denoising of rotationally invariant rectangular matrices

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

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

Tangent functional connectomes uncover more unique phenotypic traits

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

Robust Differentiable SVD

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

Further results on latent discourse models and word embeddings

Construction of optimal spectral methods in phase retrieval