Concave matrix-function error transfer can fail for exact Nyström approximations
Recorded by the registry's curators from GitHub; the authors did not submit it here.
Matthew J. Colbrook
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$, even when the input
excess is required to be arbitrarily small. Both examples use the same fixed
nonnegative nondecreasing concave function and satisfy positive-semidefinite
order. They do not contradict positive transfer theorems for operator-monotone
functions.
Claims
Files and sources
- Paper
- OpenProblemsInNLA @ eb7c9d6, manuscripts/03_concave_transfer_counterexamples.pdf ↗
- Posted on GitHub
- 11 September 2026
No verification run is on record for this version.