Tensor Arnoldi-Tikhonov and GMRES-type methods for ill-posed problems with a t-product structure. (English) Zbl 1481.65060
Summary: This paper describes solution methods for linear discrete ill-posed problems defined by third order tensors and the t-product formalism introduced in [M. E. Kilmer and C. D. Martin, Linear Algebra Appl. 435, No. 3, 641–658 (2011; Zbl 1228.15009)]. A t-product Arnoldi (t-Arnoldi) process is defined and applied to reduce a large-scale Tikhonov regularization problem for third order tensors to a problem of small size. The data may be represented by a laterally oriented matrix or a third order tensor, and the regularization operator is a third order tensor. The discrepancy principle is used to determine the regularization parameter and the number of steps of the t-Arnoldi process. Numerical examples compare results for several solution methods, and illustrate the potential superiority of solution methods that tensorize over solution methods that matricize linear discrete ill-posed problems for third order tensors.
MSC:
| 65F22 | Ill-posedness and regularization problems in numerical linear algebra |
| 65F10 | Iterative numerical methods for linear systems |
| 15A69 | Multilinear algebra, tensor calculus |
Keywords:
discrepancy principle; linear discrete ill-posed problem; tensor Arnoldi process; t-product; tensor Tikhonov regularizationCitations:
Zbl 1228.15009References:
| [1] | Beik, FPA; Jbilou, K.; Najafi-Kalyani, M.; Reichel, L., Golub-Kahan bidiagonalization for ill-conditioned tensor equations with applications, Numer. Algorithms, 84, 1535-1563 (2020) · Zbl 1483.65069 · doi:10.1007/s11075-020-00911-y |
| [2] | Beik, FPA; Najafi-Kalyani, M.; Reichel, L., Iterative Tikhonov regularization of tensor equations based on the Arnoldi process and some of its generalizations, Appl. Numer. Math., 151, 425-447 (2020) · Zbl 1432.65049 · doi:10.1016/j.apnum.2020.01.011 |
| [3] | Buccini, A.; Pasha, M.; Reichel, L., Generalized singular value decomposition with iterated Tikhonov regularization, J. Comput. Appl. Math., 373, 112276 (2020) · Zbl 1524.65177 · doi:10.1016/j.cam.2019.05.024 |
| [4] | Calvetti, D.; Lewis, B.; Reichel, L., On the regularizing properties of the GMRES method, Numer. Math., 91, 605-625 (2002) · Zbl 1022.65044 · doi:10.1007/s002110100339 |
| [5] | Calvetti, D.; Morigi, S.; Reichel, L.; Sgallari, F., Tikhonov regularization and the L-curve for large, discrete ill-posed problems, J. Comput. Appl. Math., 123, 423-446 (2000) · Zbl 0977.65030 · doi:10.1016/S0377-0427(00)00414-3 |
| [6] | Calvetti, D.; Reichel, L., Tikhonov regularization of large linear problems, BIT Numer. Math., 43, 263-283 (2003) · Zbl 1038.65048 · doi:10.1023/A:1026083619097 |
| [7] | Donatelli, M.; Martin, D.; Reichel, L., Arnoldi methods for image deblurring with anti-reflective boundary conditions, Appl. Math. Comput., 253, 135-150 (2015) · Zbl 1338.94006 |
| [8] | El Guide, M., El Ichi, A., Jbilou, K., Beik, F.P.: Tensor GMRES and Golub-Kahan bidiagonalization methods via the Einstein product with applications to image and video processing. https://arxiv.org/pdf/2005.07458.pdf · Zbl 1538.65066 |
| [9] | El Ichi, M., El Guide, A., Jbilou, K.: Discrete cosine transform LSQR and GMRES methods for multidimensional ill-posed problems. https://arxiv.org/pdf/2103.11847.pdf (2021) · Zbl 1538.65066 |
| [10] | El Guide, M., El Ichi, A., Jbilou, K., Sadaka, R.: Tensor Krylov subspace methods via the T-product for color image processing. https://arxiv.org/pdf/2006.07133.pdf (2020) · Zbl 1538.65066 |
| [11] | Ely, G., Aeron, S., Hao, N., Kilmer, M.E.: 5d and 4d pre-stack seismic data completion using tensor nuclear norm (TNN). In: SEG International Exposition and Eighty-Third Annual Meeting at Houston, TX (2013) |
| [12] | Engl, HW; Hanke, M.; Neubauer, A., Regularization of Inverse Problems (1996), Dordrecht: Kluwer, Dordrecht · Zbl 0859.65054 · doi:10.1007/978-94-009-1740-8 |
| [13] | Fenu, C.; Reichel, L.; Rodriguez, G., GCV for Tikhonov regularization via global Golub-Kahan decomposition, Numer. Linear Algebra Appl., 23, 467-484 (2016) · Zbl 1374.65064 · doi:10.1002/nla.2034 |
| [14] | Gazzola, S.; Novati, P.; Russo, MR, On Krylov projection methods and Tikhonov regularization, Electron. Trans. Numer. Anal., 44, 83-123 (2015) · Zbl 1312.65065 |
| [15] | Golub, GH; Heath, M.; Wahba, G., Generalized cross-validation as a method for choosing a good ridge parameter, Technometrics, 21, 215-223 (1979) · Zbl 0461.62059 · doi:10.1080/00401706.1979.10489751 |
| [16] | Hansen, PC, Analysis of discrete ill-posed problems by means of the L-curve, SIAM Rev., 34, 561-580 (1992) · Zbl 0770.65026 · doi:10.1137/1034115 |
| [17] | Hansen, PC, Regularization tools version 4.0 for MATLAB 7.3, Numer. Algorithms, 46, 189-194 (2007) · Zbl 1128.65029 · doi:10.1007/s11075-007-9136-9 |
| [18] | Hao, N.; Kilmer, ME; Braman, K.; Hoover, RC, Facial recognition using tensor-tensor decompositions, SIAM J. Imaging Sci., 6, 437-463 (2013) · Zbl 1305.15061 · doi:10.1137/110842570 |
| [19] | Huang, G.; Reichel, L.; Yin, F., On the choice of subspace for large-scale Tikhonov regularization problems in general form, Numer. Algorithms, 81, 33-55 (2019) · Zbl 1434.65042 · doi:10.1007/s11075-018-0534-y |
| [20] | Kernfeld, E.; Kilmer, M.; Aeron, S., Tensor-tensor products with invertible linear transforms, Linear Algebra Appl., 485, 545-570 (2015) · Zbl 1323.15016 · doi:10.1016/j.laa.2015.07.021 |
| [21] | Kilmer, M., Braman, K., Hao, N.: Third order tensors as operators on matrices: a theoretical and computational framework. Technical Report, Department of Computer Science, Tufts University (2011) · Zbl 1269.65044 |
| [22] | Kilmer, ME; 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, 148-172 (2013) · Zbl 1269.65044 · doi:10.1137/110837711 |
| [23] | Kilmer, ME; Martin, CD, Factorization strategies for third-order tensors, Linear Algebra Appl., 435, 641-658 (2011) · Zbl 1228.15009 · doi:10.1016/j.laa.2010.09.020 |
| [24] | Kindermann, S., Convergence analysis of minimization-based noise level-free parameter choice rules for linear ill-posed problems, Electron. Trans. Numer. Anal., 38, 233-257 (2011) · Zbl 1287.65043 |
| [25] | Kindermann, S.; Raik, K., A simplified L-curve method as error estimator, Electron. Trans. Numer. Anal., 53, 217-238 (2020) · Zbl 1475.65024 · doi:10.1553/etna_vol53s217 |
| [26] | Kolda, TG; Bader, BW, Tensor decompositions and applications, SIAM Rev., 51, 455-500 (2009) · Zbl 1173.65029 · doi:10.1137/07070111X |
| [27] | Lewis, B.; Reichel, L., Arnoldi-Tikhonov regularization methods, J. Comput. Appl. Math., 226, 92-102 (2009) · Zbl 1166.65016 · doi:10.1016/j.cam.2008.05.003 |
| [28] | Lu, C.; Feng, J.; Chen, Y.; Liu, W.; Lin, Z.; Yan, S., Tensor robust principal component analysis with a new tensor nuclear norm, IEEE Trans. Pattern Anal. Mach. Intell., 42, 925-938 (2020) · doi:10.1109/TPAMI.2019.2891760 |
| [29] | Lund, K.: The tensor t-function: a definition for functions of third-order tensors. arXiv preprint. arXiv:1806.07261 (2018) |
| [30] | Martin, CD; Shafer, R.; LaRue, B., An order-\(p\) tensor factorization with applications in imaging, SIAM J. Sci. Comput., 35, A474-A490 (2013) · Zbl 1273.15032 · doi:10.1137/110841229 |
| [31] | Miao, Y.; Qi, L.; Wei, Y., T-Jordan canonical form and T-Drazin inverse based on the T-product, Commun. Appl. Math. Comput., 3, 201-220 (2021) · Zbl 1476.15045 · doi:10.1007/s42967-019-00055-4 |
| [32] | Miao, Y.; Qi, L.; Wei, Y., Generalized tensor function via the tensor singular value decomposition based on the T-product, Linear Algebra Appl., 590, 258-303 (2020) · Zbl 1437.15034 · doi:10.1016/j.laa.2019.12.035 |
| [33] | Neubauer, A., Augmented GMRES-type versus CGNE methods for the solution of linear ill-posed problems, Electron. Trans. Numer. Anal., 51, 412-431 (2019) · Zbl 1437.65049 · doi:10.1553/etna_vol51s412 |
| [34] | Reichel, L.; Shyshkov, A., A new zero-finder for Tikhonov regularization, BIT Numer. Math., 48, 627-643 (2008) · Zbl 1161.65029 · doi:10.1007/s10543-008-0179-7 |
| [35] | Reichel, L., Ugwu, U.O.: The tensor Golub-Kahan-Tikhonov method applied to the solution of ill-posed problems with a t-product structure. Numer. Linear Algebra Appl. 29,(2022). doi:10.1002/nla.2412 · Zbl 07511593 |
| [36] | Reichel, L.; Rodriguez, G., Old and new parameter choice rules for discrete ill-posed problems, Numer. Algorithms, 63, 65-87 (2013) · Zbl 1267.65045 · doi:10.1007/s11075-012-9612-8 |
| [37] | Saad, Y., Iterative Methods for Sparse Linear Systems (2003), Philadelphia: SIAM, Philadelphia · Zbl 1002.65042 · doi:10.1137/1.9780898718003 |
| [38] | Saad, Y.; Schultz, MH, GMRES: a generalized minimal residual method for solving nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 7, 856-869 (1986) · Zbl 0599.65018 · doi:10.1137/0907058 |
| [39] | Savas, B.; Eldén, L., Krylov-type methods for tensor computations, Linear Algebra Appl., 438, 891-918 (2013) · Zbl 1258.65032 · doi:10.1016/j.laa.2011.12.007 |
| [40] | Soltani, S.; Kilmer, ME; Hansen, PC, A tensor-based dictionary learning approach to tomographic image reconstruction, BIT Numer. Math., 56, 1425-1454 (2015) · Zbl 1355.65036 · doi:10.1007/s10543-016-0607-z |
| [41] | Trefethen, LN; Bau, D. III, Numerical Linear Algebra (1997), Philadelphia: SIAM, Philadelphia · Zbl 0874.65013 · doi:10.1137/1.9780898719574 |
| [42] | Zhang, Z., Ely, G., Aeron, S., Hao, N., Kilmer, M. E.: Novel methods for multilinear data completion and de-noising based on tensor-SVD. In: IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2014, Columbus, OH, USA, June 23-28, 2014, pp. 3842-3849 (2014) |
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.
