Residual Cancellation and Sharp Data-Selection Bounds for Least Squares

How sparsely can one retrain minimum-norm least squares without greatly increasing the full empirical objective? Let $R_d(n)$ be worst-case loss inflation for feature rank $d$ and weighted budget $n$. Prior work resolved only the rank budget and exact recovery at twice the rank, leaving the intermediate regime open and conjecturing the case one point short of exact recovery. On the effective feature span, whitening valid for spanning selections reveals an orthogonal split between failure to span and failure to cancel signed residual vectors. Orthogonal regular-simplex blocks give an explicit lower frontier. We prove the exact global frontier in the upper half: $R_d(n)=(3d-n)/d$ for $\lceil3d/2\rceil\leq n\leq2d$, settling that conjecture. The proof locks positive residual circuits: each rank-at-least-two circuit costs one extra point while removing at least two dimensions; the irreducible case comprises mutually orthogonal rank-one components. This decomposition suggests SpanCancel, a post-fit coreset search with a certifying LP branch and an explicitly heuristic fallback. On random-feature regression through effective rank $201$, the LP branch numerically certifies recovery of the full-data optimizer at every reported budget above the rank. The result connects sparse objective preservation, experimental design, and optimization-aware data selection.