{"id":"arxiv/2608.22247","url":"https://arxiv.org/abs/2608.22247","tags":["cs.DS","cs.CC","math.ST"],"score":0,"title":"Near-Optimal Bounds for Sketching the Schatten Norms","domain":"cs.DS","source":"arxiv","authors":["Lin F. Yang"],"reviews":0,"subject":"cs.DS","summary":"Let $k_{1,\\varepsilon}(n)$ be the smallest number of real linear measurements needed by a randomized oblivious sketch that estimates the nuclear norm of every fixed real $n\\times n$ matrix within a factor $1\\pm\\varepsilon$, with probability at least $2/3$. For every fixed $0 0$ that is not a positive even integer, there are positive constants $A_{p,\\varepsilon},C_{p,\\varepsilon},c_p$ such that \\[ \\frac{n^2}{(\\log n)^{A_{p,\\varepsilon}}} \\le k_{p,\\varepsilon}(n) \\le C_{p,\\varepsilon}\\frac{n^2}{(\\log n)^{c_p}}, \\] so $k_{p,\\varepsilon}(n)=n^{2-o(1)}$ throughout the non-even regime. Together…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-23","reactions":{}}