标题： 一种高性能GPU CountSketch实现及其在Multisketching和最小二乘问题中的应用 显示英文标题

标题： A High Performance GPU CountSketch Implementation and Its Application to Multisketching and Least Squares Problems

摘要： 随机投影是一种降维技术，它在高概率下大约保留范数和奇异值，最多有$O(1)$的失真因子。 文献中最流行的投影是高斯投影和子采样随机哈达玛变换，而 CountSketch 具有较低的复杂度。 结合两个投影，称为多投影，提供了一种通过结合 CountSketch 和高斯投影快速降低矩阵维度的经济方法。 然而，关于高性能 CountSketch 实现的研究很少。 在这项工作中，我们开发了 CountSketch 的高效 GPU 实现，并使用该技术展示了多投影的性能。 我们还展示了在多投影最小二乘求解器中使用此实现的潜力，其速度比正则方程快$77\%$倍，且数值稳定性显著提高，代价是相对残差范数中引入了一个$O(1)$的乘法因子。 显示英文摘要

摘要： Random sketching is a dimensionality reduction technique that approximately preserves norms and singular values up to some $O(1)$ distortion factor with high probability. The most popular sketches in literature are the Gaussian sketch and the subsampled randomized Hadamard transform, while the CountSketch has lower complexity. Combining two sketches, known as multisketching, offers an inexpensive means of quickly reducing the dimension of a matrix by combining a CountSketch and Gaussian sketch. However, there has been little investigation into high performance CountSketch implementations. In this work, we develop an efficient GPU implementation of the CountSketch, and demonstrate the performance of multisketching using this technique. We also demonstrate the potential for using this implementation within a multisketched least squares solver that is up to $77\%$ faster than the normal equations with significantly better numerical stability, at the cost of an $O(1)$ multiplicative factor introduced into the relative residual norm.