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