← 研踪 PaperTrailarXiv:2611.12867 · v1
Optimal Injectivity of the SparseStack
SparseStack 的最优单侧注入性
首次提交 2026-11-10 02:53
版本更新 2026-11-10 02:53
雷达观测 2026-11-10 15:22
摘要
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 at linear sketch dimension , we show that one-sided injectivity permits strictly sparser sketches, establishing matching (up to factors) upper and lower bounds of . First, we prove that the SparseStack sketch achieves constant injectivity at linear dimension with row sparsity only , well below the 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 to achieve linear-dimension injectivity, confirming that the scale is fundamental. To bypass the lack of an operator-norm upper bound when , 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 of size , bypassing union bounds over supports; and (iii) a two-tier coordinate isolation analysis in the second half that suppresses collisions to , reliably preserving these heavy coordinates.
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 at linear sketch dimension , we show that one-sided injectivity permits strictly sparser sketches, establishing matching (up to factors) upper and lower bounds of . First, we prove that the SparseStack sketch achieves constant injectivity at linear dimension with row sparsity only , well below the 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 to achieve linear-dimension injectivity, confirming that the scale is fundamental. To bypass the lack of an operator-norm upper bound when , 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 of size , bypassing union bounds over supports; and (iii) a two-tier coordinate isolation analysis in the second half that suppresses collisions to , reliably preserving these heavy coordinates.
查看此版本解读 →查看此版本原文 ↗