Preserving Extreme Singular Values with One Oblivious Sketch

John M. Mango, Ronald Katende · 2025

Read Preserving Extreme Singular Values with One Oblivious Sketch by John M. Mango, Ronald Katende (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-12802.txt.

Introduction

John M. Mango and Ronald Katende study when one small linear sketch can preserve the extreme singular values of every low-rank matrix. Sketches compress matrices for fast computation, but classical results do not control the extreme singular values. The authors state a conjecture: a sketch with only modestly more rows than the rank should suffice for that stronger preservation task.

On the constructive side, they pair a sparse sketch with a balancing map and show the sketched singular values collapse to a common scale when the input is well conditioned and incoherent. On the negative side, they prove sharper accuracy demands force much larger sketches. Experiments on structured matrix families show balancing improves conditioning and speeds iterative solvers, while coherent or nearly rank-deficient inputs fail as predicted. The paper mixes a conjecture, partial progress, and evidence about its limits.

Catalog record

CREATORJohn M. Mango, Ronald Katende
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE44 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-12802

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Preserving Extreme Singular Values with One Oblivious Sketch John M. Mango, Ronald Katende Abstract We investigate when a single linear sketch can simultaneously control the largest and smallest nonzero singular values of every rank- r r matrix. Classical oblivious subspace embeddings of size s = Θ ⁡ ( r / ε 2 ) s=\Theta(r/\varepsilon^{2}) guarantee ( 1 ± ε ) (1\pm\varepsilon) distortion of all vectors in an r r -dimensional subspace, but they do not provide uniform, constant-factor control of the extreme singular values or the resulting condition numbers. We formalize a Single-Sketch Extreme-Values Conjecture predicting that sketch dimension s = O ⁡ ( r ​ log ⁡ r ) s=O(r\log r) suffices for constant-factor preservation. We take two steps toward this conjecture. On the constructive side, we show that composing a sparse oblivious embedding with a deterministic geometric balancing map in the sketch space yields a sketch S S for which all nonzero singular values of S ​ A SA collapse to a common scale, provided the input matrix has bounded condition number and low coherence. Under these assumptions, the resulting sketch achieves constant-factor control of the extreme singular values and produces a perfectly conditioned representation of the column space. On the negative side, we prove that any oblivious sketch that preserves all nonzero singular values within relative error ε \varepsilon for every rank- r r matrix must satisfy the Johnson–Lindenstrauss type lower bound s = Ω ⁡ ( r + log ⁡ ( 1 / δ ) ε 2 ) , s=\Omega\!\left(\frac{r+\log(1/\delta)}{\varepsilon^{2}}\right), showing that strong, uniform guarantees necessarily require quadratic dependence on 1 / ε 1/\varepsilon . Numerical experiments on structured matrix families (including low-coherence and moderately conditioned inputs) demonstrate that the proposed balancing scheme consistently improves conditioning and accelerates downstream iterative methods, while coherent or nearly rank-deficient matrices exhibit the predicted failure modes. Together, these results clarify the gap between what is conjecturally possible and what is provably necessary for single-sketch extreme-value preservation. Keywords: linear sketching, oblivious subspace embeddings, extreme singular values, condition number, matrix coherence; dimensionality reduction; randomized numerical linear algebra; sparse embeddings; balancing transforms; Johnson–Lindenstrauss lower bounds. MSCcodes: 68W20, 65F35, 65F22, 15A18, 68Q25, 60B20 1 Introduction Approximating the singular spectra of large matrices through small random projections is a central task in numerical linear algebra, data compression, and machine learning. Randomized sketching methods, including oblivious subspace embeddings (OSE) and randomized low-rank approximation, provide strong guarantees for average-case preservation of subspace geometry [ 1 ] . Such sketches typically preserve the norms of all vectors in an r -dimensional subspace up to a factor 1\pm\varepsilon using a dimension s=O(r/\varepsilon^{2}) , while supporting multiplication in input-sparsity time [ 2 , 3 ] . Importance sampling approaches further refine these guarantees by focusing on leverage scores, which sharpen control of directions that dominate the subspace geometry [ 4 ] . These results emphasize global norm preservation or average geometric distortion, but many applications depend critically on the behavior of the extreme singular values. Conditioning, numerical stability, and robustness of downstream computations are all governed by the largest and smallest singular values of a matrix or its sketch. CountSketch-type maps and modern sparse embeddings achieve near-optimal scaling in r and \varepsilon for norm preservation [ 5 , 6 ] , and recent work attains optimal embedding dimension with nearly optimal sparsity [ 7 ] . Advances in conditioned low-rank approximation [ 8 ] , rectangular Johnson–Lindenstrauss transforms [ 9 ] , and robust sketching under spectral decay or coherence constraints [ 10 , 11 ] all highlight regimes in which the largest and smallest singular values become decisive. What remains unclear is whether one can preserve both extremes of the spectrum for every rank r matrix using a single oblivious sketch with only s=O(r\log r) rows. This question motivates the following conjecture. Conjecture (Single Sketch Extreme Values). There exists an oblivious sketching matrix S\in\mathbb{R}^{s\times m} with s=O(r\log r) such that for all rank- r matrices A , c_{1}\,\sigma_{\max}(A)\leq\sigma_{\max}(SA)\leq C_{1}\,\sigma_{\max}(A),\qquad c_{2}\,\sigma_{\min}(A)\leq\sigma_{\min}(SA)\leq C_{2}\,\sigma_{\min}(A), for universal constants c_{i},C_{i}>0 . A positive resolution would extend stable embedding and conditioned low-rank approximation results [ 8 , 9 ] by showing that one small oblivious sketch can preserve the condition number of any rank- r matrix up to constant factors. A negative resolution would expose a fundamental gap between subspace norm preservation and simultaneous control of extreme singular values, strengthening recent impossibility results in adversarial and high-coherence regimes [ 11 , 12 ] . Contributions We address this conjecture through complementary constructive and impossibility results and connect these findings to conditioning and solver performance in scientific computing. 1. Formalization and implications of the conjecture. We formalize the Single Sketch Extreme Values conjecture and clarify its implications for condition number preservation and stability of sketched linear systems. Our analysis shows how a positive resolution would imply uniform constant-factor control of \kappa(SA) for all rank- r matrices and relates this behaviour to recent work on stable JL embeddings, sketch-based preconditioning, and controlled spectral distortion [ 13 ] . 2. Complementary theoretical results in constructive and oblivious regimes. In a constructive setting we introduce a scheme that couples a CountSketch-type transform with a deterministic balancing operator in the sketch space. Under structural conditions such as bounded coherence or a modest spectral gap, which are known to support refined guarantees in modern sketching and randomized numerical linear algebra [ 10 , 14 ] , we prove constant-factor control of all nonzero singular values of the sketched matrix, producing a perfectly conditioned representation. In contrast, in a fully oblivious setting we build an adversarial family of rank- r matrices and show that no sketch with s=O(r\log r) rows can maintain constant-factor control of both the largest and smallest singular values for every matrix in this family. The proof reduces the desired extreme-value control to a standard OSE requirement and then applies sharp adversarial lower bounds [ 11 , 12 ] , giving a clear separation between what can be achieved via data-dependent balancing and what a single oblivious sketch can guarantee. 3. Proof techniques and numerical illustration. We develop concise proofs that highlight the geometric structure underlying both results and complement the theory with numerical experiments. These experiments show how the constructive scheme behaves under varying coherence and spectral profiles and how the impossibility phenomenon manifests on adversarial families. We also observe runtime and stability trends aligned with empirical studies of sketch-based conditioning [ 15 ] , indicating how the proposed balancing operator can be incorporated into iterative solvers and scientific-computing pipelines. This perspective isolates the role of extreme singular values in single-pass sketching, delineates the boundary between data-dependent and fully oblivious constructions, and provides geometric and algorithmic insights relevant to sketched preconditioning and robust numerical linear algebra. 1.1 Preliminaries and related work Let A\in\mathbb{R}^{m\times n} have rank r , and let S\in\mathbb{R}^{s\times m} be a random sketching matrix. A distribution over sketching matrices is an oblivious subspace embedding (OSE) if, with high probability, (1-\varepsilon)\,\|Ax\|_{2}\leq\|SAx\|_{2}\leq(1+\varepsilon)\,\|Ax\|_{2}\quad\text{for all }x\in\mathbb{R}^{n}\text{ with }Ax\in\mathrm{range}(A). Dense Gaussian embeddings provide a first example of such distributions and already achieve optimal dimension up to constants [ 1 ] . Subsampled randomized Hadamard transforms extend this to fast structured maps [ 16 ] , while CountSketch and OSNAP give

Read the complete text