PreprintCC BY 4.0arXiv
Acceleration of the BSS Algorithm
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 𝒪(σ2nm3) 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 𝒪(σ2nm2.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 𝒪(σ2m2(n+m1.5)).}
Related
- A Projection Anderson Acceleration Algorithm for Non-quasi-monotone Variational Inequalities with Hölder Continuous Terms
- Acceleration of the Method of Alternating Projections on subspaces by GMRES
- Spacetimes of maximal proper acceleration and muon mean lifetime
- Polynomial Acceleration of Alternating Projections: Chebyshev Acceleration, Convergence Rates, and Retractions
- An Equivalence result for sketched Anderson Acceleration and sketched GMRES
BibTeX
@misc{sommerfeld2026acceleration,
title = {{Acceleration of the BSS Algorithm}},
author = {Tizian Sommerfeld},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.35474},
eprint = {2610.35474},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.35474},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Acceleration of the BSS Algorithm
AU - Tizian Sommerfeld
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.35474
UR - https://arxiv.org/abs/2610.35474
AB - 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 𝒪(σ^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 𝒪(σ^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 𝒪(σ^2m^2(n+m^1.5)).}
ER -