Exploit spectral outliers without losing input sparsity
Let $A \in \mathbb{R}^{n \times n}$ be nonsingular, with singular values $\sigma_1 \ge \dots \ge \sigma_n > 0$, and write $N = \operatorname{nnz}(A)$ and $\kappa_2(A) = \sigma_1/\sigma_n$. The input consists of the nonzero entries of $A$ with their indices, a vector $b \ne 0$, $\varepsilon \in (0, 1/2)$, $k \in \{0, \dots, n - 1\}$ and $\kappa \ge 1$, with the promise $\sigma_{k+1}/\sigma_n \le \kappa$: all but the $k$ largest singular values lie within a factor $\kappa$ of the smallest. Algorithms may access the entries of $A$ directly and perform exact arithmetic operations. Fix any $\omega_0 > 2$ for which square matrices of order $m$ can be multiplied with $O(m^{\omega_0})$ arithmetic operations. Amsel et al. note that Krylov subspace methods need $\tilde{O}(k + \kappa)$ products with $A$ and $A^{T}$ for such systems, and that Dereziński and Sidford's randomized sketching methods use $O(k^{\omega}) + \tilde{O}(n^2\kappa)$ arithmetic operations, where $\omega$ is the exponent of the matrix multiplication algorithm used.
Problem. Is there a randomized algorithm that, for every such input, returns $\widehat x$ with $\|A\widehat x - b\|_2 \le \varepsilon\|b\|_2$ with probability at least $0.99$, using at most $$C\,(k^{\omega_0} + N\kappa)\,\bigl[1 + \log(n\kappa_2(A)/\varepsilon)\bigr]^q$$ exact arithmetic operations, where $C$ and $q$ may depend on the chosen multiplication algorithm but not on the input?
Source: Amsel et al. (2026), Problem 2.5 (Section 2.4, scribe Dereziński), from the Simons Institute workshop Linear Systems and Eigenvalue Problems (2025); made precise by OpenProblemsInNLA (accuracy ‖Ax̂ − b‖₂ ≤ ε‖b‖₂ with probability 0.99, the factor [1 + log(nκ₂(A)/ε)]^q for Õ, and any admissible ω₀ for ω).
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Keywords
- OpenProblemsInNLA, randomized algorithms, singular values, sparse linear systems
- Literature checked
- Oct. 8, 2026 by clemens-admin
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},
}
@inproceedings{derezinski2026,
author = {Derezi{\'n}ski, Micha{\l} and Sidford, Aaron},
title = {Approaching Optimality for Solving Dense Linear Systems with Low-Rank Structure},
booktitle = {Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)},
publisher = {SIAM},
year = {2026},
pages = {925--938},
doi = {10.1137/1.9781611978971.37},
eprint = {2507.11724},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ke01,
author = {Townsend, Alex},
title = {{KE-01}: Exploit spectral outliers without losing input sparsity},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/linear-systems-and-elimination/KE-01/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
For a sparse nonsingular matrix with at most $k$ singular-value outliers and tail condition number at most $\kappa$, conjugate gradients on the implicit normal equations gives a deterministic $O(N[k+1+\kappa\log(2/\varepsilon)])$ arithmetic bound. We give its residual-norm proof and identify regimes where it already meets the target cost. We then prove an input-sparsity bound for explicitly sparse positive definite matrices whose spectral …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Open → Partially resolved | The registry's curators | Exact-arithmetic bounds, a flat-tail special case, and the remaining sparsity gap v1 recorded from OpenProblemsInNLA @ eb7c9d6, holden-ke01-2026-09-12/report.pdf. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00195, "Exploit spectral outliers without losing input sparsity", clopen.solutions.