Research Activities > Programs >
Sparse Representation in Redundant Systems
>
Vladimir Temlyakov
|
|
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-1(φm) ≥
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-1(φm) ≥
t sup | Ffm-1(ψj)|,
φm
ε
{±ψj}j=1 to Nm
1 ≤ j ≤ Nm
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]
|
|
|
