Concave-function transfer of Frobenius 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 $\|M\|_F^2 = \sum_{i,j} M_{ij}^2$. Persson, Meyer and Musco proved the implication below when $f$ is in addition operator monotone, and noted that its premise, on a difference of squared norms, is stronger than $\|A - \widehat A_k\|_F^2 \le (1 + \varepsilon)\|A - A_k\|_F^2$.
Problem. Does $$\|A\|_F^2 - \|\widehat A_k\|_F^2 \le (1 + \varepsilon)\, \|A - A_k\|_F^2$$ imply $$\|f(A) - f(\widehat A)_k\|_F^2 \le (1 + \varepsilon)\, \|f(A) - f(A)_k\|_F^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 (Frobenius norm, f concave and non-decreasing, A ⪰ Â) and Section 5; stated by OpenProblemsInNLA with the stronger premise of their Theorem 2.5.
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-ra09,
author = {Townsend, Alex},
title = {{RA-09}: Concave-function transfer of Frobenius 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-09/README.md},
note = {Read at commit eb7c9d6, 2026-10-07},
}
Resolution claims
Let $f:[0,\infty)\to[0,\infty)$ be continuous and nondecreasing, with $f(x)/x$ nonincreasing on $(0,\infty)$. This class includes every nonnegative nondecreasing concave function. We prove that ordinary relative Frobenius approximation error transfers from $A$ to $f(A)$ without loss whenever $0\preceq B\preceq A$ and $B$ has the prescribed low rank. No operator-monotonicity assumption or stronger trace-deficit hypothesis is needed. Without the order assumption, the relative …
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-00241, "Concave-function transfer of Frobenius low-rank error", clopen.solutions.