The greedy block Kaczmarz (GBK) method has been successfully applied in areas such as data mining, image reconstruction, and large-scale image restoration. However, the computation of pseudo-inverses in each iterative step of the GBK method not only complicates the computation and slows down the convergence rate, but it is also ill-suited for distributed implementation. The leverage score sampling free pseudo-inverse GBK algorithm proposed in this paper demonstrated significant potential in the field of image reconstruction. By ingeniously transforming the problem framework, the algorithm not only enhanced the efficiency of processing systems of linear equations with multiple solution vectors but also optimized specifically for applications in image reconstruction. A methodology that combined theoretical and experimental approaches has validated the robustness and practicality of the algorithm, providing valuable insights for technical advancements in related disciplines.
Citation: Wenya Shi, Xinpeng Yan, Zhan Huan. Faster free pseudoinverse greedy block Kaczmarz method for image recovery[J]. Electronic Research Archive, 2024, 32(6): 3973-3988. doi: 10.3934/era.2024178
[1] | Fang Wang, Weiguo Li, Wendi Bao, Li Liu . Greedy randomized and maximal weighted residual Kaczmarz methods with oblique projection. Electronic Research Archive, 2022, 30(4): 1158-1186. doi: 10.3934/era.2022062 |
[2] | Ranran Li, Hao Liu . On global randomized block Kaczmarz method for image reconstruction. Electronic Research Archive, 2022, 30(4): 1442-1453. doi: 10.3934/era.2022075 |
[3] | Koung Hee Leem, Jun Liu, George Pelekanos . A regularized eigenmatrix method for unstructured sparse recovery. Electronic Research Archive, 2024, 32(7): 4365-4377. doi: 10.3934/era.2024196 |
[4] | Qin Guo, Binlei Cai . Learning capability of the rescaled pure greedy algorithm with non-iid sampling. Electronic Research Archive, 2023, 31(3): 1387-1404. doi: 10.3934/era.2023071 |
[5] | John Daugherty, Nate Kaduk, Elena Morgan, Dinh-Liem Nguyen, Peyton Snidanko, Trung Truong . On fast reconstruction of periodic structures with partial scattering data. Electronic Research Archive, 2024, 32(11): 6481-6502. doi: 10.3934/era.2024303 |
[6] | Zhengyu Liu, Yufei Bao, Changhai Wang, Xiaoxiao Chen, Qing Liu . A fast matrix completion method based on truncated $ {\mathit{L}}_{2, 1} $ norm minimization. Electronic Research Archive, 2024, 32(3): 2099-2119. doi: 10.3934/era.2024095 |
[7] | Jingqian Xu, Ma Zhu, Baojun Qi, Jiangshan Li, Chunfang Yang . AENet: attention efficient network for cross-view image geo-localization. Electronic Research Archive, 2023, 31(7): 4119-4138. doi: 10.3934/era.2023210 |
[8] | Daochang Zhang, Dijana Mosić, Liangyun Chen . On the Drazin inverse of anti-triangular block matrices. Electronic Research Archive, 2022, 30(7): 2428-2445. doi: 10.3934/era.2022124 |
[9] | Huimin Qu, Haiyan Xie, Qianying Wang . Multi-convolutional neural network brain image denoising study based on feature distillation learning and dense residual attention. Electronic Research Archive, 2025, 33(3): 1231-1266. doi: 10.3934/era.2025055 |
[10] | Jiange Liu, Yu Chen, Xin Dai, Li Cao, Qingwu Li . MFCEN: A lightweight multi-scale feature cooperative enhancement network for single-image super-resolution. Electronic Research Archive, 2024, 32(10): 5783-5803. doi: 10.3934/era.2024267 |
The greedy block Kaczmarz (GBK) method has been successfully applied in areas such as data mining, image reconstruction, and large-scale image restoration. However, the computation of pseudo-inverses in each iterative step of the GBK method not only complicates the computation and slows down the convergence rate, but it is also ill-suited for distributed implementation. The leverage score sampling free pseudo-inverse GBK algorithm proposed in this paper demonstrated significant potential in the field of image reconstruction. By ingeniously transforming the problem framework, the algorithm not only enhanced the efficiency of processing systems of linear equations with multiple solution vectors but also optimized specifically for applications in image reconstruction. A methodology that combined theoretical and experimental approaches has validated the robustness and practicality of the algorithm, providing valuable insights for technical advancements in related disciplines.
In this paper, we aim to develop a novel weak Galerkin (WG) finite element method for the biharmonic equation that is applicable to non-convex polytopal meshes and eliminates the need for traditional stabilizers. To this aim, we consider the biharmonic equation with Dirichlet and Neumann boundary conditions. The goal is to find an unknown function u satisfying
Δ2u=f,inΩ,u=ξ,on∂Ω,∂u∂n=ν,on∂Ω, | (1.1) |
where Ω⊂Rd is an open bounded domain with a Lipschitz continuous boundary ∂Ω. The domain Ω considered in this paper can be of any dimension d≥2. For the sake of clarity in presentation, we will focus on the case where d=2 throughout this paper. However, the analysis presented here can be readily extended to higher dimensions (d≥3) without significant modifications.
The variational formulation of the model problem (1.1) is as follows: Find an unknown function u∈H2(Ω) satisfying u|∂Ω=ξ and ∂u∂n|∂Ω=ν, and the following equation
2∑i,j=1(∂2iju,∂2ijv)=(f,v),∀v∈H20(Ω), | (1.2) |
where ∂2ij denotes the second order partial derivative with respect to xi and xj, and H20(Ω)={v∈H2(Ω):v|∂Ω=0,∇v|∂Ω=0}.
The WG finite element method offers an innovative framework for the numerical solution of partial differential equations (PDEs). This approach approximates differential operators within a structure inspired by the theory of distributions, particularly for piecewise polynomial functions. Unlike traditional methods, WG reduces the regularity requirements on approximating functions through the use of carefully designed stabilizers. Extensive studies have highlighted the versatility and effectiveness of WG methods across a wide range of model PDEs, as demonstrated by numerous references [1,2,3,4,5,6] for an incomplete list, establishing WG as a powerful tool in scientific computing. The defining feature of WG methods lies in their innovative use of weak derivatives and weak continuities to construct numerical schemes based on the weak forms of the underlying PDEs. This unique structure provides WG methods with exceptional flexibility, enabling them to address a wide variety of PDEs while ensuring both stability and accuracy in their numerical solutions.
This paper presents a simplified formulation of the WG finite element method, capable of handling both convex and non-convex elements in finite element partitions. A key innovation of our method is the elimination of stabilizers through the use of higher-degree polynomials for computing weak second-order partial derivatives. This design preserves the size and global sparsity of the stiffness matrix while substantially reducing the programming complexity associated with traditional stabilizer-dependent methods. The method leverages bubble functions as a critical analytical tool, representing a significant improvement over existing stabilizer-free WG methods [7], which are limited to convex polytopal meshes. Our approach is versatile, accommodating arbitrary dimensions and polynomial degrees in the discretization process. In contrast, prior stabilizer-free WG methods [7] often require specific polynomial degree combinations and are restricted to 2D or 3D settings. Theoretical analysis establishes optimal error estimates for the WG approximations in both the discrete H2 norm and an L2 norm.
This paper is organized as follows. Section 2 provides a brief review of the definition of the weak-second order partial derivative and its discrete counterpart. In Section 3, we introduce an efficient WG scheme that eliminates the need for stabilization terms. Section 4 establishes the existence and uniqueness of the solution. The error equation for the proposed WG scheme is derived in Section 5. Section 6 focuses on obtaining the error estimate for the numerical approximation in the discrete H2 norm, while Section 7 extends the analysis to derive the error estimate in the L2 norm.
Throughout this paper, we adopt standard notations. Let D be any open, bounded domain with a Lipschitz continuous boundary in Rd. The inner product, semi-norm, and norm in the Sobolev space Hs(D) for any integer s≥0 are denoted by (⋅,⋅)s,D, |⋅|s,D and ‖⋅‖s,D respectively. For simplicity, when the domain D is Ω, the subscript D is omitted from these notations. In the case s=0, the notations (⋅,⋅)0,D, |⋅|0,D and ‖⋅‖0,D are further simplified as (⋅,⋅)D, |⋅|D and ‖⋅‖D, respectively.
This section provides a brief review of the definition of weak weak-second partial derivatives and their discrete counterparts, as introduced in [5].
Let T be a polygonal element with boundary ∂T. A weak function on T is represented as v={v0,vb,vg}, where v0∈L2(T), vb∈L2(∂T) and vg∈[L2(∂T)]2. The first component, v0, denotes the value of v within the interior of T, while the second component, vb, represents the value of v on the boundary of T. The third component vg∈R2 with components vgi (i=1,2) approximates the gradient ∇v on the boundary ∂T. In general, vb and vg are treated as independent of the traces of v0 and ∇v0, respectively.
The space of all weak functions on T, denote by W(T), is defined as
W(T)={v={v0,vb,vg}:v0∈L2(T),vb∈L2(∂T),vg∈[L2(∂T)]2}. |
The weak second order partial derivative, ∂2ij,w, is a linear operator mapping W(T) to the dual space of H2(T). For any v∈W(T), ∂2ij,wv is defined as a bounded linear functional on H2(T), given by:
(∂2ij,wv,φ)T=(v0,∂2jiφ)T−⟨vbni,∂jφ⟩∂T+⟨vgi,φnj⟩∂T,∀φ∈H2(T), |
where n, with components ni(i=1,2), represents the unit outward normal vector to ∂T.
For any non-negative integer r≥0, let Pr(T) denote the space of polynomials on T with total degree at most r. A discrete weak second order partial derivative, ∂2ij,w,r,T, is a linear operator mapping W(T) to Pr(T). For any v∈W(T), ∂2ij,w,r,Tv is the unique polynomial in Pr(T) satisfying
(∂2ij,w,r,Tv,φ)T=(v0,∂2jiφ)T−⟨vbni,∂jφ⟩∂T+⟨vgi,φnj⟩∂T,∀φ∈Pr(T). | (2.1) |
For a smooth v0∈H2(T), applying standard integration by parts to the first term on the right-hand side of (2.1) yields:
(∂2ij,w,r,Tv,φ)T=(∂2ijv0,φ)T−⟨(vb−v0)ni,∂jφ⟩∂T+⟨vgi−∂iv0,φnj⟩∂T, | (2.2) |
for any φ∈Pr(T).
Let Th be a finite element partition of the domain Ω⊂R2 into polygons. Assume that Th satisfies the shape regularity condition [8]. Let Eh represent the set of all edges in Th, and denote the set of interior edges by E0h=Eh∖∂Ω. For any element T∈Th, let hT be its diameter, and define the mesh size as h=maxT∈ThhT.
Let k, p and q be integers such that k≥p≥q≥1. For any element T∈Th, the local weak finite element space is defined as:
V(k,p,q,T)={{v0,vb,vg}:v0∈Pk(T),vb∈Pp(e),vg∈[Pq(e)]2,e⊂∂T}. |
By combining the local spaces V(k,p,q,T) across all elements T∈Th and ensuring continuity of vb and vg along the interior edges E0h, we obtain the global weak finite element space:
Vh={{v0,vb,vg}: {v0,vb,vg}|T∈V(k,p,q,T),∀T∈Th}. |
The subspace of Vh consisting of functions with vanishing boundary values on ∂Ω is defined as:
V0h={v∈Vh:vb|∂Ω=0,vg|∂Ω=0}. |
For simplicity, the discrete weak second order partial derivative ∂2ij,wv is used to denote the operator ∂2ij,w,r,Tv defined in (2.1) on each element T∈Th, as:
(∂2ij,wv)|T=∂2ij,w,r,T(v|T),∀T∈Th. |
On each element T∈Th, let Q0 denote the L2 projection onto Pk(T). On each edge e⊂∂T, let Qb and Qn denote the L2 projection operators onto Pp(e) and Pq(e), respectively. For any w∈H2(Ω), the L2 projection into the weak finite element space Vh is denoted by Qhw, defined as:
(Qhw)|T:={Q0(w|T),Qb(w|∂T),Qn(∇w|∂T)},∀T∈Th. |
The simplified WG numerical scheme, free from stabilization terms, for solving the biharmonic equation (1.1) is formulated as follows:
Weak Galerkin Algorithm 3.1. Find uh={u0,ub,ug}∈Vh such that ub=Qbξ, ug⋅n=Qnν and ug⋅τ=Qn(∇ξ⋅τ) on ∂Ω, and satisfy:
(∂2wuh,∂2wv)=(f,v0),∀v={v0,vb,vg}∈V0h, | (3.1) |
where τ∈R2 is the tangential direction along ∂Ω, and the terms are defined as:
(∂2wuh,∂2wv)=∑T∈Th2∑i,j=1(∂2ij,wuh,∂2ij,wv)T, |
(f,v0)=∑T∈Th(f,v0)T. |
Recall that Th is a shape-regular finite element partition of the domain Ω. Consequently, for any T∈Th and ϕ∈H1(T), the following trace inequality holds [8]:
‖ϕ‖2∂T≤C(h−1T‖ϕ‖2T+hT‖∇ϕ‖2T). | (4.1) |
If ϕ is a polynomial on the element T∈Th, a simpler form of the trace inequality applies [8]:
‖ϕ‖2∂T≤Ch−1T‖ϕ‖2T. | (4.2) |
For any v={v0,vb,vg}∈Vh, define the norm:
|||v|||=(∂2wv,∂2wv)12, | (4.3) |
and introduce the discrete H2- semi-norm:
‖v‖2,h=(∑T∈Th‖2∑i,j=1∂2ijv0‖2T+h−3T‖v0−vb‖2∂T+h−1T‖∇v0−vg‖2∂T)12. | (4.4) |
Lemma 4.1. For v={v0,vb,vg}∈Vh, there exists a constant C such that for i,j=1,2,
‖∂2ijv0‖T≤C‖∂2ij,wv‖T. |
Proof. Let T∈Th be a polytopal element with N edges denoted as e1,⋯, eN. Importantly, T can be non-convex. On each edge ei, construct a linear function li(x) satisfying li(x)=0 on ei as:
li(x)=1hT→AX⋅ni, |
where A is a fixed point on ei, X is any point on ei, ni is the normal vector to ei, and hT is the diameter of T.
Define the bubble function for T as:
ΦB=l21(x)l22(x)⋯l2N(x)∈P2N(T). |
It is straightforward to verify that ΦB=0 on ∂T. The function ΦB can be scaled such that ΦB(M)=1 where M is the barycenter of T. Additionally, there exists a subdomain ˆT⊂T such that ΦB≥ρ0 for some constant ρ0>0.
For v={v0,vb,vg}∈Vh, let r=2N+k−2 and choose φ=ΦB∂2ijv0∈Pr(T) in (2.2). This yields:
(∂2ij,wv,ΦB∂2ijv0)T=(∂2ijv0,ΦB∂2ijv0)T−⟨(vb−v0)ni,∂j(ΦB∂2ijv0)⟩∂T+⟨vgi−∂iv0,ΦB∂2ijv0nj⟩∂T=(∂2ijv0,ΦB∂2ijv0)T, | (4.5) |
where we applied ΦB=0 on ∂T.
Using the domain inverse inequality [8], there exists a constant C such that
(∂2ijv0,ΦB∂2ijv0)T≥C(∂2ijv0,∂2ijv0)T. | (4.6) |
By applying the Cauchy-Schwarz inequality to (4.5) and (4.6), we obtain
(∂2ijv0,∂2ijv0)T≤C(∂2ij,wv,ΦB∂2ijv0)T≤C‖∂2ij,wv‖T‖ΦB∂2ijv0‖T≤C‖∂2ij,wv‖T‖∂2ijv0‖T, |
which implies:
‖∂2ijv0‖T≤C‖∂2ij,wv‖T. |
This completes the proof.
Remark 4.1. If the polytopal element T is convex, the bubble function in Lemma 4.1 can be simplified to:
ΦB=l1(x)l2(x)⋯lN(x). |
This simplified bubble function satisfies 1) ΦB=0 on ∂T, 2) there exists a subdomain ˆT⊂T such that ΦB≥ρ0 for some constant ρ0>0. The proof of Lemma 4.1 follows the same approach, using this simplified bubble function. In this case, we set r=N+k−2.
By constructing an edge-based bubble function,
φek=Πi=1,⋯,N,i≠kl2i(x), |
it can be easily verified that 1) φek=0 on each edge ei for i≠k, and 2) there exists a subdomain ^ek⊂ek such that φek≥ρ1 for some constant ρ1>0. Let φ=(vb−v0)lkφek. It is straightforward to verify the following properties: 1) φ=0 on each edge ei for i=1,⋯,N, 2) ∇φ=0 on each edge ei for i≠k, and 3) ∇φ=(v0−vb)(∇lk)φek=O((v0−vb)φekhTC) on ek, where C is a constant vector.
Lemma 4.2. [9] For {v0,vb,vg}∈Vh, let φ=(vb−v0)lkφek. The following inequality holds:
‖φ‖2T≤ChT∫ek(vb−v0)2ds. | (4.7) |
Lemma 4.3. For {v0,vb,vg}∈Vh, let φ=(vgi−∂iv0)φek. The following inequality holds:
‖φ‖2T≤ChT∫ek(vgi−∂iv0)2ds. | (4.8) |
Proof. Define the extension of vg, originally defined on the edge ek, to the entire polytopal element T as:
vg(X)=vg(Projek(X)), |
where X=(x1,x2) is any point in T, Projek(X) denotes the orthogonal projection of X onto the plane H⊂R2 containing ek. If Projek(X) is not on ek, vg(Projek(X)) is defined as the extension of vg from ek to H. The extension preserves the polynomial nature of vg as demonstrated in [9].
Let vtrace denote the trace of v0 on ek. Define its extension to T as:
vtrace(X)=vtrace(Projek(X)). |
This extension is also polynomial, as demonstrated in [9].
Let φ=(vgi−∂iv0)φek. Then,
‖φ‖2T=∫Tφ2dT=∫T((vgi−∂iv0)(X)φek)2dT≤ChT∫ek((vgi−∂iv0)(Projek(X))φek)2dT≤ChT∫ek(vgi−∂iv0)2ds, |
where we used the facts that 1) φek=0 on each edge ei for i≠k, 2) there exists a subdomain ^ek⊂ek such that φek≥ρ1 for some constant ρ1>0, and applied the properties of the projection.
This completes the proof of the lemma.
Lemma 4.4. There exist two positive constants, C1 and C2, such that for any v={v0,vb,vg}∈Vh, the following equivalence holds:
C1‖v‖2,h≤|||v|||≤C2‖v‖2,h. | (4.9) |
Proof. Consider the edge-based bubble function defined as
φek=Πi=1,⋯,N,i≠kl2i(x). |
First, extend vb from the edge ek to the element T. Similarly, let vtrace denote the trace of v0 on the edge ek and extend vtrace to the element T. For simplicity, we continue to use vb and v0 to represent their respective extensions. Details of these extensions can be found in Lemma 4.3. Substituting φ=(vb−v0)lkφek into (2.2), we obtain
(∂2ij,wv,φ)T=(∂2ijv0,φ)T−⟨(vb−v0)ni,∂jφ⟩∂T+⟨vgi−∂iv0,φnj⟩∂T=(∂2ijv0,φ)T+Ch−1T∫ek|vb−v0|2φekds, | (4.10) |
where we used 1) φ=0 on each edge ei for i=1, ⋯, N, 2) ∇φ=0 on each edge ei for i≠k, and 3) ∇φ=(v0−vb)(∇lk)φek=O((v0−vb)φekhTC) on ek, where C is a constant vector.
Recall that 1) φek=0 on each edge ei for i≠k, and 2) there exists a subdomain ^ek⊂ek such that φek≥ρ1 for some constant ρ1>0. Using Cauchy-Schwarz inequality, the domain inverse inequality [8], (4.10) and Lemma 4.2, we deduce:
∫ek|vb−v0|2ds≤C∫ek|vb−v0|2φekds≤ChT(‖∂2ij,wv‖T+‖∂2ijv0‖T)‖φ‖T≤Ch32T(‖∂2ij,wv‖T+‖∂2ijv0‖T)(∫ek|vb−v0|2ds)12, |
which, from Lemma 4.1, leads to:
h−3T∫ek|vb−v0|2ds≤C(‖∂2ij,wv‖2T+‖∂2ijv0‖2T)≤C‖∂2ij,wv‖2T. | (4.11) |
Next, extend vg from the edge ek to the element T, denoting the extension by the same symbol for simplicity. Details of this extension are in Lemma 4.3. Substituting φ=(vgi−∂iv0)φek into (2.2), we obtain:
(∂2ij,wv,φ)T=(∂2ijv0,φ)T−⟨(vb−v0)ni,∂jφ⟩∂T+⟨vgi−∂iv0,φnj⟩∂T=(∂2ijv0,φ)T−⟨(vb−v0)ni,∂jφ⟩∂T+∫ek|vgi−∂iv0|2φekds, | (4.12) |
where we used φek=0 on edge ei for i≠k, and the fact that there exists a sub-domain ^ek⊂ek such that φek≥ρ1 for some constant ρ1>0. This, together with Cauchy-Schwarz inequality, the domain inverse inequality [8], the inverse inequality, the trace inequality (4.2), (4.11) and Lemma 4.3, gives
∫ek|vgi−∂iv0|2ds≤C∫ek|vgi−∂iv0|2φekds≤C(‖∂2ij,wv‖T+‖∂2ijv0‖T)‖φ‖T+C‖v0−vb‖∂T‖∂jϕ‖∂T≤Ch12T(‖∂2ij,wv‖T+‖∂2ijv0‖T)(∫ek|vgi−∂iv0|2ds)12+Ch32T‖∂2ij,wv‖Th−1T(∫ek|vgi−∂iv0|2ds)12. |
Applying Lemma 4.1, gives
h−1T∫ek|vgi−∂iv0|2ds≤C(‖∂2ij,wv‖2T+‖∂2ijv0‖2T)≤C‖∂2ij,wv‖2T. | (4.13) |
Using Lemma 4.1, Eqs (4.11), (4.13), (4.3) and (4.4), we deduce:
C1‖v‖2,h≤|||v|||. |
Finally, using the Cauchy-Schwarz inequality, inverse inequalities, and the trace inequality (4.2) in (2.2), we derive:
|(∂2ij,wv,φ)T|≤‖∂2ijv0‖T‖φ‖T+‖(vb−v0)ni‖∂T‖∂jφ‖∂T+‖vgi−∂iv0‖∂T‖φnj‖∂T≤‖∂2ijv0‖T‖φ‖T+h−32T‖vb−v0‖∂T‖φ‖T+h−12T‖vgi−∂iv0‖∂T‖φ‖T, |
which gives:
‖∂2ij,wv‖2T≤C(‖∂2ijv0‖2T+h−3T‖vb−v0‖2∂T+h−1T‖vgi−∂iv0‖2∂T), |
and further gives
|||v|||≤C2‖v‖2,h. |
This completes the proof.
Theorem 4.5. The WG scheme 3.1 admits a unique solution.
Proof. Assume that u(1)h∈Vh and u(2)h∈Vh are two distinct solutions of the WG scheme 3.1. Define ηh=u(1)h−u(2)h∈V0h. Then, ηh satisfies
(∂2ij,wηh,∂2ij,wv)=0,∀v∈V0h. |
Choosing v=ηh yields |||ηh|||=0. From the equivalence of norms in (4.9), it follows that ‖ηh‖2,h=0, which yields ∂2ijη0=0 for i,j=1,2 on each T, η0=ηb and ∇η0=ηg on each ∂T. Consequently, η0 is a linear function on each element T and ∇η0=C on each T.
Since ∇η0=ηg on each ∂T, it follows that ∇η0 is continuous across the entire domain Ω. Thus, ∇η0=C throughout Ω. Furthermore, the condition ηg=0 on ∂Ω implies ∇η0=0 in Ω and ηg=0 on each ∂T. Therefore, η0 is a constant on each element T.
Since η0=ηb on ∂T, the continuity of η0 over Ω implies η0 is globally constant. From ηb=0 on ∂Ω, we conclude η0=0 throughout Ω. Consequently, ηb=η0=0 on each ∂T, which implies ηh≡0 in Ω. Thus, u(1)h≡u(2)h, proving the uniqueness of the solution.
Let Qr denote the L2 projection operator onto the finite element space of piecewise polynomials of degree at most r.
Lemma 5.1. The following property holds:
∂2ij,wu=Qr(∂2iju),∀u∈H2(T). | (5.1) |
Proof. For any u∈H2(T), using (2.2), we have
(∂2ij,wu,φ)T=(∂2iju,φ)T−⟨(u|∂T−u|T)ni,∂jφ⟩∂T+⟨(∇u|∂T)i−∂i(u|T),φnj⟩∂T=(∂2iju,φ)T=(Qr(∂2iju),φ)T, |
for all φ∈Pr(T). This completes the proof.
Let u be the exact solution of the biharmonic equation (1.1), and uh∈Vh its numerical approximation obtained from the WG scheme 3.1. The error function, denoted by eh, is defined as
eh=u−uh. | (5.2) |
Lemma 5.2. The error function eh defined in (5.2) satisfies the following error equation:
(∂2weh,∂2wv)=ℓ(u,v),∀v∈V0h, | (5.3) |
where
ℓ(u,v)=∑T∈Th2∑i,j=1−⟨(vb−v0)ni,∂j((Qr−I)∂2iju)⟩∂T+⟨vgi−∂iv0,(Qr−I)∂2ijunj⟩∂T. |
Proof. Using (5.1), standard integration by parts, and substituting φ=Qr∂2iju into (2.2), we obtain
∑T∈Th2∑i,j=1(∂2ij,wu,∂2ij,wv)T=∑T∈Th2∑i,j=1(Qr∂2iju,∂2ij,wv)T=∑T∈Th2∑i,j=1(∂2ijv0,Qr∂2iju)T−⟨(vb−v0)ni,∂j(Qr∂2iju)⟩∂T+⟨vgi−∂iv0,Qr∂2ijunj⟩∂T=∑T∈Th2∑i,j=1(∂2ijv0,∂2iju)T−⟨(vb−v0)ni,∂j(Qr∂2iju)⟩∂T+⟨vgi−∂iv0,Qr∂2ijunj⟩∂T=∑T∈Th2∑i,j=1((∂2ij)2u,v0)T+⟨∂2iju,∂iv0⋅nj⟩∂T−⟨∂j(∂2iju)⋅ni,v0⟩∂T−⟨(vb−v0)ni,∂j(Qr∂2iju)⟩∂T+⟨vgi−∂iv0,Qr∂2ijunj⟩∂T=(f,v0)+∑T∈Th2∑i,j=1−⟨(vb−v0)ni,∂j((Qr−I)∂2iju)⟩∂T+⟨vgi−∂iv0,(Qr−I)∂2ijunj⟩∂T, | (5.4) |
where we used (1.1), ∂2ijv0∈Pk−2(T) and r=2N+k−2≥k−2, ∑T∈Th∑2i,j=1⟨∂2iju,vgi⋅nj⟩∂T=∑T∈Th∑2i,j=1⟨∂2iju,vgi⋅nj⟩∂Ω=0 since vgi=0 on ∂Ω, and ∑T∈Th∑2i,j=1⟨∂j(∂2iju)⋅ni,vb⟩∂T=∑T∈Th∑2i,j=1⟨∂j(∂2iju)⋅ni,vb⟩∂Ω=0 since vb=0 on ∂Ω.
Subtracting (3.1) from (5.4) yields
∑T∈Th2∑i,j=1(∂2ij,weh,∂2ij,wv)T=∑T∈Th2∑i,j=1−⟨(vb−v0)ni,∂j((Qr−I)∂2iju)⟩∂T+⟨vgi−∂iv0,(Qr−I)∂2ijunj⟩∂T. |
This concludes the proof.
Lemma 6.1. [5] Let Th be a finite element partition of the domain Ω satisfying the shape regularity assumption specified in [8]. For any 0≤s≤2 and 1≤m≤k, the following estimates hold:
∑T∈Th2∑i,j=1h2sT‖∂2iju−Qr∂2iju‖2s,T≤Ch2(m−1)‖u‖2m+1, | (6.1) |
∑T∈Thh2sT‖u−Q0u‖2s,T≤Ch2(m+1)‖u‖2m+1. | (6.2) |
Lemma 6.2. If u∈Hk+1(Ω), then there exists a constant C such that
|||u−Qhu|||≤Chk−1‖u‖k+1. | (6.3) |
Proof. Utilizing (2.2), the trace inequalities (4.1) and (4.2), the inverse inequality, and the estimate (6.2) for m=k and s=0,1,2, we analyze the following summation for any φ∈Pr(T):
∑T∈Th2∑i,j=1(∂2ij,w(u−Qhu),φ)T=∑T∈Th2∑i,j=1(∂2ij(u−Q0u),φ)T−⟨(Q0u−Qbu)ni,∂jφ⟩∂T+⟨(∂iu−Qn(∂iu))−∂i(u−Q0u),φnj⟩∂T≤(∑T∈Th2∑i,j=1‖∂2ij(u−Q0u)‖2T)12(∑T∈Th‖φ‖2T)12+(∑T∈Th2∑i=1‖(Q0u−Qbu)ni‖2∂T)12(∑T∈Th2∑j=1‖∂jφ‖2∂T)12+(∑T∈Th2∑i=1‖∂i(Q0u)−Qn(∂iu)‖2∂T)12(∑T∈Th2∑j=1‖φnj‖2∂T)12≤(∑T∈Th2∑i,j=1‖∂2ij(u−Q0u)‖2T)12(∑T∈Th‖φ‖2T)12+(∑T∈Thh−1T‖Q0u−u‖T+hT‖Q0u−u‖21,T)12(∑T∈Thh−3T‖φ‖2T)12+(∑T∈Th2∑i=1h−1T‖∂i(Q0u)−∂iu‖2T+hT‖∂i(Q0u)−∂iu‖21,T)12(∑T∈Thh−1T‖φ‖2T)12≤Chk−1‖u‖k+1(∑T∈Th‖φ‖2T)12. |
Letting φ=∂2ij,w(u−Qhu) gives
∑T∈Th2∑i,j=1(∂2ij,w(u−Qhu),∂2ij,w(u−Qhu))T≤Chk−1‖u‖k+1|||u−Qhu|||. |
This completes the proof.
Theorem 6.3. Suppose the exact solution u of the biharmonic equation (1.1) satisfies u∈Hk+1(Ω). Then, the error estimate satisfies:
|||u−uh|||≤Chk−1‖u‖k+1. | (6.4) |
Proof. Note that r≥1. For the first term on the right-hand side of the error equation (5.3), using Cauchy-Schwarz inequality, the trace inequality (4.1), the estimate (6.1) with m=k and s=1,2, and (4.9), we have
|∑T∈Th2∑i,j=1−⟨(vb−v0)ni,∂j((Qr−I)∂2iju)⟩∂T|≤C(∑T∈Th2∑i=1h−3T‖(vb−v0)ni‖2∂T)12⋅(∑T∈Th2∑i,j=1h3T‖∂j((Qr−I)∂2iju)‖2∂T)12≤C‖v‖2,h(∑T∈Th2∑i,j=1h2T‖∂j((Qr−I)∂2iju)‖2T+h4T‖∂j((Qr−I)∂2iju)‖21,T)12≤Chk−1‖u‖k+1|||v|||. | (6.5) |
For the second term on the right-hand side of the error equation (5.3), using the Cauchy-Schwarz inequality, the trace inequality (4.1), the estimate (6.1) with m=k and s=0,1, and (4.9), we have
|∑T∈Th2∑i,j=1⟨vgi−∂iv0,(Qr−I)∂2ijunj⟩∂T|≤C(∑T∈Th2∑i=1h−1T‖vgi−∂iv0‖2∂T)12(∑T∈Th2∑i,j=1hT‖(Qr−I)∂2ijunj‖2∂T)12≤C‖v‖2,h(∑T∈Th2∑i,j=1‖(Qr−I)∂2ijunj‖2T+h2T‖(Qr−I)∂2ijunj‖21,T)12≤C‖v‖2,hhk−1‖u‖k+1≤Chk−1‖u‖k+1|||v|||. | (6.6) |
Substituting (6.5) and (6.6) into (5.3) gives
(∂2ij,weh,∂2ij,wv)≤Chk−1‖u‖k+1|||v|||. | (6.7) |
Using Cauchy-Schwarz inequality, letting v=Qhu−uh in (6.7), the error estimate (6.3) gives
|||u−uh|||2=∑T∈Th2∑i,j=1(∂2ij,w(u−uh),∂2ij,w(u−Qhu))T+(∂2ij,w(u−uh),∂2ij,w(Qhu−uh))T≤|||u−uh||||||u−Qhu|||+Chk−1‖u‖k+1|||Qhu−uh|||≤|||u−uh||||||u−Qhu|||+Chk−1‖u‖k+1(|||Qhu−u|||+|||u−uh|||)≤|||u−uh||||||u−Qhu|||+Chk−1‖u‖k+1hk−1‖u‖k+1+Chk−1‖u‖k+1|||u−uh|||, |
which further gives
|||u−uh|||≤|||u−Qhu|||+Chk−1‖u‖k+1≤Chk−1‖u‖k+1. |
This completes the proof.
To derive the error estimate in the L2 norm, we use the standard duality argument. The error is expressed as eh=u−uh={e0,eb,eg}, and we define ζh=Qhu−uh={ζ0,ζb,ζg}∈V0h. Consider the dual problem associated with the biharmonic equation (1.1), which seeks a function w∈H20(Ω) satisfying:
Δ2w=ζ0,in Ω,w=0,on ∂Ω,∂w∂n=0,on ∂Ω. | (7.1) |
We assume the following regularity condition for the dual problem:
‖w‖4≤C‖ζ0‖. | (7.2) |
Theorem 7.1. Let u∈Hk+1(Ω) be the exact solution of the biharmonic equation (1.1), and let uh∈Vh denote the numerical solution obtained using the weak Galerkin scheme 3.1. Assume that the H4-regularity condition (7.2) holds. Then, there exists a constant C such that
‖e0‖≤Chk+1‖u‖k+1. |
Proof. Testing the dual problem (7.1) with ζ0 and applying integration by parts, we derive:
‖ζ0‖2=(Δ2w,ζ0)=∑T∈Th2∑i,j=1(∂2ijw,∂2ijζ0)T−⟨∂2ijw,∂iζ0⋅nj⟩∂T+⟨∂j(∂2ijw)⋅ni,ζ0⟩∂T=∑T∈Th2∑i,j=1(∂2ijw,∂2ijζ0)T−⟨∂2ijw,(∂iζ0−ζgi)⋅nj⟩∂T+⟨∂j(∂2ijw)⋅ni,ζ0−ζb⟩∂T, | (7.3) |
where we used ∑T∈Th∑2i,j=1⟨∂2ijw,ζgi⋅nj⟩∂T=∑2i,j=1⟨∂2ijw,ζgi⋅nj⟩∂Ω=0 due to ζg=0 on ∂Ω, and ∑T∈Th∑2i,j=1⟨∂j(∂2ijw)⋅ni,ζb⟩∂T=∑2i,j=1⟨∂j(∂2ijw)⋅ni,ζb⟩∂Ω=0 due to ζb=0 on ∂Ω.
Letting u=w and v=ζh in (5.4) gives
∑T∈Th2∑i,j=1(∂2ij,ww,∂2ij,wζh)T=∑T∈Th2∑i,j=1(∂2ijw,∂2ijζ0)T−⟨(ζb−ζ0)ni,∂j(Qr∂2ijw)⟩∂T+⟨ζgi−∂iζ0,Qr∂2ijwnj⟩∂T, |
which is equivalent to
∑T∈Th2∑i,j=1(∂2ijw,∂2ijζ0)T=∑T∈Th2∑i,j=1(∂2ij,ww,∂2ij,wζh)T+⟨(ζb−ζ0)ni,∂j(Qr∂2ijw)⟩∂T−⟨ζgi−∂iζ0,Qr∂2ijwnj⟩∂T. |
Substituting the above equation into (7.3) and using (5.3) gives
‖ζ0‖2=∑T∈Th2∑i,j=1(∂2ij,ww,∂2ij,wζh)T+⟨(ζb−ζ0)ni,∂j((Qr−I)∂2ijw)⟩∂T−⟨ζgi−∂iζ0,(Qr−I)∂2ijwnj⟩∂T=∑T∈Th2∑i,j=1(∂2ij,ww,∂2ij,weh)T+(∂2ij,ww,∂2ij,w(Qhu−u))T−ℓ(w,ζh)=∑T∈Th2∑i,j=1(∂2ij,wQhw,∂2ij,weh)T+(∂2ij,w(w−Qhw),∂2ij,weh)T+(∂2ij,ww,∂2ij,w(Qhu−u))T−ℓ(w,ζh)=ℓ(u,Qhw)+∑T∈Th2∑i,j=1(∂2ij,w(w−Qhw),∂2ij,weh)T+(∂2ij,ww,∂2ij,w(Qhu−u))T−ℓ(w,ζh)=J1+J2+J3+J4. | (7.4) |
We will estimate the four terms Ji(i=1, ⋯, 4) on the last line of (7.4) individually.
For J1, using the Cauchy-Schwarz inequality, the trace inequality (4.1), the inverse inequality, the estimate (6.1) with m=k and s=0,1,2, the estimate (6.2) with m=3 and s=0,1,2, gives
J1=ℓ(u,Qhw)≤|∑T∈Th2∑i,j=1−⟨(Qbw−Q0w)ni,∂j((Qr−I)∂2iju)⟩∂T+⟨Qn(∂iw)−∂iQ0w,(Qr−I)∂2ijunj⟩∂T|≤(∑T∈Th2∑i=1‖(Qbw−Q0w)ni‖2∂T)12(∑T∈Th2∑i,j=1‖∂j((Qr−I)∂2iju)‖2∂T)12+(∑T∈Th2∑i=1‖Qn(∂iw)−∂iQ0w‖2∂T)12(∑T∈Th2∑i,j=1‖(Qr−I)∂2ijunj‖2∂T)12≤(∑T∈Thh−1T‖w−Q0w‖2T+hT‖w−Q0w‖21,T)12⋅(∑T∈Th2∑i,j=1h−1T‖∂j((Qr−I)∂2iju)‖2T+hT‖∂j((Qr−I)∂2iju)‖21,T)12+(∑T∈Th2∑i=1h−1T‖∂iw−∂iQ0w‖2T+hT‖∂iw−∂iQ0w‖21,T)12⋅(∑T∈Th2∑i,j=1h−1T‖(Qr−I)∂2ijunj‖2T+hT‖(Qr−I)∂2ijunj‖21,T)12≤Chk+1‖u‖k+1‖w‖4. | (7.5) |
For J2, using Cauchy-Schwarz inequality, (6.3) with k=3 and (6.4) gives
J2≤|||w−Qhw||||||eh|||≤Chk−1‖u‖k+1h2‖w‖4≤Chk+1‖u‖k+1‖w‖4. | (7.6) |
For J3, denote by Q1 a L2 projection onto P1(T). Using (2.1) gives
(∂2ij,w(Qhu−u),Q1∂2ij,ww)T=(Q0u−u,∂2ji(Q1∂2ij,ww))T−⟨Qbu−u,∂j(Q1∂2ij,ww)⟩∂T+⟨Qn(∂iu)−∂iu,Q1∂2ij,wwnj⟩∂T=0, | (7.7) |
where we used ∂2ji(Q1∂2ij,ww)=0, ∂j(Q1∂2ij,ww)=C and the property of the projection operators Qb and Qn and p≥q≥1.
Using (7.7), Cauchy-Schwarz inequality, (5.1) and (6.3), gives
J3≤|∑T∈Th2∑i,j=1(∂2ij,ww,∂2ij,w(Qhu−u))T|=|∑T∈Th2∑i,j=1(∂2ij,ww−Q1∂2ij,ww,∂2ij,w(Qhu−u))T|=|∑T∈Th2∑i,j=1(Qr∂2ijw−Q1Qr∂2ijw,∂2ij,w(Qhu−u))T|≤(∑T∈Th2∑i,j=1‖Qr∂2ijw−Q1Qr∂2ijw‖2T)12|||Qhu−u|||≤Chk+1‖u‖k+1‖w‖4. | (7.8) |
For J4, using Cauchy-Schwarz inequality, the trace inequality (4.1), Lemma 4.4, the estimate (6.1) with m=3 and s=0,1, (6.3), (6.4) gives
J4=ℓ(w,ζh)≤|∑T∈Th2∑i,j=1−⟨(ζb−ζ0)ni,∂j((Qr−I)∂2ijw)⟩∂T+⟨ζgi−∂iζ0,(Qr−I)∂2ijwnj⟩∂T|≤(∑T∈Th2∑i=1‖(ζb−ζ0)ni‖2∂T)12(∑T∈Th2∑i,j=1‖∂j((Qr−I)∂2ijw)‖2∂T)12+(∑T∈Th2∑i=1‖ζgi−∂iζ0‖2∂T)12(∑T∈Th2∑i,j=1‖(Qr−I)∂2ijwnj‖2∂T)12≤(∑T∈Th2∑i,j=1h2T‖∂j((Qr−I)∂2ijw)‖2T+h4T‖∂j((Qr−I)∂2ijw)‖21,T)12⋅(∑T∈Thh−3T‖ζ0−ζb‖2∂T)12+(∑T∈Th2∑i,j=1‖(Qr−I)∂2ijwnj‖2T+h2T‖(Qr−I)∂2ijwnj‖21,T)12⋅(∑T∈Th2∑i=1h−1T‖ζgi−∂iζ0‖2∂T)12≤Ch2‖w‖4|||ζh|||≤Ch2‖w‖4(|||u−uh|||+|||u−Qhu|||)≤Chk+1‖w‖4‖u‖k+1. | (7.9) |
Substituting (7.5), (7.6), (7.8) and (7.9) into (7.4), and using (7.2), gives
‖ζ0‖2≤Chk+1‖w‖4‖u‖k+1≤Chk+1‖u‖k+1‖ζ0‖. |
This gives
‖ζ0‖≤Chk+1‖u‖k+1, |
which, using the triangle inequality and (6.2) with m=k and s=0, gives
‖e0‖≤‖ζ0‖+‖u−Q0u‖≤Chk+1‖u‖k+1. |
This completes the proof of the theorem.
The author declares she has not used Artificial Intelligence (AI) tools in the creation of this article.
The research of Chunmei Wang was partially supported by National Science Foundation Grant DMS-2136380.
The author declares there is no conflict of interest.
[1] | A. C. Kak, M. Slaney, Principles of computerized tomographic imaging, Society for Industrial and Applied Mathematics, New York, 2001. |
[2] |
J. A. Fessler, B. P. Sutton, Nonuniform fast Fourier transforms using min-max interpolation, IEEE T. Signal Proces., 51 (2003), 560–574. https://doi.org/10.1109/TSP.2002.807005 doi: 10.1109/TSP.2002.807005
![]() |
[3] |
S. F. Gull, G. J. Daniell, Image reconstruction from incomplete and noisy data, Nature, 272 (1978), 686–690. https://doi.org/10.1038/272686a0 doi: 10.1038/272686a0
![]() |
[4] |
X. L. Zhao, T. Z. Huang, X. M. Gu, L. J. Deng, Vector extrapolation based Landweber method for discrete ill-posed problems, Math. Probl. Eng., 2017 (2017), 1375716. https://doi.org/10.1155/2017/1375716 doi: 10.1155/2017/1375716
![]() |
[5] |
S. C. Park, M. K. Park, M. G. Kang, Super-resolution image reconstruction: a technical overview, IEEE Signal Proc. Mag., 20 (2003), 21–36. https://doi.org/10.1109/MSP.2003.120320 doi: 10.1109/MSP.2003.120320
![]() |
[6] | F. Natterer, F. Wübbeling, Mathematical methods in image reconstruction, Society for Industrial and Applied Mathematics, New York, 2001. |
[7] |
G. L. Zeng, Image reconstruction—a tutorial, Comput. Med. Imag. Grap., 25 (2001), 97–103. https://doi.org/10.1016/S0895-6111(00)00059-8 doi: 10.1016/S0895-6111(00)00059-8
![]() |
[8] | J. I. Goldstein, D. E. Newbury, J. R. Michael, N. W. M. Ritchie, J. H. J. Scott, D. C. Joy, X-Rays, in Scanning Electron Microscopy and X-Ray Microanalysis, Springer, (2018), 39–63. https://doi.org/10.1007/978-1-4939-6676-9_4 |
[9] | P. Toft, The Radon Transform-Theory and Implementation, Ph.D thesis, Technical University of Denmark in Copenhagen, 1996. |
[10] | A. Rahman, System of linear equations in Computed Tomography (CT), Bachelor's thesis, Brac University in Dacca, 2018. |
[11] | G. T. Herman, Fundamentals of Computerized Tomography: Image Reconstruction from Projections, Springer Science & Business Media, Berlin, 2009. |
[12] |
Y. Censor, G. T. Herman, M. Jiang, A note on the behavior of the randomized Kaczmarz algorithm of Strohmer and Vershynin, J. Fourier Anal. Appl., 15 (2009), 431–436. https://doi.org/10.1007/s00041-009-9077-x doi: 10.1007/s00041-009-9077-x
![]() |
[13] | O. Axelsson, Iterative Solution Methods, Cambridge University Press, Cambridge, 1996. |
[14] | I. Gohberg, I. A. Fel_dman, Convolution Equations and Projection Methods for Their Solution, American Mathematical Soc., Providence, 2005. |
[15] | Z. Z. Bai, C. H. Jin, Column-decomposed relaxation methods for the overdetermined systems of linear equations, Int. J. Appl. Mat. Com.-Pol., 13 (2003), 71–82. |
[16] | S. Kaczmarz, Angenäherte auflösung von systemen linearer glei-chungen, Bull. Int. Acad. Pol. Sci. Lett. Class. Sci. Math. Nat., (1937), 355–357. |
[17] | M. Brooks, A Survey of Algebraic Algorithms in Computerized Tomography, Master's Thesis, University of Ontario Institute of Technology in Oshawa, 2010. |
[18] |
Y. Censor, Parallel application of block-iterative methods in medical imaging and radiation therapy, Math. Program., 42 (1988), 307–325. https://doi.org/10.1007/BF01589408 doi: 10.1007/BF01589408
![]() |
[19] |
C. Byrne, A unified treatment of some iterative algorithms in signal processing and image reconstruction, Inverse Probl., 20 (20031), 103. https://doi.org/10.1088/0266-5611/20/1/006 doi: 10.1088/0266-5611/20/1/006
![]() |
[20] | D. A. Lorenz, S. Wenger, F. Schöpfer, M. Magnor, A sparse Kaczmarz solver and a linearized Bregman method for online compressed sensing, in 2014 IEEE International Conference on Image Processing (ICIP), (2014), 1347–1351. https://doi.org/10.1109/ICIP.2014.7025269 |
[21] |
J. D. Moorman, T. K. Tu, D. Molitor, D. Needell, Randomized Kaczmarz with averaging, BIT Numer. Math., 61 (2021), 337–359. https://doi.org/10.1007/s10543-020-00824-1 doi: 10.1007/s10543-020-00824-1
![]() |
[22] |
T. Strohmer, R. Vershynin, A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl., 15 (2009), 262–278. https://doi.org/10.1007/s00041-008-9030-4 doi: 10.1007/s00041-008-9030-4
![]() |
[23] | A. Zouzias, N. M. Freris, Randomized extended Kaczmarz for solving least squares, SIAM J. Matrix Anal. A., 34 (2013), 773–793. |
[24] | K. Du, X. H. Sun, Pseudoinverse-free randomized block iterative algorithms for consistent and inconsistent linear systems, preprint, arXiv: 2011.10353. |
[25] |
D. Needell, J. A. Tropp, Paved with good intentions: analysis of a randomized block Kaczmarz method, Linear Algebra Appl., 441 (2014), 199–221. https://doi.org/10.1016/j.laa.2012.12.022 doi: 10.1016/j.laa.2012.12.022
![]() |
[26] |
Z Z. Bai, W. T. Wu, On relaxed greedy randomized Kaczmarz methods for solving large sparse linear systems, Appl. Math. Lett., 83 (2018), 21–26. https://doi.org/10.1016/j.aml.2018.03.008 doi: 10.1016/j.aml.2018.03.008
![]() |
[27] |
Z Z. Bai, W. T. Wu, On greedy randomized Kaczmarz method for solving large sparse linear systems, SIAM J. Sci. Comput., 40 (2018), A592–A606. https://doi.org/10.1137/17M1137747 doi: 10.1137/17M1137747
![]() |
[28] |
E. Rebrova, D. Needell, On block Gaussian sketching for the Kaczmarz method, Numer. Algor., 86 (2021), 443–473. https://doi.org/10.1007/s11075-020-00895-9 doi: 10.1007/s11075-020-00895-9
![]() |
[29] |
Y. Q. Niu, B. Zheng, A greedy block Kaczmarz algorithm for solving large-scale linear systems, Appl. Math. Lett., 104 (2020), 106294. https://doi.org/10.1016/j.aml.2020.106294 doi: 10.1016/j.aml.2020.106294
![]() |
[30] |
I. Necoara, Faster randomized block Kaczmarz algorithms, SIAM J. Matrix Anal. A., 40 (2019), 1425–1452. https://doi.org/10.1137/19M1251643 doi: 10.1137/19M1251643
![]() |
[31] |
T. Elfving, Block-iterative methods for consistent and inconsistent linear equations, Numer. Math., 35 (1980), 1–12. https://doi.org/10.1007/BF01396365 doi: 10.1007/BF01396365
![]() |
[32] |
D. P. Woodruff, Sketching as a tool for numerical linear algebra, Found. Trends Theor. Comput. Sci., 10 (2014), 1–157. http://doi.org/10.1561/0400000060 doi: 10.1561/0400000060
![]() |
[33] |
Y. Zhang, H. Li, L. Tang, Greedy randomized sampling nonlinear Kaczmarz methods, Calcolo, 61 (2024). https://doi.org/10.1007/s10092-024-00577-1 doi: 10.1007/s10092-024-00577-1
![]() |
[34] |
J. Zhang, Y. Wang, J. Zhao, On maximum residual nonlinear Kaczmarz-type algorithms for large nonlinear systems of equations, J. Comput. Appl. Math., 425 (2023), 115065. https://doi.org/10.1016/j.cam.2023.115065 doi: 10.1016/j.cam.2023.115065
![]() |
[35] |
T. Li, T. J. Kao, D. Isaacson, J. C. Newell, G. J. Saulnier, Adaptive Kaczmarz method for image reconstruction in electrical impedance tomography, Physiol. Meas., 34 (2013), 595. https://doi.org/10.1088/0967-3334/34/6/595 doi: 10.1088/0967-3334/34/6/595
![]() |
[36] | M. B. Cohen, C. Musco, C. Musco, Input sparsity time low-rank approximation via ridge leverage score sampling, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, (2017), 1758–1777. https://doi.org/10.1137/1.9781611974782.115 |
[37] | A. Rudi, D. Calandriello, L. Carratino, L. Rosasco, On fast leverage score sampling and optimal learning, Adv. Neural Inform. Process. Syst., 31 (2018). |
[38] |
Y. Zhang, H. Li, A count sketch maximal weighted residual Kaczmarz method for solving highly overdetermined linear systems, Appl. Math. Comput., 410 (2021), 126486. https://doi.org/10.1016/j.amc.2021.126486 doi: 10.1016/j.amc.2021.126486
![]() |
[39] |
Y. Jiang, G. Wu, L. Jiang, A semi-randomized Kaczmarz method with simple random sampling for large-scale linear systems, Adv. Comput. Math., 49 (2023). https://doi.org/10.1007/s10444-023-10018-2 doi: 10.1007/s10444-023-10018-2
![]() |
[40] | G. Wu, Q. Chang, A semi-randomized block Kaczmarz method with simple random sampling for large-scale linear systems with multiple right-hand sides, preprint, arXiv: 2212.08797. |