Preserving Extreme Singular Values with One Oblivious Sketch
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911268835688448 |
|---|---|
| author | Mango, John M. Katende, Ronald |
| author_facet | Mango, John M. Katende, Ronald |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_12802 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Preserving Extreme Singular Values with One Oblivious Sketch Mango, John M. Katende, Ronald Numerical Analysis Data Structures and Algorithms 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. |
| title | Preserving Extreme Singular Values with One Oblivious Sketch |
| topic | Numerical Analysis Data Structures and Algorithms |
| url | https://arxiv.org/abs/2511.12802 |