Preserving Extreme Singular Values with One Oblivious Sketch

Abstract

We study when a single linear sketch can control the largest and smallest nonzero singular values of every rank-$r$ matrix. Classical oblivious embeddings require $s=\hat{I}˜(r/{\epsilon }^2)$ for $(1\pm \epsilon )$ distortion, but this does not yield constant-factor control of extreme singular values or condition numbers. We formalize a conjecture that $s=O(r\log r)$ suffices for such preservation. On the constructive side, we show that combining a sparse oblivious sketch with a deterministic geometric balancing map produces a sketch whose nonzero singular values collapse to a common scale under bounded condition number and coherence. On the negative side, we prove that any oblivious sketch achieving relative $\epsilon$-accurate singular values for all rank-$r$ matrices must satisfy $s=\hat{I}\text{c◯}((r+\log (1/\hat{I}´))/{\epsilon }^2)$. Numerical experiments on structured matrix families confirm that balancing improves conditioning and accelerates iterative solvers, while coherent or nearly rank-deficient inputs manifest the predicted failure modes.