| Математический сборник |
|
|
|
|
|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях) Разреженное восстановление в некоторых функциональных классах в интегральных нормах В. Н. Темляковabcd a Математический институт им. В. А. Стеклова Российской академии наук, г. Москва b Московский государственный университет имени М. В. Ломоносова c Московский центр фундаментальной и прикладной математики d University of South Carolina, Columbia, SC, USA
Англоязычная версия:
Sbornik: Mathematics, 2024, Volume 215, Issue 10, Pages DOI: https://doi.org/10.4213/sm10086e 
Реферативные базы данных:
    § 1. ВведениеЭта работа является продолжением работы [18]. Мы сформулируем результаты из [18], которые мы будем использовать в нашем анализе. Читатель может найти обсуждение предыдущих результатов, непосредственно связанных с результатами из [18] и из настоящей работы, в работе [18]. Результаты о дискретизации можно найти в недавних обзорах [2] и [10]. Начнем с краткого описания некоторых необходимых нам понятий разреженной аппроксимации. Пусть $X$ – банахово пространством с нормой $\|\cdot\|:=\|\cdot\|_X$, и пусть $\mathcal D=\{g_i\}_{i=1}^\infty $ – система (счетная) элементов из $X$. Для заданного подмножества $J\subset \mathbb N$ определяем $V_J(\mathcal D):=\operatorname{span}\{g_j\colon j\in J\}$. Для положительного целого числа $v$ определяем $\mathcal{X}_v(\mathcal D)$ как совокупность всех линейных подпространств $V_J(\mathcal D)$ с $|J|=v$. Обозначим $\Sigma_v(\mathcal D)$ множество всех $v$-членных приближений по $\mathcal D$: $\Sigma_v(\mathcal D):=\bigcup_{V\in\mathcal X_v(\mathcal D)} V$. Для $f\in X$ определим
$$
\begin{equation*}
\sigma_v(f,\mathcal D)_X:=\inf_{g\in\Sigma_v(\mathcal D)}\|f-g\|_X, \qquad v=1,2,\dots\,.
\end{equation*}
\notag
$$
Для функционального класса ${\mathbf F}\subset X$ определим
$$
\begin{equation*}
\sigma_v({\mathbf F},\mathcal D)_X:=\sup_{f\in{\mathbf F}} \sigma_v(f,\mathcal D)_X, \qquad \sigma_0({\mathbf F},\mathcal D)_X:=\sup_{f\in{\mathbf F}} \|f\|_X.
\end{equation*}
\notag
$$
В этой работе мы рассматриваем случай $X=L_p(\Omega,\mu)$, $1\leqslant p<\infty$. Точнее, пусть $\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
$$
В случае $X=L_p(\Omega,\mu)$ иногда для краткости мы пишем $\sigma_v(\cdot,\cdot)_p$ вместо $\sigma_v(\cdot,\cdot)_{L_p(\Omega,\mu)}$. Мы изучаем системы функций, которые имеют свойство универсальной дискретизации по значениям в точках. Определение 1.1. Пусть $1\leqslant p<\infty$. Говорим, что множество $\xi:=\{\xi^j\}_{j=1}^m \subset\Omega$ обеспечивает $L_p$-универсальную дискретизацию по выборке (по значениям в точках) для набора $\mathcal X:=\{X(n)\}_{n=1}^k$ конечномерных линейных подпространств $X(n)$, если Будем использовать краткую форму $L_p$-удв для $L_p$-универсальной дискретизации по выборке (1.1). Мы используем $C$, $C'$ и $c$, $c'$ для обозначения различных положительных постоянных. Их аргументы указывают параметры, от которых они могут зависеть. Обычно эти постоянные не зависят от функции $f$ и меняющихся параметров $m$, $v$, $u$. Для краткости используем следующие обозначения. Для двух неотрицательных последовательностей $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\gg b_n$ означает, что $b_n\ll a_n$, а $a_n\asymp b_n$ означает, что $a_n\ll b_n$ и $a_n \gg b_n$. Для действительного числа $x$ обозначим $[x]$ целую часть $x$, $\lceil x\rceil$ – наименьшее целое число, которое больше или равно $x$. Для множества $\xi$, состоящего из $m$ точек из $\Omega$, обозначим
$$
\begin{equation}
\Omega_m:=\xi:=\{\xi^1,\dots, \xi^m\}\subset \Omega, \qquad\mu_m:=\frac1{m}\sum_{j=1}^m \delta_{\xi^j}, \qquad\mu_\xi:= \frac{\mu+\mu_m}{2},
\end{equation}
\tag{1.2}
$$
где $\delta_{\mathbf x}$ обозначает меру Дирака в точке ${\mathbf x}$. Для удобства будем обозначать $\|\cdot\|_{L_p(\nu)}$ норму $L_p$, определенную по мере $\nu$ на $\Omega$. Иногда используем обозначение $\|\cdot\|_{p}$. Основная цель работы состоит в изучении оптимального восстановления на специальных классах функций многих переменных. Для функционального класса ${\mathbf F}\subset \mathcal C(\Omega)$ определим (см. [19])
$$
\begin{equation*}
\varrho_m^o({\mathbf F},L_p):=\inf_{\xi } \inf_{\mathcal M} \sup_{f\in {\mathbf F}}\|f-\mathcal M(f(\xi^1),\dots,f(\xi^m))\|_p,
\end{equation*}
\notag
$$
где $\mathcal M$ пробегает все отображения $\mathcal M \colon \mathbb C^m \to L_p(\Omega,\mu)$ и $\xi$ пробегает все подмножества $\{\xi^1,\dots,\xi^m\}$ из $m$ точек в $\Omega$. Мы используем индекс $o$, чтобы подчеркнуть оптимальность. В [18] мы изучали поведение $\varrho_m^o({\mathbf F},L_p)$ для нового вида классов – ${\mathbf A}^r_\beta(\Psi)$. Мы установили порядки $\varrho_m^o({\mathbf A}^r_\beta(\Psi),L_p)$ (с точностью до логарифмического по $m$ множителя) в случае $1\leqslant p\leqslant 2$ для класса равномерно ограниченных ортонормированных систем $\Psi$. Дадим определение классов ${\mathbf A}^r_\beta(\Psi)$. Для данного $1\leqslant p\leqslant \infty$ пусть $\Psi=\{\psi_{{\mathbf k}}\}_{{\mathbf k} \in \mathbb Z^d}$, $\psi_{\mathbf k} \in \mathcal C(\Omega)$, $\|\psi_{\mathbf k}\|_p \leqslant B$, ${\mathbf k}\in\mathbb Z^d$, – система в пространстве $L_p(\Omega,\mu)$. Рассмотрим функции, представимые в виде абсолютно сходящегося ряда
$$
\begin{equation}
f=\sum_{{\mathbf k}\in\mathbb Z^d} a_{\mathbf k}(f)\psi_{\mathbf k}, \qquad \sum_{{\mathbf k}\in\mathbb Z^d} |a_{\mathbf k}(f)|<\infty.
\end{equation}
\tag{1.3}
$$
Для $\beta \in (0,1]$ и $r>0$ рассмотрим следующий класс ${\mathbf A}^r_\beta(\Psi)$ функций $f$, которые имеют представление (1.3), удовлетворяющее следующим условиям:
$$
\begin{equation}
\biggl(\sum_{[2^{j-1}]\leqslant \|{\mathbf k}\|_\infty <2^j} |a_{\mathbf k}(f)|^\beta\biggr)^{1/\beta} \leqslant 2^{-rj}, \qquad j=0,1,\dots\, .
\end{equation}
\tag{1.4}
$$
В специальном случае, когда $\Psi$ – это тригонометрическая система $\mathcal T^d:=\{e^{i({\mathbf k},{\mathbf x})}\}_{{\mathbf k}\in \mathbb Z^d}$, мы доказали в [18] (см. теорема 4.6) следующую нижнюю оценку:
$$
\begin{equation}
\varrho_m^o({\mathbf A}^r_\beta(\mathcal T^d),L_1) \gg m^{1/2-1/\beta-r/d}.
\end{equation}
\tag{1.5}
$$
В [18] мы дополнили эту нижнюю оценку следующей оценкой сверху. Предположим, что $\Psi$ равномерно ограниченная, $\|\psi_{\mathbf k}\|_\infty \leqslant B$, ${\mathbf k}\in\mathbb Z^d$, ортонормированная система. Пусть $1\leqslant p\leqslant 2$, $\beta \in (0,1]$ и $r>0$, тогда
$$
\begin{equation}
\begin{aligned} \, \notag \varrho_{m}^{o}({\mathbf A}^r_\beta(\Psi),L_p(\Omega,\mu)) &\leqslant \varrho_{m}^{o}({\mathbf A}^r_\beta(\Psi),L_2(\Omega,\mu)) \\ &\ll (m(\log(m+1))^{-5})^{1/2 -1/\beta-r/d}. \end{aligned}
\end{equation}
\tag{1.6}
$$
В [18] отмечено, что $(\log(m+1))^{-5}$ в (1.6) можно заменить на $(\log(m+1))^{-4}$. Оценки (1.5) и (1.6) показывают, что, вообще говоря, для равномерно ограниченных ортонормированных систем $\Psi$, например, для тригонометрической системы $\mathcal T^d$, различие между верхней и нижней оценками состоит в дополнительном логарифмическом по $m$ множителе. В этой работе, так же как и в работе [18], мы изучаем специальный случай, когда $\Psi$ удовлетворяет определенным ограничениям. Мы сформулируем эти ограничения в форме условий, наложенных на $\Psi$. Условие A. Предположим, что $\Psi$ – равномерно ограниченная система, а именно, предположим, что $\Psi:=\{\varphi_j\}_{j=1}^\infty$ является системой равномерно ограниченных функций на $\Omega \subset \mathbb R^d$ такой, что Условие B2. Предположим, что $ \Psi $ – система Рисса, т.е. для любого $N\in\mathbb{N}$ и произвольного $(a_1,\dots, a_N) \in\mathbb C^N$ где $0< R_1 \leqslant R_2 <\infty$. Условие B3. Предположим, что $\Psi$ – система Бесселя, т.е. существует постоянная $K>0$ такая, что для любого $N\in\mathbb{N}$ и произвольного $(a_1,\dots, a_N) \in\mathbb C^N$ Ясно, что условие B1 влечет условие B2 с $R_1=R_2=1$. Условие B2 влечет условие B3 с $K=R_1^{-2}$. В случае $2<p<\infty$ следующие оценки сверху были доказаны в [18] (см. теорема 4.2 и замечание 6.1). Теорема 1.1 (см. [18]). Предположим, что $\Psi$ – равномерно ограниченная система Рисса (в пространстве $L_2(\Omega,\mu)$), удовлетворяющая (1.7) и (1.8) для некоторых постоянных $0<R_1\leqslant R_2<\infty$. Пусть $2<p<\infty$, $\beta \in (0,1]$ и $r>0$. Существуют постоянные $c'=c'(r,\beta,p,R_1,R_2,d)$ и $C'=C'(r,\beta,p,d)$ такие, что для любого $v\in\mathbb{N}$ справедлива оценка для произвольного $m$, удовлетворяющего неравенству Результаты об универсальной $L_p$-дискретизации играли важную роль при доказательстве теоремы 1.1. Сейчас мы сформулируем соответствующий результат. Теорема 1.2 (см. [3]). Предположим, что $\mathcal D_N=\{\varphi_j\}_{j=1}^N$ – равномерно ограниченная система Рисса, удовлетворяющая (1.7) и (1.8) с некоторыми постоянными $0<R_1\leqslant R_2<\infty$. Пусть $2<p<\infty$, и пусть $1\leqslant u\leqslant N$ – целое число. Тогда для достаточно большой постоянной $C=C(p,R_1,R_2)$ и произвольного $\varepsilon\in (0, 1)$ существуют $m$ точек $\xi^1,\dots, \xi^m\in \Omega$ с такие, что для любого $f\in \Sigma_u(\mathcal D_N)$ Для равномерно ограниченной системы Рисса теорема 1.1 дает следующую оценку сверху:
$$
\begin{equation}
\varrho_{m}^{o}({\mathbf A}^r_\beta(\Psi),L_p(\Omega,\mu)) \ll \biggl(\frac{m}{(\log m)^2}\biggr)^{(2/p)(1/2 -1/\beta -r/d)} .
\end{equation}
\tag{1.12}
$$
В этой работе мы улучшаем (1.12). Для равномерно ограниченной системы Рисса $\Psi$ следствие 5.1 (см. ниже) дает для $2\leqslant p<\infty$
$$
\begin{equation}
\varrho_{m}^{o}({\mathbf A}^r_\beta(\Psi),L_p(\Omega,\mu)) \ll \biggl(\frac{m}{(\log m)^4}\biggr)^{1-1/p -1/\beta -r/d} .
\end{equation}
\tag{1.13}
$$
Более того, оценка (1.13) дается простым жадным алгоритмом – алгоритмом слабого ортогонального преследования (АСОП) (см. определение ниже). Верхняя оценка (5.11) и нижняя оценка из предложения 5.1 (см. ниже) дают следующие неравенства в специальном случае $d$-мерной тригонометрической системы $\mathcal T^d$
$$
\begin{equation}
m^{1-1/p -1/\beta -r/d}\ll \varrho_{m}^{o}({\mathbf A}^r_\beta(\mathcal T^d),L_p) \ll \biggl(\frac{m}{(\log m)^3}\biggr)^{1-1/p -1/\beta -r/d} .
\end{equation}
\tag{1.14}
$$
Дальнейшие обсуждения могут быть найдены в § 6. § 2. Предварительный материалАлгоритм слабого ортогонального преследования (АСОП) – это жадный алгоритм, определенный по заданному словарю (системе) $\mathcal D=\{g\}$ в гильбертовом пространстве, снабженном скалярным произведением $ \langle\cdot,\cdot\rangle$ и нормой $\|\cdot\|_H$. Этот алгоритм также известен под названием слабый ортогональный жадный алгоритм (см., например, [15]). Алгоритм слабого ортогонального преследования (АСОП)Пусть $\mathcal D=\{g\}$ – система ненулевых элементов из $H$ таких, что $\|g\|_H\leqslant 1$. Пусть задана последовательность $\tau:=\{t_k\}_{k=1}^\infty\subset [0, 1]$ параметров слабости. Для данного $f_0\in H$ определим последовательность $\{f_k\}_{k=1}^\infty\subset H$ остатков для $k=1,2,\dots$ индуктивно. (1) $g_k\in \mathcal D$ – любой элемент, удовлетворяющий условию
$$
\begin{equation*}
|\langle f_{k-1},g_k\rangle | \geqslant t_k \sup_{g\in \mathcal D} |\langle f_{k-1},g\rangle |.
\end{equation*}
\notag
$$
(2) Пусть $H_k:=\operatorname{span} \{g_1,\dots,g_k\}$. Определим $G_k(\cdot, \mathcal D)$ как оператор ортогонального проектирования из $H$ на $H_k$. (3) Определим остаток после $k$-й итерации алгоритма В случае, когда $t_k=1$ для $k=1,2,\dots$, АСОП называется алгоритмом ортогонального преследования (АОП). В этой работе мы рассматриваем лишь случай, когда $t_k=t\in (0, 1]$ для $k=1,2,\dots$ . Термин слабый в определении АСОП означает, что на шаге (1) мы не стремимся выбрать оптимальный элемент словаря, на котором достигается верхняя грань. Очевидная причина – в общем случае мы не знаем, что оптимальный элемент существует. Другая, практическая причина, состоит в том, что более слабое условие легче реализовать на практике. Ясно, что $g_k$ может быть не единственным. Однако все сформулированные ниже результаты не зависят от выбора $g_k$. Для удобства в дальнейших приложениях будем использовать обозначение $\operatorname{\textrm{АСОП}}(\mathcal D; t)_H$ для АСОП, определенного по данному параметру слабости $t\in (0, 1]$ и системе $\mathcal D$ в гильбертовом пространстве $H$. UP($u,D$). ($u,D$)-свойство безусловностиГоворим, что система $\mathcal D=\{\varphi_i\}_{i\in I}$ элементов гильбертова пространства $H=(H, \|\cdot\|)$ является ($u,D$)-безусловной с постоянной $U>0$ для некоторых целых чисел $1\leqslant u\leqslant D$, если для любого $f=\sum_{i\in A} c_i \varphi_i\in \Sigma_u(\mathcal D)$ с $A\subset I$ и $J\subset I\setminus A$ таких, что $|A|+|J| \leqslant D$, имеем
$$
\begin{equation}
\biggl\|\sum_{i\in A} c_i \varphi_i\biggr\|\leqslant U\inf_{g\in V_J(\mathcal D)}\biggl \|\sum_{i\in A} c_i \varphi_i-g\biggr\|,
\end{equation}
\tag{2.1}
$$
где $ V_J(\mathcal D):=\operatorname{span}\{\varphi_i\colon i\in J\}$. Выше мы сформулировали определение для случая счетной (или конечной) системы $\mathcal D$. Подобное определение можно дать и для произвольной системы $\mathcal D$. Теорема 2.1 (см. [11; следствие I.1]). Пусть $\mathcal D$ – словарь в гильбертовом пространстве $H=(H, \|\cdot\|)$, имеющий свойство $\mathbf{UP}(u,D)$ с постоянной $U>0$ для некоторых целых чисел $1\leqslant u\leqslant D$. Пусть $f_0\in H$, и пусть $t\in (0, 1]$ – параметр слабости. Тогда существует положительная постоянная $c_\ast:=c(t,U)$, зависящая только от $t$ и $U$, такая, что $\operatorname{\textrm{АСОП}}(\mathcal D; t)_H$, примененный к $f_0$, дает где $C>1$ – абсолютная постоянная, а $f_k$ обозначает остаток от $f_0$ после $k$-й итерации алгоритма. Мы рассмотрим гильбертово пространство $L_2(\Omega_m,\mu_m)$ вместо $L_2(\Omega,\mu)$, где $\Omega_m=\{\xi^\nu\}_{\nu=1}^m$ – множество точек, которое обеспечивает хорошую универсальную дискретизацию, а $\mu_m$ – равномерная вероятностная мера на $\Omega_m$, т.е. $\mu_m\{ \xi^\nu\}=1/m$, $\nu=1,\dots,m$. Пусть $\mathcal D_N(\Omega_m)$ обозначает сужение системы $\mathcal D_N$ на множество $\Omega_m$. Теорема 2.2 (см. ниже) гарантирует, что простой жадный алгоритм АСОП дает соответствующее неравенство Лебега в норме $L_2(\Omega_m,\mu_m)$ и, следовательно, обеспечивает хорошее разреженное восстановление. Теорема 2.2 (см. [4]). Пусть $\mathcal D_N=\{\varphi_j\}_{j=1}^N$ – равномерно ограниченная система Рисса в $L_2(\Omega, \mu)$, удовлетворяющая (1.7) и (1.8) при некоторых постоянных $0<R_1\leqslant R_2<\infty$. Пусть $\Omega_m=\{\xi^1,\dots, \xi^m\}$ – конечное подмножество $\Omega$, обеспечивающее $L_2$-универсальную дискретизацию (1.1) для набора $\mathcal X_u(\mathcal D_N)$ и заданных целых чисел $1\leqslant u\leqslant N$. По данному параметру слабости $0<t\leqslant 1$ можно найти константу (целое число) $c=c(t,R_1,R_2)\geqslant 1$ такую, что для любого целого числа, удовлетворяющего неравенствам $0\leqslant v\leqslant u/(1+c)$, и произвольного $f_0\in \mathcal C(\Omega)$ алгоритм Напомним, что модуль гладкости банахова пространства $X$ определяется следующим образом:
$$
\begin{equation}
\eta(w):=\eta(X,w):=\sup_{x,y\in X\colon \|x\|=\|y\|=1}\biggl[\frac{\|x+wy\|+\|x-wy\|}{2} -1\biggr], \qquad w>0,
\end{equation}
\tag{2.4}
$$
и $X$ называется равномерно гладким, если $\eta(w)/w\to 0$ при $w\to 0+$. Хорошо известно, что пространство $L_p$ при $1< p<\infty$ является равномерно гладким банаховым пространством с
$$
\begin{equation}
\eta(L_p,w)\leqslant \begin{cases} \dfrac{(p-1)w^2}2, & 2\leqslant p <\infty, \\ \dfrac{w^p}p,& 1\leqslant p\leqslant 2. \end{cases}
\end{equation}
\tag{2.5}
$$
§ 3. Новые результаты в оценках сверхуВ дополнение к сформулированным во введении условиям на систему $\Psi$ нам нужно еще одно свойство системы $\Psi$. $u$-членное неравенство НикольскогоПусть $1\leqslant q\leqslant p\leqslant \infty$, и пусть $\Psi$ – система из $L_p:=L_p(\Omega,\mu)$. Для натурального числа $u$ говорим, что система $\Psi$ удовлетворяет $u$-членному неравенству Никольского для пары $(q,p)$ с постоянной $H$, если выполнено следующее неравенство:
$$
\begin{equation}
\|f\|_p \leqslant H\|f\|_q \quad \forall\, f\in \Sigma_u(\Psi).
\end{equation}
\tag{3.1}
$$
В таком случае пишем $\Psi \in \mathrm{NI}(q,p,H,u)$. Отметим, что очевидно $H\geqslant 1$. Теорема 3.1. Пусть $\mathcal D_N=\{\varphi_j\}_{j=1}^N$ является равномерно ограниченной системой Рисса в $L_2(\Omega, \mu)$, удовлетворяющей (1.7) и (1.8) при некоторых постоянных $0<R_1\leqslant R_2<\infty$. Пусть $\Omega_m=\{\xi^1,\dots, \xi^m\}$ – конечное подмножество $\Omega$, которое обеспечивает $L_2$-универсальную дискретизацию для набора $\mathcal X_u(\mathcal D_N)$, $1\leqslant u\leqslant N$. В дополнение предположим, что $\mathcal D_N \in \mathrm{NI}(2,p,H,u)$ с $p\in [2,\infty)$. Тогда для заданного параметра слабости $0<t\leqslant 1$ найдется постоянная (целое число) $c=c(t,R_1,R_2)\geqslant 1$ такая, что для любого целого числа, удовлетворяющего неравенствам $0\leqslant v\leqslant u/(1+c)$, и произвольного $f_0\in \mathcal C(\Omega)$ алгоритм Доказательство. Начнем с неравенства (3.2). Оно вытекает из неравенства (2.2) в теореме 2.2. Для полноты изложения мы приведем здесь это простое доказательство. Используя (1.8), мы получим, что для любых множеств $A\subset \{1,2,\dots, N\}$ и $\Lambda\subset \{1,\dots, N\}\setminus A$ и для любых последовательностей $\{x_i\}_{i\in A},$ $\{c_i\}_{i\in\Lambda}\subset\mathbb C$ выполнено
$$
\begin{equation*}
\biggl\|\sum_{i\in A}x_i\varphi_i-\sum_{i\in\Lambda}c_i\varphi_i\biggr\|_{L_2(\Omega,\mu)}^2 \geqslant R_1^2 \sum_{i\in A} |x_i|^2 \geqslant R_2^{-2} R_1^2\biggl \|\sum_{i\in A}x_i\varphi_i \biggr\|_{L_2(\Omega,\mu)}^2.
\end{equation*}
\notag
$$
Это означает, что система $\mathcal D_N$ имеет свойство $\mathbf{UP}(v,N)$ с постоянной $U_1=R_2/R_1$ в пространстве $L_2(\Omega,\mu)$ для любых целых чисел $1\leqslant v< N$. Далее, из неравенств дискретизации (1.1) с $\mathbf {\mathcal{X}}=\mathbf {\mathcal{X}}_u(\mathcal D_N)$ вытекает, что система $\mathcal D:=\mathcal D_N(\Omega_m)$, которая является сужением $\mathcal D_N$ на $\Omega_m=\{\xi^1, \dots,\xi^m\}$, имеет свойство $\mathbf{UP}(v,u)$ в пространстве $L_2(\Omega_m,\mu_m)$ с постоянной $U_2=U_1 3^{1/2}$ для любого целого $1\leqslant v\leqslant u$. Таким образом, применяя теорему 2.1 к дискретизированной системе $\mathcal D_N(\Omega_m)$ в гильбертовом пространстве $L_2(\Omega_m,\mu_m)$, мы получим, что алгоритм
$$
\begin{equation*}
\operatorname{\textrm{АСОП}}\bigl(\mathcal D_N(\Omega_m); t\bigr)_{L_2(\Omega_m,\mu_m)},
\end{equation*}
\notag
$$
примененный к $f_0$, суженному на ${\Omega_m}$, дает
$$
\begin{equation*}
\|f_{cv}\|_{L_2(\Omega_m,\mu_m)}\leqslant C_0\sigma_v(f_0,\mathcal D_N(\Omega_m))_{L_2(\Omega_m,\mu_m)}
\end{equation*}
\notag
$$
при условии $v+c v\leqslant u$, где $c=c(t, R_1, R_2)\in\mathbb N$. Это доказывает (3.2) в теореме 3.1.
Сейчас мы выведем (3.3) из (3.2). Пусть $h\in \Sigma_v(\mathcal D_N)$ таково, что
$$
\begin{equation*}
\|f_0-h\|_{L_p(\mu_\xi)}=\sigma_v(f_0,\mathcal D_N)_{L_p(\mu_\xi)}.
\end{equation*}
\notag
$$
Имеем
$$
\begin{equation*}
\|f_{cv}\|_{L_p(\Omega,\mu)} \leqslant \|h-f_0\|_{L_p(\Omega,\mu)}+\|h-G_{cv}(f_0,\mathcal D_N(\Omega_m))\|_{L_p(\Omega,\mu)}.
\end{equation*}
\notag
$$
Во-первых, оценим
$$
\begin{equation*}
\|h-f_0\|_{L_p(\Omega,\mu)} \leqslant 2^{1/p}\|h-f_0\|_{L_p(\mu_\xi)}=2^{1/p}\sigma_v(f_0,\mathcal D_N)_{L_p(\mu_\xi)}.
\end{equation*}
\notag
$$
Во-вторых, учитывая, что $h-G_{cv}(f_0,\mathcal D_N(\Omega_m)) \in \Sigma_u(\mathcal D_N)$, по нашему предположению $\mathcal D_N \in \mathrm{NI}(2,p,H,u)$ и благодаря дискретизации (1.1) заключаем
$$
\begin{equation}
\begin{aligned} \, \notag \|h-G_{cv}(f_0,\mathcal D_N(\Omega_m))\|_{L_p(\Omega,\mu)} &\leqslant H \|h- G_{cv}(f_0,\mathcal D_N(\Omega_m))\|_{L_2(\Omega,\mu)} \\ &\leqslant 2^{1/2}H\|h-G_{cv}(f_0,\mathcal D_N(\Omega_m))\|_{L_2(\Omega_m,\mu_m)}. \end{aligned}
\end{equation}
\tag{3.4}
$$
Далее, (3.2) влечет
$$
\begin{equation*}
\begin{aligned} \, &\|h-G_{cv}(f_0,\mathcal D_N(\Omega_m))\|_{L_2(\Omega_m,\mu_m)} \leqslant \|h-f_0\|_{L_2(\Omega_m,\mu_m)}+\|f_{cv}\|_{L_2(\Omega_m,\mu_m)} \\ &\qquad \leqslant \|h-f_0\|_{L_p(\Omega_m,\mu_m)}+C_0\sigma_v(f_0,\mathcal D_N(\Omega_m))_{L_2(\Omega_m,\mu_m)} \\ &\qquad \leqslant 2^{1/p}(\|h-f_0\|_{L_p(\mu_\xi)}+C_0\sigma_v(f_0,\mathcal D_N(\Omega_m))_{L_p(\mu_\xi)}) \\ &\qquad \leqslant 2^{1/p}(1+C_0)\sigma_v(f_0,\mathcal D_N)_{L_p(\mu_\xi)}. \end{aligned}
\end{equation*}
\notag
$$
Отсюда и из (3.4) вытекает Наконец, что завершает доказательство теоремы. Для краткости обозначим $L_p(\xi):=L_p(\Omega_m,\mu_m)$, где $\Omega_m=\{\xi^\nu\}_{\nu=1}^m$ и $\mu_m(\xi^\nu)=1/m$, $\nu=1,\dots,m$. Пусть $B_v(f,\mathcal D_N,L_p(\xi))$ обозначает наилучшее $v$-членное приближение $f$ в норме $L_p(\xi)$ по системе $\mathcal D_N$. Отметим, что $B_v(f,\mathcal D_N,L_p(\xi))$ может быть не единственным. Очевидно, что
$$
\begin{equation}
\|f-B_v(f,\mathcal D_N,L_p(\xi))\|_{L_p(\xi)}=\sigma_v(f,\mathcal D_N)_{L_p(\xi)}.
\end{equation}
\tag{3.6}
$$
В [5] была доказана следующая теорема. Теорема 3.2 (см. [5]). Пусть $1\leqslant p<\infty$, и пусть $m$, $v$, $N$ – натуральные числа такие, что $2v\leqslant N$. Пусть $\mathcal D_N\subset \mathcal C(\Omega)$ – система из $N$ элементов. Предположим, что существует множество $\xi:=\{\xi^j\}_{j=1}^m \subset \Omega $, которое обеспечивает одностороннюю $L_p$-универсальную дискретизацию Докажем следующую версию теоремы 3.2. Теорема 3.3. Пусть $2\leqslant p\leqslant \infty$, и пусть $m$, $v$, $N$ – натуральные числа такие, что $2v\leqslant N$. Пусть $\mathcal D_N\subset \mathcal C(\Omega)$ – система из $N$ элементов такая, что $\mathcal D_N \in \mathrm{NI}(2,p,H,2v)$. Предположим, что существует множество $\xi:=\{\xi^j\}_{j=1}^m \subset \Omega $, которое обеспечивает одностороннюю $L_2$-универсальную дискретизацию Доказательство. Доказательства неравенств (3.11) и (3.12) похожи. Начнем с неравенства (3.11). Для краткости обозначим $g:=B_v(f,\mathcal D_N,L_2(\xi))$ и $h:=B_v(f,\mathcal D_N,L_p(\mu_\xi))$. Тогда
$$
\begin{equation*}
\|f-g\|_{L_p(\mu)} \leqslant \|f-h\|_{L_p(\mu)}+\|h-g\|_{L_p(\mu)}.
\end{equation*}
\notag
$$
Во-первых, оценим
$$
\begin{equation*}
\|f-h\|_{L_p(\mu)} \leqslant 2^{1/p} \|f-h\|_{L_p(\mu_\xi)}=2^{1/p} \sigma_v(f,\mathcal D_N)_{L_p(\mu_\xi)}.
\end{equation*}
\notag
$$
Во-вторых, используя очевидный факт $h-g\in \Sigma_{2v}(\mathcal D_N)$, благодаря предположению $\mathcal D_N \in \mathrm{NI}(2,p,H,2v)$ получим и с помощью (3.10) и тривиального неравенства $\|f-g\|_{L_2(\xi)} \leqslant \|f-h\|_{L_2(\xi)}$ продолжим
$$
\begin{equation*}
\begin{aligned} \, \|h-g\|_{L_p(\mu)} &\leqslant HD \|h-g\|_{L_2(\xi)} \leqslant 2HD \|f-h\|_{L_2(\xi)} \leqslant 2HD \|f-h\|_{L_p(\xi)} \\ & \leqslant 2^{1+1/p}HD \|f-h\|_{L_p(\mu_\xi)}=2^{1+1/p}HD \sigma_v(f,\mathcal D_N)_{L_p(\mu_\xi)}. \end{aligned}
\end{equation*}
\notag
$$
Собирая воедино полученные выше неравенства, завершаем доказательство (3.11).
Сейчас докажем (3.12). Обозначим $g:=B_v(f,\mathcal D_N,L_2(\xi))$ и $h:=B_v(f,\mathcal D_N,L_\infty)$. Тогда Во-первых, оценим
$$
\begin{equation*}
\|f-h\|_p \leqslant \|f-h\|_\infty=\sigma_v(f,\mathcal D_N)_\infty.
\end{equation*}
\notag
$$
Во-вторых, учитывая очевидный факт $h-g\in \Sigma_{2v}(\mathcal D_N)$, по предположению $\mathcal D_N \in \mathrm{NI}(2,p,H,2v)$ получим и продолжим с помощью (3.10) и тривиального неравенства $\|f-g\|_{L_2(\xi)} \leqslant \|f-h\|_{L_2(\xi)}$
$$
\begin{equation*}
\begin{aligned} \, \|h-g\|_p &\leqslant HD \|h-g\|_{L_2(\xi)} \leqslant 2HD \|f-h\|_{L_2(\xi)} \\ &\leqslant 2 HD \|f-h\|_\infty=2 HD \sigma_v(f,\mathcal D_N)_\infty. \end{aligned}
\end{equation*}
\notag
$$
Собирая воедино полученные выше неравенства, завершаем доказательство (3.12).
Теорема доказана. § 4. Новые результаты в оценках снизуОбсудим нижние оценки для нелинейной характеристики $\varrho_m^o({\mathbf A}^r_\beta(\Psi),L_p)$. Сделаем это в специальном случае, когда $\Psi$ – это тригонометрическая система $\mathcal T^d:=\{e^{i({\mathbf k},{\mathbf x})}\}_{{\mathbf k}\in \mathbb Z^d}$. Для ${\mathbf N}=(N_1,\dots,N_d)$, $N_j\in \mathbb{N}_0$, $j=1,\dots,d$, обозначим
$$
\begin{equation*}
\mathcal T({\mathbf N},d):=\biggl\{f=\sum_{{\mathbf k}\colon |k_j|\leqslant N_j, \,j=1,\dots,d} c_j e^{i({\mathbf k},{\mathbf x})}\biggr\},\qquad \vartheta({\mathbf N}):=\prod_{j=1}^d (2N_j+1).
\end{equation*}
\notag
$$
В этом параграфе $\Omega=\mathbb T^d$ и $\mu$ – это нормированная мера Лебега на $\mathbb T^d$. Лемма 4.1. Пусть $1\leqslant q\leqslant p\leqslant \infty$, и пусть $\mathcal T({\mathbf N},d)_q$ обозначает единичный $L_q$-шар подпространства $\mathcal T({\mathbf N},d)$. Тогда для $m\leqslant \vartheta({\mathbf N})/2$ имеем Доказательство. Для заданного множества $\xi\subset \mathbb T^d:=[0,2\pi)^d$ точек $\xi^1,\dots,\xi^m$ рассмотрим следующее подпространство:
$$
\begin{equation*}
T(\xi):=\{f\in \mathcal T({\mathbf N},d)\colon f(\xi^\nu)=0,\ \nu=1,\dots,m\}.
\end{equation*}
\notag
$$
Пусть $g_\xi\in T(\xi)$ и точка ${\mathbf x}^*$ таковы, что $|g_\xi({\mathbf x}^*)|=\|g_\xi\|_\infty=1$. Для дальнейших рассуждений нам понадобятся классические тригонометрические полиномы. Одномерное ядро Фейера порядка $j-1$:
$$
\begin{equation*}
\mathcal K_{j} (x):=\sum_{|k|\leqslant j} \biggl(1-\frac{|k|}j\biggr) e^{ikx} =\frac{(\sin (jx/2))^2}{j (\sin (x/2))^2}.
\end{equation*}
\notag
$$
Ядро Фейера является четным неотрицательным тригонометрическим полиномом порядка $j-1$. Оно удовлетворяет следующим очевидным соотношениям:
$$
\begin{equation}
\| \mathcal K_{j} \|_1=1, \qquad \| \mathcal K_{j} \|_{\infty}=j.
\end{equation}
\tag{4.1}
$$
Пусть $\mathcal K_{\mathbf j}({\mathbf x}):=\prod_{i=1}^d \mathcal K_{j_i}(x_i)$ – $d$-мерное ядро Фейера для ${\mathbf j}=(j_1,\dots,j_d)$ и ${\mathbf x}=(x_1,\dots,x_d)$. Положим
$$
\begin{equation}
f({\mathbf x}):=g_\xi({\mathbf x})\mathcal K_{\mathbf N}({\mathbf x}-{\mathbf x}^*).
\end{equation}
\tag{4.2}
$$
Тогда $f\in \mathcal T(2{\mathbf N},d)$, $f(\xi^\nu)=0$, $\nu=1,\dots,m$, и
$$
\begin{equation}
\|f\|_q \leqslant \|g_\xi\|_\infty \|\mathcal K_{\mathbf N}\|_q \leqslant C_1(d)\vartheta({\mathbf N})^{1-1/q}.
\end{equation}
\tag{4.3}
$$
На последнем шаге мы воспользовались известной оценкой нормы $L_q$ ядра Фейера (см. [17; с. 83, (3.2.7)]). Из (4.1) получаем
$$
\begin{equation}
|f({\mathbf x}^*)| \geqslant C_2(d) \vartheta({\mathbf N}).
\end{equation}
\tag{4.4}
$$
По неравенству Никольского для $\mathcal T(2{\mathbf N},d)$ (см. [17; с. 90, теорема 3.3.2]) находим из (4.4)
Пусть $\mathcal M$ – отображение из $\mathbb C^m$ в $L_p$. Обозначим $g_0:=\mathcal M(\mathbf 0)$. Тогда
$$
\begin{equation*}
\biggl\|\frac{f}{\|f\|_q} -g_0\biggr\|_p+\biggl\|-\frac{f}{\|f\|_q}-g_0\biggr\|_p \geqslant 2\biggl\|\frac{f}{\|f\|_q}\biggr\|_p.
\end{equation*}
\notag
$$
Это и соотношения (4.3), (4.5) в совокупности с тем фактом, что обе функции $f/\|f\|_q$ и $-f/\|f\|_q$ принадлежат $\mathcal T(2{\mathbf N},d)_q$, завершают доказательство леммы 4.1. Покажем, как теорема 3.2 может быть использована для доказательства того, что теорема 1.2 не может быть существенно улучшена в смысле соотношения между $m$ и $u$. Предложение 4.1. Пусть $d\in \mathbb{N}$ и $p\in (2,\infty)$. Существует положительная постоянная $C(d,p)$ со следующим свойством. Для любого Доказательство. Доказательство проведем от противного. Предположим, что существует множество $\xi:=\{\xi^j\}_{j=1}^m \subset \mathbb T^d $, которое обеспечивает одностороннюю $L_p$-универсальную дискретизацию (3.7) для $\mathcal X_{2v}(\mathcal D_N)$. Тогда по теореме 3.2 выполнено неравенство (3.8) для любой функции $f\in\mathcal C(\mathbb T^d)$. Возьмем функцию $f$ из доказательства леммы 4.1, определенную в (4.2). По определению $f$ имеем $f(\xi^j)=0$ для всех $j=1,\dots,m$. Следовательно, $B_v(f,\mathcal D_N,L_p(\xi))=0$ и с помощью (4.5) получаем
$$
\begin{equation}
\|f-B_v(f,\mathcal D_N,L_p(\xi))\|_p \geqslant C_3(d)\vartheta({\mathbf N})^{1-1/p}.
\end{equation}
\tag{4.6}
$$
С другой стороны, по (4.3) с $q=2$ находим
$$
\begin{equation}
\sum_{{\mathbf k}\in \mathbb Z^d} |\widehat f({\mathbf k})| \leqslant \vartheta(2{\mathbf N})^{1/2} \|f\|_2^{1/2} \leqslant C_1(d) \vartheta(2{\mathbf N})^{1/2}\vartheta({\mathbf N})^{1/2} \leqslant C_1'(d)\vartheta({\mathbf N}).
\end{equation}
\tag{4.7}
$$
По (2.5) получаем, что $\eta(L_p(\mathbb T^d,\mu_\xi),w) \leqslant (p-1)w^2/2$. Известно (см., например, [15; с. 342]), что для любого словаря $\mathcal D=\{g\}$, $\|g\|_X \leqslant 1$, в банаховом пространстве $X$ с $\eta(X,w) \leqslant \gamma w^q$, $1<q\leqslant 2$, выполнено Здесь
Отметим, что (4.8) доказано в [15] для действительных банаховых пространств. Ясно, что мы можем получить результаты для комплексных $\mathcal D_N$ из соответствующих результатов для действительных тригонометрических полиномов из $\mathcal T(2{\mathbf N},d)$. Применим неравенство (4.8) и из (4.7) найдем
$$
\begin{equation}
\sigma_v(f,\mathcal D_N)_{L_p(\mathbb T^d, \mu_\xi)} \leqslant C_1(d,p)\vartheta({\mathbf N}) (v+1)^{-1/2}.
\end{equation}
\tag{4.9}
$$
Подставляя (4.6) и (4.9) в (3.8), получаем
$$
\begin{equation*}
v+1 \leqslant C(d,p)(2D+1)^2 \vartheta({\mathbf N})^{2/p}
\end{equation*}
\notag
$$
с некоторой положительной постоянной $C(d,p)$. Выбираем эту постоянную $C(d,p)$ и завершаем доказательство предложения 4.1. § 5. Оптимальное восстановление на функциональных классахСледующая теорема была доказана в [18]. Теорема 5.1 (см. [18]). Пусть $1<p<\infty$, $r>0$, $\beta\in (0,1]$. Предположим, что $\|\psi_{\mathbf k}\|_{L_p(\Omega,\mu)} \leqslant B$, ${\mathbf k}\in\mathbb Z^d$, с некоторой вероятностной мерой $\mu$ на $\Omega$. Тогда существуют две константы $c^*=c(r,\beta,p,d)$ и $C=C(r,\beta,p,d)$ такие, что для любого $v\in \mathbb{N}$ найдется $J\in\mathbb{N}$, не зависящее от меры $\mu$, $2^J \leqslant v^{c^*}$, со следующим свойством ($p^*:=\min\{p,2\}$): Более того, эта оценка дается простым жадным алгоритмом. Перейдем к новому результату о восстановлении по выборке (по значениям в точках). В доказательстве теоремы 5.3 (см. ниже) нам нужен следующий известный результат об универсальной дискретизации. Теорема 5.2 (см. [4]). Пусть $1\leqslant p\leqslant 2$. Предположим, что $ \mathcal D_N{=}\,\{\varphi_j\}_{j=1}^N\subset\mathcal C(\Omega)$ – система, удовлетворяющая условиям (1.7) и (1.9) с некоторой постоянной $K\geqslant 1$. Пусть $\xi^1,\dots, \xi^m$ – независимые случайные точки на $\Omega$, распределенные согласно $\mu$. Тогда существуют постоянные $C=C(p)>1$ и $c=c(p)>0$ такие, что для целых чисел $1\leqslant u\leqslant N$ и неравенства выполняются с вероятностью $\geqslant 1-2 \exp( -cm/(Ku\log^2 (2Ku)))$. Теорема 5.3. Предположим, что $\Psi$ – равномерно ограниченная система Рисса (в пространстве $L_2(\Omega,\mu)$), удовлетворяющая (1.7) и (1.8) с некоторыми постоянными $0<R_1\leqslant R_2<\infty$. Пусть $2\leqslant p<\infty$ и $r>0$. Для $v\in\mathbb{N}$ обозначим $u:=\lceil (1+c)v\rceil$, где $c$ – постоянная из теоремы 3.1. Кроме того, предположим, что $\Psi \in \mathrm{NI}(2,p,H,u)$ с $p\in [2,\infty)$. Тогда существуют постоянные $c'=c'(r,\beta,p,R_1,R_2,d)$ и $C'=C'(r,\beta,p,d)$ такие, что имеет место неравенство для $m$, удовлетворяющего неравенству Более того, эта оценка дается АСОП. Доказательство. Сначала мы воспользуемся теоремой 5.1 в пространстве $L_p(\Omega,\mu)$. В нашем случае $B=1$ и $2<p<\infty$, что влечет $p^*=2$. Рассмотрим систему $\Psi_J:=\{\psi_{\mathbf k}\}_{\|{\mathbf k}\|_\infty <2^J}$, $2^J \leqslant v^{c^*}$, из теоремы 5.1. Отметим, что $J$ не зависит от $\mu$. По теореме 3.1 с $\mathcal D_N=\Psi_J$ и теореме 5.2 с $p=2$ и $K=R_1^{-2}$ существуют $m$ точек $\xi^1,\dots, \xi^m\in \Omega$ с таких, что для произвольной $f_0\in \mathcal C(\Omega)$ алгоритм АСОП с параметром слабости $t$, примененный к $f_0$ по системе $\mathcal D_N(\Omega_m)$ в пространстве $L_2(\Omega_m,\mu_m)$, для целого числа $v$, удовлетворяющего неравенствам $1\leqslant v \leqslant u/(1+c)$, дает
$$
\begin{equation}
\|f_{cv} \|_{L_p(\Omega,\mu)} \leqslant C'H \sigma_v(f_0,\mathcal D_N)_{L_p(\Omega, \mu_\xi)}.
\end{equation}
\tag{5.4}
$$
Для того чтобы оценить правую часть (5.4), применяем теорему 5.1 в пространстве $L_p(\Omega, \mu_\xi)$. Для того чтобы это можно было сделать, достаточно проверить, что $\|\psi_{\mathbf k}\|_{L_p(\Omega, \mu_\xi)} \leqslant 1$, ${\mathbf k}\in\mathbb Z^d$. Это следует из предположения, что $\Psi$ удовлетворяет (1.7). Таким образом, по теореме 5.1 получаем для $f_0 \in {\mathbf A}^r_\beta(\Psi)$
$$
\begin{equation}
\sigma_v(f_0,\Psi_J)_{L_p(\Omega, \mu_\xi)} \leqslant Cv^{1/2 -1/\beta-r/d}.
\end{equation}
\tag{5.5}
$$
Объединяя (5.5), (5.4) и принимая во внимание (5.3) и оценку завершаем доказательство теоремы. Следствие 5.1. Предположим, что $\Psi$ является равномерно ограниченной системой Рисса (в пространтстве $L_2(\Omega,\mu)$), удовлетворяющей (1.7) и (1.8) с некоторыми постоянными $0<R_1\leqslant R_2<\infty$. Пусть $2\leqslant p<\infty$ и $r>0$. Существуют постоянные $c=c(r,\beta,p,R_1,R_2,d)$ и $C=C(r,\beta,p,d)$ такие, что имеет место оценка для $m$, удовлетворяющего неравенству Более того, эта оценка дается АСОП. Доказательство. Докажем, что система $\Psi$, удовлетворяющая условиям следствия 5.1, удовлетворяет условию $\Psi \in \mathrm{NI}(2,p,H,u)$ с $H=C(R_2) u^{1/2-1/p}$, которое требуется в теореме 5.3. Тогда следствие 5.1 вытекает из теоремы 5.3. Действительно, пусть
$$
\begin{equation*}
f:=\sum_{{\mathbf k} \in Q} c_{\mathbf k} \psi_{\mathbf k}, \qquad |Q| \leqslant u.
\end{equation*}
\notag
$$
Тогда Используя хорошо известное простое неравенство $\|f\|_p \leqslant \|f\|_2^{2/p}\|f\|_\infty^{1-2/p}$, $2\leqslant p\leqslant \infty$, получим Мы вывели теорему 5.3 из теоремы 3.1. Сформулируем аналог теоремы 5.3, который может быть выведен из теоремы 3.3 таким же путем, каким теорема 5.3 была выведена из теоремы 3.1. Теорема 5.4. Пусть $2\leqslant p<\infty$, и пусть $m$, $v$ – натуральные числа. Пусть $\Psi$ является равномерно ограниченной системой Бесселя, удовлетворяющей (1.7) и (1.9) и такой, что $\Psi \in \mathrm{NI}(2,p,H,2v)$. Существуют постоянные $c=c(r,\beta,p,K,d)$ и $C=C(r,\beta,p,d)$ такие, что имеет место оценка для $m$, удовлетворяющих неравенству В специальном случае, когда $\Psi=\mathcal T^d$ является тригонометрической системой, следствие 5.1 дает
$$
\begin{equation}
\varrho_{m}^{o}({\mathbf A}^r_\beta(\mathcal T),L_p(\Omega,\mu)) \ll v^{1-1/p -1/\beta -r/d} \quad\text{для }\ m\gg v (\log(2v ))^4.
\end{equation}
\tag{5.8}
$$
В [4] отмечено, что известные результаты о свойстве ограниченной изометрии (англ. Restricted Isometry Property (RIP)) для тригонометрической системы могут быть использованы для улучшения результатов об универсальной дискретизации в норме $L_2$ в случае тригонометрической системы. Объясним это в деталях. Пусть $M\in \mathbb{N}$ и $d\in \mathbb{N}$. Обозначим $\Pi(M):=[-M,M]^d$ – $d$-мерный куб. Рассмотрим систему $\mathcal T^d(M):=\mathcal T^d(\Pi(M))$ функций $e^{i({\mathbf k},{\mathbf x})}$, ${\mathbf k} \in \Pi(M)$, определенную на $\mathbb T^d=[0,2\pi)^d$. Тогда $\mathcal T^d(M)$ – ортонормированная система в $L_2(\mathbb T^d,\mu)$ с нормированной мерой Лебега $\mu$ на $\mathbb T^d$. Для числа элементов этой системы имеем $N(M):=|\mathcal T^d(M)|=(2M+1)^d$. Мы заинтересованы в оценках на $m(\mathcal X_v(\mathcal T^d(M)),2)$ в специальном случае, когда $M\leqslant v^c$ с некоторой постоянной $c$, которая может зависеть от $d$. Тогда теорема 5.2 с $p=2$ дает
$$
\begin{equation}
m(\mathcal X_v(\mathcal T^d(v^c)),2) \leqslant C(c,d) v (\log (2v))^4.
\end{equation}
\tag{5.9}
$$
В [4] указано, что известные результаты из [8] и [1] позволяют улучшить оценку (5.9):
$$
\begin{equation}
m(\mathcal X_v(\mathcal T^d(v^c)),2) \leqslant C(c,d) v (\log (2v))^3.
\end{equation}
\tag{5.10}
$$
Это, в свою очередь, влечет следующую оценку:
$$
\begin{equation}
\varrho_{m}^{o}({\mathbf A}^r_\beta(\mathcal T^d),L_p) \ll v^{1-1/p -1/\beta -r/d} \quad\text{для}\quad m\gg v (\log(2v ))^3.
\end{equation}
\tag{5.11}
$$
Докажем, что (5.11) не может быть существенно улучшена. Воспользуемся леммой 4.1. Возьмем $n\in\mathbb{N}$ и положим $N:=2^n-1$, ${\mathbf N}:=(N,\dots,N)$. Тогда для $f\in \mathcal T({\mathbf N},d)_2$ по неравенству Гёльдера с параметром $2/\beta$ получим
$$
\begin{equation*}
\begin{aligned} \, \biggl(\sum_{{\mathbf k}\colon \|{\mathbf k}\|_\infty\leqslant N} |\widehat f({\mathbf k})|^\beta\biggr)^{1/\beta} &\leqslant (2N+1)^{d(1/\beta-1/2)} \biggl(\sum_{{\mathbf k}\colon \|{\mathbf k}\|_\infty\leqslant N} |\widehat f({\mathbf k})|^2\biggr)^{1/2} \\ &=(2N+1)^{d(1/\beta-1/2)}\|f\|_2 . \end{aligned}
\end{equation*}
\notag
$$
Эта оценка и лемма 4.1 с $q=2$ влекут следующую оценку снизу.
§ 6. ОбсуждениеВ этой работе мы подчеркиваем важность классов ${\mathbf A}^r_\beta(\Psi)$, которые определены с помощью структурных, а не гладкостных условий. Приведем краткую историю развития этой идеи. Первый результат, который связал наилучшие приближения $\sigma_v(f,\Psi)_2$ со сходимостью ряда $\sum_{k}|\langle f,\psi_k\rangle|$ был получен С. Б. Стечкиным [13] в 1955 г. в случае ортонормированной системы $\Psi$. Сейчас мы сформулируем его результат и более общий результат. Следующие классы были введены в [6] при изучении разреженных приближений по произвольным системам (словарям) $\mathcal D$ в гильбертовом пространстве $H$. Для общего словаря $\mathcal D$ и числа $\beta>0$ определим следующий класс функций (элементов):
$$
\begin{equation*}
\mathcal A^o_\beta(\mathcal D,M):=\biggl\{f\in H\colon f=\sum_{k\in \Lambda} c_kg_k,\, g_k\in \mathcal D,\, |\Lambda| <\infty,\, \sum_{k\in \Lambda} |c_k|^\beta \leqslant M^\beta\biggr\},
\end{equation*}
\notag
$$
и определим $\mathcal A_\beta(\mathcal D,M)$ как замыкание (в $H$) множества $\mathcal A^o_\beta(\mathcal D,M)$. Далее, определим $\mathcal A_\beta(\mathcal D)$ как объединение классов $\mathcal A_\beta(\mathcal D,M)$ по всем $M>0$. В случае, когда $\mathcal D$ – ортонормированная система, С. Б. Стечкин в [13] доказал (см. обсуждение этого результата в [7; п. 7.4]), что
$$
\begin{equation}
f\in \mathcal A_1(\mathcal D) \quad \text{тогда и только тогда, когда}\quad \sum_{v=1}^\infty (v^{1/2}\sigma_v(f,\mathcal D)_2)\frac{1}{v} <\infty.
\end{equation}
\tag{6.1}
$$
Следующий вариант (6.1) для классов $\mathcal A_\beta(\mathcal D)$, $\beta\in (0,2)$, был получен в [6]:
$$
\begin{equation}
f\in \mathcal A_\beta(\mathcal D) \quad \text{тогда и только тогда, когда}\quad \sum_{v=1}^\infty (v^{\alpha}\sigma_v(f,\mathcal D)_H)^\beta\frac{1}{v} <\infty,
\end{equation}
\tag{6.2}
$$
где $\alpha:=1/\beta-1/2$. В частности, (6.2) влечет, что для $f\in \mathcal A_\beta(\mathcal D)$, $\beta\in (0,2)$, имеем Напомним, что соотношения (6.1)–(6.3) были доказаны для ортонормированной системы $\mathcal D$. Очень интересно отметить, что в действительности (6.3) остается справедливым для общей нормированной системы $\mathcal D$ при условии $\beta \in (0,1]$. В случае $\beta=1$ это было доказано Б. Мореем (см. [12]). Для $\beta \in (0,1]$ это было доказано в [6]. Отметим, что классы $\mathcal A_1(\mathcal D)$ и их обобщения на банаховы пространства играют фундаментальную роль в изучении наилучших $v$-членных приближений и свойств сходимости жадных приближений по общим словарям $\mathcal D$ (см. [15]). Этот факт побудил специалистов ввести и изучать функциональные классы, определяемые ограничениями на коэффициенты их разложений. Объясним этот подход в деталях. Пусть, как и выше, система $\Psi:=\{\psi_{\mathbf k}\}_{{\mathbf k}\in \mathbb Z^d}$ индексирована ${\mathbf k}\in\mathbb Z^d$. Рассмотрим последовательность подмножеств $\mathcal G:=\{G_j\}_{j=1}^\infty$, $G_j \subset \mathbb Z^d$, $j=1,2,\dots$, таких, что
$$
\begin{equation}
G_1\subset G_2\subset \dots \subset G_j\subset G_{j+1} \subset \dotsb, \qquad \bigcup_{j=1}^\infty G_j=\mathbb Z^d.
\end{equation}
\tag{6.4}
$$
Рассмотрим функции, представимые в виде абсолютно сходящегося ряда,
$$
\begin{equation}
f=\sum_{{\mathbf k}\in\mathbb Z^d} a_{\mathbf k}(f)\psi_{\mathbf k}, \qquad \sum_{{\mathbf k}\in\mathbb Z^d} |a_{\mathbf k}(f)|<\infty.
\end{equation}
\tag{6.5}
$$
Для $\beta \in (0,1]$ и $r>0$ определим класс ${\mathbf A}^r_\beta(\Psi,\mathcal G)$ функций $f$, которые допускают представления (6.5), удовлетворяющие следующим условиям:
$$
\begin{equation}
\biggl(\sum_{ {\mathbf k}\in G_j\setminus G_{j-1}} |a_{\mathbf k}(f)|^\beta\biggr)^{1/\beta} \leqslant 2^{-rj}, \qquad j=1,2,\dots, \qquad G_0:=\varnothing .
\end{equation}
\tag{6.6}
$$
Также можно рассмотреть следующую, более узкую, версию этого класса ${\mathbf A}^r_\beta(\Psi,\mathcal G,\infty)$ – класс функций $f$, которые допускают представления (6.5), удовлетворяющие условиям
$$
\begin{equation}
\sum_{j=1}^\infty 2^{r\beta j} \sum_{ {\mathbf k}\in G_j\setminus G_{j-1}} |a_{\mathbf k}(f)|^\beta \leqslant 1, \qquad G_0:=\varnothing .
\end{equation}
\tag{6.7}
$$
Вероятно, первая реализация идеи рассмотрения классов ${\mathbf A}^r_\beta(\Psi,\mathcal G)$ была осуществлена в [16] в специальном случае, когда $\Psi$ является тригонометрической системой $\mathcal T^d:=\{e^{i({\mathbf k},{\mathbf x})}\}_{{\mathbf k}\in\mathbb Z^d}$. Перейдем к определению классов ${\mathbf W}^{a,b}_A(\mathcal T^d)$ из [16], которые соответствуют случаю $\beta=1$. Приведем необходимые обозначения. Для вектора $\mathbf s=(s_1,\dots,s_d )$ с неотрицательными целыми координатами обозначим
$$
\begin{equation*}
\rho(\mathbf s):=\bigl\{ \mathbf k\in\mathbb Z^d\colon [2^{s_j-1}] \leqslant |k_j| < 2^{s_j},\, j=1,\dots,d \bigr\},
\end{equation*}
\notag
$$
где $[a]$ означает целую часть действительного числа $a$. Для $f\in L_1 (\mathbb T^d)$ определим
$$
\begin{equation*}
\delta_{\mathbf s} (f,\mathbf x):=\sum_{\mathbf k\in\rho(\mathbf s)} \widehat f(\mathbf k)e^{i(\mathbf k,\mathbf x)},\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
$$
Рассмотрим функции с абсолютно сходящимися рядами Фурье. Для таких функций определим норму Винера ($A$-норма или $\ell_1$-норма): Следующие классы, которые удобны при изучении разреженных приближений по тригонометрической системе, были введены и изучены в [16]. Для $f\in L_1(\mathbb T^d)$ определим
$$
\begin{equation*}
f_j:=\sum_{\|{\mathbf s}\|_1=j}\delta_{\mathbf s}(f), \qquad j\in \mathbb{N}_0, \quad \mathbb{N}_0:=\mathbb{N}\cup \{0\}.
\end{equation*}
\notag
$$
Для параметров $ a\in \mathbb R_+$, $ b\in \mathbb R$ определим класс
$$
\begin{equation*}
{\mathbf W}^{a,b}_A:=\{f\colon \|f_j\|_A \leqslant 2^{-aj}(\overline j)^{(d-1)b},\, \overline j:=\max(j,1), \, j\in \mathbb{N}\}.
\end{equation*}
\notag
$$
В этом случае
$$
\begin{equation*}
G_j:=\bigcup_{{\mathbf s}\colon \|{\mathbf s}\|_1 \leqslant j} \rho({\mathbf s}), \qquad j=1,2,\dots,
\end{equation*}
\notag
$$
и классы ${\mathbf W}^{a,b}_A$ с $b=0$ аналогичны определенным выше классам ${\mathbf A}^a_1(\mathcal T^d,\mathcal G)$. Более узкая версия ${\mathbf A}^a_1(\mathcal T^d,\mathcal G,\infty)$ этих классов была недавно изучена в [9]. Классы ${\mathbf A}^r_\beta(\Psi)$, изучаемые в этой работе, соответствуют случаю классов ${\mathbf A}^r_\beta(\Psi,\mathcal G)$ с
$$
\begin{equation}
G_j:=\{{\mathbf k}\in \mathbb Z^d\colon \|{\mathbf k}\|_\infty <2^j\}, \qquad j=1,2,\dots\,.
\end{equation}
\tag{6.8}
$$
Отметим, что классы ${\mathbf A}^r_\beta(\mathcal T^d)$ связаны с периодическими изотропными классами Никольского $H^r_q$. Имеется несколько эквивалентных определений классов $H^r_q$. Дадим удобное для нас определение. Пусть $r>0$ и $1\leqslant q\leqslant \infty$. Класс $H^r_q$ состоит из периодических функций $f$ от $d$ переменных, удовлетворяющих следующим условиям:
$$
\begin{equation*}
\biggl\|\sum_{[2^{j-1}] \leqslant \|{\mathbf k}\|_\infty< 2^j} \widehat f({\mathbf k}) e^{i({\mathbf k},{\mathbf x})}\biggr\|_q \leqslant 2^{-rj}, \qquad j=0,1,\dots\,.
\end{equation*}
\notag
$$
Например, легко видеть, что в случае $q=2$ и $r/d >1/2$ класс $H^r_q$ вложен в класс ${\mathbf A}^{r-d/2}_1(\mathcal T^d)$. Однако класс ${\mathbf A}^{r-d/2}_1(\mathcal T^d)$ значительно больше, чем класс $H^r_2$. Например, возьмем ${\mathbf k} \in G_j\setminus G_{j-1}$ с $G_j$, определенным в (6.8). Тогда функция $g_{\mathbf k}:=2^{-(r-d/2)j}e^{i({\mathbf k},{\mathbf x})}$ принадлежит ${\mathbf A}^{r-d/2}_1(\mathcal T^d)$, но не принадлежит никакому классу $H^{r'}_2$ с $r'> r-d/2$. Приведем краткое сравнение результатов о восстановлении по выборке в классах $H^r_q$ и ${\mathbf A}^r_\beta(\mathcal T^d)$. Напомним постановку задачи об оптимальном линейном восстановлении. Для фиксированных $m$ и множества точек $\xi:=\{\xi^j\}_{j=1}^m\subset\Omega$ пусть $\Phi $ – линейный оператор из $\mathbb C^m$ в $L_p(\Omega,\mu)$. Определим для класса ${\mathbf F}$ (обычно центрально симметричное и компактное подмножество $L_p(\Omega,\mu)$) (см. [14])
$$
\begin{equation*}
\varrho_m({\mathbf F},L_p):=\inf_{\text{линейные}\, \Phi;\,\xi} \, \sup_{f\in {\mathbf F}} \|f-\Phi(f(\xi^1),\dots,f(\xi^m))\|_p.
\end{equation*}
\notag
$$
Известно (см. [17; теорема 3.6.4, с. 125]), что для всех $1\leqslant p,q\leqslant \infty$, $r >d/q$, имеем
$$
\begin{equation}
\varrho_m(H^r_q,L_p) \asymp m^{-r/d+(1/q-1/p)_+}, \qquad (a)_+:=\max(a,0).
\end{equation}
\tag{6.9}
$$
Ясно, что (6.9) влечет такие же верхние оценки для $\varrho^o_m(H^r_q,L_p)$. Результаты о нижних оценках для $\varrho^o_m(\mathcal T({\mathbf N},d)_q,L_p)$ из [18; лемма 4.3] и лемма 4.1 этой работы показывают, что выполнено следующее соотношение:
$$
\begin{equation}
\varrho^o_m(H^r_q,L_p) \asymp m^{-r/d+(1/q-1/p)_+}.
\end{equation}
\tag{6.10}
$$
В частности,
$$
\begin{equation}
\varrho^o_m(H^r_2,L_p) \asymp m^{-r/d+(1/2-1/p)_+}.
\end{equation}
\tag{6.11}
$$
Нижняя оценка (1.5) из [18] и нижняя оценка в (1.14) этой работы дают следующую оценку в случае $\beta=1$:
$$
\begin{equation}
\varrho^o_m({\mathbf A}^r_1(\mathcal T^d,L_p) \gg m^{-1/2+(1/2-1/p)_+-r/d}.
\end{equation}
\tag{6.12}
$$
Верхняя оценка в (1.14) этой работы дает следующую оценку:
$$
\begin{equation}
\varrho^o_m({\mathbf A}^r_1(\mathcal T^d,L_p) \ll \biggl(\frac{m}{(\log m)^3}\biggr)^{-1/2+(1/2-1/p)_+-r/d}.
\end{equation}
\tag{6.13}
$$
Соотношения (6.11)–(6.13) означают, что мы получаем близкие оценки для класса $H^r_2$ и более широкого класса ${\mathbf A}^{r-d/2}_1(\mathcal T^d)$, $r>d/2$. Отметим, что для класса $H^r_2$ мы получаем такие же оценки для линейного восстановления по выборке. В [18] доказано, что для линейного восстановления по выборке в классе ${\mathbf A}^r_\beta(\mathcal T^d)$ имеем
$$
\begin{equation}
\varrho_m({\mathbf A}^r_\beta(\mathcal T^d,L_2) \gg m^{-r/d}.
\end{equation}
\tag{6.14}
$$
Неравенства (6.14) с $\beta=1$ и (6.13) с $p=2$ демонстрируют, что нелинейное восстановление по выборке обеспечивает лучшие гарантии ошибки, чем линейное восстановление по выборке.
Цитирование в формате AMSBIB
\RBibitem{Tem24} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|