| Математический сборник |
|
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье) Скорость сходимости пороговых жадных алгоритмов В. Н. Темляковabcd a Математический институт им. В. А. Стеклова Российской академии наук, г. Москва b Московский государственный университет имени М. В. Ломоносова c Московский центр фундаментальной и прикладной математики d University of South Carolina, Columbia, SC, USA
Англоязычная версия:
Sbornik: Mathematics, 2024, Volume 215, Issue 2, Pages DOI: https://doi.org/10.4213/sm9926e 
Реферативные базы данных:
     § 1. ВведениеЭта работа является продолжением совсем недавней работы [14], где мы нашли скорость сходимости некоторых стандартных жадных алгоритмов по произвольным словарям. Новый аспект работы [14] состоит в том, что мы оценивали ошибку приближения произведением двух норм: нормы $f$ и $A_1$-нормы $f$. Обычно используется только $A_1$-норма $f$. В этой работе мы сосредоточены на специальном классе словарей, а именно, на различных типах базисов: жадные базисы, безусловные базисы и квазижадные базисы. Мы изучаем скорость сходимости классического порогового жадного алгоритма по базисам в стиле работы [14]. Здесь мы рассматриваем приближение в равномерно гладких банаховых пространствах. Для банахова пространства $X$ определяем модуль гладкости
$$
\begin{equation*}
\rho(u):=\rho(u,X):=\sup_{\|x\|=\|y\|=1}\biggl(\frac{1}{2}(\|x+uy\|+\|x-uy\|)-1\biggr).
\end{equation*}
\notag
$$
Равномерно гладкое банахово пространство – это пространство, удовлетворяющее соотношению Здесь мы изучаем случай $X=L_p$. Пусть $\Omega$ – компакт в $\mathbb R^d$ с определенной на нем вероятностной мерой $\mu$. Под $L_p$ нормой, $1\leqslant p< \infty$, функции, определенной на $\Omega$, мы понимаем
$$
\begin{equation*}
\|f\|_p:=\|f\|_{L_p(\Omega,\mu)}:=\biggl(\int_\Omega |f|^p\,d\mu\biggr)^{1/p}.
\end{equation*}
\notag
$$
Под нормой $L_\infty$ мы понимаем равномерную норму непрерывных функций
$$
\begin{equation*}
\|f\|_\infty:=\max_{\mathbf x\in\Omega} |f(\mathbf x)|
\end{equation*}
\notag
$$
и иногда пишем (с некоторым отклонением от стандартного обозначения) $L_\infty(\Omega)$ вместо $\mathcal C(\Omega)$ для множества непрерывных на $\Omega$ функций. Хорошо известно (см., например, [3; лемма B.1]), что в случае $X=L_p$, $1\leqslant p < \infty$, мы имеем
$$
\begin{equation}
\rho(u,L_p) \leqslant \begin{cases} \dfrac{u^p}{p} & \text{для } 1\leqslant p\leqslant 2 , \\ \dfrac{(p-1)u^2}2 & \text{для } 2\leqslant p<\infty. \end{cases}
\end{equation}
\tag{1.1}
$$
Говорим, что множество элементов (функций) $\mathcal D$ из $X$ является словарем, если каждый элемент $g\in \mathcal D$ имеет норму, не превосходящую единицу ($\|g\|\leqslant 1$), и $\overline{\operatorname{span}}\, \mathcal D=X$. Определим наилучшее $m$-членное приближение по $\mathcal D$ следующим образом:
$$
\begin{equation*}
\sigma_m(f):=\sigma_m(f,\mathcal D)_X:=\inf_{g_1,\dots,g_m} \inf_{c_k} \biggl\|f -\sum_{k=1}^m c_kg_k\biggr\|_X,
\end{equation*}
\notag
$$
где инфимум берется по коэффициентам $c_k$ и множествам из $m$ элементов $g_1,\dots,g_m$, $g_i\in\mathcal D$, $i=1,\dots,m$. Пусть $\mathcal D^\pm:=\{\pm g\colon g\in \mathcal D\}$. Обозначим $A_1(\mathcal D)$ замыкание выпуклой оболочки $\mathcal D^\pm$. Для $f\in X$ определим следующую норму:
$$
\begin{equation*}
\|f\|_{A_1(\mathcal D)}:=\inf \biggl\{M\colon \frac fM\in A_1(\mathcal D)\biggr\}.
\end{equation*}
\notag
$$
Ясно, что $\|f\|_X\leqslant \|f\|_{A_1(\mathcal D)}$. Следующий результат является следствием известных результатов о жадных приближениях (см. [14; замечание 3.2]). Предложение 1.1. Пусть $X$ – равномерно гладкое банахово пространство с $\rho(u,X) \leqslant \gamma u^q$, $1<q\leqslant 2$. Тогда для любого словаря $\mathcal D$ и любого $\alpha \in [0,1]$ для всех $f\in X$ таких, что $\|f\|_{A_1(\mathcal D)} <\infty$, $f\neq 0$, имеем Обозначим $p^*:=\min(p,2)$. Тогда предложение 1.1 и соотношение (1.1) влекут Следствие 1.1. Пусть $1<p<\infty$. Тогда для любого словаря $\mathcal D\subset L_p(\Omega,\mu)$ и любого $\alpha \in [0,1]$ для всех $f\in L_p(\Omega,\mu)$ таких, что $\|f\|_{A_1(\mathcal D)} <\infty$, $f\neq 0$, имеем Пусть дано банахово пространство $X$ с базисом (базисом Шаудера) $\Psi=\{\psi_k\}_{k=1}^\infty$. Предположим, что $0<c_0\leqslant \|\psi_k\|_X\leqslant 1$, $k=1,2,\dots$, и рассмотрим следующий теоретический жадный алгоритм. Для заданного элемента $f\in X$ рассмотрим разложение Для элемента $f\in X$ говорим, что перестановка $\varrho$ натуральных чисел является убывающей, если
$$
\begin{equation}
|c_{k_1}(f,\Psi) |\geqslant |c_{k_2}(f,\Psi) | \geqslant \dotsb ,
\end{equation}
\tag{1.5}
$$
где $\varrho(j)=k_j$, $j=1,2,\dots$, и пишем $\varrho \in D(f)$. Если неравенства в (1.5) строгие, то $D(f)$ состоит лишь из одной перестановки. Определим $m$-е жадное приближение $f$ по базису $\Psi$, которое соответствует перестановке $\varrho \in D(f)$, формулой
$$
\begin{equation*}
G_m(f):=G_m(f,\Psi):=G_m(f,\Psi,\varrho):=\sum_{j=1}^m c_{k_j}(f,\Psi)\psi_{k_j}.
\end{equation*}
\notag
$$
Алгоритм $G_m(\cdot,\Psi)$, определенный выше, является простым алгоритмом, который описывает теоретическую схему для $m$-членных приближений элемента $f$. Название этого алгоритма – пороговый жадный алгоритм (ПЖА) (thresholding greedy algorithm (TGA)) или просто жадный алгоритм (ЖА) (greedy algorithm (GA)). Для того чтобы понять эффективность этого алгоритма, мы сравниваем его точность с наилучшей возможной точностью, когда приближаем линейными комбинациями из $m$ элементов базиса $\Psi$. Самое большее, чего мы можем достичь с алгоритмом $G_m$, это или несколько слабее
$$
\begin{equation}
\|f-G_m(f,\Psi,\varrho)\|_X \leqslant G\sigma_m(f,\Psi)_X,
\end{equation}
\tag{1.6}
$$
для всех элементов $f\in X$ с константой $G=C(X,\Psi)$, независящей от $f$ и $m$. Ясно, что, когда $X=H$ – это гильбертово пространство и $\mathcal B$ – это ортонормированный базис, мы имеем
$$
\begin{equation*}
\|f-G_m(f,\mathcal B,\varrho)\|_H=\sigma_m(f,\mathcal B)_H.
\end{equation*}
\notag
$$
Рассмотрим следующую асимптотическую характеристику ПЖА по заданному базису $\Psi$:
$$
\begin{equation*}
\gamma_m(\alpha,X,\Psi):=\sup_{f\in X\colon \|f\|_{A_1(\Psi)}<\infty,\,f\neq 0}\, \sup_{\varrho\in D(f)} \frac{\|f-G_m(f,\Psi,\varrho)\|_X}{\|f\|_X^{1-\alpha} \|f\|_{A_1(\Psi)}^\alpha}, \qquad \alpha\in [0,1].
\end{equation*}
\notag
$$
В основном мы изучаем случай $X=L_p$, $1\leqslant p\leqslant \infty$. В этом случае мы пишем $\gamma_m(\alpha,p,\Psi)$. Следующее понятие жадного базиса (greedy basis) было введено в [6]. Определение 1.1. Называем $\Psi$ жадным базисом, если для каждого $f\in X$ существует перестановка $\varrho \in D(f)$ такая, что с константой $C$, независящей от $f$ и $m$. Известно (см. [6]), что для жадного базиса $\Psi$ неравенство (1.7) выполняется для всех перестановок $\varrho \in D(f)$. Следовательно, определение 1.1 и следствие 1.1 влекут следующие оценки для жадных базисов. Теорема 1.1. Пусть $1<p<\infty$. Тогда для любого жадного базиса $\Psi$ в $L_p(\Omega,\mu)$ и любого $\alpha \in [0,1]$ имеем В настоящей работе мы развиваем теорему 1.1 в различных направлениях. В § 3 мы рассматриваем базис Хаара, который является жадным базисом в $L_p$, $1<p<\infty$ (см. [9]). Мы находим правильный порядок величины $\gamma_m(\alpha,L_p([0,1],\mu),\Psi)$ в том случае, когда $\Psi$ является базисом Хаара $\mathcal H_p$ и $\mu=\lambda$ является мерой Лебега. Полученные оценки лучше, чем соответствующие оценки в теореме 1.1 в случае $2<p<\infty$. Читатель может найти результаты о жадных приближениях гладких функций многих переменных по базисам, подобным базису Хаара, в работах [10] и [11]. Мы также рассматриваем базисы, которые не являются жадными базисами. В § 2 мы находим правильный порядок величины $\gamma_m(\alpha,L_p(\mathbb T^d,\lambda),\Psi)$ в случае, когда $\Psi$ является тригонометрической системой. Читатель может найти обзор результатов по скорости убывания наилучших $m$-членных тригонометрических приближений гладких функций многих переменных в [13; гл. 9]. Известно (см. [6]), что жадные базисы – это в точности те базисы, которые одновременно являются и безусловными, и демократическими (см. определения ниже, в § 3). В § 3 (см. теоремы 3.1 и 3.2) мы доказываем, что теорема 1.1 остается справедливой при условии, что $\Psi$ – это безусловный базис. В п. 3.2 мы обсуждаем более широкий класс базисов, чем класс безусловных базисов – класс квазижадных базисов. Оказалось, что теорема 1.1 может быть расширена на класс квазижадных базисов (см. теорему 3.5 ниже). Наконец, в п. 3.2 мы доказываем, что некоторые оценки ошибок можно улучшить для подкласса квазижадных базисов, а именно, для равномерно ограниченных квазижадных базисов. Мы обозначаем $C$, $C(p,d)$ и т.д. различные постоянные с аргументами, указывающими, от каких параметров они зависят. Для краткости используем следующие обозначения. Для двух неотрицательных последовательностей $a=\{a_n\}_{n=1}^\infty$ и $b=\{b_n\}_{n=1}^\infty$ соотношение (порядковое неравенство) $a_n \ll b_n$ означает, что существует число $C(a,b)$ такое, что для всех $n$ имеем $ a_n\leqslant C(a,b)b_n$, а соотношение $a_n\asymp b_n$ означает, что $a_n\ll b_n$ и $b_n\ll a_n$. § 2. Тригонометрическая системаВ этом параграфе мы рассматриваем случай $X=L_p({\mathbb T}^d,\lambda)$, $1\leqslant p \leqslant \infty$, $\lambda$ – нормированная мера Лебега на $\mathbb T^d$, $\Psi={\mathcal T}^d:= \{e^{i(\mathbf k,\mathbf x)}\}_{\mathbf k\in {\mathbb Z}^d}$ – тригонометрическая система. Для нас удобно работать с комплексной тригонометрической системой. Результаты этого параграфа остаются справедливыми и для действительной тригонометрической системы. Более того, отметим, что мы можем использовать общие результаты, полученные для действительных банаховых пространств и действительной тригонометрической системы, и вывести из этих результатов соответствующие результаты для комплексной тригонометрической системы. Обозначим
$$
\begin{equation*}
\|f\|_{A_1(\mathcal T^d)}:=\sum_{\mathbf k\in \mathbb Z^d} |\widehat f(\mathbf k)|, \qquad \widehat f(\mathbf k):=(2\pi)^{-d}\int_{\mathbb T^d} f(\mathbf x)e^{-i(\mathbf k,\mathbf x)}\,d\mathbf x.
\end{equation*}
\notag
$$
Следующая теорема 2.1 известна (см. [8] и [12; с. 25, теорема 2.2.1]). Начнем со случая $2\leqslant p< \infty$. Доказательство. Верхняя оценка следует из теоремы 2.1 и следствия 1.1. Сейчас мы докажем нижнюю оценку. Понятно, что достаточно провести доказательство в случае $d=1$. Мы используем полиномы Рудина–Шапиро (см., например, [12; приложение, п. 7.4]):
$$
\begin{equation}
{\mathcal R}_m(x)=\sum_{|k| \leqslant m} \epsilon_k e^{ikx}, \qquad \epsilon_k=\pm 1, \quad x \in \mathbb T,
\end{equation}
\tag{2.1}
$$
которые удовлетворяют оценке с абсолютной постоянной $C_1$. Для $s=\pm 1$ обозначим Пусть $s=\pm 1$ таково, что $|\Lambda_s| > |\Lambda_{-s}|$. Тогда $|\Lambda_{-s}|\leqslant m$. Пусть $G_m(\mathcal R_m)$ будет реализацией ПЖА, примененного к $f=\mathcal R_m$, содержащее все гармоники из $\Lambda_{-s}$ и, может быть, некоторые гармоники из $\Lambda_s$. Обозначим $f_m:=\mathcal R_m - G_m(\mathcal R_m)$. Тогда все гармоники $f_m$ содержатся в $\Lambda_s$, и, следовательно, С помощью неравенства Никольского для тригонометрических полиномов (см. [12; приложение, с. 253, теорема 7.5.4]) соотношение (2.3) влечет
$$
\begin{equation}
\|f_m\|_p \geqslant C_2m^{-1/p}\|f_m\|_\infty \geqslant C_2m^{1-1/p} .
\end{equation}
\tag{2.4}
$$
Понятно, что Сравнивая (2.2), (2.4) и (2.5), мы получаем требуемые в случае $2 \leqslant p < \infty$ оценки. Теорема доказана. Следующее утверждение может представлять независимый интерес. Следствие 2.1. Пусть $2\leqslant p< \infty$. Тогда для любой $f\in L_p$ и каждого $m\in \mathbb{N}$ имеем Действительно, это вытекает из теоремы 2.2 с $\alpha=2h(p)$ и из наблюдения о том, что постоянная в оценке сверху в теореме 2.2 может зависеть только от $p$. Перейдем к случаю $1\leqslant p\leqslant 2$. Доказательство. Начнем с оценок сверху. В случае $1<p\leqslant 2$ мы можем действовать так же, как в доказательстве теоремы 2.2, и применить теорему 2.1 и следствие 1.1. Это дает
$$
\begin{equation*}
\gamma_m(\alpha,p,\mathcal T^d) \leqslant C(p) m^{h(p)-\alpha/p'}, \qquad p':=\frac{p}{p-1}.
\end{equation*}
\notag
$$
Ясно, что для всех $\alpha\in(0,1]$ и $p<2$ имеем Следовательно, нужна другая аргументация. Обозначим $f_m:=f-G_m(f,\mathcal T^d)$. Тогда по теореме 2.1 получаем Нам нужна следующая хорошо известная простая лемма из [7; с. 92] (см. [2; п. 7.4], где обсуждается история).
Лемма 2.1. Пусть $a_1\geqslant a_2\geqslant \cdots \geqslant a_M\geqslant 0$ и $1\leqslant q\leqslant p\leqslant \infty$. Тогда для всех $m\leqslant M$ имеем По лемме 2.1 с $q=1$ и $p=2$ получаем
$$
\begin{equation}
\|f_m\|_p \leqslant \|f_m\|_2 \leqslant m^{-1/2}\|f\|_{A_1(\mathcal T^d)}.
\end{equation}
\tag{2.7}
$$
Записывая $\|f_m\|_p=\|f_m\|_p^{1-\alpha}\|f_m\|_p^\alpha$ и используя (2.6) и (2.7), получаем верхнюю оценку с абсолютной постоянной в качестве дополнительного множителя. Докажем нижние оценки. Воспользуемся ядрами Валле Пуссена (см., например, [12; приложение, п. 7.4]), определенными для $m=1,2,\dots$ как
$$
\begin{equation}
\mathcal V_m(x):=\frac {1}{m} \sum_{l=m}^{2m-1} \mathcal D_l(x) , \qquad \mathcal D_l(x):= \sum_{|k|\leqslant l} e^{ikx}, \qquad x \in \mathbb T.
\end{equation}
\tag{2.8}
$$
Известно (см., например, [12; приложение, с. 246, (7.4.14)]), что
$$
\begin{equation}
\|\mathcal V_m\|_p \leqslant Cm^{1-1/p} , \qquad m=1,2,\dots , \quad 1 \leqslant p \leqslant \infty .
\end{equation}
\tag{2.9}
$$
Воспользуемся обозначениями из приведенного выше доказательства теоремы 2.2. Пусть $G_m(\mathcal V_m)$ будет реализацией ПЖА, примененного к $f=\mathcal V_m$, содержащей все гармоники из $\Lambda_{-s}$ и, может быть, некоторые гармоники из $\Lambda_s$. Обозначим $f_m:=\mathcal V_m - G_m(\mathcal V_m)$. Тогда оценка снизу для $\|f_m\|_p$ вытекает из соотношений
$$
\begin{equation*}
m \leqslant |\langle f_m,{\mathcal R}_m\rangle | \leqslant \|f_m\|_p \|{\mathcal R}_m\|_{p'} \leqslant C_1m^{1/2}\|f_m\|_p .
\end{equation*}
\notag
$$
Получаем Понятно, что Отметим, что легко проверить, что в действительности $\|\mathcal V_{m}\|_{A_1(\mathcal T)}= 3m$. Соотношения (2.9), (2.11) и (2.10) влекут требуемое неравенство в случае $1 \leqslant p \leqslant 2$. Доказательство теоремы 2.3 завершено. Следствие 2.2. Пусть $1\leqslant p\leqslant 2$. Тогда для всякой $f\in L_p$ и каждого $m\in \mathbb{N}$ имеем § 3. Безусловные и квазижадные базисыНапомним, что мы предполагаем, что $\Psi:=\{\psi_n\}_{n=1}^\infty$ является базисом (базисом Шаудера) банахова пространства $X$, удовлетворяющим условию $\|\psi_n\|_X \,{\leqslant}\, 1$, $n=1,2,\dots$ . 3.1. Безусловные базисыИмеются различные эквивалентные определения понятия безусловный базис (см., например, [12; п. 1.4]). Нам удобны следующие два эквивалентные определения. Воспользуемся представлением (I). $\Psi$ является безусловным базисом, если для любого подмножества целых чисел $\Lambda\subset \mathbb{N}$ существует ограниченная линейная проекция $P_\Lambda$, определенная как
$$
\begin{equation*}
P_\Lambda(f):=\sum_{n\in \Lambda} c_n(f)\psi_n, \qquad K:=K(\Psi):=\sup_\Lambda\|P_\Lambda\| <\infty .
\end{equation*}
\notag
$$
(II). $\Psi$ является безусловным базисом, если для каждого набора знаков $\theta:=\{\theta_n\}_{n=1}^\infty$ имеем ограниченный линейный оператор $M_\theta$, определенный как и $\sup_\theta\|M_\theta\|<\infty$.Хорошо известно, что безусловный базис $\Psi$ пространства $L_p(\Omega,\mu)$, $1\,{<}\,p\,{<}\,\infty$, обладает следующими свойствами. U1. Существуют две положительные постоянные $C_i(\Psi,p)$, $i=1,2$, такие, что для любой $f\in L_p(\Omega,\mu)$ имеем
$$
\begin{equation*}
C_1(\Psi,p) \|f\|_p \leqslant \|S(f,\Psi)\|_p \leqslant C_2(\Psi,p) \|f\|_p, \qquad S(f,\Psi):=\biggl( \sum_{n=1}^\infty |c_n(f)\psi_n|^2\biggr)^{1/2}.
\end{equation*}
\notag
$$
U2. Свойство U1 влечет следующие неравенства. Пусть $p^*:=\min(p,2)$, тогда для $f\in L_p(\Omega,\mu)$ имеем
$$
\begin{equation*}
\|f\|_p \leqslant C_3(\Psi,p) \biggl(\sum_{n=1}^\infty \|c_n(f)\psi_n\|_p^{p^*}\biggr)^{1/p^*}, \qquad 1<p<\infty.
\end{equation*}
\notag
$$
Теорема 3.1. Пусть $2\leqslant p < \infty$, и пусть $\Psi$ – безусловный базис в $L_p(\Omega,\mu)$. Тогда Доказательство. По определению (I) получаем для $f_m:=f-G_m(f,\Psi)$ Свойство U2 влечет
$$
\begin{equation}
\|f_m\|_p \leqslant C_3(\Psi,p) \biggl(\sum_{n\notin \Lambda_m(f)} \|c_n(f)\psi_n\|_p^{2}\biggr)^{1/2} \leqslant C_3(\Psi,p) \biggl(\sum_{n\notin \Lambda_m(f)} |c_n(f)|^{2}\biggr)^{1/2},
\end{equation}
\tag{3.2}
$$
где $\Lambda_m(f)$ таково, что
$$
\begin{equation*}
\min_{n\in \Lambda_m(f)}|c_n(f)| \geqslant \max_{n\notin \Lambda_m(f)}|c_n(f)|.
\end{equation*}
\notag
$$
Следовательно, по лемме 2.1 неравенство (3.2) влечет
$$
\begin{equation}
\|f_m\|_p \leqslant C_3(\Psi,p) m^{-1/2}\|f\|_{A_1(\Psi)}.
\end{equation}
\tag{3.3}
$$
Записывая $\|f_m\|_p=\|f_m\|_p^{1-\alpha}\|f_m\|_p^\alpha$ и используя (3.1) и (3.3), получаем требуемое в теореме 3.1 неравенство. Теорема доказана. Теорема 3.2. Пусть $1< p \leqslant 2$, и пусть $\Psi$ – безусловный базис в $L_p(\Omega,\mu)$. Тогда Доказательство. Это доказательство проводится так же, как и доказательство теоремы 3.1. Мы укажем только те места, где используется другая аргументация. Вместо (3.2) благодаря свойству U2 получим
$$
\begin{equation}
\|f_m\|_p \leqslant C_3(\Psi,p) \biggl(\sum_{n\notin \Lambda_m(f)} \|c_n(f)\psi_n\|_p^{p}\biggr)^{1/p} \leqslant C_3(\Psi,p) \biggl(\sum_{n\notin \Lambda_m(f)} |c_n(f)|^{p}\biggr)^{1/p}.
\end{equation}
\tag{3.4}
$$
По лемме 2.1 с $q=1$ неравенство (3.4) влечет
$$
\begin{equation}
\|f_m\|_p \leqslant C_3(\Psi,p) m^{-(1-1/p)}\|f\|_{A_1(\Psi)}.
\end{equation}
\tag{3.5}
$$
Записывая $\|f_m\|_p=\|f_m\|_p^{1-\alpha}\|f_m\|_p^\alpha$ и используя (3.1) и (3.5), получаем требуемое в теореме 3.2 неравенство. Теорема доказана. Обозначим $\mathcal H:=\{H_k\}_{k=1}^\infty$ базис Хаара на $[0,1)$, нормированный в $L_2([0,1],\lambda)$ по мере Лебега $\lambda$: $H_1=1$ на $[0,1)$ и для $k=2^n +l$, $n=0,1,\dots$, $l=1,2,\dots,2^n$
$$
\begin{equation*}
H_k=\begin{cases} 2^{n/2}, & x \in [(2l-2)2^{-n-1}, (2l-1)2^{-n-1}), \\ -2^{n/2}, & x \in [(2l-1)2^{-n-1}, 2l2^{-n-1}), \\ 0 & \text{для других }x. \end{cases}
\end{equation*}
\notag
$$
Обозначим $\mathcal H_p:=\{H_{k,p}\}_{k=1}^\infty$ базис Хаара $\mathcal H$, нормированный в $L_p([0,1],\lambda)$. Хорошо известно, что базис Хаара $\mathcal H_p$ является безусловным базисом в $L_p([0,1],\lambda)$, $1<p<\infty$ (см., например, [5]). Сейчас мы покажем, что теорема 3.1 может быть усилена для базиса Хаара. Доказательство. Базис Хаара является безусловным базисом в случае $1<p<\infty$, и, следовательно, Мы используем лемму 3.1 (см. ниже), которая справедлива для квазижадного базиса, что является более слабым условием, чем безусловность базиса. По лемме 3.1 получаем
$$
\begin{equation}
\|f_m\|_p \leqslant C_2(p) \sum_{n=m+1}^\infty a_n(f)\varphi(n)\frac{1}{n},
\end{equation}
\tag{3.7}
$$
где $\varphi(n)$ – фундаментальная функция базиса Хаара $\mathcal H_p$. В [9] (см. также [12; с. 35, лемма 2.3.3]) было доказано, что
$$
\begin{equation}
\varphi(n,\mathcal H_p,L_p([0,1],\lambda)) \leqslant C_3(p) n^{1/p}, \qquad 1<p<\infty.
\end{equation}
\tag{3.8}
$$
Соотношения (3.7) и (3.8) влекут
$$
\begin{equation}
\|f_m\|_p \leqslant C_4(p) m^{1/p-1}\|f\|_{A_1(\mathcal H_p)}.
\end{equation}
\tag{3.9}
$$
Оценки (3.6) и (3.9) влекут оценки сверху в теореме 3.3.
Докажем оценки снизу. Для заданного $m\in \mathbb{N}$ определим Тогда по (3.8)
$$
\begin{equation}
\|f\|_p \leqslant C_3(p) (2m)^{1/p}, \qquad 1<p<\infty.
\end{equation}
\tag{3.10}
$$
Для любой реализации $G_m(f,\mathcal H_p)$ алгоритма ПЖА по [12; лемма 2.3.4], получим
$$
\begin{equation}
\|f-G_m(f,\mathcal H_p)\|_p \geqslant C_5(p) m^{1/p}.
\end{equation}
\tag{3.11}
$$
Ясно, что Объединение соотношений (3.10)–(3.12) доказывает оценки снизу в теореме 3.3. Теорема доказана. Говорим, что $\Psi=\{\psi_k\}_{k=1}^\infty$ $L_p$-эквивалентен $\Phi=\{\phi_k\}_{k=1}^\infty$, если для любого конечного множества $\Lambda$ и любых коэффициентов $c_k$, $k\in \Lambda$, имеем
$$
\begin{equation}
C_1(p,\Psi,\Phi) \biggl\|\sum_{k\in \Lambda}c_k\phi_k\biggr\|_{p} \leqslant \biggl\|\sum_{k\in \Lambda}c_k\psi_k\biggr\|_{p} \leqslant C_2(p,\Psi,\Phi) \biggl\|\sum_{k\in \Lambda}c_k\phi_k\biggr\|_{p}
\end{equation}
\tag{3.13}
$$
с двумя положительными постоянными $C_1(p,\Psi,\Phi), C_2(p,\Psi,\Phi)$, которые могут зависеть от $p$, $\Psi$ и $\Phi$. Достаточные условия на $\Psi$ для $L_p$-эквивалентности базису Хаара $\mathcal H_p$ можно найти в [4] и [1]. Замечание 3.1. Теорема 3.3 справедлива для любого базиса $\Psi$, который $L_p$-эквивалентен базису Хаара $\mathcal H_p$. 3.2. Квазижадные базисыПусть, как и выше, $X$ – бесконечномерное сепарабельное банахово пространство с нормой $\|\cdot\|:=\|\cdot\|_X$, и пусть $\Psi:=\{\psi_k \}_{k=1}^{\infty}$ будет полунормированным (semi-normalized) базисом в $X$ ($0<c_0\leqslant\|\psi_k\|\leqslant 1$, $k\in {\mathbb N}$). В этом пункте мы уделяем особое внимание более широкому классу базисов, чем класс безусловных базисов – классу квазижадных базисов. Понятие квазижадного базиса было введено в [6]. Читатель может найти детальное обсуждение квазижадных базисов в [12; гл. 3]. Определение 3.1. Базис $\Psi$ называется квазижадным базисом пространства $X$, если существует постоянная $C=C(\Psi,X)$ такая, что Позднее, П. Войташчик (Wojtaszczyk) в [16] доказал, что это в точности те базисы, для которых ПЖА сходится: Сейчас мы сформулируем некоторые известные результаты, которые полезны для наших приложений. Для заданного элемента $f\in X$ рассмотрим разложение Пусть последовательность натуральных чисел $k_j,j=1,2,\dots,$ такова, что Воспользуемся обозначением для убывающей перестановки коэффициентов элемента $f$.Следующая теорема получена в [15] (см. также [12; с. 70, теорема 3.2.10]). Отметим, что в случае $p=2$ теорема 3.4 была доказана в [16]. Теорема 3.4. Пусть $\Psi=\{\psi_k\}_{k=1}^\infty$ – квазижадный базис пространства $L_p$, $1<p<\infty$. Тогда существуют положительные постоянные $C_i=C_i(p,\Psi)$, $i=1,\dots,4$, такие, что для каждой $f\in L_p$ имеем Определим фундаментальную функцию $\varphi(m):=\varphi(m,\Psi,X)$ базиса $\Psi$ в $X$ как
$$
\begin{equation*}
\varphi(m,\Psi,X):=\sup_{|A|\leqslant m}\biggl\|\sum_{k\in A}\psi_k\biggr\|.
\end{equation*}
\notag
$$
Определение 3.2. Говорим, что базис $\Psi=\{\psi_k\}_{k=1}^\infty$ является демократическим базисом в $X$, если существует постоянная $D:=D(X,\Psi)$ такая, что для любых двух конечных множеств индексов $P$ и $Q$ с одинаковым количеством элементов ($|P|=|Q|$) имеем Следующая лемма 3.1 была доказана в [12; с. 72] таким же образом, как и теорема 3.4. Теорема 3.5. Пусть $1<p<\infty$. Тогда для любого квазижадного базиса $\Psi$ в $L_p(\Omega,\mu)$ и любого $\alpha \in [0,1]$ имеем Доказательство. Доказательство основано на теореме 3.4. По определению 3.1 квазижадного базиса имеем для $f_m:=f- G_m(f,\Psi)$ По теореме 3.4 в случае $2\leqslant p <\infty$ получаем
$$
\begin{equation}
\|f_m\|_p\leqslant C_2 \sum_{n=m+1}^\infty n^{-1/2}a_n(f) \leqslant C_2m^{-1/2}\|f\|_{A_1(\Psi)}
\end{equation}
\tag{3.17}
$$
и в случае $1<p\leqslant 2$
$$
\begin{equation}
\|f_m\|_p\leqslant C_4 \sum_{n=m+1}^\infty n^{1/p-1}a_n(f) \leqslant C_4m^{1/p-1}\|f\|_{A_1(\Psi)}.
\end{equation}
\tag{3.18}
$$
Собирая вместе (3.16)–(3.18), получаем (3.15). Теорема доказана. Обсудим сейчас специальный подкласс квазижадных базисов, а именно, равномерно ограниченные квазижадные базисы. Существование равномерно ограниченных квазижадных базисов в $L_p([0,1],\lambda)$, $1<p<\infty$, известно (см. [12; с. 83, теорема 3.3.5 и с. 76, теорема 3.2.20]). Теорема 3.6. Пусть $1<p<\infty$. Тогда для любого равномерно ограниченного квазижадного базиса $\Psi$ в $L_p(\Omega,\mu)$ и любого $\alpha \in [0,1]$ имеем Доказательство. Верхние оценки могут быть доказаны точно так же, как была доказана теорема 3.5. Отметим, что в случае $2\leqslant p<\infty$ оценки сверху в теореме 3.6 непосредственно вытекают из теоремы 3.5. В случае $1<p\leqslant 2$ вместо теоремы 3.4 воспользуемся следующим предложением 3.1 (см. [12; с. 77, предложение 3.2.22]).
Предложение 3.1. Пусть $\Psi$ – равномерно ограниченный квазижадный базис $\Psi=\{\psi_j\}_{j=1}^\infty$ в $L_p$, $1<p<\infty$. Тогда для $f\in L_p$ имеем Докажем оценки снизу. Доказательство основано на следующем предложении 3.2 (см. [12; с. 76, предложение 3.2.21]). Предложение 3.2. Пусть $\Psi$ – равномерно ограниченный квазижадный базис $\Psi=\{\psi_j\}_{j=1}^\infty$ в $L_p$, $1<p<\infty$. Тогда $\Psi$ – демократический базис с фундаментальной функцией $\varphi(m,\Psi,L_p)\asymp m^{1/2}$. Предложение 3.2 означает (см. определение 3.2 выше), что существуют две положительные постоянные $c'(p,\Psi)$ и $C'(p,\Psi)$ такие, что для любого подмножества индексов $\Lambda$, $|\Lambda|=m$, имеем
$$
\begin{equation}
c'(p,\Psi) m^{1/2} \leqslant \biggl\|\sum_{k\in \Lambda} \psi_k\biggr\|_p \leqslant C'(p,\Psi) m^{1/2}.
\end{equation}
\tag{3.21}
$$
В качестве примера возьмем
$$
\begin{equation*}
f:=\sum_{k=1}^{2m} \psi_k, \qquad G_m(f,\Psi):=\sum_{k=1}^{m}\psi_k.
\end{equation*}
\notag
$$
Тогда имеем
$$
\begin{equation*}
\|f\|_p \leqslant C'(p,\Psi)(2m)^{1/2}, \qquad \|f-G_m(f,\Psi)\|_p \geqslant c'(p,\Psi)m^{1/2}, \qquad \|f\|_{A_1(\Psi)} \leqslant2m.
\end{equation*}
\notag
$$
Собирая воедино приведенные выше соотношения, получаем требуемые оценки снизу. Теорема 3.6 доказана. Замечание 3.2. В случае $2\leqslant p<\infty$ оценки снизу из теоремы 3.6 показывают, что теорема 3.5 точна в этом случае. § 4. Критерий для хорошей скорости приближенияЗдесь мы доказываем необходимые и достаточные условия на базис $\Psi$, которые обеспечивают хорошую скорость приближения элементов из $A_1(\Psi)$. Определим следующее свойство базиса $\Psi$. Безусловная оценка с параметрами $a$, $K$ ($\mathrm{UB}(a,K)$). Говорим, что базис $\Psi$ пространства $X$ удовлетворяет безусловной оценке с параметрами $a$, $K$, если для любого конечного множества $\Lambda\subset \mathbb{N}$ и любого набора знаков $\epsilon_k=\pm 1$, $k\in\Lambda$, имеем
$$
\begin{equation}
\biggl\|\sum_{k\in\Lambda} \epsilon_k\psi_k\biggr\|_X \leqslant K|\Lambda|^a.
\end{equation}
\tag{4.1}
$$
Ясно, что наше условие $\|\psi_k\|_X\leqslant 1$, $k=1,2,\dots$, гарантирует, что $\Psi$ удовлетворяет $\mathrm{UB}(1,1)$. Ограничим $a\in [0,1)$. Очевидно, что ортонормированный базис гильбертова пространства удовлетворяет $\mathrm{UB}(1/2,1)$. Есть и нетривиальные примеры базисов $\mathrm{UB}(a,K)$. Например, известно (см. [9], [12; гл. 2] и [13; гл. 8]), что для $1<p<\infty$ нормированный в $L_p$ базис Хаара функций одной переменной удовлетворяет $\mathrm{UB}(1/p,C(p))$. Читатель может найти обсуждение результатов о разреженной аппроксимации, в том числе исторические комментарии, в [13; гл. 9]. Теорема 4.1. (A) Пусть $b\in (0,1]$. Предположим, что $\Psi$ таков, что для любого $f\in A_1(\Psi)$ существует перестановка $\varrho \in D(f)$ со свойством Тогда $\Psi$ удовлетворяет $\mathrm{UB}(1-b,2)$. (B) Предположим, что $\Psi$ удовлетворяет $\mathrm{UB}(a,K)$, $a\in [0,1)$. Тогда для любого $f\in A_1(\Psi)$ и любой перестановки $\varrho \in D(f)$ имеем Доказательство. Во-первых, докажем п. (A). Введем некоторые обозначения. Для $m\,{\in}\,\mathbb{N}$ обозначим через $V(m)$ множество вершин единичного куба $[-1,1]^m$. Другими словами, $V(m)$ состоит из всех векторов $\mathbf v=(v_1,\dots,v_m)$ таких, что $v_j$ принимает значения $1$ или $-1$ для $j\,{=}\,1,\dots,m$. Для $\Lambda\,{=}\,\{k_j\}_{j=1}^m \,{\subset}\, \mathbb{N}$ и $\mathbf v \in V(m)$ обозначим Для заданных $\Lambda$ и $\mathbf v$ рассмотрим элемент где $\delta>0$, $Q\subset \mathbb{N}$ таковы, что $|Q|=m$ и $\Lambda\cap Q=\varnothing$, $\mathbf u$ – произвольный вектор из $V(m)$, например, $\mathbf u=(1,\dots,1)$. Тогда $((2+\delta)m)^{-1}f \in A_1(\Psi)$ и Принимая во внимание, что $\delta>0$ произвольно, завершаем доказательство п. (A).
Во-вторых, докажем п. (B). Доказательство основано на следующей лемме 4.1. Лемма 4.1. Пусть $\Psi=\{\psi_k\}_{k=1}^\infty$ – базис в $X$, который удовлетворяет $\mathrm{UB}(a,K)$. Тогда для каждого $f\in X$ имеем где $a_n(f)$ определены в (3.14). Доказательство. Без потери общности предположим, что $f$ нормирован таким образом, что $a_1(f)< 1$. Обозначим ${\mathcal N}_s:=\{n\colon a_n(f)\geqslant 2^{-s}\}$, $s\in \mathbb{N}$, и $N_s:=|{\mathcal N}_s|$. Отметим, что для малых $s$ множества $\mathcal N_s$ могут быть пустыми. Понятно, что для непустого $\mathcal N_s$ выполнено $\mathcal N_s=[1,N_s]$. Имеем
$$
\begin{equation}
\|f\|_X \leqslant \sum_{s=1}^\infty\biggl\|\sum_{n\in {\mathcal N}_s\setminus{\mathcal N}_{s-1}}c_{k_n}(f)\psi_{k_n} \biggr\|_X.
\end{equation}
\tag{4.4}
$$
Наше предположение, что $\Psi$ удовлетворяет $\mathrm{UB}(a,K)$, влечет, что для любого конечного $\Lambda\subset \mathbb{N}$ и любых коэффициентов $b_k$, $k\in \Lambda$, имеем
$$
\begin{equation}
\biggl\|\sum_{k\in\Lambda} b_k\psi_k\biggr\|_X \leqslant \Bigl(\max_{k\in\Lambda}|b_k|\Bigr) K|\Lambda|^a.
\end{equation}
\tag{4.5}
$$
Действительно, пусть $\Lambda=\{k_j\}_{j=1}^n$ и
$$
\begin{equation*}
\mathbf w=(w_1,\dots,w_n), \qquad w_j:=b_{k_j}\Bigl(\max_{k\in\Lambda}|b_k|\Bigr)^{-1}, \qquad j=1,\dots,n.
\end{equation*}
\notag
$$
Тогда $\mathbf w \in [-1,1]^n$ и, следовательно, $\mathbf w$ является выпуклой комбинацией элементов из $V(n)$. Это доказывает (4.5). Используя (4.5), мы выводим из (4.4)
$$
\begin{equation}
\|f\|_X\leqslant 2K\sum_{s=1}^\infty2^{-s} |{\mathcal N}_s\setminus{\mathcal N}_{s-1}|^a,
\end{equation}
\tag{4.6}
$$
$$
\begin{equation}
\|f\|_X \leqslant 2K\sum_{s=1}^\infty 2^{-s}N_s^{a} \leqslant 2K\sum_{s=1}^\infty2^{-s}\sum_{n=1}^{N_s}n^{a-1}= 2K\sum_{n=1}^\infty n^{a-1}\sum_{s\colon N_s\geqslant n} 2^{-s}.
\end{equation}
\tag{4.7}
$$
Обозначим Тогда
$$
\begin{equation*}
\sum_{s\colon N_s\geqslant n} 2^{-s} \leqslant 2^{-s(n)+1}.
\end{equation*}
\notag
$$
Заметим, что для всех $s$ таких, что $N_s\geqslant n$, имеем Следовательно, из (4.7) находим Это завершает доказательство леммы 4.1. Завершим доказательство п. (B). Имеем
$$
\begin{equation*}
\|f-G_m(f,\Psi,\varrho)\|_X=\biggl\|\sum_{n=m+1}^\infty c_{k_n}(f)\psi_{k_n}\biggr\|_X
\end{equation*}
\notag
$$
и по лемме 4.1 продолжаем
$$
\begin{equation*}
\biggl\|\sum_{n=m+1}^\infty c_{k_n}(f)\psi_{k_n}\biggr\|_X\leqslant 4K\sum_{n=m+1}^\infty n^{a-1}a_n(f) \leqslant 4K m^{a-1}\|f\|_{A_1(\Psi)}.
\end{equation*}
\notag
$$
Доказательство теоремы 4.1 завершено. БлагодарностьАвтор признателен рецензенту за полезные замечания и предложения.
Цитирование в формате AMSBIB
\RBibitem{Tem24} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|