Krylov低秩子空间的随机草图算法
Random Sketch Algorithm for Krylov Low-Rank Subspaces
DOI: 10.12677/aam.2026.1511446, PDF,   
作者: 旷 荣:成都理工大学数学科学学院,四川 成都
关键词: Krylov子空间;随机草图;IRN;Krylov Subspace; Random Sketch; IRN
摘要: 大规模线性反问题广泛应用于医学成像、图像去模糊以及遥感探测等领域。近年来,核范数正则化方法(NNR)近年来被广泛应用于低秩矩阵恢复及大规模线性逆问题求解中。然而,对于高维问题,由于系统矩阵规模巨大以及核范数正则化所引入的迭代权更新过程,传统迭代重加权核范数方法仍面临较高的计算成本。为有效求解此类问题,已有研究结合Krylov子空间迭代方法提出了IRN-GMRES-NNRp方法,通过在每次外层迭代中构造加权线性系统,并利用GMRES方法求解相应子问题,从而避免直接求解大规模正则化系统。然而,在大规模场景下,IRN-GMRES-NNRp中Arnoldi过程涉及的大量Krylov基向量存储、正交化以及残差计算仍然成为限制算法效率的主要因素。针对上述问题,本文提出一种基于随机草图技术的加IRN-GMRES-NNR方法(SINR-GMRES-NNRp)。通过引入随机草图矩阵对Krylov子空间进行压缩,降低因为正交化和基向量存储所带来的负担从而有效地提升算法效率。数值实验表明,与原始IRN-GMRES-NNR方法相比,所提出方法能够有效降低计算时间和存储需求,同时保持相近的恢复精度和收敛性能,验证了随机草图技术在大规模低秩矩阵恢复问题中的有效性。
Abstract: Large-scale linear inverse problems are widely applied in fields such as medical imaging, image deblurring, and remote sensing. In recent years, nuclear norm regularization (NNR) methods have been extensively used for low-rank matrix recovery and the solution of large-scale linear inverse problems. However, for high-dimensional problems, due to the enormous size of the system matrix and the iterative weight-update process introduced by nuclear norm regularization, traditional iterative reweighted nuclear norm methods still face high computational costs. To effectively solve such problems, previous research has combined Krylov subspace iterative methods to propose the IRN-GMRES-NNRp method, which constructs a weighted linear system at each outer iteration and uses the GMRES method to solve the corresponding subproblems, thereby avoiding the direct solution of large-scale regularized systems. Nevertheless, in large-scale scenarios, the Arnoldi process in IRN-GMRES-NNRp involves substantial storage, orthogonalization, and residual computation of Krylov basis vectors, which remain the main factors limiting algorithm efficiency. To address these issues, this paper proposes a random sketching-based IRN-GMRES-NNR method (SINR-GMRES-NNRp). By introducing a random sketching matrix to compress the Krylov subspace, the burden caused by orthogonalization and basis vector storage is reduced, effectively improving algorithmic efficiency. Numerical experiments show that, compared with the original IRN-GMRES-NNR method, the proposed method can significantly reduce computation time and storage requirements while maintaining similar recovery accuracy and convergence performance, verifying the effectiveness of random sketching technology in large-scale low-rank matrix recovery problems.
文章引用:旷荣. Krylov低秩子空间的随机草图算法[J]. 应用数学进展, 2026, 15(11): 236-247. https://doi.org/10.12677/aam.2026.1511446

参考文献

[1] Gazzola, S., Meng, C. and Nagy, J.G. (2020) Krylov Methods for Low-Rank Regularization. SIAM Journal on Matrix Analysis and Applications, 41, 1477-1504.
https://doi.org/10.1137/19m1302727
[2] Fazel, M., Hindi, H. and Boyd, S.P. (2001). A Rank Minimization Heuristic with Application to Minimum Order System Approximation. Proceedings of the 2001 American Control Conference (Cat. No.01CH37148), 25-27 June 2001, Arlington, 4734-4739.
https://doi.org/10.1109/acc.2001.945730
[3] Recht, B., Fazel, M. and Parrilo, P.A. (2010) Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization. SIAM Review, 52, 471-501.
https://doi.org/10.1137/070697835
[4] Candès, E. and Recht, B. (2012) Exact Matrix Completion via Convex Optimization. Communications of the ACM, 55, 111-119.
https://doi.org/10.1145/2184319.2184343
[5] Cai, J., Candès, E.J. and Shen, Z. (2010) A Singular Value Thresholding Algorithm for Matrix Completion. SIAM Journal on Optimization, 20, 1956-1982.
https://doi.org/10.1137/080738970
[6] Fornasier, M., Rauhut, H. and Ward, R. (2011) Low-Rank Matrix Recovery via Iteratively Reweighted Least Squares Minimization. SIAM Journal on Optimization, 21, 1614-1640.
https://doi.org/10.1137/100811404
[7] Mohan, K. and Fazel, M. (2012) Iterative Reweighted Algorithms for Matrix Rank Minimization. The Journal of Machine Learning Research, 13, 3441-3473.
[8] Gu, S., Zhang, L., Zuo, W. and Feng, X. (2014) Weighted Nuclear Norm Minimization with Application to Image Denoising. 2014 IEEE Conference on Computer Vision and Pattern Recognition, Columbus, 23-28 June 2014, 2862-2869.
https://doi.org/10.1109/cvpr.2014.366
[9] Lu, C.Y., Lin, Z.C. and Yan, S.C. (2015) Smoothed Low Rank and Sparse Matrix Recovery by Iteratively Reweighted Least Squares Minimization. IEEE Transactions on Image Processing, 24, 646-654.
https://doi.org/10.1109/tip.2014.2380155
[10] Lu, C., Tang, J., Yan, S. and Lin, Z. (2014). Generalized Nonconvex Nonsmooth Low-Rank Minimization. 2014 IEEE Conference on Computer Vision and Pattern Recognition, Columbus, 23-28 June 2014, 4130-4137.
https://doi.org/10.1109/cvpr.2014.526
[11] Lu, C., Tang, J., Yan, S. and Lin, Z. (2016) Nonconvex Nonsmooth Low Rank Minimization via Iteratively Reweighted Nuclear Norm. IEEE Transactions on Image Processing, 25, 829-839.
https://doi.org/10.1109/tip.2015.2511584
[12] Wang, H., Wang, Y. and Yang, X. (2024) Efficient Active Manifold Identification via Accelerated Iteratively Reweighted Nuclear Norm Minimization. Journal of Machine Learning Research, 25, 1-44.
[13] Wang, Y., Zhang, Y. and Fu, X. (2023) Low-Rank Matrix Recovery via Novel Double Nonconvex Nonsmooth Rank Minimization with ADMM. Multimedia Tools and Applications, 83, 15547-15564.
https://doi.org/10.1007/s11042-023-16098-y
[14] Boyd, S., Parikh, N., Chu, E., Peleato, B. and Eckstein, J. (2011) Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. Foundations and Trends® in Machine Learning, 3, 1-122.
https://doi.org/10.1561/2200000016
[15] Mohan, K. and Fazel, M. (2010) Iterative Reweighted Least Squares for Matrix Rank Minimization. 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton), Monticello, 29 September-1 October 2020, 653-661.
https://doi.org/10.1109/allerton.2010.5706969
[16] Ge, Z., Zhang, X. and Wu, Z. (2022) A Fast Proximal Iteratively Reweighted Nuclear Norm Algorithm for Nonconvex Low-Rank Matrix Minimization Problems. Applied Numerical Mathematics, 179, 66-86.
https://doi.org/10.1016/j.apnum.2022.04.008
[17] Saad, Y. (2003) Iterative Methods for Sparse Linear Systems. Society for Industrial and Applied Mathematics.
[18] Saad, Y. and Schultz, M.H. (1986) GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems. SIAM Journal on Scientific and Statistical Computing, 7, 856-869.
https://doi.org/10.1137/0907058
[19] Lee, K. and Elman, H.C. (2017) A Preconditioned Low-Rank Projection Method with a Rank-Reduction Scheme for Stochastic Partial Differential Equations. SIAM Journal on Scientific Computing, 39, S828-S850.
https://doi.org/10.1137/16m1075582
[20] Renaut, R.A., Vatankhah, S. and Ardestani, V.E. (2017) Hybrid and Iteratively Reweighted Regularization by Unbiased Predictive Risk and Weighted GCV for Projected Systems. SIAM Journal on Scientific Computing, 39, B221-B243.
https://doi.org/10.1137/15m1037925
[21] Rodríguez, P. and Wohlberg, B. (2008) An Efficient Algorithm for Sparse Representations with ℓp Data Fidelity Term. Proceedings of 4th IEEE Andean Technical Conference (ANDESCON), Cusco, October 2008.
[22] Burke, L., Carson, E. and Ma, Y. (2025) On the Numerical Stability of Sketched GMRES. arXiv: 2503.19086.
[23] Landman, M.S. and Nakatsukasa, Y. (2025) Randomized Flexible Krylov Methods for ℓp Regularization. arXiv: 2510.11237.
[24] Burke, L., Güttel, S. and Soodhalter, K.M. (2025) GMRES with Randomized Sketching and Deflated Restarting. SIAM Journal on Matrix Analysis and Applications, 46, 702-725.
https://doi.org/10.1137/23m1619472
[25] Palitta, D. and Pasha, M. (2026) A Sketched Generalized Krylov Subspace Method for Large-Scale Regularization. arXiv: 2606.18073.