A posteriori parameter choice strategy for fast multiscale methods solving ill-posed integral equations (Q421362): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
A modified discrepancy principle for Tikhonov regularization of an integral equation of the first kind is considered, with a multiscale discretization to obtain a fast solver. We give some details, and for this purpose we consider the first kind Fredholm integral equation \( (Ax)(s) = \int_E k(s,t) x(t) dt = y (s), \, s \in E \), where \( E \) is a bounded closed set in \( \mathbb{R}^d \), with \( d \geq 1 \), and \( k \) is a continuous non-degenerate kernel. The operator \( A \) is considered as a compact operator from \( X = L^2(E) \) into \( X \), with the standard \( L^2 \) norm on \( X \) which is denoted by \( \| \cdot \| \). It is assumed that the right-hand side \( y \) belongs to the range \( R(A) \) of \( A \), and noisy data \( y^\delta \in X \) with \( \| y - y^\delta \| \leq \delta \) are available only. It is moreover assumed that both \( A \) and \( A^* \) are bounded operators from \( X \) into a linear subspace \( H^r \subset X \), where \( H^r \) is equipped with some norm that is stronger than the norm \( \| \cdot \| \) on \( X \). For the discretization, finite-dimensional linear subspaces \( X_0 \subset X_1 \subset \dots \subset X \) are considered, where \( X_n \) is the space of piecewise polynomials of degree less than \( r \) corresponding to some partition \( E_n \) of \( E \). It is assumed that the orthogonal projection operators \( P_n: X \to X \) onto \( X_n \) satisfy \( \| I - P_n \|_{H^r \to X} \leq c_r \mu^{-rn/d} \) for \( n = 0, 1, \ldots \)~. Here, \( \mu > 0 \) is a parameter such that the maximum diameter of the subsets of the partition \( E_n \) can be estimated by \( O(\mu^{-n/d}) \). The regularization method under consideration is Tikhonov regularization \[ \widetilde{x}_n^{\alpha,\delta} = (\alpha I + \widetilde{A}_n^* \widetilde{A}_n)^{-1} \widetilde{A}_n^* P_n y^\delta, \quad \alpha > 0, \] where \( \widetilde{A}_n=\sum_{i=0}^{n} (P_i-P_{i-1}) A P_{n-i}: X \to X \), with \( P_{-1} = 0 \), is an approximation to \( A \) which in fact requires only a small fraction of the scalar products needed to compute the standard discretization \( P_{n} A P_{n} \). An estimation of the number of scalar products required for the computation of \( \widetilde{x}_n^{\alpha,\delta} \) is given in the paper. In addition, \( \widetilde{A}_n^* \) denotes the adjoint operator of \( \widetilde{A}_n \). The considered parameter choice rule is as follows: choose \( n \) sufficiently large, and then for regularization parameters \( \alpha_m = a_0 q^m, ~m = 0, 1, \ldots, \) compute the Tikhonov approximations until \[ \begin{aligned} \| \alpha_m^{1/2} (\alpha_m I + \widetilde{A}_n \widetilde{A}_n^*)^{-1/2} (\widetilde{A}_n \widetilde{x}_n^{\alpha_m,\delta} - P_n y^\delta ) \| \leq d \delta \tag{\(*\)} \end{aligned} \] is satisfied for the first time, where \( a_0 > 0 \) and \( 0 < q < 1 \) are fixed, and \( d > 1 \) denotes some constant chosen sufficiently large. For the parameter \( \alpha_m \) chosen by \((*)\), it is shown that \( \| \widetilde{x}_n^{\alpha_m,\delta} - x^\dagger \| = O(\delta^{2\nu/(2\nu+1)}) \) as \( \delta \to 0 \) holds provided that the minimum norm solution \( x^\dagger \in X \) of the equation \( Ax=y\) can be represented in the form \( x^\dagger \in R((A^*A)^\nu) \) for some \( 0 < \nu \leq 1 \). The paper concludes with the presentation of results of some numerical experiments. | |||
Property / review text: A modified discrepancy principle for Tikhonov regularization of an integral equation of the first kind is considered, with a multiscale discretization to obtain a fast solver. We give some details, and for this purpose we consider the first kind Fredholm integral equation \( (Ax)(s) = \int_E k(s,t) x(t) dt = y (s), \, s \in E \), where \( E \) is a bounded closed set in \( \mathbb{R}^d \), with \( d \geq 1 \), and \( k \) is a continuous non-degenerate kernel. The operator \( A \) is considered as a compact operator from \( X = L^2(E) \) into \( X \), with the standard \( L^2 \) norm on \( X \) which is denoted by \( \| \cdot \| \). It is assumed that the right-hand side \( y \) belongs to the range \( R(A) \) of \( A \), and noisy data \( y^\delta \in X \) with \( \| y - y^\delta \| \leq \delta \) are available only. It is moreover assumed that both \( A \) and \( A^* \) are bounded operators from \( X \) into a linear subspace \( H^r \subset X \), where \( H^r \) is equipped with some norm that is stronger than the norm \( \| \cdot \| \) on \( X \). For the discretization, finite-dimensional linear subspaces \( X_0 \subset X_1 \subset \dots \subset X \) are considered, where \( X_n \) is the space of piecewise polynomials of degree less than \( r \) corresponding to some partition \( E_n \) of \( E \). It is assumed that the orthogonal projection operators \( P_n: X \to X \) onto \( X_n \) satisfy \( \| I - P_n \|_{H^r \to X} \leq c_r \mu^{-rn/d} \) for \( n = 0, 1, \ldots \)~. Here, \( \mu > 0 \) is a parameter such that the maximum diameter of the subsets of the partition \( E_n \) can be estimated by \( O(\mu^{-n/d}) \). The regularization method under consideration is Tikhonov regularization \[ \widetilde{x}_n^{\alpha,\delta} = (\alpha I + \widetilde{A}_n^* \widetilde{A}_n)^{-1} \widetilde{A}_n^* P_n y^\delta, \quad \alpha > 0, \] where \( \widetilde{A}_n=\sum_{i=0}^{n} (P_i-P_{i-1}) A P_{n-i}: X \to X \), with \( P_{-1} = 0 \), is an approximation to \( A \) which in fact requires only a small fraction of the scalar products needed to compute the standard discretization \( P_{n} A P_{n} \). An estimation of the number of scalar products required for the computation of \( \widetilde{x}_n^{\alpha,\delta} \) is given in the paper. In addition, \( \widetilde{A}_n^* \) denotes the adjoint operator of \( \widetilde{A}_n \). The considered parameter choice rule is as follows: choose \( n \) sufficiently large, and then for regularization parameters \( \alpha_m = a_0 q^m, ~m = 0, 1, \ldots, \) compute the Tikhonov approximations until \[ \begin{aligned} \| \alpha_m^{1/2} (\alpha_m I + \widetilde{A}_n \widetilde{A}_n^*)^{-1/2} (\widetilde{A}_n \widetilde{x}_n^{\alpha_m,\delta} - P_n y^\delta ) \| \leq d \delta \tag{\(*\)} \end{aligned} \] is satisfied for the first time, where \( a_0 > 0 \) and \( 0 < q < 1 \) are fixed, and \( d > 1 \) denotes some constant chosen sufficiently large. For the parameter \( \alpha_m \) chosen by \((*)\), it is shown that \( \| \widetilde{x}_n^{\alpha_m,\delta} - x^\dagger \| = O(\delta^{2\nu/(2\nu+1)}) \) as \( \delta \to 0 \) holds provided that the minimum norm solution \( x^\dagger \in X \) of the equation \( Ax=y\) can be represented in the form \( x^\dagger \in R((A^*A)^\nu) \) for some \( 0 < \nu \leq 1 \). The paper concludes with the presentation of results of some numerical experiments. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Robert Plato / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65R20 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65J20 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 45B05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 45Q05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 47A52 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65J10 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65J22 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65R30 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 65R32 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6038154 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
inverse problem | |||
Property / zbMATH Keywords: inverse problem / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
ill-posed problem | |||
Property / zbMATH Keywords: ill-posed problem / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Fredholm integral equation of the first kind | |||
Property / zbMATH Keywords: Fredholm integral equation of the first kind / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Tikhonov regularization | |||
Property / zbMATH Keywords: Tikhonov regularization / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
parameter choice | |||
Property / zbMATH Keywords: parameter choice / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
multiscale method | |||
Property / zbMATH Keywords: multiscale method / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
modified discrepancy principle | |||
Property / zbMATH Keywords: modified discrepancy principle / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
fast solver | |||
Property / zbMATH Keywords: fast solver / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
numerical experiments | |||
Property / zbMATH Keywords: numerical experiments / rank | |||
Normal rank |
Revision as of 21:45, 29 June 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A posteriori parameter choice strategy for fast multiscale methods solving ill-posed integral equations |
scientific article |
Statements
A posteriori parameter choice strategy for fast multiscale methods solving ill-posed integral equations (English)
0 references
23 May 2012
0 references
A modified discrepancy principle for Tikhonov regularization of an integral equation of the first kind is considered, with a multiscale discretization to obtain a fast solver. We give some details, and for this purpose we consider the first kind Fredholm integral equation \( (Ax)(s) = \int_E k(s,t) x(t) dt = y (s), \, s \in E \), where \( E \) is a bounded closed set in \( \mathbb{R}^d \), with \( d \geq 1 \), and \( k \) is a continuous non-degenerate kernel. The operator \( A \) is considered as a compact operator from \( X = L^2(E) \) into \( X \), with the standard \( L^2 \) norm on \( X \) which is denoted by \( \| \cdot \| \). It is assumed that the right-hand side \( y \) belongs to the range \( R(A) \) of \( A \), and noisy data \( y^\delta \in X \) with \( \| y - y^\delta \| \leq \delta \) are available only. It is moreover assumed that both \( A \) and \( A^* \) are bounded operators from \( X \) into a linear subspace \( H^r \subset X \), where \( H^r \) is equipped with some norm that is stronger than the norm \( \| \cdot \| \) on \( X \). For the discretization, finite-dimensional linear subspaces \( X_0 \subset X_1 \subset \dots \subset X \) are considered, where \( X_n \) is the space of piecewise polynomials of degree less than \( r \) corresponding to some partition \( E_n \) of \( E \). It is assumed that the orthogonal projection operators \( P_n: X \to X \) onto \( X_n \) satisfy \( \| I - P_n \|_{H^r \to X} \leq c_r \mu^{-rn/d} \) for \( n = 0, 1, \ldots \)~. Here, \( \mu > 0 \) is a parameter such that the maximum diameter of the subsets of the partition \( E_n \) can be estimated by \( O(\mu^{-n/d}) \). The regularization method under consideration is Tikhonov regularization \[ \widetilde{x}_n^{\alpha,\delta} = (\alpha I + \widetilde{A}_n^* \widetilde{A}_n)^{-1} \widetilde{A}_n^* P_n y^\delta, \quad \alpha > 0, \] where \( \widetilde{A}_n=\sum_{i=0}^{n} (P_i-P_{i-1}) A P_{n-i}: X \to X \), with \( P_{-1} = 0 \), is an approximation to \( A \) which in fact requires only a small fraction of the scalar products needed to compute the standard discretization \( P_{n} A P_{n} \). An estimation of the number of scalar products required for the computation of \( \widetilde{x}_n^{\alpha,\delta} \) is given in the paper. In addition, \( \widetilde{A}_n^* \) denotes the adjoint operator of \( \widetilde{A}_n \). The considered parameter choice rule is as follows: choose \( n \) sufficiently large, and then for regularization parameters \( \alpha_m = a_0 q^m, ~m = 0, 1, \ldots, \) compute the Tikhonov approximations until \[ \begin{aligned} \| \alpha_m^{1/2} (\alpha_m I + \widetilde{A}_n \widetilde{A}_n^*)^{-1/2} (\widetilde{A}_n \widetilde{x}_n^{\alpha_m,\delta} - P_n y^\delta ) \| \leq d \delta \tag{\(*\)} \end{aligned} \] is satisfied for the first time, where \( a_0 > 0 \) and \( 0 < q < 1 \) are fixed, and \( d > 1 \) denotes some constant chosen sufficiently large. For the parameter \( \alpha_m \) chosen by \((*)\), it is shown that \( \| \widetilde{x}_n^{\alpha_m,\delta} - x^\dagger \| = O(\delta^{2\nu/(2\nu+1)}) \) as \( \delta \to 0 \) holds provided that the minimum norm solution \( x^\dagger \in X \) of the equation \( Ax=y\) can be represented in the form \( x^\dagger \in R((A^*A)^\nu) \) for some \( 0 < \nu \leq 1 \). The paper concludes with the presentation of results of some numerical experiments.
0 references
inverse problem
0 references
ill-posed problem
0 references
Fredholm integral equation of the first kind
0 references
Tikhonov regularization
0 references
parameter choice
0 references
multiscale method
0 references
modified discrepancy principle
0 references
fast solver
0 references
numerical experiments
0 references