A Counter-Example to the General Convergence of Partially Greedy Algorithms

Rémi GribonvalJ. Approx. Theory 2001 · OpenReview

Abstract

In a separable Hilbert space H<math><mtext>H</mtext></math>, greedy algorithms iteratively define m-term approximants to a given vector from a complete redundant dictionary D<math><mtext>D</mtext></math>. With very large dictionaries, the pure greedy algorithm cannot be implemented and must be replaced with a weak greedy algorithm. In numerical applications, partially greedy algorithms have been introduced to reduce the numerical complexity. A conjecture about their convergence arises naturally from the observation of numerical experiments. We introduce, study and disprove this conjecture.
BibTeX
@article{gribonval2001counter,
  author = {Rémi Gribonval},
  title = {{A Counter-Example to the General Convergence of Partially Greedy Algorithms}},
  journal = {J. Approx. Theory},
  year = {2001},
  url = {https://openreview.net/forum?id=HWTw0haS2R},
}

Loading related content...

Figure