GCV for Tikhonov regularization via global Golub-Kahan decomposition. (Q2829107)

This paper is concerned with the solution of ill-conditioned, large-scale least-squares problems of the form \(\min_{\mathbf x \in \mathbb{R}^n} \| A \mathbf x - \mathbf b \|\), where \(A \in \mathbb{R}^{m\times n}\), and \(\| \cdot \|\) denotes the Euclidean vector norm. The data vector is of the form \(\mathbf b = \widehat{\mathbf b} + \mathbf e \in \mathbb{R}^m\), where \(\widehat{\mathbf b} \in \mathbb{R}^m\) is the unknown error-free vector, and \(\mathbf e \in \mathbb{R}^m\) denotes the measurement error of unknown norm. For a suitable choice of the regularization parameter \(\mu >0\) in Tikhonov regularization \(\min_{\mathbf x \in \mathbb{R}^n} \{ \| A \mathbf x - \mathbf b \|^2 + \mu^2 \| \mathbf x \|^2 \} \), the authors consider the minimization of the generalized cross validation (GCV) function NEWLINE\[NEWLINE\mathcal{V}(\mu) := \frac{\| A \mathbf x_\mu - \mathbf b \|^2}{(\text{trace}(I_m-A(\mu)))^2},NEWLINE\]NEWLINE where \(A(\mu) = A(A^T A + \mu^2 I_n)^{-1} A^T\), and \(\mathbf x_\mu = (A^T A + \mu^2 I_n)^{-1} A^T \mathbf b\) denotes the minimizer of the Tikhonov functional, and \(I_m \in \mathbb{R}^{m\times m}\) is the identity matrix. This paper describes a novel method for computing upper and lower bounds for the GCV function \(\mathcal{V}(\mu)\) to determine a suitable approximation of the minimizer of \(\mathcal{V}(\mu)\). For the efficient estimation of the denominator, a splitting of the form \(\text{trace}(I_m-A(\mu)) = \text{trace}(f_\mu(AA^T)) = \sum_{j=1}^{\tilde{m}} \text{trace}(E_j^T f_\mu(AA^T) E_j)\) is used, where \(f_\mu(t) = \mu^2 / (t+\mu^2)\). In addition, \(E_j = [\mathbf e_{(j-1)k+1},\dots, \mathbf e_{\min\{jk,m\}} ], \;j = 1,\dots, \tilde{m}\), are matrices with at most \(k\) columns, respectively, where \(k\) is large, and \(\mathbf e_i \in \mathbb{R}^{m}\) denotes the \(i\)\,th unit vector, and \(\tilde{m} = \lfloor (m + k - 1)/k \rfloor\). A global Golub-Kahan decomposition method is applied to derive upper and lower bounds for the trace of each submatrix \(E_j^T f_\mu(AA^T) E_j\), by taking into account a relation with Gauss-type quadrature. Bounds for the nominator \(\| A \mathbf x_\mu - \mathbf b \|^2\) are obtained by applying a standard Golub-Kahan bidiagonalization, again in relation with Gauss-type quadrature. In addition, the authors consider the appropriate choice of the number of iterations with the Golub-Kahan methods so that \(\mathcal{V}(\mu)\) is approximated with a given small relative error. Finally, results of a series of numerical experiments with test problems are presented.