当今世界,随着科技的发展,数据量爆炸性增长。一方面是生活产生的数据增加,一方面是数据处理是会使数据维度增加。比如,在购物系统中,若是商品种类中有一万种不同的物品,经过独热编码后将变成一万多种特征。大量的数据,大量的特征一方面,使得大规模模型的算法有了更好的精度,神经网络机器学习等依托于大量的数据在处理各种问题中展现了其优越性,但是另一方面,也对算法有了更多的要求。过大的数据量使得模型训练变得及其缓慢,读取数据需要占据太大的空间,这种情形对设备性能要求过高。此外,对于过大的数据,传统算法也难以发挥其性能。基于这种考虑,人们通过降维来压缩数据,希望能在保留有用信息的同时,无用的信息被舍弃,即将数据映射为低维空间,从而在低维空间中可以更快地求解问题。本文中主要考虑求解回归问题。回归问题是最常见,基础的问题,文中主要考虑了最小二乘回归问题和岭回归问题。最小二乘回归是最常见的数据拟合方法,在满足一定条件下其是对数据的无偏估计。然而最小二乘回归方法对异常值敏感,且当特征完全共线性或者相关性很高时,无法求解或者效果很差。相比之下,带二范数惩罚项的线性回归问题通过放弃最小二乘的无偏性,提高了模型的稳定性,更符合实际的情况,最小二乘为特殊情况下的岭回归问题,即正则参数为零时。本文应用随机算法加速求解岭回归问题,着重考虑具有对角块性质的SRHT。随机算法通过如随机抽样,随机嵌入等方式进行数据降维,相比确定性算法在一定程度上损失了无偏性,同时具有更快的速度优势。但是诸如SRHT,高斯嵌入等由于需要访问所有数据,故而不便于分布式和并行化程序设计。具有对角块的随机嵌入由于其特殊的结构,可以并行进行变换操作,所以在计算上有着更快的优势,但是与此同时需要更大的嵌入维度才能保证精度。考虑到其在计算速度方面的优越性,本文探讨其在岭回归问题中的应用。SRHT的一种理解为均匀化数据的重要性,然后再均匀抽样。而块对角的SRHT只在部分数据中进行变换,使得数据在块中在一定程度上均衡,但是块和块之间的信息可能会有很大的差别,故而块对角的随机草图往往需要更大的嵌入维度,我们针对该问题,通过非均匀抽样来提高其嵌入性能。