{"ID":2841126,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2511.12802","arxiv_id":"2511.12802","title":"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=Θ(r/\\varepsilon^{2})$ for $(1\\pm\\varepsilon)$ 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 $\\varepsilon$-accurate singular values for all rank-$r$ matrices must satisfy $s=Ω((r+\\log(1/δ))/\\varepsilon^{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.","short_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=Θ(r/\\varepsilon^{2})$ for $(1\\pm\\varepsilon)$ distortion, but this does not yield constant-factor control of extreme singular values or condition numbers....","url_abs":"https://arxiv.org/abs/2511.12802","url_pdf":"https://arxiv.org/pdf/2511.12802v1","authors":"[\"John M. Mango\",\"Ronald Katende\"]","published":"2025-11-16T22:15:31Z","proceeding":"math.NA","tasks":"[\"math.NA\",\"cs.DS\"]","methods":"[]","has_code":false}