Speaker
Description
I will present Randomly Pivoted LU (RPLU), a randomized variant of Gaussian elimination with complete pivoting that samples pivots proportional to squared Schur-complement entries, and analyze its low-rank approximation properties. I will highlight two regimes where RPLU is particularly effective at low-rank approximation: (i) memory-limited settings, where a rank-$k$ approximation can be computed with $\mathcal{O}(k^2+m+n)$ storage and $\mathcal{O}(k^3+m+n+k\mathcal{M}(\mathbf{A}))$ work (with $\mathcal{M}(\mathbf{A})$ the cost of a matvec with $\mathbf{A} \in \mathbb{C}^{m \times n}$ or $\mathbf{A}^* $), and (ii) structured problems where $\mathbf{A}$ and its Schur complements admit fast updates (e.g., Cauchy-like matrices). I will discuss applications to fast computation of high-degree rational approximants.