Seminar, Hosted by Institute for Computational and Experimental Research in Mathematics (ICERM), Brown University
Estimating a matrix's singular values with interpolative decompositions
Abstract
Alex Townsend examines what greedy pivoting can guarantee in rank-revealing factorizations, which remain important alongside randomized sampling and sketching. A local maximum-volume viewpoint gives sharp criteria for reliable rank revelation by pivoted Gaussian elimination and QR. The comparison with pivoted Cholesky on smooth-kernel matrices shows that greedy pivoting there cannot exhibit Kahan-like behavior. These results clarify the theoretical strengths and limitations of deterministic steps in matrix approximation.
Topics
- greedy pivoting, search World Wide
- rank-revealing factorizations, search World Wide
- randomized sampling, broader topic: sampling
- sketching
- local maximum-volume, search World Wide
- pivoted Gaussian elimination, search World Wide
- pivoted Cholesky, search World Wide
- smooth-kernel matrices, search World Wide
- matrix approximation, search World Wide