最小二乘法是误差拟合、模型估计的常用方法，在科学技术领域有广泛的应用．对于超大规模的最小二乘问题，在通常情况下得不到精确解，而利用传统的矩阵分解方法在规模增大的情况下会大大增加求解时间和空间复杂度．随着随机算法的不断成熟以及它所具有的简单快速的优点，为不精确求解最小二乘问题提供了一种有效方法．本文主要介绍了一种新的随机算法求解最小二乘问题．　　一方面，本文首先介绍了求解最小二乘问题的随机投影算法——Blendenpik算法及其在求解过程中表现出来的优势，并指出其不能求解超大规模最小二乘问题的缺点．进一步对此算法进行改进并提出通过对超大规模矩阵的行进行随机采样，为了改进矩阵的一致性，通过快速walsh-Hadamard变换对采样后矩阵进行变换，将矩阵的维数降低，最后，对新得到的最小二乘问题利用QR分解进行求解．　　另一方面，本文证明了新算法得到的解满足误差边界，以及解的收敛性问题，并分析算法求解需要的时间和空间复杂度．最后，通过数值试验表明随机采样算法相比与 Blendenpik算法和QR分解算法在求解时间上要小，并且在计算机内存限制的情况下新算法比Blendenpik算法和QR分解求解的规模要大．