Augmented Lagrangian method for tensor low-rank and sparsity models in multi-dimensional image recovery. (English) Zbl 07909964
Summary: Multi-dimensional images can be viewed as tensors and have often embedded a low-rankness property that can be evaluated by tensor low-rank measures. In this paper, we first introduce a tensor low-rank and sparsity measure and then propose low-rank and sparsity models for tensor completion, tensor robust principal component analysis, and tensor denoising. The resulting tensor recovery models are further solved by the augmented Lagrangian method with a convergence guarantee. And its augmented Lagrangian subproblem is computed by the proximal alternative method, in which each variable has a closed-form solution. Numerical experiments on several multi-dimensional image recovery applications show the superiority of the proposed methods over the state-of-the-art methods in terms of several quantitative quality indices and visual quality.
MSC:
| 94A08 | Image processing (compression, reconstruction, etc.) in information and communication theory |
| 68U10 | Computing methodologies for image processing |
| 65K10 | Numerical optimization and variational techniques |
References:
| [1] | Abov, KD; Foi, A.; Katkovnik, V.; Egiazarian, K., Image Denoising by Sparse 3-D Transform-domain Collaborative Filtering, IEEE Trans. Image Process., 16, 8, 2080-2095, 2007 · doi:10.1109/TIP.2007.901238 |
| [2] | Aharon, M.; Elad, M.; Bruckstein, A., \(K\)-SVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation, IEEE Trans. Signal Process., 54, 11, 4311-4322, 2006 · Zbl 1375.94040 · doi:10.1109/TSP.2006.881199 |
| [3] | Attouch, H.; Bolte, J.; Redont, P.; Soubeyran, A., Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality, Math. Oper. Res., 35, 2, 438-457, 2010 · Zbl 1214.65036 · doi:10.1287/moor.1100.0449 |
| [4] | Caelles, S., Montes, A., Maninis, K.K., Chen, Y., Van Gool, L., Perazzi, F., Pont-Tuset, J.: The 2018 DAVIS Challenge on Video Object Segmentation, (2018) |
| [5] | Cai, J-F; Candès, EJ; Shen, Z., A Singular Value Thresholding Algorithm for Matrix Completion, SIAM J. Optim., 20, 4, 1956-1982, 2010 · Zbl 1201.90155 · doi:10.1137/080738970 |
| [6] | Candès, EJ; Wakin, MB; Boyd, SP, Enhancing Sparsity by Reweighted \(\ell_1\) Minimization, J. Fourier Anal. Appl., 14, 5-6, 877-905, 2008 · Zbl 1176.94014 · doi:10.1007/s00041-008-9045-x |
| [7] | Cao, W.; Wang, Y.; Sun, J.; Meng, D.; Yang, C.; Cichocki, A.; Xu, Z., Total Variation Regularized Tensor RPCA for Background Subtraction from Compressive Measurements, IEEE Trans. Image Process., 25, 9, 4075-4090, 2016 · Zbl 1408.94065 · doi:10.1109/TIP.2016.2579262 |
| [8] | Cao, W.; Wang, Y.; Yang, C.; Chang, X.; Han, Z.; Xu, Z., Folded-concave Penalization Approaches to Tensor Completion, Neurocomputing, 152, 261-273, 2015 · doi:10.1016/j.neucom.2014.10.069 |
| [9] | Carroll, JD; Chang, JJ, Analysis of Individual Differences in Multidimensional Scaling via an N-way Generalization of “Eckart-Young” Decomposition, Psychometrika, 35, 283-319, 1970 · Zbl 0202.19101 · doi:10.1007/BF02310791 |
| [10] | Clarke, FH, Optimization and Nonsmooth Analysis, 1983, New York: John Wiley & Sons Inc, New York · Zbl 0582.49001 |
| [11] | Chang, Y.; Yan, L.; Zhao, XL; Fang, H.; Zhang, Z.; Zhong, S., Weighted Low-rank Tensor Recovery for Hyperspectral Image Restoration, IEEE Trans. Cybern., 50, 11, 4558-4572, 2020 · doi:10.1109/TCYB.2020.2983102 |
| [12] | Donoho, DL, De-noising by Soft-thresholding, IEEE Trans. Inf. Theory, 41, 3, 613-627, 1995 · Zbl 0820.62002 · doi:10.1109/18.382009 |
| [13] | Elad, M.; Aharon, M., Image Denoising via Sparse and Redundant Representations over Learned Dictionaries, IEEE Trans. Image Process., 15, 12, 3736-3745, 2006 · doi:10.1109/TIP.2006.881969 |
| [14] | Girometti, L., Lanza, A., Morigi, S.: Ternary Image Decomposition with Automatic Parameter Selection via Auto- and Cross-correlation. Adv. Comput. Math. 49(1), (2023) · Zbl 1515.94015 |
| [15] | Gandy, S.; Recht, B.; Yamada, I., Tensor Completion and Low-n-rank Tensor Recovery via Convex Optimization, Inverse Probl., 27, 2, 025010, 2011 · Zbl 1211.15036 · doi:10.1088/0266-5611/27/2/025010 |
| [16] | Golbabaee, M., Vandergheynst, P.: Joint Trace/TV Norm Minimization: a New Efficient Approach for Spectral Compressive Imaging. IEEE Int. Conf. Image Process., (2013) |
| [17] | Goldfarb, D.; Qin, Z., Robust Low-rank Tensor Recovery: Models and Algorithms, SIAM J. Matrix Anal. Appl., 35, 1, 225-253, 2014 · Zbl 1296.65086 · doi:10.1137/130905010 |
| [18] | Gong, P., Zhang, C., Lu, Z., Huang, J. Z., Ye, J.: A General Iterative Shrinkage and Thresholding Algorithm for Non-convex Regularized Optimization Problems, In ICML, (2013) |
| [19] | Gu, S., Zhang, L., Zuo, W., Feng, X.: Weighted Nuclear Norm Minimization with Application to Image Denoising, In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, pp. 2862-2869, (2014) |
| [20] | Harshman, RA, Foundations of the PARAFAC Procedure: Models and Conditions for an “explanatory” Multi-modal Factor Analysis, UCLA Working Papers in Phonetics, 16, 1-84, 1970 |
| [21] | Hastad, J., Tensor Rank is NP-complete, J. Algorithms, 11, 644-654, 1990 · Zbl 0716.65043 · doi:10.1016/0196-6774(90)90014-6 |
| [22] | Jiang, TX; Huang, TZ; Zhao, XL; Ji, TY; Deng, LJ, Matrix Factorization for Low-rank Tensor Completion Using Framelet Prior, Inf. Sci., 436-437, 403-417, 2018 · Zbl 1448.15015 · doi:10.1016/j.ins.2018.01.035 |
| [23] | Kilmer, ME; Misha, E.; Braman, K.; Hao, N.; Hoover, RC, Third-order Tensors as Operators on Matrices: A Theoretical and Computational Framework with Applications in Imaging, SIAM J. Matrix Anal. Appl., 34, 1, 148-172, 2013 · Zbl 1269.65044 · doi:10.1137/110837711 |
| [24] | Kolda, TG; Bader, BW, Tensor Decompositions and Applications, SIAM Rev., 51, 3, 455-500, 2009 · Zbl 1173.65029 · doi:10.1137/07070111X |
| [25] | De Lathauwer, L.; De Moor, B.; Vandewalle, J., Computation of the Canonical Decomposition by Means of a Simultaneous Generalized Schur Decomposition, SIAM J. Matrix Anal. Appl., 26, 295-327, 2004 · Zbl 1080.65031 · doi:10.1137/S089547980139786X |
| [26] | Lewis, AS; Sendov, HS, Nonsmooth Analysis of Singular Values, Part II: Appl., Set-Valued Anal., 13, 3, 243-264, 2005 · Zbl 1129.49026 |
| [27] | Li, L.; Huang, W.; Gu, IY-H; Tian, Q., Statistical Modeling of Complex Backgrounds for Foreground Object Detection, IEEE Trans. Image Process., 13, 11, 1459-1472, 2004 · doi:10.1109/TIP.2004.836169 |
| [28] | Li, M.; Li, W.; Xiao, M., Nonconvex Multi-view Subspace Clustering via Simultaneously Learning the Representation Tensor and Affinity Matrix, Inverse Probl., 38, 10, 105008, 2022 · Zbl 07584935 · doi:10.1088/1361-6420/ac8ac5 |
| [29] | Li, Y-F; Shang, K.; Huang, Z-H, Low Tucker Rank Tensor Recovery via ADMM Based on Exact and Inexact Iteratively Reweighted Algorithms, J. Comput. Appl. Math., 331, 64-81, 2018 · Zbl 1377.65066 · doi:10.1016/j.cam.2017.09.029 |
| [30] | Lin, Z., Liu, R., Su, Z.: Linearized Alternating Direction Method with Adaptive Penalty for Low Rank Representation, Adv. Neural Inf. Process. Syst. (NIPS), (2011) |
| [31] | Liu, X.; Bourennane, S.; Fossati, C., Denoising of Hyperspectral Images Using the PARAFAC Model and Statistical Performance Analysis, IEEE Trans. Geosci. Remote Sens., 50, 10, 3717-3724, 2012 · doi:10.1109/TGRS.2012.2187063 |
| [32] | Liu, J.; Musialski, P.; Wonka, P.; Ye, J., Tensor Completion for Estimating Missing Values in Visual Data, IEEE Trans. Pattern Anal. Mach. Intell., 35, 1, 208-220, 2013 · doi:10.1109/TPAMI.2012.39 |
| [33] | Lu, J.; Xu, C.; Hu, Z.; Liu, X.; Jiang, Q.; Meng, D.; Lin, Z., A New Nonlocal Low-rank Regularization Method with Applications to Magnetic Resonance Image Denoising, Inverse Problems, 38, 6, 2022 · Zbl 07525943 · doi:10.1088/1361-6420/ac65ac |
| [34] | Lu, Z.; Zhang, Y., An Augmented Lagrangian Approach for Sparse Principal Component Analysis, Math. Program., 135, 1-2, 149-193, 2012 · Zbl 1263.90093 · doi:10.1007/s10107-011-0452-4 |
| [35] | Lu, C., Zhu, C., Xu, C., Yan, S., Lin, Z.: Generalized Singular Value Thresholding. In Proceedings of the 29th AAAI Conference on Artificial Intelligence, pp. 1805-1811, (2015) |
| [36] | Maggioni, M., Foi, A.: Nonlocal Transform-domain Denoising of Volumetric Data with Groupwise Adaptive Variance Estimation. In SPIE, (2012) |
| [37] | Mohaoui, S., Hakim, A., Raghay, S.: Tensor Completion via Bilevel Minimization with Fixed-point Constraint to Estimate Missing Elements in Noisy Data. Adv. Comput. Math. 47(10), (2021) · Zbl 1468.90096 |
| [38] | Niu, S.; Yu, G.; Ma, J.; Wang, J., Nonlocal Low-rank and Sparse Matrix Decomposition for Spectral CT Reconstruction, Inverse Probl., 34, 2, 024003, 2018 · Zbl 1427.94024 · doi:10.1088/1361-6420/aa942c |
| [39] | Peng, Y., Meng, D., Xu, Z., Gao, C., Yang, Y., Zhang, B.: Decomposable Nonlocal Tensor Dictionary Learning for Multispectral Image Denoising, In CVPR, (2014) |
| [40] | Prater-Bennette, A.; Shen, L.; Tripp, EE, The Proximity Operator of the Log-Sum Penalty, J. Sci. Comput., 93, 3, 67, 2022 · Zbl 1508.90094 · doi:10.1007/s10915-022-02021-4 |
| [41] | Qiu, D.; Bai, M.; Ng, MK; Zhang, X., Nonlocal Robust Tensor Recovery with Nonconvex Regularization, Inverse Probl., 37, 3, 035001, 2021 · Zbl 1464.65039 · doi:10.1088/1361-6420/abd85b |
| [42] | Recht, B.; Fazel, M.; Parrilo, PA, Guaranteed Minimum-rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization, SIAM Rev., 52, 471-501, 2010 · Zbl 1198.90321 · doi:10.1137/070697835 |
| [43] | Renard, N.; Bourennane, S.; Blanc-Talon, J., Denoising and Dimensionality Reduction Using Multilinear Tools for Hyperspectral Images, IEEE Geosci. Remote Sens. Letters, 5, 2, 138-142, 2008 · doi:10.1109/LGRS.2008.915736 |
| [44] | Sidiropoulos, ND; Lathauwer, LD; Fu, X.; Huang, K.; Papalexakis, EE; Faloutsos, C., Tensor Decomposition for Signal Processing and Machine Learning, IEEE Trans. Signal Process., 13, 3551-3582, 2017 · Zbl 1415.94232 · doi:10.1109/TSP.2017.2690524 |
| [45] | Saibaba, A.K., Minster, R., Kilmer, M.E.: Efficient Randomized Tensor-based Algorithms for Function Approximation and Low-rank Kernel Interactions. Adv. Comput. Math. 48(66), (2022) · Zbl 1505.65184 |
| [46] | Tucker, LR, Some Mathematical Notes on Three-mode Factor Analysis, Psychometrika, 31, 279-311, 1966 · doi:10.1007/BF02289464 |
| [47] | Wald, L.: Data Fusion: Definitions and Architectures: Fusion of Images of Different Spatial Resolutions, Presses des IEcole MINES, (2002) |
| [48] | Wang, Z.; Bovik, AC; Sheikh, HR; Simoncelli, EP, Image Quality Assessment: From Error Visibility to Structural Similarity, IEEE Trans. Image Process., 13, 4, 600-612, 2004 · doi:10.1109/TIP.2003.819861 |
| [49] | Xie, Q.; Zhao, Q.; Meng, D.; Xu, Z., Kronecker-basis-representation Based Tensor Sparsity and Its Applications to Tensor Recovery, IEEE Trans. Pattern Anal. Mach. Intell., 40, 8, 1888-1902, 2017 · doi:10.1109/TPAMI.2017.2734888 |
| [50] | Xu, N., Yang, L., Fan, Y., Yue, D., Liang, Y., Yang, J., Huang, T.: Youtube-VOS: A Large-scale Video Object Segmentation Benchmark, (2018) |
| [51] | Yang, Y., Feng, Y.: Half-quadratic Alternating Direction Method of Multipliers for Robust Orthogonal Tensor Approximation. Adv. Comput. Math. 49(24), (2023) · Zbl 1518.90086 |
| [52] | Yasuma, F.; Mitsunaga, T.; Iso, D.; Nayar, SK, Generalized Assorted Pixel Camera: Postcapture Control of Resolution, Dynamic Range, and Spectrum, IEEE Trans. Image Process., 19, 9, 2241-2253, 2010 · Zbl 1371.94437 · doi:10.1109/TIP.2010.2046811 |
| [53] | Zeng, Y., Fu, J., Chao, H.: Learning Joint Spatial-Temporal Transformations for Video Inpainting. In ECCV, (2020) |
| [54] | Zhang, H.; Cheng, L.; Zhu, W., Nuclear Norm Regularization with a Low-rank Constraint for Matrix Completion, Inverse Probl., 26, 11, 115009, 2010 · Zbl 1206.65140 · doi:10.1088/0266-5611/26/11/115009 |
| [55] | Zhang, Z., Ely, G., Aeron, S., Hao, N., Kilmer, M.: Novel Methods for Multilinear Data Completion and De-noising Based on Tensor-SVD. In CVPR, (2014) |
| [56] | Zhang, Z.; Zhang, L.; Mou, X.; Zhang, D., FSIM: A Feature Similarity Index for Image Quality Assessment, IEEE Trans. Image Process., 20, 8, 2378-2386, 2011 · Zbl 1373.62333 · doi:10.1109/TIP.2011.2109730 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
