Lower estimations of pure greedy algorithm with shrinkage

Existing studies on the PGA have established its sharp convergence rate. Among its variants, the PGA with Shrinkage was shown in previous research to admit an upper bound, which may indeed be sharp. Motivated by this conjecture, we construct a worst-case dictionary and an initial iterate to derive a lower bound for the residual of the PGA with Shrinkage. The generally recognized optimal rate of greedy algorithms for arbitrary dictionaies and f A₁ (D) is m^-1/2. Our main results demonstrate that for every s₀ s 1 where s₀ = 0. 33, the PGA with Shrinkage achieves its sharp convergence rate. We also obtain a lower estimate for 0< s< s₀, but there is a gap between the existing upper bound. Notably, for every 0< s 1 the rate of the PGA with Shrinkage is bounded below by m^- where 0. 18< <0. 37, which is suboptimal. Finally, we complete the proof of the upper bound theorem of the PGA with Shrinkage to establish a comprehensive convergence rate characterization.