Concave-function transfer of spectral low-rank error
Let $A, \widehat A \in \mathbb{R}^{n \times n}$ be symmetric with $A \succeq \widehat A \succeq 0$ in the positive semidefinite order, and let $f : [0, \infty) \to [0, \infty)$ be continuous, concave and nondecreasing. For a symmetric positive semidefinite $X = \sum_{i=1}^n \lambda_i q_i q_i^{\mathsf T}$, with $q_1, \dots, q_n$ orthonormal and $\lambda_1 \ge \cdots \ge \lambda_n \ge 0$, put $$X_k = \sum_{i=1}^k \lambda_i q_i q_i^{\mathsf T}, \qquad f(X) = \sum_{i=1}^n f(\lambda_i)\, q_i q_i^{\mathsf T}, \qquad f(X)_k = \sum_{i=1}^k f(\lambda_i)\, q_i q_i^{\mathsf T},$$ so that $X_k$ and $f(X)_k$ use the same eigenvectors, which may be chosen arbitrarily within repeated eigenspaces. Let $\|\cdot\|_2$ be the spectral norm. Persson, Meyer and Musco proved the implication below when $f$ is in addition operator monotone, even without the hypothesis $A \succeq \widehat A$, and showed by an example that for concave nondecreasing $f$ it can fail when $A \not\succeq \widehat A$.
Problem. Does $$\|A - \widehat A_k\|_2 \le (1 + \varepsilon)\, \|A - A_k\|_2$$ imply $$\|f(A) - f(\widehat A)_k\|_2 \le (1 + \varepsilon)\, \|f(A) - f(A)_k\|_2$$ for all $n \ge 2$ and $1 \le k < n$, every such pair $A, \widehat A$, every such $f$, every choice of the eigendecompositions and every $\varepsilon \ge 0$?
Source: Persson, Meyer and Musco (2025), Table 1 (operator norm, f concave and non-decreasing, A ⪰ Â) and Section 5; made precise by OpenProblemsInNLA (every choice of eigenvectors).
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- FA
- Keywords
- low-rank approximations, matrix functions, Nyström approximations, OpenProblemsInNLA
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{persson2025,
author = {Persson, David and Meyer, Raphael A. and Musco, Christopher},
title = {Algorithm-Agnostic Low-Rank Approximation of Operator Monotone Matrix Functions},
journal = {SIAM J. Matrix Anal. Appl.},
volume = {46},
number = {1},
year = {2025},
pages = {1--21},
doi = {10.1137/23M1619435},
eprint = {2311.14023},
archivePrefix = {arXiv},
}
@article{persson2026,
author = {Persson, David and Chen, Tyler and Musco, Christopher},
title = {Randomized block-{K}rylov subspace methods for low-rank approximation of matrix functions},
journal = {Linear Algebra Appl.},
volume = {741},
year = {2026},
pages = {32--65},
doi = {10.1016/j.laa.2026.03.029},
eprint = {2502.01888},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ra08,
author = {Townsend, Alex},
title = {{RA-08}: Concave-function transfer of spectral low-rank error},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/randomized-and-low-rank-approximation/RA-08/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
We give exact Nyström counterexamples to two proposed concave matrix-function error-transfer principles. A rational positive-definite $6\times6$ matrix has a rank-three Nyström approximation that is exactly optimal in spectral norm, yet applying $f(x)=\min(x,1)$ destroys optimality. A rational lower bound certifies the strict violation at a fixed nonzero perturbation. Separately, a growing-dimensional Nyström construction rules out every dimension-independent nuclear-norm relative-excess factor $1+C\varepsilon$, …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-08 | Needs verification → Solution claimed | clemens-admin | Listed with the record of its solution, unreviewed. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00240, "Concave-function transfer of spectral low-rank error", clopen.solutions.