Constant-loss nuclear-error transfer without matrix ordering
Note: OpenProblemsInNLA (RA-10) lists this problem as solved in Lean, with a proof at https://github.com/ajt60gaibb/OpenProblemsInNLA/tree/5487945e5a72abd952b0c89915915de8cc9b3e65/randomized-and-low-rank-approximation/RA-10/lean. It imports OpenProblemsInNLA's shared Lean statement library from GitHub, which the registry's offline verifier cannot fetch, so it has not been checked here.
For a real symmetric positive semidefinite $X \in \mathbb{R}^{n \times n}$ with an ordered orthonormal eigendecomposition $X = \sum_{i=1}^n \lambda_i q_i q_i^{\mathsf T}$, $\lambda_1 \ge \cdots \ge \lambda_n \ge 0$, and a function $f : [0, \infty) \to [0, \infty)$, let $$X_k = \sum_{i=1}^k \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},$$ with the same eigenvectors in both truncations, and let $\|\cdot\|_*$ be the nuclear norm. The function $f$ is operator monotone if $f(H) \succeq f(G)$ for all real symmetric $H \succeq G \succeq 0$ of every size. Persson, Meyer and Musco proved the implication below with $C = 1$ when $A \succeq \widehat A \succeq 0$, and gave an example with $A \not\succeq \widehat A$, $f(x) = \sqrt{x}$ and $k = 1$ in which it fails with $C = 1$.
Problem. Is there a constant $C \ge 1$ such that for every $n \ge 2$, every $1 \le k < n$, all real symmetric positive semidefinite $A, \widehat A \in \mathbb{R}^{n \times n}$, every $\varepsilon \ge 0$, every continuous operator monotone $f : [0, \infty) \to [0, \infty)$ and every choice of ordered eigenvectors, $$\|A - \widehat A_k\|_* \le (1 + \varepsilon)\|A - A_k\|_*$$ implies $$\|f(A) - f(\widehat A)_k\|_* \le (1 + C\varepsilon)\|f(A) - f(A)_k\|_*?$$
Source: Persson, Meyer and Musco (2025; arXiv 2023), §1.2 and the end of §5, who note that their counterexamples do not rule out the guarantee with 1 + Cε in place of 1 + ε, for a fixed constant C ≥ 1, under relaxed assumptions; the nuclear-norm case without the ordering A ⪰ Â, stated by OpenProblemsInNLA.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- NA — Numerical Analysis
- Secondary
- FA
- Keywords
- low-rank approximations, matrix functions, OpenProblemsInNLA, operator monotone functions
- 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},
}
@misc{openproblemsinnla-ra10,
author = {Townsend, Alex},
title = {{RA-10}: Constant-loss nuclear-error transfer without matrix ordering},
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-10/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
The manuscript proves that the transfer holds with the universal constant $C = 11$: for real positive semidefinite $A$ and $\widehat A$, any ordered eigenbasis of $\widehat A$ used for both truncations, every continuous operator monotone $f : [0, \infty) \to [0, \infty)$ and every $\varepsilon \ge 0$, $\|A - \widehat A_k\|_* \le (1 + \varepsilon)\|A - A_k\|_*$ implies $\|f(A) …
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-00242, "Constant-loss nuclear-error transfer without matrix ordering", clopen.solutions.