Sparsity-Dimension Trade-Offs for Oblivious Subspace Embeddings
Proceedings of the ACM on Management of Data · 12.05.2026 · 4 (2) · 1-25
DOI: 10.1145/3801912 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the ACM on Management of Data, online erschienen am 14.05.2026. Verfasst von Yi Li und 1 weiteren Autor:innen. Die Arbeit nennt 11 Literaturangaben. Gefördert von: Singapore Ministry of Education, VILLUM Foundation grant, National Natural Science Foundation of China.
Abstract (Originalsprache)
An oblivious subspace embedding (OSE), characterized by parameters m,n,d ,∈,δ, is a random matrix ∏∈ ℝ m x n such that for any d -dimensional subspace T ⊆ ⊏ n , Pr ∏[ [∀ x ∈ T , (1-∈)|| x || 2 ≤(1+∈)|| x || 2 ] ≥(1-δ). When an OSE has s ≤ 1/2.001≬ nonzero entries in each column, we show it must hold that m = Ω( d 2 /(∈ 2 s 1+O(δ )), which is the first lower bound with multiplicative factors of d 2 and 1/∈, improving on the previous Ω( d 2 / s O(δ) ) lower bound due to Li and Liu (PODS 2022). When an OSE has s =Ω(log(1/∈)/∈) nonzero entries in each column, we show it must hold that m = Ω(( d /∈)1+1/4.001∈ s / s O(δ) ), which is the first lower bound with multiplicative factors of d and 1/𘆘, improving on the previous Ω ( d 1+1/(16∈ s +4) ) lower bound due to Nelson and Nguyên (ICALP 2014). This second result is a special case of a more general trade-off among d ,∈, s ,δ and m .
Förderung
- Singapore Ministry of Education
- VILLUM Foundation grant
- National Natural Science Foundation of China
- startup funding from Nanjing University
- Nanjing University “Miaopu Program” Leading Talent Grant
- Fundamental and Interdisciplinary Disciplines Breakthrough Plan of the Ministry of Education of China
Zitieren
APA
Li, Y., & Liu, M. (2026). Sparsity-Dimension Trade-Offs for Oblivious Subspace Embeddings. Proceedings of the ACM on Management of Data, 4(2), 1-25. https://doi.org/10.1145/3801912
Vancouver
Li Y, Liu M. Sparsity-Dimension Trade-Offs for Oblivious Subspace Embeddings. Proceedings of the ACM on Management of Data. 2026;4(2):1-25. doi:10.1145/3801912
BibTeX
@article{Li2026,
author = {Li, Yi and Liu, Mingmou},
title = {Sparsity-Dimension Trade-Offs for Oblivious Subspace Embeddings},
journal = {Proceedings of the ACM on Management of Data},
year = {2026},
volume = {4},
number = {2},
pages = {1--25},
doi = {10.1145/3801912}
}
EUVIMED