Paperlane

no. 3 · Tuesday 27 October 2026

Acceleration of the BSS Algorithm

Tizian Sommerfeld

math.NA

Abstract

Bartel, Schäfer and Ullrich investigated the BSS subsampling algorithm, which is based on the work by Batson, Spielman and Srivastava. While this algorithm works well, the bottleneck is its complexity of $\mathcal{O}(σ^2nm^3)$ for a frame of $n$ vectors of dimension $m$ and oversampling $σ^2$. We continue their work by showing that the algorithm can be implemented in $\mathcal{O}(σ^2nm^{2.5})$. Moreover, for some special cases, an even faster implementation is possible. In particular, BSS subsampling of Fourier-type frames on a full frequency cube can be implemented in essentially $\mathcal{O}(σ^2m^2(n+m^{1.5}))$.}

fields
Numerical Analysis
pdf ↗ page arXiv:2610.35474 ↗