The Precision Wall: An Optimizer-Dependent Boundary for Optimization under Power-Law Measurement Spectra

In low-rank matrix sensing of a rank-$D$ factor U^\ast \in R^V × D, replacing isotropic Gaussian designs with power-law measurement covariance Σ= diag(j^-s)_j=1^V leaves the Burer--Monteiro landscape free of spurious local minima, yet division-normalised first-order optimizers stall above a critical exponent s^\ast. We trace this failure to a numerical precision wall. At the ground truth, the smallest non-gauge expected Hessian eigenvalue scales at leading order as V^-(s+1)D^-s. When this curvature drops below the effective denominator floor ε_O of optimizer $O$, normalisation noise overwhelms rare-direction gradients, yielding the leading-order boundary s^\ast_O(V, D) = [\log(1/ε_O) - \log V]/\log(VD) + δ_O, where δ_O is a metric-dependent detection lag. With δ_Adam calibrated on four configurations and frozen, this formula predicts Adam's onset within $0.45$ across all 16 cells of a held-out grid (V \in \64,128,256,512\ × D \in \4,8,16,32\), separates fixed-$VD$ pairs, and distinguishes denominator-precision walls from conditioning and sign-quantisation walls. The approximation fails at $D = 2$, reflects a finite-$D$ spectral crossover, and saturates below \varepsilon_0 = 10^-8 at a dynamical floor.