Video Library
Most viewed videos

New in collection

You may need the following programs to see the files

International conference on Function Spaces and Approximation Theory dedicated to the 110th anniversary of S. M. Nikol'skii
May 27, 2015 10:00–10:40, Пленарные доклады, Moscow, Steklov Mathematical Institute of RAS

Sparse approximation with respect to the trigonometric system

V. N. Temlyakovab

a Steklov Mathematical Institute of Russian Academy of Sciences
b University of South Carolina, USA
Video records:
MP4 1,067.3 Mb
MP4 270.8 Mb
Adobe PDF 105.2 Kb

Number of views:
This page:259
Video files:130

V. N. Temlyakov
Photo Gallery

Видео не загружается в Ваш браузер:
  1. Установите Adobe Flash Player    

  2. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  3. Сообщите администратору портала о данной ошибке

Abstract: Sparse approximation with respect to dictionaries is a very important topic in the high-dimensional approximation. The main motivation for the study of sparse approximation is that many real world signals can be well approximated by sparse ones. Sparse approximation automatically implies a need for nonlinear approximation, in particular, for greedy approximation. We give a brief description of a sparse approximation problem and present a discussion of the obtained results and their relation to previous work. In a general setting we are working in a Banach space $X$ with a redundant system of elements $\mathcal D$ (dictionary $\mathcal D$). There is a solid justification of importance of a Banach space setting in numerical analysis in general and in sparse approximation in particular. Let $X$ be a real Banach space with norm $\|\cdot\|:=\|\cdot\|_X$. We say that a set of elements (functions) $\mathcal D$ from $X$ is a dictionary if each $g\in \mathcal D$ has norm one ($\|g\|=1$), and the closure of span $\mathcal D$ is $X$. A symmetrized dictionary is $\mathcal D^\pm:=\{\pm g:g\in \mathcal D\}$. For a nonzero element $g\in X$ we let $F_g$ denote a norming (peak) functional for $g$:
$$ \|F_g\|_{X^*} =1,\qquad F_g(g) =\|g\|_X. $$
The existence of such a functional is guaranteed by the Hahn-Banach theorem.
An element (function, signal) $s\in X$ is said to be $m$-sparse with respect to $\mathcal D$ if it has a representation $s=\sum_{i=1}^mc_ig_i$, $g_i\in \mathcal D$, $i=1,…,m$. The set of all $m$-sparse elements is denoted by $\Sigma_m(\mathcal D)$. For a given element $f$ we introduce the error of best $m$-term approximation
$$ \sigma_m(f,\mathcal D)_X := \inf_{s\in\Sigma_m(\mathcal D)} \|f-s\|_X. $$

Let $t\in (0,1]$ be a given nonnegative number. We define the Weak Chebyshev Greedy Algorithm (WCGA) that is a generalization for Banach spaces of Weak Orthogonal Greedy Algorithm .
Weak Chebyshev Greedy Algorithm (WCGA).
We define $f_0 := f$. Then for each $m\ge 1$ we inductively define
  • 1) $\varphi_m \in {\mathcal D}$ is any element satisfying
    $$ |F_{f_{m-1}}(\varphi_m)| \ge t\sup_{g\in {\mathcal D}} |F_{f_{m-1}}(g)|; $$

  • 2) define
    $$ \Phi_m := \operatorname{span} \{\varphi_j\}_{j=1}^m, $$
    and define $G_m $ to be the best approximant to $f$ from $\Phi_m$;
  • 3) denote
    $$ f_m := f-G_m. $$

We demonstrated that the Weak Chebyshev Greedy Algorithm (WCGA) is very good for $m$-term approximation with respect to a special class of dictionaries, in particular, for the trigonometric system. The trigonometric system is a classical system that is known to be difficult to study. We studied among other problems the problem of nonlinear sparse approximation with respect to it. Let ${\mathcal R}{\mathcal T}$ denote the real trigonometric system $1,\sin 2\pi x,\cos 2\pi x, …$ on $[0,1]$ and let ${\mathcal R}{\mathcal T}_p$ to be its version normalized in $L_p([0,1])$. Denote ${\mathcal R}{\mathcal T}_p^d := {\mathcal R}{\mathcal T}_p\times\cdots\times {\mathcal R}{\mathcal T}_p$ the $d$-variate trigonometric system. We need to consider the real trigonometric system because the algorithm WCGA is well studied for the real Banach space. We proved the following Lebesgue-type inequality for the WCGA.
Theorem. Let $\mathcal D$ be the normalized in $L_p$, $2\le p<\infty$, real $d$-variate trigonometric system. Then for any $f\in L_p$ the WCGA with weakness parameter $t$ gives
$$ \|f_{C(t,p,d)m\ln (m+1)}\|_p \le C\sigma_m(f,\mathcal D)_p . $$

The above Lebesgue-type inequality guarantees that the WCGA works very well for each individual function $f$.

Materials: abstract.pdf (105.2 Kb)

Language: English

SHARE: FaceBook Twitter Livejournal
Contact us:
 Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2018