Near-Optimal Bounds for Sketching the Schatten--1 Norm
Lin F. Yang
cs.DS, cs.CC, math.ST
2026-08-23
A (1±ε) linear sketch of an n×n nuclear norm needs n^{2-o(1)} measurements: n²/polylog lower, O(n² (log log n)²/log n) upper, versus the old Ω(n)–O(n²).
The nuclear norm, also called Schatten-1, is the sum of a matrix's singular values. The task is clean: draw a random linear map S before seeing A, store k real numbers S(A), and decode a (1±ε) estimate of ||A||{S1}. The estimate must succeed with probability at least 2/3 for every fixed n×n real matrix.
If A is promised positive semidefinite, the nuclear norm equals the trace, so one measurement is exact. Vector ℓ1 has sketches whose dimension is independent of the ambient size at fixed accuracy. Matrices do not inherit that. Changing one entry moves every singular value, and both singular directions are unknown.
Li, Nguyễn, and Woodruff placed this question in the general linear-sketch model. The conference paper proved Ω(√n); the journal version raised that to Ω(n). The matching upper bound stayed the trivial O(n²) obtained by storing every entry. Where the true complexity sits inside that polynomial range was open. This paper nearly closes it.
The lower bound holds for every rank-k linear measurement and every measurable decoder. Two random-matrix laws have nuclear norms in disjoint relative-error ranges, yet every k-dimensional projection of them is close in total variation. A valid estimator would label the two laws; if the observations cannot, no such estimator exists.
At the scalar level, two laws on squared singular values match moments of degrees 0 through K, while their square-root expectations differ by a fixed relative gap. K is on the order of (1/100) log n / log log n. Those atom weights need not be multiples of 1/n. A Steinitz rearrangement plus a handful of control particles turns them into n equal-weight spectra, joined by a path that keeps the first K moments exactly constant at every time. Left and right singular vectors are independent Haar orthogonal matrices; a small Gaussian perturbation makes the observed densities differentiable.
Fisher information along the path controls total variation. Tensor orders through 2K cancel because those spectral moments never move. The first surviving order is the odd integer m=2K+1. An odd-order random-rotation lemma says a rank-k projection sees at most about (k/n²)^{K+1} of the squared energy, up to factors exponential in K log K. With that K, the two endpoints are indistinguishable whenever k ≤ n²/(log n)^{Aε}.
The upper bound stores four independent Gaussian products drawn before the input: GA, WA, AR₀, and YA. The decoder picks a spectral cutoff from stored data. The head is a few large singular directions; the tail is required to have large stable rank, meaning Frobenius energy is not piled into one direction. The head nuclear norm is estimated by Gaussian regression without reconstructing A. The tail approximates √x by a polynomial of degree about log n / log log n and estimates each power sum unbiasedly from Gaussian cycle statistics. Head cost is about n² log b / b; tail cost is about n^{2-c/b} poly(b). They meet at b ≍ log n / log log n. Cutoff selection lives entirely in the decoder; the four maps stay fixed and linear.
For every fixed 0<ε<1 there exist constants Aε, Cε depending only on ε such that, for all large n,
n² / (log n)^{Aε} ≤ kε(n) ≤ Cε n² {log log(e^e n)}² / log(e n)
| Work | Model | Lower bound | Upper bound |
| Li–Nguyễn–Woodruff, conference | general linear | Ω(√n) | O(n²) |
| Same authors, journal | general linear | Ω(n) | O(n²) |
| This paper | general linear | n²/(log n)^{Aε} | Oε(n² (log log n)² / log n) |
The polynomial gap collapses to a polylogarithmic one. For every fixed c>0, O(n^{2-c}) measurements are impossible. The upper bound saves a factor of about log n / (log log n)² against storing the whole matrix. The decoder assigns failure probability 1/100 to each of four events (covariance, Frobenius, head regression, tail estimate) and succeeds with probability at least 0.96. With α=ρ=η=ε/20 the total relative error is at most 2ε/5.
Positive-semidefinite inputs still need one measurement. The theorem is for unrestricted real square matrices.
Anyone using the nuclear norm as a convex proxy in matrix completion or low-rank models should not read this as a drop-in compressor. It is a measurement-complexity fact: under oblivious linear measurements, exact real arithmetic, and a uniform (1±ε) guarantee, the nuclear norm barely compresses. The dimension-free sketches that work for vector ℓ1 do not exist here.
The only saving is polylogarithmic. That is rarely worth a heavier decoder if one was going to store the n×n matrix anyway. Decoder runtime is outside the model.
The useful split is this: adding singular values is easy once the matrix is PSD; it is hard when both singular directions are unknown. Sparse matrices, row-order streams, and multi-pass algorithms already have different space bounds in prior work. Bilinear sketches of the form SAT already had nearly linear lower bounds; this paper does not revisit that model.
A logarithmic gap remains. The lower bound is n²/(log n)^{Aε} with an ε-dependent exponent; the upper bound is Oε(n² (log log n)² / log n). The optimal power of log n is unset, and extra iterated-log factors are not ruled out. Accuracy ε is fixed before n grows; the joint (n,ε) dependence is open.
The model counts exact real measurements, not bits. The theorem does not say that every streaming algorithm needs n^{2-o(1)} bits. The turnstile linearization theorem of Li, Nguyễn, and Woodruff controls the log of the number of reachable states, not the number of sketch rows. The strongest finite-memory bound quoted here is still the nearly linear bit-space lower bound for non-even Schatten powers, including p=1, on sparse bounded-integer matrices. Those two lower bounds sit side by side; they are not the same quantity.
The upper bound is not a Turing-machine algorithm. Gaussian coefficients are real, stored values are exact, and decoder workspace is free. A finite-precision version would have to discretize the maps, control rounding in the cutoff, regression, and moment steps, and assign b bits per measurement. The paper pins k and says nothing about b. Rectangular and complex matrices, update time, decode time, and numerical stability are left open.
A footnote states the paper was prepared with GPT-5.6-sol. The proofs are written out in full. Constants are not optimized, and there are no numerical experiments.