View abstract

Session III.1 - Numerical Linear Algebra

Tuesday, June 20, 15:30 ~ 16:00

Structured matrix recovery from matrix-vector products

Alex Townsend

Cornell University, United States   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

Can one recover a structured matrix efficiently from only matrix-vector products? If so, how many are needed? In this talk, we will describe algorithms to recover structured matrices, such as tridiagonal, Toeplitz-like, and hierarchical low-rank, from matrix-vector products. In particular, we derive an algorithm for recovering an unknown $N\times N$ hierarchical low-rank matrix from only $\mathcal{O}((k+p)\log N)$ matrix-vector products that is stable with high probability, where $k$ is the rank of the off-diagonal blocks, and $p$ is a small oversampling parameter. We do this by carefully constructing randomized input vectors for our matrix-vector products that use the hierarchical structure of the matrix. While existing algorithms for hierarchical matrix recovery use a recursive “peeling" procedure based on elimination, our approach uses a recursive projection procedure,

Joint work with Diana Halikias (Cornell University).

View abstract PDF