Near-Optimal Bounds for Sketching the Schatten--1 Norm

Abstract

Let $k_\epsilon(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\epsilon$, with probability at least $2/3$. For every fixed $0<\epsilon<1$, the proved result is $$ \frac{n^2}{(\log n)^{A_\epsilon}} \;\le\; k_\epsilon(n) \;\le\; C_\epsilon\frac{n^2\{\log\log(e^e n)\}^2}{\log(e n)} $$ for all sufficiently large $n$, where $A_\epsilon,C_\epsilon$ depend only on $\epsilon$. Previously, the best bounds for general linear sketches were $\Omega(n)$ and the trivial $O(n^2)$ upper bound (Li, Nguyen, Woodruff, 2019). The theorem therefore nearly resolves the open measurement-complexity question left by that work: the displayed lower and upper bounds are tight up to polylogarithmic factors. In particular, the complexity is $n^{2-o(1)}$, and for every fixed $c>0$, $O(n^{2-c})$ measurements are impossible. The upper bound is obtained by a fixed Gaussian sketch whose decoder combines implicit low-rank recovery with moment estimation on a high-stable-rank residual. The lower bound constructs moment-matched spectra, randomizes their singular vectors, and compares every low-dimensional observation through an odd-order tensor estimate and a Fisher-information path argument.