MATH Seminar

Title: Structured Low-Rank Approximation and the Proxy Point Method
Seminar: Computational Math
Speaker: Mikhail Lepilov of Purdue University
Contact: Lars Ruthotto, lruthotto@emory.edu
Date: 2022-02-17 at 1:00PM
Venue: Online
Download Flyer
Abstract: Structured algorithms for large, dense matrices require efficient low-rank approximation methods to obtain their computational cost savings. There are many ways of obtaining such approximations depending on the type of matrix involved. For kernel matrices, analytic approximation methods such as truncated Taylor expansions or the proxy point method have been used in the Fast Multipole Method and other structured matrix algorithms. In this talk, we focus on the proxy point method, in which pairwise interactions between two separated clusters are approximated using the interactions of each cluster with a smaller chosen set of "proxy" points that separate the clusters. We perform a new accuracy analysis of this method when applied to 1D analytic kernels, and we then use it to devise a sublinear-time algorithm for constructing the HSS approximation of certain Cauchy and Toeplitz matrices. Finally, we extend this method its analysis to analytic kernels in several complex variables.