PaperlayerView exact revision on arXiv

Source-linked AI summary

On weak greedy algorithms

A. S. Spivak, V. N. Temlyakov

arXiv:2604.26064v1math.NAmath.FA

TL;DR

Weak greedy algorithms are usually studied for convergence over an entire space, while this paper addresses both weakness sequences and convergence on the smaller dictionary-associated class A1(D). It extends rate results to weakness sequences in Hilbert and uniformly smooth Banach spaces and gives convergence criteria for A1(D), including a necessary-and-sufficient condition for orthonormal bases. The main sequence-based rate results require monotonicity, which the authors identify as an unresolved restriction.

  • Problem

    The paper addresses the limited scalar-parameter treatment of weak greedy algorithms and the usual focus on convergence for all elements of a space rather than the subset A1(D).

  • Method

    The paper extends weak greedy rate analyses to weakness sequences in Hilbert and uniformly smooth Banach spaces and studies A1(D)-convergence for greedy algorithms.

  • Results

    The paper obtains sequence-based rate results and shows that, for orthonormal bases, a condition on the weakness sequence is necessary and sufficient for A1(D)-convergence; the criterion also governs convergence for all dictionaries.

  • Takeaways & Limitations

    Weak greedy convergence can be analyzed on the generalized octahedron A1(D), and in the paper’s all-dictionary setting the convergence and A1(D)-convergence criteria coincide.

  • Takeaways & Limitations

    The main new rate results require a monotone decreasing weakness sequence, and the authors leave removal of this assumption open.

Abstract

from arXiv · show

The main goal of this paper is twofold. First, we extend some results known in the case of weak greedy algorithms with a scalar parameter to the case of weak greedy algorithms with a weakness sequence. Second, we formulate a new setting of the problem of convergence of greedy algorithms. Usually, we are interested in convergence of an algorithm for all elements of the space. We suggest to study convergence of an algorithm for a subset, which is a generalized octahedron associated with a given dictionary.

1 Introduction

The paper extends weak greedy approximation results from a scalar weakness parameter to weakness sequences and studies convergence on the dictionary-dependent subset A1(D). It also introduces the relevant dictionary and algorithmic framework and highlights monotonicity as an assumption for key new results.

  • 1 Introduction: Weak greedy algorithms relax the optimal greedy selection inequality through a weakness parameter or sequence.The weakness sequence includes scalar weakness as the special case t_k=t.
  • 1 Introduction: The paper extends scalar-parameter results to weakness sequences and formulates convergence over A1(D), the generalized octahedron associated with a dictionary.A1(D) is the closure of the convex hull of the symmetrized dictionary.
  • 1 Introduction: The paper also studies connections between greedy algorithms and remote consecutive projections, presenting comments that complement an existing survey.The discussion appears in Section 5.
  • 1 Introduction: The new weakness-sequence results in Theorems 2.3 and 3.2 require the weakness sequence to be monotone.The authors state that removing this assumption remains open.
  • 1 Introduction: Theorem 5.8 bounds the residual in remote projections by the product of the norms of f and its A1(D)-norm.The paper identifies this as a new feature in the theory of remote projections.

2 Some results on the rate of convergence of the WGA(D, τ)

This section develops rate-of-convergence results for weak greedy algorithms in Hilbert spaces with weakness sequences, including parameterized and thresholding variants. The principal extensions assume nonincreasing weakness sequences and provide bounds that remain asymptotically close to scalar-parameter bounds when t_m tends to zero.

  • 2 Some results on the rate of convergence of the WGA(D, τ): The section introduces WGA(D,τ,b), a weak greedy algorithm with a weakness sequence τ and tuning parameter b.The original WGA(D,τ) is recovered when b=1.
  • 2 Some results on the rate of convergence of the WGA(D, τ): The rate results assume a nonincreasing weakness sequence and apply to functions in A1(D), with extensions also stated for arbitrary f and dictionaries.The section includes previously known scalar-parameter results alongside the sequence-based extensions.
  • 2 Some results on the rate of convergence of the WGA(D, τ): Theorem 2.3 extends a scalar-weakness convergence bound to a nonincreasing weakness sequence in Hilbert spaces.The result applies to any Hilbert space H.
  • 2 Some results on the rate of convergence of the WGA(D, τ): The bounds in (2.6) and (2.7) are asymptotically close when t_m tends to zero.
  • 2 Some results on the rate of convergence of the WGA(D, τ): Theorem 2.3 also applies to the Thresholding Weak Greedy Algorithm after replacing its greedy step.The proof uses only the greedy step needed for the stated inequality.

3 Some results on the rate of convergence of the DGA(τ, b, µ)

This section extends rate-of-convergence analysis from Hilbert spaces to uniformly smooth Banach spaces using a dual greedy algorithm governed by a weakness sequence, tuning parameter, and smoothness majorant. The results assume nonincreasing weakness sequences and power-type smoothness bounds.

  • 3 Some results on the rate of convergence of the DGA(τ, b, µ): The paper formulates the Banach-space results for dictionaries and elements in the generalized octahedron A1(D).A1(D) is treated as a natural geometrically defined class associated with the dictionary.
  • 3 Some results on the rate of convergence of the DGA(τ, b, µ): The DGA(τ,b,µ) is defined in uniformly smooth Banach spaces using a weakness sequence, parameter b, and majorant µ of the modulus of smoothness.The algorithm constructs residual and approximant sequences through greedy selection and a coefficient equation.
  • 3 Some results on the rate of convergence of the DGA(τ, b, µ): The Banach-space analysis uses the modulus of smoothness and its majorant to establish existence of the coefficient selected by the algorithm.The assumptions ensure the defining equation has a solution.
  • 3 Some results on the rate of convergence of the DGA(τ, b, µ): Theorem 3.1 gives a convergence rate for DGA(τ,b,µ) when ρ(u)≤γu^q with 1<q≤2 and τ is nonincreasing.The result is stated for f∈A1(D).
  • 3 Some results on the rate of convergence of the DGA(τ, b, µ): Theorem 3.2 extends the Banach-space rate bound to the weakness-sequence setting under the same power-type smoothness framework.The corresponding inequality also holds for the modified algorithm DGA(τ,b,µ)*.

4 Convergence of the Weak Thresholding Greedy Algorithm for A1(D)

The paper reframes convergence by asking whether weak greedy algorithms converge for every element of A1(D), rather than for the whole space. For an orthonormal basis in a Hilbert space, it gives a necessary and sufficient condition on the weakness sequence and extends the statement to suitable Banach-space bases.

  • 4 Convergence of the Weak Thresholding Greedy Algorithm for A1(D): The section studies convergence of greedy algorithms on A1(D) instead of the entire space X.It presents separate problems for a fixed dictionary and for all dictionaries.
  • 4 Convergence of the Weak Thresholding Greedy Algorithm for A1(D): For a Hilbert-space orthonormal basis, WTGA(τ), WGA(τ), and WOGA(τ) coincide.The equivalence is specific to the orthonormal-basis setting described.
  • 4 Convergence of the Weak Thresholding Greedy Algorithm for A1(D): Theorem 4.1 gives a necessary and sufficient condition on τ for WTGA(τ) to converge for every f∈A1(Ψ).The same theorem applies to WGA(τ) and WOGA(τ).
  • 4 Convergence of the Weak Thresholding Greedy Algorithm for A1(D): If the condition fails, a realization of WTGA(τ) does not converge for a constructed element f0∈A1(Ψ).
  • 4 Convergence of the Weak Thresholding Greedy Algorithm for A1(D): Theorem 4.1 extends to Banach-space bases whose basis elements have norms bounded above and below by positive constants.

5 Applications of weak greedy algorithms for remote consecutive projections

This section establishes the connection between weak greedy algorithms and remote consecutive projections, then transfers convergence results under weakness-sequence conditions. It also relates several projection algorithms to distinct approximation steps sharing a common greedy step.

  • Weak remote projections: WRPA iteratively projects onto selected subspaces, with each choice governed by the weakness sequence τ.The algorithm starts from x0 and forms xn as the projection onto Ln, where Ln satisfies a τ-dependent selection condition.
  • Weak remote projections: The condition ∩L∈L L = {0} makes the associated collection D(L) a dictionary whose span is dense in H.Each subspace L is associated with DL = L⊥ ∩ S(H), and D(L) is the union of these sets.
  • Greedy-projection correspondence: Relation (5.4) establishes a connection between WRPA(L, τ) and weak greedy algorithms.This connection allows weak-greedy convergence results to yield corresponding results for remote projections.
  • Convergence results: Theorems 5.2, 5.4, and 5.7 provide WRPA convergence results under stated conditions on the weakness sequence and, where applicable, the subsequence.These results assume ∩L∈L L = {0}; Theorem 5.7 uses the subsequence and weakness-sequence conditions of Theorem 5.6.
  • Convergence results: Theorem 5.6 generalizes earlier results, recovering Theorem 5.1 for nk = k and Theorem 5.5 for τ = τ(N, t).The generalization is obtained for a subsequence N and a weakness sequence τ satisfying its stated conditions.
  • Greedy-projection correspondence: Several greedy algorithms share the same greedy step while differing in their approximation steps, including WGA, WOGA, RGA, and thresholding-type algorithms.For remote projections, the greedy step with respect to subspaces is equivalent to a greedy step with respect to the dictionary D(L).

6 Discussion

The discussion establishes convergence criteria for weak greedy algorithms with weakness sequences, including convergence on A1(D), and compares these criteria across settings. It also identifies monotonicity as a key assumption and notes limits on improving the convergence-rate results.

  • Convergence notions: The paper distinguishes ordinary convergence for every f ∈ X from A1(D)-convergence restricted to f ∈ A1(D).The restricted setting is presented as a separate convergence problem for a given dictionary.
  • Convergence criteria: Finding necessary and sufficient convergence criteria for a specific greedy algorithm is difficult and has been solved only in a few cases.The discussion cites a criterion for WGA(τ) that covers all weakness sequences τ.
  • Comparison of criteria: The discussion contrasts the criterion for A1(D)-convergence with the criterion for convergence when the dictionary is an orthonormal basis.The two conditions are explicitly described as very different.
  • Scope and limitations: The most technically involved results assume a monotone decreasing weakness sequence, leaving rate-of-convergence results without monotonicity as an open direction.The authors also state that these results cannot be substantially improved and support this with a lower-bound example.
Loading 2604.26064v1…