新的求解大规模线性最小二乘问题的随机算法* (2014年)

目的 针对传统的求解线性最小二乘问题方法的计算、存储复杂度大，不适于大规模问题的缺点，提出新的随机算法近似求解大规模线性最小二乘问题。方法 通过随机采样对超大规模线性最小二乘问题的系数矩阵进行约减，利用快速Walsh-Hadamard对问题进行变换来保留原问题的重要信息，再用QR分解算法求解约减问题，得到原问题的近似解。结果 该方法有效降低了问题的求解复杂度和存储复杂度。结论数值实验表明新算法和相关算法相比求解精度可接受，但大大减少求解时间且在同等计算平台下可处理更大规模的问题。