Estimating a matrix's singular values with interpolative decompositions

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.