{"id":"arxiv/2610.35474","url":"https://arxiv.org/abs/2610.35474","tags":["math.NA"],"score":0,"title":"Acceleration of the BSS Algorithm","domain":"math.NA","source":"arxiv","authors":["Tizian Sommerfeld"],"reviews":0,"subject":"math.NA","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-26","reactions":{}}