2026-07-23T13:58:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23432 2025-10-02T12:54:58Z ddc:004 open_access

Optimal Oblivious Subspace Embeddings with Near-Optimal Sparsity Chenakkod, Shabarish Dereziński, Michał Dong, Xiaoyu Randomized linear algebra matrix sketching subspace embeddings An oblivious subspace embedding is a random m× n matrix Π such that, for any d-dimensional subspace, with high probability Π preserves the norms of all vectors in that subspace within a 1±ε factor. In this work, we give an oblivious subspace embedding with the optimal dimension m = Θ(d/ε²) that has a near-optimal sparsity of Õ(1/ε) non-zero entries per column of Π. This is the first result to nearly match the conjecture of Nelson and Nguyen [FOCS 2013] in terms of the best sparsity attainable by an optimal oblivious subspace embedding, improving on a prior bound of Õ(1/ε⁶) non-zeros per column [Chenakkod et al., STOC 2024]. We further extend our approach to the non-oblivious setting, proposing a new family of Leverage Score Sparsified embeddings with Independent Columns, which yield faster runtimes for matrix approximation and regression tasks. In our analysis, we develop a new method which uses a decoupling argument together with the cumulant method for bounding the edge universality error of isotropic random matrices. To achieve near-optimal sparsity, we combine this general-purpose approach with new trace inequalities that leverage the specific structure of our subspace embedding construction. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shabarish Chenakkod and Michał Dereziński and Xiaoyu Dong 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.55 urn:nbn:de:0030-drops-234324 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.55 eng https://creativecommons.org/licenses/by/4.0/legalcode