Acceleration of the BSS Algorithm

arXiv:2610.35474v1 Announce Type: new Abstract: Bartel, Sch\"{a}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}(\sigma^2nm^3)$ for a frame of $n$ vectors of dimension $m$ and oversampling $\sigma^2$. We continue their work by showing that the algorithm can be implemented in $\mathcal{O}(\sigma^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}(\sigma^2m^2(n+m^{1.5}))$.}