Robust blockwise random pivoting: fast and accurate adaptive interpolative decomposition (Q6936081)

This interesting paper studies robust blockwise random pivoting. More precisely, it focuses on fast and accurate adaptive interpolative decomposition (ID). Mathematically ID can be described as follows. Let us be given a set \(X:=[x_1,...,x_n]^{T}\in\mathbb R^{n\times d}\) consisting of \(n\geq 1\) data points say \(\left\{x_i\in \mathbb R^d\right\}_{i\in [n]}\), \(\varepsilon>0\) small enough and a target rank \(r\in \mathcal{N}\). The aim is to construct an \((r,\varepsilon)\) ID of the set \(X\) so the following holds: \(X\approx WX_{S}\) where \(||X-WX_S||_F^2\leq (1+\varepsilon)||X-<X>_r||_F^2\) where: \(k\) is an unknown target rank, \(<X>_r\) is the optimal rank-\(r\) approximation of the set \(X\), \(S=\left\{s_1,...,s_k\right\}\subset[n]\) are the skeleton indices corresponding to the row skeleton \(k\times d\) submatrix \(X_S:=[x_{s_1},...,x_{s_k}]^T\in\mathbb R^{k\times d}\) and \(W\in \mathbb R^{n\times k}\) is an interpolation matrix that (nearly) minimizes \(||X-WX_S||_F^2\). Here, \(||.||_F\) is the Frobenius matrix norm. \N\NID has many applications, for example in numerical analysis, data compression, machine learning and many others. Essentially, ID constructs a low-rank approximation formed by a basis consisting of row/column skeletons in the original matrix and a corresponding interpolation matrix.\N\NIn this paper, the authors study accurate and fast ID algorithms for empirical performance, including accuracy in both skeleton selection and interpolation matrix construction, efficiency in terms of asymptotic complexity and hardware efficiency, as well as rank-adaptiveness.\N\NThe paper is very well written and has a very good set of references.