arXiv:2411.08773cs.DScs.LG2024-11被引 9

提出近最优稀疏度的随机投影矩阵,高效保持子空间向量范数。

Optimal Oblivious Subspace Embeddings with Near-optimal Sparsity

  • 构造具有近最优每列非零元数的随机嵌入矩阵
  • 实现最优维数 m=Θ(d/ε²) 与近最优稀疏度 Õ(1/ε)
  • 适用于高速矩阵近似与回归任务,适合大规模数据处理

一种无感知子空间嵌入是指一个随机的 m×n 矩阵 Π,使得对于任意 d 维子空间,以高概率 Π 能在 1±ε 因子内保持该子空间中所有向量的范数。本文给出了一个最优维度 m=Θ(d/ε²) 的无感知子空间嵌入,其每列非零元素数量为近最优的 Õ(1/ε)。这是首次在最优嵌入的稀疏度上近乎匹配 Nelson 与 Nguyen(FOCS 2013)的猜想,优于此前 Õ(1/ε⁶) 的界(Chenakkod 等,STOC 2024)。我们进一步将方法扩展至非无感知情形,提出一类独立列的杠杆率稀疏嵌入,显著提升矩阵近似与回归任务的运行效率。分析中引入了新的去耦合与累积量方法,用于界定各向同性随机矩阵的边缘普遍性误差;通过结合针对嵌入构造结构的新迹不等式,实现了近最优稀疏度。

原文摘要 · Abstract (English)

An oblivious subspace embedding is a random $m\times n$ matrix $Π$ such that, for any $d$-dimensional subspace, with high probability $Π$ preserves the norms of all vectors in that subspace within a $1\pmε$ factor. In this work, we give an oblivious subspace embedding with the optimal dimension $m=Θ(d/ε^2)$ that has a near-optimal sparsity of $\tilde O(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 $\tilde O(1/ε^6)$ 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 traces inequalities that leverage the specific structure of our subspace embedding construction.

子空间嵌入稀疏矩阵随机投影矩阵近似

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。