用复数变量改进张量压缩，降低误差且保持高效。
Improving TensorSketch Using Complex Random Variables
- 引入复数随机变量优化稀疏张量压缩算法
- 方差随次数增长从3^p/D降至2^p/D
- 适合处理高维稀疏数据的机器学习任务
TensorSketch 通过高效压缩高维多项式核（如 ℝ^{d^p}）实现快速计算。现有方法中，密集型 Johnson-Lindenstrauss 投影成本为 $O(pDd)$，而稀疏型 CountSketch 算法在稀疏输入下更快，运行时间为 $O(p( nz{fx} + D /log D))$。但两者方差均随多项式阶数 $p$ 指数级增长，达 $3^p/D$。最近工作表明，使用复数分布可将方差降至 $2^p/D$，但仅适用于密集投影，无法适配稀疏算法。本文提出一种简单变体，既保留了原稀疏算法的输入稀疏性优势，又达到 $2^p/D$ 的方差边界。实验在合成与真实数据集上验证了有效性。
原文摘要 · Abstract (English)
\texttt{TensorSketch} by~\cite{pham2013fast,kar2012random} provides efficient sketching algorithms for high-dimensional polynomial kernels $\vec{x}^{\otimes p} \in \R^{d^p}$. \cite{kar2012random} uses dense Johnson-Lindenstrauss (JL)-type projections with computational cost $O(pDd)$, where $D$ denotes the sketch dimension, whereas~\cite{pham2013fast} extends the sparse \texttt{CountSketch}~\citep{count_sketch} algorithm, yielding a faster algorithm for high-dimensional sparse inputs with running time $O\big(p(\nnz{\vec{x}} + D \log D)\big)$. However, the variance of both estimators grows exponentially with the polynomial degree $p$, scaling as $3^{p}/D$. Recent work by~\cite{pmlr-v206-wacker23a} showed that using complex-valued distribution reduces this dependence to $2^{p}/D$ for the approach of~\cite{kar2012random}. However, their method relies on dense JL-type projections with computational cost $O(pDd)$ and does not extend to the algorithm of~\cite{pham2013fast}. In this work, we introduce a simple variant of \texttt{TensorSketch}~\citep{pham2013fast} that achieves the same variance bound as~\cite{pmlr-v206-wacker23a}, while retaining its advantage of the input-sparsity running time. We validate our results with supporting experiments on synthetic and real-world datasets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。