跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.12867 · v1

Optimal Injectivity of the SparseStack

SparseStack 的最优单侧注入性

首次提交 2026-11-10 02:53
版本更新 2026-11-10 02:53
雷达观测 2026-11-10 15:22
arXiv ↗PDF ↗

摘要

An Oblivious Subspace Injection (OSI) is a random sketching matrix that reliably preserves the minimum singular value of any fixed subspace with high constant probability, requiring only a one-sided spectral lower bound without controlling upper singular values. While classical Oblivious Subspace Embeddings (OSEs) fundamentally require row sparsity Ω(log⁡r)Ω(\log r) at linear sketch dimension k=O(r)k = O(r), we show that one-sided injectivity permits strictly sparser sketches, establishing matching (up to log⁡log⁡r\log\log r factors) upper and lower bounds of Θ~(log⁡r)\tildeΘ(\sqrt{\log r}). First, we prove that the SparseStack sketch achieves constant injectivity at linear dimension k=Θ(r)k = Θ(r) with row sparsity only ζ=O(log⁡r)ζ= O(\sqrt{\log r}), well below the Θ(log⁡r)Θ(\log r) barrier where standard operator-norm concentration fails. Second, we establish a matching lower bound: any isotropic random sketching matrix satisfying a mild row-overlap condition requires row sparsity ζ=Ω(log⁡r/log⁡log⁡r)ζ= Ω(\sqrt{\log r / \log \log r}) to achieve linear-dimension injectivity, confirming that the log⁡r\sqrt{\log r} scale is fundamental. To bypass the lack of an operator-norm upper bound when ζ=O(log⁡r)ζ= O(\sqrt{\log r}), we decouple the sketch into two independent halves and introduce three techniques: (i) a uniform lower bound for flat vectors via randomized rounding, controlling discretization error using solely the Frobenius norm; (ii) a Gaussian truncation and minimax duality argument showing that all non-flat vectors escaping injectivity in the first half concentrate on a single universal coordinate subset I⊆[n]I \subseteq [n] of size O(r/ζ)O(r/ζ), bypassing union bounds over supports; and (iii) a two-tier coordinate isolation analysis in the second half that suppresses collisions to e−Ω(ζ2)≪1/re^{-Ω(ζ^2)} \ll 1/r, reliably preserving these heavy coordinates.

AI 论文解读

基于摘要 · 非全文审阅

作者证明 SparseStack 草图在行稀疏度约 √log r 时即可实现线性维度的单侧子空间注入,并给出匹配下界,说明该尺度是本质的。

正在读取账号与研究记录…

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-10 02:53 · 最新观测版本

Optimal Injectivity of the SparseStack

An Oblivious Subspace Injection (OSI) is a random sketching matrix that reliably preserves the minimum singular value of any fixed subspace with high constant probability, requiring only a one-sided spectral lower bound without controlling upper singular values. While classical Oblivious Subspace Embeddings (OSEs) fundamentally require row sparsity Ω(log⁡r)Ω(\log r) at linear sketch dimension k=O(r)k = O(r), we show that one-sided injectivity permits strictly sparser sketches, establishing matching (up to log⁡log⁡r\log\log r factors) upper and lower bounds of Θ~(log⁡r)\tildeΘ(\sqrt{\log r}). First, we prove that the SparseStack sketch achieves constant injectivity at linear dimension k=Θ(r)k = Θ(r) with row sparsity only ζ=O(log⁡r)ζ= O(\sqrt{\log r}), well below the Θ(log⁡r)Θ(\log r) barrier where standard operator-norm concentration fails. Second, we establish a matching lower bound: any isotropic random sketching matrix satisfying a mild row-overlap condition requires row sparsity ζ=Ω(log⁡r/log⁡log⁡r)ζ= Ω(\sqrt{\log r / \log \log r}) to achieve linear-dimension injectivity, confirming that the log⁡r\sqrt{\log r} scale is fundamental. To bypass the lack of an operator-norm upper bound when ζ=O(log⁡r)ζ= O(\sqrt{\log r}), we decouple the sketch into two independent halves and introduce three techniques: (i) a uniform lower bound for flat vectors via randomized rounding, controlling discretization error using solely the Frobenius norm; (ii) a Gaussian truncation and minimax duality argument showing that all non-flat vectors escaping injectivity in the first half concentrate on a single universal coordinate subset I⊆[n]I \subseteq [n] of size O(r/ζ)O(r/ζ), bypassing union bounds over supports; and (iii) a two-tier coordinate isolation analysis in the second half that suppresses collisions to e−Ω(ζ2)≪1/re^{-Ω(ζ^2)} \ll 1/r, reliably preserving these heavy coordinates.

查看此版本解读 →查看此版本原文 ↗