Quasi-optimal Hierarchically Semi-separable Matrix Approximation

Abstract. We present a randomized algorithm for producing a quasi-optimal hierarchically semiseparable (HSS) approximation to an [Formula: see text] matrix [Formula: see text] using only matrix-vector products with [Formula: see text] and [Formula: see text]. We prove that, using [Formula: see text] matrix-vector products and [Formula: see text] additional runtime, the algorithm returns an HSS matrix [Formula: see text] with rank-[Formula: see text] blocks whose expected Frobenius norm error [Formula: see text] is at most [Formula: see text] times worse than the best possible approximation error by an HSS rank-[Formula: see text] matrix. In fact, the algorithm we analyze in a simple modification of an empirically effective method proposed by [J. Levitt and P.-G. Martinsson, SIAM J. Sci. Comput., 46 (2024), pp. A1747–A1763]. As a stepping stone towards our main result, we prove two results that are of independent interest: a similar guarantee for a variant of the algorithm which accesses [Formula: see text]’s entries directly, and explicit error bounds for near-optimal subspace approximation using projection-cost-preserving sketches. To the best of our knowledge, our analysis constitutes the first polynomial-time quasi-optimality result for HSS matrix approximation, both in the explicit access model and the matrix-vector product query model. Reproducibility of computational results. This paper has been awarded the “SIAM Reproducibility Badge: Code and data available” as a recognition that the authors have followed reproducibility principles valued by SIMAX and the scientific computing community. Code and data that allow readers to reproduce the results in this paper are available at https://github.com/NoahAmsel/HSS-approximation . [Formula: see text]