A Non-monotone Alternating Newton-Like Directional Method for Low-Rank and Sparse Matrix Compressive Recovery

doi:10.1007/s40305-023-00520-1

Journal of the Operations Research Society of China ›› 2026, Vol. 14 ›› Issue (1): 246-269.doi: 10.1007/s40305-023-00520-1

Previous Articles Next Articles

A Non-monotone Alternating Newton-Like Directional Method for Low-Rank and Sparse Matrix Compressive Recovery

Chuan-Long Wang¹, Qian-Ying Shen¹, Xi-Hong Yan¹, Chao Li²

1 Shanxi Key Laboratory for Intelligent Optimization Computing and Blockchain Technology, College of Mathematics and Statistics, Taiyuan Normal University, Jinzhong 030619, Shanxi, China;
2 The Hong Kong Polytechnic University, Hong Kong, China

Received:2022-05-11 Revised:2023-09-14 Online:2026-03-30 Published:2026-03-16
Contact: Chuan-Long Wang E-mail:clwang1964@163.com
Supported by:
This work was supported by the National Natural Science Foundations of China (Nos.11901424 and 12371381),and the special fund for Science and Technology Innovation Teams of Shanxi Province (No.202204051002018).

Abstract

Abstract: With wide-spread real-world applications, low-rank and sparse matrix recovery, where the concerned matrix with incomplete data is divided into a low-rank part and a sparse part, recently has attracted significant interest. To solve this structured non-convex optimization problem, we propose a non-monotone alternating Newton-like directional method which essentially updates two blocks of variables associated with the low-rank part using a single step of simple line-search along the Newton-like descent directions and another block of variables associated with the sparse part using a nonmonotone search. In particular, the non-monotone search technique helps our method find a better Newton-like descent direction in the next step. Moreover, we prove the global convergence of the proposed algorithm and discuss the iteration number in given precision under some mild conditions. Finally, computational results show the efficiency of the developed algorithm.

Key words: Low-rank and sparse, Matrix compressive recovery, Alternating Newton-like method, Non-monotone search

CLC Number:

90C25

Chuan-Long Wang, Qian-Ying Shen, Xi-Hong Yan, Chao Li. A Non-monotone Alternating Newton-Like Directional Method for Low-Rank and Sparse Matrix Compressive Recovery[J]. Journal of the Operations Research Society of China, 2026, 14(1): 246-269.

TrendMD

References

[1] Candés, E., Li, X.D., Ma, Y., Wright, J.: Robust principal component analysis? J. Assoc. Comput. Mach. 58, 1-37(2011)
[2] Meng, F., Yang, X., Zhou, C.: The augmented Lagrange multipliers method for matrix completion from corrupted samplings with application to mixed Gaussian-impulse noise removal. PLoS One 9, e108125(2014)
[3] Raffenroth, R.C., Toit, P.C.D., Scharf, L.L., Jayasumana, A.P., Nong, R.: Space-time signal processing for distributed pattern detection in sensor networks. IEEE J. Sel. Top. Signal Process 7, 38-49(2013)
[4] Chanderasekaran, V., Sanghavi, S., Parrilo, P.A., Willsky, A.S.: Rank-sparsity incoherence for matrix decomposition. SIAM J. Optim. 21, 572-596(2011)
[5] Wright, J., Ganesh, A., Rao, S., Ma, Y.: Robust principal component analysis: exact recovery of corrupted low-rank matrices via convex optimization. In: Advances in Neural Information Processing Systems (2009)
[6] Hovhabbusyan, V., Panagakis, Y., Parpas, P., Zafeiriou, S.: Fast multilevel algorithms for compressive principal component pursuit. SIAM J. Imaging Sci 12, 624-649(2019)
[7] Netrapalli, P., Niranjan, U.N., Sanghavi, S., Anandkumar, A., Jain, P.: Non-convex robust PCA, 1107-1115(2014)
[8] Gu, Q.Q., Wang, Z.R., Liu, H.: Low-rank and sparse structure pursuit via alternating minimization. J. Mach. Learn. Res. 51, 600-609(2016)
[9] Cai, H.Q., Cai, J.F., Wei, K.: Accelerated alternating projections for robust principal component analysis. J. Mach. Learn. Res. 20, 1-33(2019)
[10] Chen, Y., Jalali, A., Sanghavi, S., Caramanis, C.: Low-rank matrix recovery from errors and erasures. IEEE Trans. Inf. Theory 59, 4324-4337(2011)
[11] Chen, Y.D., Xu, H., Caramanis, C., Sanghavi, S.: Robust matrix completion and corrupted columns. In: Proceedings of the 28th International Conference on International Conference on Machine Learning, pp. 873-880(2011)
[12] Li, C., Wang, C.L., Wang, J.: Convergence analysis of the augmented Lagrange multiplier algorithm for a class of matrix compressive recovery. Appl. Math. Lett. 59, 12-17(2016)
[13] Azghani, M., Esmaeili, A., Behdin, K., Marvasti, F.: Missing low-rank and sparse decomposition based on smoothed nuclear norm. IEEE Trans. Circuits Syst. Video Technol. (2019). https://doi.org/10.1109/TCSVT.2019.2907467
[14] Yi, X.Y., Park, D., Chen, Y.D., Caramanis, C.: Fast algorithms for robust PCA via gradient descent, pp. 4152-4160(2016). arXiv:1605.07784
[15] Wang, Y.X., Lee, C.M., Cheong, L., Toh, K.C.: Practical matrix completion and corruption recovery using proximal alternating robust subspace minimiaztion. Int. J. Comput. Vis. 111, 315-344(2015)
[16] Zhou, T., Tao, D.: GoDec: randomized low-rank and sparse matrix decomposition in noisy case. In: Proceedings of the 28th International Conference on Machine Learning (2011)
[17] Tong, T., Ma, C., Chi, Y.: Accelerating ill-conditioned low-rank matrix estimation via scaled gradient descent. arXiv:2005.08898v2(2020)
[18] Dai, Y.H.: On the nonmonotone line search. J. Optim. Theory Appl. 112, 315-330(2002)
[19] Toint, P.L.: An assessment of non-monotone line search techniques for unconstrained optimization. SIAM J. Sci. Comput. 17, 725-739(1996)
[20] Tanner, J., Wei, K.: Low rank matrix completion by alternating steepest descent methods. Appl. Comput. Harmon. Anal. 40, 417-429(2016)
[21] Recht, B.: A simpler approach to matrix completion. J. Mach. Learn. Res. 12, 3413-3430(2011)

A Non-monotone Alternating Newton-Like Directional Method for Low-Rank and Sparse Matrix Compressive Recovery

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 1

Recommended Articles

Metrics

Comments