Structured condition numbers of structured Tikhonov regularization problem and their estimations

Both structured componentwise and structured normwise perturbation analysis of the Tikhonov regularization are presented. The structured matrices under consideration include: Toeplitz, Hankel, Vandermonde, and Cauchy matrices. Structured normwise, mixed and componentwise condition numbers for the Tikhonov regularization are introduced and their explicit expressions are derived. For the general linear structure, based on the derived expressions, we prove structured condition numbers are smaller than their corresponding unstructured counterparts. By means of the power method and small sample statistical condition estimation (SCE), fast condition estimation algorithms are proposed. Our estimation methods can be integrated into Tikhonov regularization algorithms that use the generalized singular value decomposition (GSVD). For large scale linear structured Tikhonov regularization problems, we show how to incorporate the SCE into the preconditioned conjugate gradient (PCG) method to get the posterior error estimations. The structured condition numbers and perturbation bounds are tested on some numerical examples and compared with their unstructured counterparts. Our numerical examples demonstrate that the structured mixed condition numbers give sharper perturbation bounds than existing ones, and the proposed condition estimation algorithms are reliable. Also, an image restoration example is tested to show the effectiveness of the SCE for large scale linear structured Tikhonov regularization problems.