论文标题
使用子采样的随机hadamard变换，最佳迭代素描
Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform
论文作者
论文摘要
随机预测或素描被广泛用于许多算法和学习环境中。在这里，我们研究了迭代性黑森州草图的性能，以解决最小二乘问题。通过利用并扩展了随机矩阵理论的最新结果，这些矩阵的限制光谱随机采样了随机采样的随机hadamard变换和截断的HAAR矩阵，我们可以研究并将所得算法与以前无法进行的精确度进行比较。我们的技术贡献包括预计矩阵倒数第二时的新公式。我们还发现渐近最佳步骤尺寸和收敛速率的简单闭合表达式。这些表明，HAAR和随机Hadamard矩阵的收敛速率是相同的，并且在高斯随机投影上渐近改善。这些技术可以应用于采用随机减小的其他算法。
Random projections or sketching are widely used in many algorithmic and learning contexts. Here we study the performance of iterative Hessian sketch for least-squares problems. By leveraging and extending recent results from random matrix theory on the limiting spectrum of matrices randomly projected with the subsampled randomized Hadamard transform, and truncated Haar matrices, we can study and compare the resulting algorithms to a level of precision that has not been possible before. Our technical contributions include a novel formula for the second moment of the inverse of projected matrices. We also find simple closed-form expressions for asymptotically optimal step-sizes and convergence rates. These show that the convergence rate for Haar and randomized Hadamard matrices are identical, and asymptotically improve upon Gaussian random projections. These techniques may be applied to other algorithms that employ randomized dimension reduction.
