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. document.getElementById('cloak6cc48313afb8ce54c85891e2ac6a8c28').innerHTML = ''; var prefix = '&#109;a' + 'i&#108;' + '&#116;o'; var path = 'hr' + 'ef' + '='; var addy6cc48313afb8ce54c85891e2ac6a8c28 = 't&#111;wns&#101;nd' + '&#64;'; addy6cc48313afb8ce54c85891e2ac6a8c28 = addy6cc48313afb8ce54c85891e2ac6a8c28 + 'c&#111;rn&#101;ll' + '&#46;' + '&#101;d&#117;'; var addy_text6cc48313afb8ce54c85891e2ac6a8c28 = 't&#111;wns&#101;nd' + '&#64;' + 'c&#111;rn&#101;ll' + '&#46;' + '&#101;d&#117;';document.getElementById('cloak6cc48313afb8ce54c85891e2ac6a8c28').innerHTML += '<a ' + path + '\'' + prefix + ':' + addy6cc48313afb8ce54c85891e2ac6a8c28 + '\'>'+addy_text6cc48313afb8ce54c85891e2ac6a8c28+'<\/a>';

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