EUVIMEDEUVIMED entdecken
Crossref

Sparsity-Dimension Trade-Offs for Oblivious Subspace Embeddings

Yi Li, Mingmou Liu

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →