Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform
Optimal Iterative Sketching with the Subsampled Randomized Hadamard Transform
复制标题
使用子采样随机 Hadamard 变换进行最优迭代草图绘制
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Mert Pilanci
中科院分区：
文献类型：
--
作者：
Jonathan Lacotte;Sifan Liu;Edgar Dobriban;Mert Pilanci
随机投影或草图广泛用于许多算法和学习环境中。在这里，我们研究的性能迭代海森素描最小二乘问题。通过利用和扩展随机矩阵理论的最新结果，对用子采样随机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.
使用随机投影的最小二乘法的下界和近乎最优收缩估计器
DOI：
10.1109/jsait.2020.3039509
发表时间：
2020
期刊：
IEEE Journal on Selected Areas in Information Theory
影响因子：
--
作者：
Sridhar, Srivatsan;Pilanci, Mert;Ozgur, Ayfer
通讯作者：
Ozgur, Ayfer
DOI：
10.1098/rspb.1996.0104
发表时间：
1996-06-22
影响因子：
4.7
作者：
Boomsma, JJ
通讯作者：
Boomsma, JJ
DOI：
--
发表时间：
2020
期刊：
International conference on machine learning
影响因子：
--
作者：
Lacotte, Jonathan;Pilanci, Mert
通讯作者：
Pilanci, Mert