[ Search | Site Map | Contact ]

Center for Scientific Computation and Mathematical Modeling

Research Activities > Programs > Sparse Representation in Redundant Systems > Vladimir Temlyakov


Sparse Representation in Redundant Systems


CSIC Building (#406), Seminar Room 4122.
Directions: home.cscamm.umd.edu/directions


On Greedy Algorithms with Restricted Depth Search1

 

Dr. Vladimir Temlyakov

Department of Mathematics, University of South Carolina


Abstract:   We continue to study effeciency of approximation and convergence of greedy type algorithms in uniformly smooth Banach spaces. This talk is based on a development of recent results in the direction of making practical algorithms out of theoretical approximation methods. The Weak Chebyshev Greedy Algorithm (WCGA) is a general approximation method that works well in an arbitrary uniformly smooth Banach space X for any dictionary D. It is an inductive procedure with each step of implementation consisting of several substeps. We describe the first substep of a particular case of the WCGA. Let t ε (0, 1]. Then at the first substep of the mth step we are looking for an element φm from a given symmetric dictionary D satisfying

(1)  Ffm-1m) ≥ t sup Ffm-1(g)
                         g ε D

where fm-1 is a residual after (m-1)th step and Ffm-1 is a norming functional of fm-1. It is a greedy step of the WCGA. It is clear that in the case of infinite dictionary D there is no direct computationally feasible way of evaluating supgεDFfm-1(g). This is the main issue that we address in the talk. We consider countable dictionaries D = {±ψj}j=1 to ∞  and replace the inequality used above by

 Ffm-1m) ≥ t sup       | Ffm-1j)|,  φm ε {±ψj}j=1 to Nm
                 1 ≤ jNm

The restriction j ≤ Nm is known in the literature as the depth search condition. We prove convergence and rate of convergence results for such a modification of the WCGA.

1This research was supported by the National Science Foundation Grant DMS 0200187

[LECTURE SLIDES]