Accurate selected bidiagonal singular vectors in O(kn) work
Let $B \in \mathbb{R}^{n \times n}$ be upper bidiagonal, with singular values $\sigma_1(B) \ge \cdots \ge \sigma_n(B) \ge 0$. Let $\epsilon$ be the unit roundoff, assume that $\epsilon n$ is small, and exclude overflow and underflow. The MRRR algorithm (MR³) of Dhillon and Parlett computes $k$ eigenpairs of a symmetric tridiagonal matrix in $O(kn)$ operations; Willems and Lang proved its accuracy under assumptions some of which can only be checked while it runs. Applied separately to $B^T B$ and $B B^T$, it can give large residuals $\|Bv - \sigma u\|_2$, and applied to the Golub–Kahan matrix it often gives singular vectors that are not orthogonal enough. Großer and Lang, and later Willems and Lang, adapted MR³ to the bidiagonal singular value problem; Marques, Demmel and Vasconcelos report test matrices on which the implementation of Willems and Lang returns eigenvectors that are far from orthogonal.
Problem. Given $k$ distinct indices $j_1, \ldots, j_k \in \{1, \ldots, n\}$, is there a floating-point algorithm that computes, in $O(kn)$ arithmetic operations, triplets $(\widehat\sigma_i, \widehat u_i, \widehat v_i)$ with $\widehat\sigma_i \ge 0$ and unit vectors $\widehat u_i, \widehat v_i$, such that $$|\widehat\sigma_i - \sigma_{j_i}(B)| \le C \epsilon n \|B\|_2, \qquad \|B \widehat v_i - \widehat\sigma_i \widehat u_i\|_2 \le C \epsilon n \|B\|_2, \qquad \|B^T \widehat u_i - \widehat\sigma_i \widehat v_i\|_2 \le C \epsilon n \|B\|_2$$ for every $i$, and $$|\widehat u_i^T \widehat u_l| \le C \epsilon n, \qquad |\widehat v_i^T \widehat v_l| \le C \epsilon n \qquad (i \ne l),$$ where $C$ is a universal constant, independent of gaps between and clusters of the singular values? For a repeated singular value, any orthonormal basis of its singular subspaces is allowed.
Source: Amsel et al. (2026), Problem 3.8, from the workshop Linear Systems and Eigenvalue Problems at the Simons Institute (October 2025); stated in this form by AIM — Open Applied Problems, which adds the accuracy of the singular values, the second residual and the requested indices.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- NA — Numerical Analysis
- Keywords
- AIM Open Applied Problems, bidiagonal matrices, floating-point algorithms, singular value decompositions
References
@misc{amsel2026,
author = {Amsel, Noah and Baumann, Yves and Beckman, Paul and B{\"u}rgisser, Peter and Cama{\~n}o, Chris and Chen, Tyler and Chow, Edmond and Damle, Anil and Derezinski, Michal and Embree, Mark and Epperly, Ethan N. and Falgout, Robert and Fornace, Mark and Greenbaum, Anne and Greif, Chen and Halikias, Diana and Huang, Zhen and Jarlebring, Elias and Koutis, Yiannis and Kressner, Daniel and Kyng, Rasmus and Liesen, J{\"o}rg and Lok, Jackie and Meyer, Raphael A. and Nakatsukasa, Yuji and Pearce, Kate and Peng, Richard and Persson, David and Rebrova, Eliza and Schneider, Ryan and Shah, Rikhav and Solomonik, Edgar and Srivastava, Nikhil and Townsend, Alex and Webber, Robert J. and Williams, Jess},
title = {Linear systems and eigenvalue problems: open questions from a {S}imons workshop},
year = {2026},
eprint = {2602.05394},
archivePrefix = {arXiv},
note = {Version 3, 21 August 2026},
}
@article{dhillon2004,
author = {Dhillon, Inderjit S. and Parlett, Beresford N.},
title = {Multiple representations to compute orthogonal eigenvectors of symmetric tridiagonal matrices},
journal = {Linear Algebra Appl.},
volume = {387},
year = {2004},
pages = {1--28},
doi = {10.1016/j.laa.2003.12.028},
}
@article{willems2013,
author = {Willems, Paul R. and Lang, Bruno},
title = {A framework for the {$MR^3$} algorithm: theory and implementation},
journal = {SIAM J. Sci. Comput.},
volume = {35},
number = {2},
year = {2013},
pages = {A740--A766},
doi = {10.1137/110834020},
}
@article{grosser2003,
author = {Gro{\ss}er, Benedikt and Lang, Bruno},
title = {An {$O(n^2)$} algorithm for the bidiagonal {SVD}},
journal = {Linear Algebra Appl.},
volume = {358},
number = {1-3},
year = {2003},
pages = {45--70},
doi = {10.1016/S0024-3795(01)00398-6},
}
@article{willems2012,
author = {Willems, Paul R. and Lang, Bruno},
title = {The {MR}$^3$-{GK} algorithm for the bidiagonal {SVD}},
journal = {Electron. Trans. Numer. Anal.},
volume = {39},
year = {2012},
pages = {1--21},
}
@article{marques2020,
author = {Marques, Osni and Demmel, James and Vasconcelos, Paulo B.},
title = {Bidiagonal {SVD} computation via an associated tridiagonal eigenproblem},
journal = {ACM Trans. Math. Software},
volume = {46},
number = {2},
year = {2020},
pages = {14:1--14:25},
doi = {10.1145/3361746},
}
@misc{aim-accurate-bidiagonal-svd,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Accurate selected bidiagonal singular vectors in O(kn) work}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/042-accurate-bidiagonal-svd.md},
note = {Entry 042 at commit a153f46, 2026-10-13},
}
Resolution claims
Computing a few singular vectors of a bidiagonal matrix requires control of orthogonality as well as residuals when singular values cluster. We give a rational-filter construction for any requested set of $k$ ordered singular triplets of a real $n\times n$ upper bidiagonal matrix. For $\epsilon=2^{-p}$, $16\le p\le53$ and $n\epsilon\le1/64$, its represented unit directions satisfy both singular-vector residual bounds, ordered-value accuracy …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-18 | Open → Solution claimed | The registry's curators | Selected bidiagonal singular directions with fixed-format linear output work v1 recorded from AIM @ 24edaad, paper/main.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00325, "Accurate selected bidiagonal singular vectors in O(kn) work", clopen.solutions.