Loading [MathJax]/jax/output/SVG/jax.js
Research article Special Issues

Faster free pseudoinverse greedy block Kaczmarz method for image recovery

  • 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

    Related Papers:

    [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Ω,un=ν,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 d2. 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 (d3) without significant modifications.

    The variational formulation of the model problem (1.1) is as follows: Find an unknown function uH2(Ω) satisfying u|Ω=ξ and un|Ω=ν, and the following equation

    2i,j=1(2iju,2ijv)=(f,v),vH20(Ω), (1.2)

    where 2ij denotes the second order partial derivative with respect to xi and xj, and H20(Ω)={vH2(Ω):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 s0 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 v0L2(T), vbL2(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 vgR2 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}:v0L2(T),vbL2(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 vW(T), 2ij,wv is defined as a bounded linear functional on H2(T), given by:

    (2ij,wv,φ)T=(v0,2jiφ)Tvbni,jφT+vgi,φnjT,φH2(T),

    where n, with components ni(i=1,2), represents the unit outward normal vector to T.

    For any non-negative integer r0, 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 vW(T), 2ij,w,r,Tv is the unique polynomial in Pr(T) satisfying

    (2ij,w,r,Tv,φ)T=(v0,2jiφ)Tvbni,jφT+vgi,φnjT,φPr(T). (2.1)

    For a smooth v0H2(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(vbv0)ni,jφT+vgiiv0,φnjT, (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 TTh, let hT be its diameter, and define the mesh size as h=maxTThhT.

    Let k, p and q be integers such that kpq1. For any element TTh, the local weak finite element space is defined as:

    V(k,p,q,T)={{v0,vb,vg}:v0Pk(T),vbPp(e),vg[Pq(e)]2,eT}.

    By combining the local spaces V(k,p,q,T) across all elements TTh 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}|TV(k,p,q,T),TTh}.

    The subspace of Vh consisting of functions with vanishing boundary values on Ω is defined as:

    V0h={vVh: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 TTh, as:

    (2ij,wv)|T=2ij,w,r,T(v|T),TTh.

    On each element TTh, let Q0 denote the L2 projection onto Pk(T). On each edge eT, let Qb and Qn denote the L2 projection operators onto Pp(e) and Pq(e), respectively. For any wH2(Ω), 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)},TTh.

    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ξ, ugn=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)=TTh2i,j=1(2ij,wuh,2ij,wv)T,
    (f,v0)=TTh(f,v0)T.

    Recall that Th is a shape-regular finite element partition of the domain Ω. Consequently, for any TTh and ϕH1(T), the following trace inequality holds [8]:

    ϕ2TC(h1Tϕ2T+hTϕ2T). (4.1)

    If ϕ is a polynomial on the element TTh, a simpler form of the trace inequality applies [8]:

    ϕ2TCh1Tϕ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:

    v2,h=(TTh2i,j=12ijv02T+h3Tv0vb2T+h1Tv0vg2T)12. (4.4)

    Lemma 4.1. For v={v0,vb,vg}Vh, there exists a constant C such that for i,j=1,2,

    2ijv0TC2ij,wvT.

    Proof. Let TTh 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)=1hTAXni,

    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 ˆTT such that ΦBρ0 for some constant ρ0>0.

    For v={v0,vb,vg}Vh, let r=2N+k2 and choose φ=ΦB2ijv0Pr(T) in (2.2). This yields:

    (2ij,wv,ΦB2ijv0)T=(2ijv0,ΦB2ijv0)T(vbv0)ni,j(ΦB2ijv0)T+vgiiv0,ΦB2ijv0njT=(2ijv0,ΦB2ijv0)T, (4.5)

    where we applied ΦB=0 on T.

    Using the domain inverse inequality [8], there exists a constant C such that

    (2ijv0,ΦB2ijv0)TC(2ijv0,2ijv0)T. (4.6)

    By applying the Cauchy-Schwarz inequality to (4.5) and (4.6), we obtain

    (2ijv0,2ijv0)TC(2ij,wv,ΦB2ijv0)TC2ij,wvTΦB2ijv0TC2ij,wvT2ijv0T,

    which implies:

    2ijv0TC2ij,wvT.

    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 ˆTT 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+k2.

    By constructing an edge-based bubble function,

    φek=Πi=1,,N,ikl2i(x),

    it can be easily verified that 1) φek=0 on each edge ei for ik, and 2) there exists a subdomain ^ekek such that φekρ1 for some constant ρ1>0. Let φ=(vbv0)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 ik, and 3) φ=(v0vb)(lk)φek=O((v0vb)φekhTC) on ek, where C is a constant vector.

    Lemma 4.2. [9] For {v0,vb,vg}Vh, let φ=(vbv0)lkφek. The following inequality holds:

    φ2TChTek(vbv0)2ds. (4.7)

    Lemma 4.3. For {v0,vb,vg}Vh, let φ=(vgiiv0)φek. The following inequality holds:

    φ2TChTek(vgiiv0)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 HR2 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 φ=(vgiiv0)φek. Then,

    φ2T=Tφ2dT=T((vgiiv0)(X)φek)2dTChTek((vgiiv0)(Projek(X))φek)2dTChTek(vgiiv0)2ds,

    where we used the facts that 1) φek=0 on each edge ei for ik, 2) there exists a subdomain ^ekek 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:

    C1v2,h|||v|||C2v2,h. (4.9)

    Proof. Consider the edge-based bubble function defined as

    φek=Πi=1,,N,ikl2i(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 φ=(vbv0)lkφek into (2.2), we obtain

    (2ij,wv,φ)T=(2ijv0,φ)T(vbv0)ni,jφT+vgiiv0,φnjT=(2ijv0,φ)T+Ch1Tek|vbv0|2φekds, (4.10)

    where we used 1) φ=0 on each edge ei for i=1, , N, 2) φ=0 on each edge ei for ik, and 3) φ=(v0vb)(lk)φek=O((v0vb)φekhTC) on ek, where C is a constant vector.

    Recall that 1) φek=0 on each edge ei for ik, and 2) there exists a subdomain ^ekek 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|vbv0|2dsCek|vbv0|2φekdsChT(2ij,wvT+2ijv0T)φTCh32T(2ij,wvT+2ijv0T)(ek|vbv0|2ds)12,

    which, from Lemma 4.1, leads to:

    h3Tek|vbv0|2dsC(2ij,wv2T+2ijv02T)C2ij,wv2T. (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 φ=(vgiiv0)φek into (2.2), we obtain:

    (2ij,wv,φ)T=(2ijv0,φ)T(vbv0)ni,jφT+vgiiv0,φnjT=(2ijv0,φ)T(vbv0)ni,jφT+ek|vgiiv0|2φekds, (4.12)

    where we used φek=0 on edge ei for ik, and the fact that there exists a sub-domain ^ekek 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|vgiiv0|2dsCek|vgiiv0|2φekdsC(2ij,wvT+2ijv0T)φT+Cv0vbTjϕTCh12T(2ij,wvT+2ijv0T)(ek|vgiiv0|2ds)12+Ch32T2ij,wvTh1T(ek|vgiiv0|2ds)12.

    Applying Lemma 4.1, gives

    h1Tek|vgiiv0|2dsC(2ij,wv2T+2ijv02T)C2ij,wv2T. (4.13)

    Using Lemma 4.1, Eqs (4.11), (4.13), (4.3) and (4.4), we deduce:

    C1v2,h|||v|||.

    Finally, using the Cauchy-Schwarz inequality, inverse inequalities, and the trace inequality (4.2) in (2.2), we derive:

    |(2ij,wv,φ)T|2ijv0TφT+(vbv0)niTjφT+vgiiv0TφnjT2ijv0TφT+h32Tvbv0TφT+h12Tvgiiv0TφT,

    which gives:

    2ij,wv2TC(2ijv02T+h3Tvbv02T+h1Tvgiiv02T),

    and further gives

    |||v|||C2v2,h.

    This completes the proof.

    Theorem 4.5. The WG scheme 3.1 admits a unique solution.

    Proof. Assume that u(1)hVh and u(2)hVh are two distinct solutions of the WG scheme 3.1. Define ηh=u(1)hu(2)hV0h. Then, ηh satisfies

    (2ij,wηh,2ij,wv)=0,vV0h.

    Choosing v=ηh yields |||ηh|||=0. From the equivalence of norms in (4.9), it follows that ηh2,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 ηh0 in Ω. Thus, u(1)hu(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),uH2(T). (5.1)

    Proof. For any uH2(T), using (2.2), we have

    (2ij,wu,φ)T=(2iju,φ)T(u|Tu|T)ni,jφT+(u|T)ii(u|T),φnjT=(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 uhVh its numerical approximation obtained from the WG scheme 3.1. The error function, denoted by eh, is defined as

    eh=uuh. (5.2)

    Lemma 5.2. The error function eh defined in (5.2) satisfies the following error equation:

    (2weh,2wv)=(u,v),vV0h, (5.3)

    where

    (u,v)=TTh2i,j=1(vbv0)ni,j((QrI)2iju)T+vgiiv0,(QrI)2ijunjT.

    Proof. Using (5.1), standard integration by parts, and substituting φ=Qr2iju into (2.2), we obtain

    TTh2i,j=1(2ij,wu,2ij,wv)T=TTh2i,j=1(Qr2iju,2ij,wv)T=TTh2i,j=1(2ijv0,Qr2iju)T(vbv0)ni,j(Qr2iju)T+vgiiv0,Qr2ijunjT=TTh2i,j=1(2ijv0,2iju)T(vbv0)ni,j(Qr2iju)T+vgiiv0,Qr2ijunjT=TTh2i,j=1((2ij)2u,v0)T+2iju,iv0njTj(2iju)ni,v0T(vbv0)ni,j(Qr2iju)T+vgiiv0,Qr2ijunjT=(f,v0)+TTh2i,j=1(vbv0)ni,j((QrI)2iju)T+vgiiv0,(QrI)2ijunjT, (5.4)

    where we used (1.1), 2ijv0Pk2(T) and r=2N+k2k2, TTh2i,j=12iju,vginjT=TTh2i,j=12iju,vginjΩ=0 since vgi=0 on Ω, and TTh2i,j=1j(2iju)ni,vbT=TTh2i,j=1j(2iju)ni,vbΩ=0 since vb=0 on Ω.

    Subtracting (3.1) from (5.4) yields

    TTh2i,j=1(2ij,weh,2ij,wv)T=TTh2i,j=1(vbv0)ni,j((QrI)2iju)T+vgiiv0,(QrI)2ijunjT.

    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 0s2 and 1mk, the following estimates hold:

    TTh2i,j=1h2sT2ijuQr2iju2s,TCh2(m1)u2m+1, (6.1)
    TThh2sTuQ0u2s,TCh2(m+1)u2m+1. (6.2)

    Lemma 6.2. If uHk+1(Ω), then there exists a constant C such that

    |||uQhu|||Chk1uk+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):

    TTh2i,j=1(2ij,w(uQhu),φ)T=TTh2i,j=1(2ij(uQ0u),φ)T(Q0uQbu)ni,jφT+(iuQn(iu))i(uQ0u),φnjT(TTh2i,j=12ij(uQ0u)2T)12(TThφ2T)12+(TTh2i=1(Q0uQbu)ni2T)12(TTh2j=1jφ2T)12+(TTh2i=1i(Q0u)Qn(iu)2T)12(TTh2j=1φnj2T)12(TTh2i,j=12ij(uQ0u)2T)12(TThφ2T)12+(TThh1TQ0uuT+hTQ0uu21,T)12(TThh3Tφ2T)12+(TTh2i=1h1Ti(Q0u)iu2T+hTi(Q0u)iu21,T)12(TThh1Tφ2T)12Chk1uk+1(TThφ2T)12.

    Letting φ=2ij,w(uQhu) gives

    TTh2i,j=1(2ij,w(uQhu),2ij,w(uQhu))TChk1uk+1|||uQhu|||.

    This completes the proof.

    Theorem 6.3. Suppose the exact solution u of the biharmonic equation (1.1) satisfies uHk+1(Ω). Then, the error estimate satisfies:

    |||uuh|||Chk1uk+1. (6.4)

    Proof. Note that r1. 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

    |TTh2i,j=1(vbv0)ni,j((QrI)2iju)T|C(TTh2i=1h3T(vbv0)ni2T)12(TTh2i,j=1h3Tj((QrI)2iju)2T)12Cv2,h(TTh2i,j=1h2Tj((QrI)2iju)2T+h4Tj((QrI)2iju)21,T)12Chk1uk+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

    |TTh2i,j=1vgiiv0,(QrI)2ijunjT|C(TTh2i=1h1Tvgiiv02T)12(TTh2i,j=1hT(QrI)2ijunj2T)12Cv2,h(TTh2i,j=1(QrI)2ijunj2T+h2T(QrI)2ijunj21,T)12Cv2,hhk1uk+1Chk1uk+1|||v|||. (6.6)

    Substituting (6.5) and (6.6) into (5.3) gives

    (2ij,weh,2ij,wv)Chk1uk+1|||v|||. (6.7)

    Using Cauchy-Schwarz inequality, letting v=Qhuuh in (6.7), the error estimate (6.3) gives

    |||uuh|||2=TTh2i,j=1(2ij,w(uuh),2ij,w(uQhu))T+(2ij,w(uuh),2ij,w(Qhuuh))T|||uuh||||||uQhu|||+Chk1uk+1|||Qhuuh||||||uuh||||||uQhu|||+Chk1uk+1(|||Qhuu|||+|||uuh|||)|||uuh||||||uQhu|||+Chk1uk+1hk1uk+1+Chk1uk+1|||uuh|||,

    which further gives

    |||uuh||||||uQhu|||+Chk1uk+1Chk1uk+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=uuh={e0,eb,eg}, and we define ζh=Qhuuh={ζ0,ζb,ζg}V0h. Consider the dual problem associated with the biharmonic equation (1.1), which seeks a function wH20(Ω) satisfying:

    Δ2w=ζ0,in Ω,w=0,on Ω,wn=0,on Ω. (7.1)

    We assume the following regularity condition for the dual problem:

    w4Cζ0. (7.2)

    Theorem 7.1. Let uHk+1(Ω) be the exact solution of the biharmonic equation (1.1), and let uhVh 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

    e0Chk+1uk+1.

    Proof. Testing the dual problem (7.1) with ζ0 and applying integration by parts, we derive:

    ζ02=(Δ2w,ζ0)=TTh2i,j=1(2ijw,2ijζ0)T2ijw,iζ0njT+j(2ijw)ni,ζ0T=TTh2i,j=1(2ijw,2ijζ0)T2ijw,(iζ0ζgi)njT+j(2ijw)ni,ζ0ζbT, (7.3)

    where we used TTh2i,j=12ijw,ζginjT=2i,j=12ijw,ζginjΩ=0 due to ζg=0 on Ω, and TTh2i,j=1j(2ijw)ni,ζbT=2i,j=1j(2ijw)ni,ζbΩ=0 due to ζb=0 on Ω.

    Letting u=w and v=ζh in (5.4) gives

    TTh2i,j=1(2ij,ww,2ij,wζh)T=TTh2i,j=1(2ijw,2ijζ0)T(ζbζ0)ni,j(Qr2ijw)T+ζgiiζ0,Qr2ijwnjT,

    which is equivalent to

    TTh2i,j=1(2ijw,2ijζ0)T=TTh2i,j=1(2ij,ww,2ij,wζh)T+(ζbζ0)ni,j(Qr2ijw)Tζgiiζ0,Qr2ijwnjT.

    Substituting the above equation into (7.3) and using (5.3) gives

    ζ02=TTh2i,j=1(2ij,ww,2ij,wζh)T+(ζbζ0)ni,j((QrI)2ijw)Tζgiiζ0,(QrI)2ijwnjT=TTh2i,j=1(2ij,ww,2ij,weh)T+(2ij,ww,2ij,w(Qhuu))T(w,ζh)=TTh2i,j=1(2ij,wQhw,2ij,weh)T+(2ij,w(wQhw),2ij,weh)T+(2ij,ww,2ij,w(Qhuu))T(w,ζh)=(u,Qhw)+TTh2i,j=1(2ij,w(wQhw),2ij,weh)T+(2ij,ww,2ij,w(Qhuu))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)|TTh2i,j=1(QbwQ0w)ni,j((QrI)2iju)T+Qn(iw)iQ0w,(QrI)2ijunjT|(TTh2i=1(QbwQ0w)ni2T)12(TTh2i,j=1j((QrI)2iju)2T)12+(TTh2i=1Qn(iw)iQ0w2T)12(TTh2i,j=1(QrI)2ijunj2T)12(TThh1TwQ0w2T+hTwQ0w21,T)12(TTh2i,j=1h1Tj((QrI)2iju)2T+hTj((QrI)2iju)21,T)12+(TTh2i=1h1TiwiQ0w2T+hTiwiQ0w21,T)12(TTh2i,j=1h1T(QrI)2ijunj2T+hT(QrI)2ijunj21,T)12Chk+1uk+1w4. (7.5)

    For J2, using Cauchy-Schwarz inequality, (6.3) with k=3 and (6.4) gives

    J2|||wQhw||||||eh|||Chk1uk+1h2w4Chk+1uk+1w4. (7.6)

    For J3, denote by Q1 a L2 projection onto P1(T). Using (2.1) gives

    (2ij,w(Qhuu),Q12ij,ww)T=(Q0uu,2ji(Q12ij,ww))TQbuu,j(Q12ij,ww)T+Qn(iu)iu,Q12ij,wwnjT=0, (7.7)

    where we used 2ji(Q12ij,ww)=0, j(Q12ij,ww)=C and the property of the projection operators Qb and Qn and pq1.

    Using (7.7), Cauchy-Schwarz inequality, (5.1) and (6.3), gives

    J3|TTh2i,j=1(2ij,ww,2ij,w(Qhuu))T|=|TTh2i,j=1(2ij,wwQ12ij,ww,2ij,w(Qhuu))T|=|TTh2i,j=1(Qr2ijwQ1Qr2ijw,2ij,w(Qhuu))T|(TTh2i,j=1Qr2ijwQ1Qr2ijw2T)12|||Qhuu|||Chk+1uk+1w4. (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)|TTh2i,j=1(ζbζ0)ni,j((QrI)2ijw)T+ζgiiζ0,(QrI)2ijwnjT|(TTh2i=1(ζbζ0)ni2T)12(TTh2i,j=1j((QrI)2ijw)2T)12+(TTh2i=1ζgiiζ02T)12(TTh2i,j=1(QrI)2ijwnj2T)12(TTh2i,j=1h2Tj((QrI)2ijw)2T+h4Tj((QrI)2ijw)21,T)12(TThh3Tζ0ζb2T)12+(TTh2i,j=1(QrI)2ijwnj2T+h2T(QrI)2ijwnj21,T)12(TTh2i=1h1Tζgiiζ02T)12Ch2w4|||ζh|||Ch2w4(|||uuh|||+|||uQhu|||)Chk+1w4uk+1. (7.9)

    Substituting (7.5), (7.6), (7.8) and (7.9) into (7.4), and using (7.2), gives

    ζ02Chk+1w4uk+1Chk+1uk+1ζ0.

    This gives

    ζ0Chk+1uk+1,

    which, using the triangle inequality and (6.2) with m=k and s=0, gives

    e0ζ0+uQ0uChk+1uk+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.
  • Reader Comments
  • © 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(1141) PDF downloads(48) Cited by(0)

Figures and Tables

Figures(2)  /  Tables(4)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog