新的求解大规模线性最小二乘问题的随机算法
|
摘要
目的针对传统的求解线性最小二乘问题方法的计算、存储复杂度大,不适于大规模问题的缺点,提出新的随机算法近似求解大规模线性最小二乘问题。方法通过随机采样对超大规模线性最小二乘问题的系数矩阵进行约减,利用快速Walsh-Hadamard对问题进行变换来保留原问题的重要信息,再用QR分解算法求解约减问题,得到原问题的近似解。结果该方法有效降低了问题的求解复杂度和存储复杂度。结论数值实验表明新算法和相关算法相比求解精度可接受,但大大减少求解时间且在同等计算平台下可处理更大规模的问题。
Objective—To propose a new random algorithm for solving the very large-scale linear least squares problems because some state-of-art methods for the least squares problems are not suitable for solving very large-scale problems except that the computational complexity and the memory complexity are very high.Methods—The coefficients matrix of the very large-scale least squares problems is reduced by random sampling;then the resulted matrix is transformed with the fast WalshHadamard to save the important information as soon as possible;at last,the reduced problem is solved by QR decomposition to obtain the approximated solution of the original problem.Results—The computational complicity and the memory cost of the new algorithm are less than the related algorithms.Conclusion—The numerical experiments show that the new algorithm is efficient to save the training time with comparable approximated solution,and the new algorithm can solve larger size of problems with the same computing platform.
Objective—To propose a new random algorithm for solving the very large-scale linear least squares problems because some state-of-art methods for the least squares problems are not suitable for solving very large-scale problems except that the computational complexity and the memory complexity are very high.Methods—The coefficients matrix of the very large-scale least squares problems is reduced by random sampling;then the resulted matrix is transformed with the fast WalshHadamard to save the important information as soon as possible;at last,the reduced problem is solved by QR decomposition to obtain the approximated solution of the original problem.Results—The computational complicity and the memory cost of the new algorithm are less than the related algorithms.Conclusion—The numerical experiments show that the new algorithm is efficient to save the training time with comparable approximated solution,and the new algorithm can solve larger size of problems with the same computing platform.
引文
[1]GOLUB G H,VANLOAN C F.Matrix Computations[M].Baltimore:Johns Hopkins University Press,1996.
[2]DRINEAS P,MAHONEY M W,MUTHUKRISHNAN S,et al.Faster least squares approximation[J].Numerische Mathematik,2011,117(2):219-249.
[3]AVRON H,MAYMOUNKOV P,TOLEDO S.Blendenpik:Supercharging LAPACK's least-squares solver[J].SIAM Journal on Scientific Computing,2010,32(3):1217-1236.
[4]胡善瑞,王明辉,田保光.一类矩阵方程最小二乘问题的LSQR方法[J].枣庄学院学报,2011,28(2):52-56.
[5]ROKHLIN V,TYGERT M.A fast randomized algorithm for over determined linear least-squares regression[J].Proceedings of the National Academy of Sciences,2008,105(36):13212-13217.
[6]贺红,马绍汉.随机算法的一般性原理[J].计算机科学,2002,29(1):90-92.
[7]BOUTSIDIS C,DRINEAS P.Random projections for the nonnegative least-squares problem[J].Linear Algebra and its Applications,2009,431(5):760-771.
[8]李鹏程.新的求解超大规模最小二乘问题的随机算法[D].西安:西安电子科技大学,2013.
[9]NOCEDAL J,WRIGHT S J.Numerical Optimization[M].New York:Springer,2006.
[2]DRINEAS P,MAHONEY M W,MUTHUKRISHNAN S,et al.Faster least squares approximation[J].Numerische Mathematik,2011,117(2):219-249.
[3]AVRON H,MAYMOUNKOV P,TOLEDO S.Blendenpik:Supercharging LAPACK's least-squares solver[J].SIAM Journal on Scientific Computing,2010,32(3):1217-1236.
[4]胡善瑞,王明辉,田保光.一类矩阵方程最小二乘问题的LSQR方法[J].枣庄学院学报,2011,28(2):52-56.
[5]ROKHLIN V,TYGERT M.A fast randomized algorithm for over determined linear least-squares regression[J].Proceedings of the National Academy of Sciences,2008,105(36):13212-13217.
[6]贺红,马绍汉.随机算法的一般性原理[J].计算机科学,2002,29(1):90-92.
[7]BOUTSIDIS C,DRINEAS P.Random projections for the nonnegative least-squares problem[J].Linear Algebra and its Applications,2009,431(5):760-771.
[8]李鹏程.新的求解超大规模最小二乘问题的随机算法[D].西安:西安电子科技大学,2013.
[9]NOCEDAL J,WRIGHT S J.Numerical Optimization[M].New York:Springer,2006.