| Успехи математических наук |
|
|
|
|
|
Эта публикация цитируется в 6 научных статьях (всего в 6 статьях) Односторонние неравенства дискретизации и восстановление по выборке И. В. Лимоноваabc, Ю. В. Малыхинab, В. Н. Темляковabcd a Математический институт им. В. А. Стеклова Российской академии наук b Московский государственный университет им. М. В. Ломоносова c Московский центр фундаментальной и прикладной математики d University of South Carolina, Columbia, SC, USA
Англоязычная версия:
Russian Mathematical Surveys, 2024, Volume 79, Issue 3, Pages DOI: https://doi.org/10.4213/rm10175e 
Реферативные базы данных:
     1. ВведениеВ настоящее время достигнут значительный прогресс в изучении дискретизации интегральных норм как для заданного конечномерного пространства функций, так и для конечного набора таких пространств (универсальная дискретизация). Результаты о дискретизации по значениям в точках оказываются весьма полезными для различных приложений, в частности в задачах восстановления по выборке (т. е. по значениям в точках выборки). С недавними результатами о восстановлении по выборке читатель может ознакомиться в работах [4], [27], [28], [34], [45], [3], [18], [48], [30], [17], [14], [9]–[11], [1], [25], [26], [46], [24], [47], [40]. Систематическое изучение дискретизации по значениям в точках $L_p$-норм функций из заданного конечномерного подпространства было начато в 2017 г. в [42] и [43]. Первые результаты в этом направлении были получены в 1930-е годы и восходят к С. Н. Бернштейну, Й. Марцинкевичу и А. Зигмунду. В настоящее время это обширная и активно развивающаяся область исследований, имеющая глубокие связи с другими важными направлениями. На эту тему есть две обзорные работы: [7] и [20]. Работа [7] охватывает результаты по точной весовой дискретизации, дискретизации равномерной нормы многомерных тригонометрических полиномов, а также некоторые результаты об универсальной дискретизации. В [20] приводятся недавние результаты о дискретизации по значениям в точках и подробно рассматриваются связи с другими областями исследований, в частности с теорией моментов случайных векторов, теорией подматриц, обладающих хорошими свойствами, с вложениями конечномерных подпространств, с разреженной аппроксимацией, теорией обучения и восстановлением по выборке. В последнее время в ряде работ результаты о дискретизации и об универсальной дискретизации по значениям в точках успешно применялись в задачах восстановления по выборке. Более того, оказалось, что для некоторых из этих приложений достаточно иметь одностороннее неравенство дискретизации. Это обстоятельство побудило нас написать настоящую работу про односторонние неравенства дискретизации и их приложения к задачам восстановления по выборке. В этом смысле статья дополняет обзоры [7] и [20]. Пусть $(\Omega,\mu)$ – вероятностное пространство. Мы рассматриваем измеримые функции, которые определены в каждой точке $\Omega$, и не отождествляем функции, различающиеся на множестве меры нуль (обоснование см. в [20; разд. 2]). Определим стандартным образом $L_p$-норму при $1\leqslant p< \infty$:
$$
\begin{equation*}
\|f\|_p:=\|f\|_{L_p(\Omega,\mu)}:= \biggl(\int_\Omega |f|^p\,d\mu\biggr)^{1/p}.
\end{equation*}
\notag
$$
Под $L_\infty$-нормой мы понимаем равномерную норму ограниченных функций: и, с некоторым отклонением от стандартных обозначений, мы пишем $L_\infty(\Omega)$ для пространства ${\mathcal B}(\Omega)$ ограниченных функций на $\Omega$. В разделах 5 и 6 нам будет удобнее предполагать, что $\Omega$ – компакт в $\mathbb{R}^d$, и рассматривать пространство ${\mathcal C}(\Omega)$ непрерывных функций.Мы также будем рассматривать дискретное пространство $L_p^m$ векторов ${\mathbf x}=(x_1,\dots,x_m)\in\mathbb{R}^m$ (или $\mathbb C^m$) с нормой
$$
\begin{equation}
\|{\mathbf x}\|_p:=\begin{cases} \biggl(\dfrac{1}{m}\displaystyle\sum_{j=1}^m|x_j|^p\biggr)^{1/p},& 1\leqslant p<\infty, \\ \displaystyle\max_{1\leqslant j\leqslant m}|x_j|,& p=\infty. \end{cases}
\end{equation}
\tag{1.1}
$$
Эта норма используется реже, чем стандартная $\ell_p^m$-норма (без весов $1/m$), но в данном случае она более удобна. Функции $f$, определенной на $\Omega$, и набору точек $\xi^1,\dots,\xi^m\in\Omega$ мы ставим в соответствие вектор-выборку (sampling vector) Существующие работы по дискретизации посвящены двусторонним неравенствам, которые показывают, что дискретная норма вектора-выборки ограничена сверху и снизу интегральной $L_p$-нормой функции (умноженной на некоторые константы). Такого рода неравенства также известны как неравенства Марцинкевича–Зигмунда. Опишем их более подробно. Задача дискретизации типа МарцинкевичаПусть $(\Omega,\mu)$ – вероятностное пространство. Будем говорить, что линейное подпространство $X_N$ (индекс $N$ здесь обычно обозначает размерность $X_N$) пространства $L_p(\Omega,\mu)$, $1\leqslant p< \infty$, допускает теорему дискретизации типа Марцинкевича с параметрами $m\in \mathbb{N}$ и $p$ и с положительными постоянными $C_1$ и $C_2$, $C_1\leqslant C_2$, если существует множество $\{\xi^j\}_{j=1}^m\subset\Omega$ такое, что для любого $f\in X_N$ выполняются неравенства
$$
\begin{equation}
C_1\|f\|_p^p \leqslant \frac{1}{m} \sum_{j=1}^m |f(\xi^j)|^p \leqslant C_2\|f\|_p^p.
\end{equation}
\tag{1.3}
$$
Рассматривалась следующая задача: для какого $m$ заданное подпространство $X_N$ допускает неравенства (1.3) дискретизации типа Марцинкевича? Задача дискретизации типа БернштейнаВ случае $p=\infty$ мы определяем $L_\infty$ как пространство ограниченных функций на $\Omega$ и требуем, чтобы выполнялись неравенства
$$
\begin{equation}
C_1\|f\|_\infty \leqslant \max_{1\leqslant j\leqslant m} |f(\xi^j)| \leqslant \|f\|_\infty \quad \forall\,f\in X_N.
\end{equation}
\tag{1.4}
$$
Недавно было установлено, что результаты о дискретизации по значениям в точках и об универсальной дискретизации квадратичной нормы полезны в задачах восстановления по выборке (см. [45]) и разреженного восстановления по выборке (см. [9], [11]) с ошибкой, измеряемой в квадратичной норме. Оказалось, что в некоторых случаях для доказательства соответствующих результатов достаточно предполагать наличие односторонней дискретизации. Неравенство (1.3) состоит из двух односторонних неравенств: левого неравенства дискретизации (ЛНД) и правого неравенства дискретизации (ПНД). В этой статье мы рассматриваем ЛНД и ПНД по отдельности. Ясно, что дискретизация типа Бернштейна является примером одностороннего неравенства дискретизации, а именно ЛНД. ПНД в неравенстве (1.4) тривиально. Отметим, что в литературе встречаются и другие названия для односторонних неравенств. Например, Д. Любински называет ПНД прямыми неравенствами, а ЛНД – обратными (см., например, [31]). В этой работе мы изучаем более общие односторонние неравенства между интегральной $L_p$-нормой функции $f$ и дискретной $L_q^m$-нормой (или весовой $\ell_q$-нормой) вектора $S(f,\xi)$. Отметим, что параметры $p$ и $q$ могут не совпадать. Мы рассматриваем следующие постановки задач. Односторонние задачи дискретизацииПусть $(\Omega,\mu)$ – вероятностное пространство, $X$ – некоторое множество функций на $\Omega$, и пусть $1\leqslant p,q\leqslant \infty$, $D>0$, $m\in\mathbb{N}$. Нас интересуют следующие свойства. ЛНД. Будем говорить, что множество $X$ допускает левое неравенство дискретизации, если
$$
\begin{equation}
\|f\|_p \leqslant D\biggl(\frac{1}{m}\sum_{j=1}^m |f(\xi^j)|^q\biggr)^{1/q}\quad \forall\,f \in X
\end{equation}
\tag{1.5}
$$
для некоторых точек $\xi^1,\dots,\xi^m\in\Omega$. Будем обозначать это свойство следующим образом: $X \in \mathcal{LD}(m,p,q,D)$. ПНД. Будем говорить, что множество $X$ допускает правое неравенство дискретизации, если
$$
\begin{equation}
\biggl(\frac{1}{m} \sum_{j=1}^m|f(\xi^j)|^q\biggr)^{1/q} \leqslant D\|f\|_p \quad \forall\,f \in X
\end{equation}
\tag{1.6}
$$
для некоторых точек $\xi^1,\dots,\xi^m\in\Omega$. Обозначение: $X \in \mathcal{RD}(m,p,q,D)$. В случае $q=\infty$ дискретная норма в (1.5) или (1.6) понимается обычным образом, см. (1.1). Отметим, что в определении ЛНД и ПНД разрешено совпадение некоторых из точек $\xi^1,\dots,\xi^m$. Допуская некоторую вольность, мы будем писать $\xi=\{\xi^j\}_{j=1}^m$, подразумевая, что некоторые элементы в этом множестве могут совпадать. Задача состоит в том, чтобы найти наименьшее $m\in\mathbb{N}$ такое, что ЛНД/ПНД имеет место для заданного $N$-мерного подпространства $X_N$ или набора подпространств $X_N$. ЛНД и ПНД могут быть сформулированы в терминах оператора выборки $S(\,\cdot\,,\xi)\colon L_p \to L_q^m$ (см. формулу (1.2)). ПНД означает выполнение неравенства $\|S f\|_q \leqslant D\|f\|_p$ для всех $f\in X$. ЛНД эквивалентно тому, что $\|f\|_p \leqslant D\|S f\|_q$ для всех $f\in X$. Будем также использовать запись $\operatorname{\text{ПНД}}(p,q)$ и $\operatorname{\text{ЛНД}}(p,q)$ в тех случаях, когда хотим подчеркнуть зависимость от параметров. Для краткости в случае $p=q$ мы часто будем указывать только один параметр, например писать $\mathcal{LD}(m,p,D)$, $\operatorname{\text{ПНД}}(p)$. Неравенства (1.5) и (1.6) выше сформулированы для случая дискретизации с равными весами $1/m$ для каждой точки $\xi^j$, $j=1,\dots,m$. В общем случае (вес $\lambda_j$ в точке $\xi^j$, $j=1,\dots,m$) мы получаем аналоги ЛНД и ПНД для весовой дискретизации, которые будем называть соответственно ВЛНД:
$$
\begin{equation*}
\|f\|_p \leqslant D\biggl(\,\sum_{j=1}^m \lambda_j|f(\xi^j)|^q\biggr)^{1/q}\quad \forall\,f \in X,
\end{equation*}
\notag
$$
и ВПНД:
$$
\begin{equation*}
\biggl(\,\sum_{j=1}^m \lambda_j|f(\xi^j)|^q\biggr)^{1/q} \leqslant D \|f\|_p\quad \forall\,f \in X.
\end{equation*}
\notag
$$
Отметим, что свойства $\mathcal{LD}$ и $\mathcal{RD}$ почти монотонны по числу точек в следующем смысле. Если $X\in\mathcal{LD}(m,p,q,D)$, то, во-первых, $X\in\mathcal{LD}(km,p,q,D)$ для любого $k\in\mathbb N$ (достаточно повторить каждую точку $k$ раз). Во-вторых, $X\in\mathcal{LD}(m',p,q,2^{1/q}D)$ для всех $m'>m$. Действительно, если $m'\leqslant 2m$, возьмём $m$ точек, обеспечивающих свойство $X\in\mathcal{LD}(m,p,q,D)$, и продублируем $m'-m$ из них; $l_q^m$-норма функций при этом не уменьшится, а нормирующий множитель $1/m^{1/q}$ уменьшится в $(m'/m)^{1/q}\leqslant 2^{1/q}$ раз; получаем $X\in\mathcal{LD}(m',p,q,2^{1/q}D)$. Общий случай сводится к рассмотренному в силу первого замечания. То же имеет место и для ПНД. Поэтому если нам не важны мультипликативные абсолютные константы, то нет разницы между утверждением
$$
\begin{equation*}
\text{``}X\in\mathcal{LD}(m,p,q,C_2)\quad\text{для некоторого}\quad m\leqslant C_1N\log N\text{''}
\end{equation*}
\notag
$$
и утверждением
$$
\begin{equation*}
\text{``}X\in\mathcal{LD}(C_1N\log N,p,q,C_2)\text{''}
\end{equation*}
\notag
$$
(в последнем выражении мы допускаем нецелые значения первого параметра $C_1N\log N$ и предполагаем, что число точек равно $[C_1N\log N]$). Структура работыДадим краткое описание наших результатов. В разделе 2 по большей части изучается ПНД. Нас интересуют нижние оценки на $m$, при которых возможно $\mathcal{RD}(m,p,q,D)$. В предложении 2.1 для $2<p<\infty$, $1\leqslant q<\infty$ мы получаем нижнюю оценку на $m$, при которой возможно ПНД при некоторых предположениях относительно подпространства $X_N$. В качестве следствия (см. следствие 2.1) мы устанавливаем, что для выполнения ПНД для подпространства ${\mathcal T}(\Lambda_N)$, порождённого лакунарной тригонометрической системой размера $N$, в случае $2<q<\infty$ необходимо как минимум порядка $N^{q/2}$ точек. Мы также показываем (см. замечание 2.2), что для ЛНД для подпространства ${\mathcal T}(\Lambda_N)$ достаточно использовать $m$ порядка $N$ точек. Кроме того, мы доказываем (см. предложение 2.3), что если оператор выборки инъективен, то нет универсальной границы для $m$ в терминах $N$, которая бы гарантировала выполнение ПНД для всех подпространств размерности $N$. Раздел 3 посвящён ЛНД. Мы показываем, что из ВЛНД с неотрицательными весами следует ЛНД (см. предложение 3.1). В качестве следствия мы получаем, что $\operatorname{\text{ЛНД}}(2)$ выполнено для любого $N$-мерного подпространства с числом точек $m$ порядка $N$ (см. предложение 3.2). Также мы формулируем открытую проблему. В разделе 4 обсуждается связь между задачами о дискретизации по значениям в точках и известными постановками о нахождении подматриц маленького размера, обладающих заданными свойствами. В частности, мы показываем, что выполнение $\operatorname{\text{ПНД}}(2)$ с $m=N$ точками является следствием результата А. А. Лунина о матрицах. В разделе 5 исследуется задача восстановления по выборке. По большей части это обзор известных результатов с простыми комментариями по их улучшению. Здесь важен случай, когда $p\ne q$. Например, оказалось, что некоторые результаты, доказанные с использованием $\operatorname{\text{ЛНД}}(p,p)$, могут быть доказаны при более слабом предположении $\operatorname{\text{ЛНД}}(p,\infty)$:
$$
\begin{equation}
\|f\|_p \leqslant D \max_{1\leqslant j \leqslant m} |f(\xi^j)|,
\end{equation}
\tag{1.7}
$$
где $p\in[1,\infty)$ (см. теорему 5.2). Кроме того, в разделе 5 мы покажем, как известные результаты о дискретизации равномерной нормы могут быть использованы вместе с результатом Дж. Кифера и Дж. Вольфовица [22] для получения ЛНД. В разделе 6 приводится краткий обзор совсем недавних результатов из работ [9]–[11]. Кроме того, как и в разделе 5, мы показываем, что некоторые из этих результатов можно усилить, заменив предположение ЛНД с параметром $p$ на более слабое предположение $\operatorname{\text{ЛНД}}(p,\infty)$ с $p\geqslant 1$ (см. (1.7)). В разделе 7 обсуждается задача дискретизации равномерной нормы. По своей природе эта задача является задачей об ЛНД, поскольку соответствующее ПНД в этом случае тривиально. В разделе 7 нас интересуют нижние границы величины $m$, необходимые для дискретизации. Теорема 7.1 является новой, она распространяет ранее известный результат для тригонометрической системы на более общие системы. Затем мы обсуждаем применение теоремы 7.1 к случаю, когда рассматриваемая система является системой Сидона. Мы будем часто использовать понятие неравенства Никольского. Для удобства читателя мы формулируем его здесь. Другие определения и обозначения вводятся ниже в тексте. Неравенства типа НикольскогоПусть $1\leqslant p\leqslant q\leqslant\infty$ и $X_N\subset L_q(\Omega)$. Неравенство называется неравенством Никольского для пары $(p,q)$ с константой $M$. Мы также будем использовать следующую краткую запись: $X_N \in \operatorname{NI}(p,q,M)$. Обычно $M$ зависит от $N$, например, $M$ может быть порядка $N^{1/p-1/q}$.2. Правые неравенства дискретизации (ПНД)В этом разделе обсуждаются необходимые для выполнения ПНД и ВПНД условия на $m$. Начнём с весовой дискретизации. Лемма 2.1. Пусть $2<p<\infty$, $1\leqslant q<\infty$ и $X_N\in\operatorname{NI}(2,p,M)$ с некоторой постоянной $M$. Предположим, что точки $\{\xi^j\}_{j=1}^m\subset \Omega$ и неотрицательные веса $\{\lambda_j\}_{j=1}^m$ таковы, что для любого $f\in X_N$ выполнено неравенство Тогда для любого ортонормированного базиса $\{u_i\}_{i=1}^N$ подпространства $X_N$ и любого $j\in \{1,\dots,m\}$ имеем: Доказательство. Хорошо известно (и легко проверить), что для любого $\omega\in\Omega$ выполнено равенство
$$
\begin{equation}
\biggl(\,\sum_{i=1}^N|u_i(\omega)|^2\biggr)^{1/2}= \sup_{f\in X_N:\|f\|_2\leqslant 1}|f(\omega)|.
\end{equation}
\tag{2.2}
$$
Пользуясь тривиальной оценкой $\lambda_j|f(\xi^j)|^q \leqslant \displaystyle\sum_{k=1}^m\lambda_k |f(\xi^k)|^q$, из (2.2) получаем
$$
\begin{equation*}
\lambda_j\biggl(\,\sum_{i=1}^N |u_i(\xi^j)|^2\biggr)^{q/2} \leqslant \sup_{f\in X_N:\|f\|_2\leqslant 1}\,\sum_{k=1}^m \lambda_k|f(\xi^k)|^q.
\end{equation*}
\notag
$$
Используя (2.1) и предположение о выполнении неравенства Никольского, видим, что правая часть последнего неравенства не превосходит Это завершает доказательство леммы. Замечание 2.1. В лемме 2.1 мы предполагаем, что веса неотрицательны. Однако дискретизация с отрицательными весами также имеет смысл. Например, в работе [29] было отмечено, что даже для случая $p=2$ существуют подпространства такие, что при минимальном числе точек $m$, необходимых для выполнения равенства для любого $f\in X_N$ (точная дискретизация), требуется, чтобы некоторые из весов $\lambda_j$, $j=1,\dots,m$, были отрицательными. Следующее утверждение является прямым следствием леммы 2.1. Предложение 2.1. Пусть $2<p<\infty$, $1\leqslant q<\infty$ и $X_N\in\operatorname{NI}(2,p,M)$ с некоторой постоянной $M$. Пусть $X_N$ обладает ортонормированным базисом $\{u_i\}_{i=1}^N$ со свойством Предположим, что $X_N\in\mathcal{RD}(m,p,q,D)$. Тогда Следствие 2.1. Пусть $\Lambda_N=\{k_i\}_{i=1}^N$ – лакунарная последовательность, т. е. $k_{i+1} \geqslant bk_i$, $b>1$, $i=1,\dots,N-1$. Обозначим Замечание 2.2. В отличие от случая ПНД, выполнения ЛНД при $2<p< \infty$, $2<q<\infty$ для лакунарных полиномов можно добиться с использованием $m=O(N)$ точек. В самом деле, из теоремы 1.1 работы [42] следует, что существует $m \leqslant CN$ точек $\xi^1,\dots,\xi^m$, дающих дискретизацию в $L_2$, откуда сразу следует ЛНД: Предложение 2.2. Пусть $2<p<\infty$ и $X_N\in\operatorname{NI}(2,p,M)$ с некоторой постоянной $M$. Пусть точки $\{\xi^j\}_{j=1}^m\subset \Omega$ и неотрицательные веса $\{\lambda_j\}_{j=1}^m$ таковы, что для любого $f\in X_N$ имеют место неравенства Тогда где $K_p$ – постоянная из неравенства Хинчина. Доказательство. Пусть $\{u_i\}_{i=1}^N$ – ортонормированный базис в $X_N$. Рассмотрим функции
$$
\begin{equation*}
f(\omega,\theta):=\sum_{i=1}^N r_i(\theta)u_i(\omega),
\end{equation*}
\notag
$$
где $\{r_i(\theta)\}_{i=1}^N$ – функции Радемахера на отрезке $[0,1]$. Тогда из предположения (2.3) мы получаем, что для каждого $\theta\in [0,1]$
$$
\begin{equation}
D_1^{-p} N^{p/2}=D_1^{-p}\|f(\,\cdot\,,\theta)\|_2^p \leqslant \sum_{j=1}^m \lambda_j |f(\xi^j,\theta)|^p.
\end{equation}
\tag{2.4}
$$
Интегрируя (2.4) по $\theta$ и используя неравенство Хинчина, получаем
$$
\begin{equation*}
D_1^{-p} N^{p/2} \leqslant \int_0^1\sum_{j=1}^m \lambda_j|f(\xi^j,\theta)|^p\,d\theta \leqslant K_p^p\sum_{j=1}^m\lambda_j\biggl(\,\sum_{i=1}^N |u_i(\xi^j)|^2\biggr)^{p/2}.
\end{equation*}
\notag
$$
Из леммы 2.1 при $q=p$ находим Предложение доказано. Замечание 2.3. В случае $2<p<\infty$ условие слабее, чем два связанных с ним условия ПНД с инъективным оператором выборкиЗдесь мы дадим простое наблюдение о том, что в случае, когда оператор выборки $f\mapsto S(f,\xi)$ инъективен, не существует априорной верхней границы для числа $m$ точек, дающих ПНД. Для $a\in(0,1/2]$ определим функцию $f_a\in C[0,1]$ следующим образом:
$$
\begin{equation*}
f_a(x):=\begin{cases} 1, & 0\leqslant x\leqslant a; \\ 2-\dfrac{x}{a}\,, & a\leqslant x\leqslant 2a; \\ 0, & 2a \leqslant x\leqslant 1. \end{cases}
\end{equation*}
\notag
$$
Предложение 2.3. Пусть $p,q\in[1,\infty)$ и $X_N$ – линейное подпространство пространства $C[0,1]$, которое содержит функции $f_a$ и $f_{a/2}$ при некотором $a\in(0,1/2]$. Предположим, что множество $\{\xi^j\}_{j=1}^m\subset\Omega$ обеспечивает выполнение свойства $X_N\in\mathcal{RD}(m,p,q,D)$ с инъективным оператором выборки, т. е. Тогда Доказательство. Воспользуемся инъективностью оператора выборки для функции $f_{a/2}$ и получим, что хотя бы одна из точек $\xi^j$, $j=1,\dots,m$, лежит на отрезке $[0,a]$. Поэтому из $\operatorname{\text{ПНД}}(p,q)$ для $f_a$ следует, что Отсюда вытекает требуемое неравенство. Предложение доказано. Мы можем взять $a$ в (2.5) сколь угодно малым и получить произвольно большие нижние границы для $m$. Таким образом, не существует верхней границы и для числа $m$ точек, обеспечивающих дискретизацию типа Марцинкевича (1.3). Отметим, что предложение 2.3 даёт решение открытой проблемы 1 из [20]. В терминах работы [20] это означает, что для каждого $1\leqslant p<\infty$ и произвольных положительных постоянных $C_1$ и $C_2$ имеет место равенство $sd(N,p,C_1,C_2)=\infty$. Отметим, что любое подпространство $X_N$ допускает $\operatorname{\text{ПНД}}(2,2)$ c $m=N$ точками (см. предложение 4.1). Это означает, что условие инъективности существенно для ПНД. $\operatorname{\text{ЛНД}}(2,2)$ с $m=O(N)$ точками также имеет место для любого $X_N$ (см. предложение 3.2). Однако мы не можем гарантировать выполнение ЛНД и ПНД с одним и тем же множеством точек с мощностью, ограниченной каким-либо $m(N)$. В противном случае мы бы получили ПНД с инъективным оператором выборки, что противоречило бы предложению 2.3. Из предложения 3.2 работы [15] следуют нижние оценки числа точек, необходимых для ПНД в случае подпространств с неравенством Никольского. Мы отсылаем читателя к [15] за конструкцией и за результатом в случае, когда $X_N\in \operatorname{NI}(1,\infty,(1+\varepsilon)N)$. Теорема 2.A [15]. Для любого $1\leqslant q<2$ и любого $N\in\mathbb{N}$ существует $N$-мерное подпространство $X_N\subset L_1([0,1])$ со следующими свойствами: (a) $X_N\in \operatorname{NI}(q,\infty,K_q^{-1}N^{1/q})$; (b) если $m\in\mathbb{N}$ и $t_j,j=1,\dots,m$, таковы, что $\displaystyle\sum_{j=1}^m|f(t_j)|^q>0$ для любого $f\in X_N\setminus\{0\}$, то существует $f\in X_N$, для которого В частности, из (2.6) следует, что если $m=o(N^{2-q/2})$, то $\operatorname{\textrm{ПНД}}(q)$ с инъективным оператором выборки не выполнено. Комментарий о ВПНДПусть $2\leqslant r<p<\infty$, $X_N\in\operatorname{NI}(2,p,M)$, и пусть точки $\xi^1,\dots,\xi^m\in\Omega$ и веса $\lambda_1,\dots,\lambda_m\in\mathbb{R}_+$, $\lambda_1+\dots+\lambda_m=1$, таковы, что
$$
\begin{equation*}
\biggl(\,\sum_{j=1}^{m} \lambda_j|f(\xi^j)|^p\biggr)^{1/p}\leqslant D\|f\|_p \quad \forall\,f\in X_N.
\end{equation*}
\notag
$$
Тогда, записывая $\lambda_j=\lambda_j^{1-r/p}\lambda_j^{r/p}$, из неравенства Гёльдера получаем:
$$
\begin{equation*}
\begin{aligned} \, \sum_{j=1}^{m} \lambda_j|f(\xi^j)|^r&\leqslant \biggl(\,\sum_{j=1}^{m} \lambda_j|f(\xi^j)|^p\biggr)^{r/p} \\ &\leqslant D^r\|f\|_p^r\leqslant D^r M^r\|f\|_2^r\leqslant D^r M^r\|f\|_r^r. \end{aligned}
\end{equation*}
\notag
$$
Таким образом, выполнение $\operatorname{NI}(2,p,M)$ и $\operatorname{\text{ВПНД}}(p)$ с константой $D$ влечёт $\operatorname{\text{ВПНД}}(r)$ с константой $DM$.
3. Левые неравенства дискретизации (ЛНД)Мы докажем, что из ВЛНД с неотрицательными весами следует ЛНД, если сумма весов в ВЛНД ограничена сверху. Это дополнительное свойство выполняется, например, если имеет место двусторонняя весовая дискретизация. Начнём с несколько более общего замечания, чем в [45]. Замечание 3.1. Пусть $\mathcal F$ – набор конечномерных подпространств такой, что если $X_N\in\mathcal F$, то Предложение 3.1. Пусть $X$ – множество функций в $L_p(\Omega,\mu)$. Пусть точки $\xi^1,\dots,\xi^m\in\Omega$ и неотрицательные веса $\lambda_1,\dots,\lambda_m$, $\lambda_1+\dots+\lambda_m\leqslant C$, таковы, что Тогда существует число $m_0\leqslant (C^2+1)m$ такое, что Доказательство. Обозначим $m_0:=\displaystyle\sum_{i=1}^m ([\lambda_iCm]+1)$. Тогда
$$
\begin{equation*}
m_0\leqslant \sum_{i=1}^m \lambda_iCm+m\leqslant (C^2+1)m.
\end{equation*}
\notag
$$
Построим новое множество точек. Для каждого $j=1,\dots,m$ возьмём точку $\xi^j$ $[\lambda_jCm]+1$ раз. Обозначим все полученные точки через $\xi_0^j$, $j=1,\dots,m_0$. Тогда
$$
\begin{equation*}
\begin{aligned} \, \biggl(\,\sum_{j=1}^{m_0}\frac{1}{m_0}\,|f(\xi_0^j)|^q\biggr)^{1/q}&= \biggl(\,\sum_{j=1}^{m}\frac{[\lambda_jCm]+1}{m_0}\, |f({\xi}^j)|^q\biggr)^{1/q} \\ &\geqslant \biggl(\,\sum_{j=1}^{m} \frac{\lambda_jCm}{(C^2+1)m}\, |f({\xi}^j)|^q\biggr)^{1/q}\geqslant \frac{1}{D}\|f\|_p\biggl(\frac{C}{C^2+1}\biggr)^{1/q}. \end{aligned}
\end{equation*}
\notag
$$
Предложение доказано. Применим эту технику к известным теоремам о дискретизации. Предложение 3.2. Пусть $1\leqslant p<\infty$. Существуют положительные постоянные $C_1(p)$ и $C_2(p)$ такие, что для любого $N$-мерного подпространства $X_N \subset L_p(\Omega,\mu)$ выполнено $X_N\in\mathcal{LD}(m, p, C_2)$, т. е. существует множество точек $\{\xi^j\}_{j=1}^m$ такое, что где Доказательство. В случае $p=2$ применим следующий результат [6; теорема 6.4]: существуют три положительные постоянные $C_1'$, $c_0$, $C_0$, множество из $m\leqslant C_1'N$ точек $\xi^1,\dots,\xi^m\in\Omega$ и множество неотрицательных весов $\lambda_j$, $j=1,\dots,m$, такие, что
$$
\begin{equation*}
c_0\|f\|_2^2\leqslant \sum_{j=1}^m \lambda_j |f(\xi^j)|^2 \leqslant C_0\|f\|_2^2\quad \forall\,f\in X_N.
\end{equation*}
\notag
$$
Из этого ВЛНД, замечания 3.1 и предложения 3.1 следует требуемое ЛНД.
Другие случаи также охватываются известными результатами о дискретизации, см. [20; D.20. An upper bound] для $p>2$ и [5; следствия 1.1, 1.2] для $1 \leqslant p < 2$. Предложение доказано. Замечание 3.2. В цитируемых работах результаты о дискретизации часто формулируются для подпространств непрерывных функций, $X_N\subset \mathcal{C}(\Omega)$. Однако любое подпространство $X_N\subset L_p$ всегда можно подходящим образом дискретизировать с помощью достаточного количества точек (см., например, предложение 4.A) и перейти к подпространству функций, определенных на дискретном множестве. Эти функции непрерывны по определению. Таким образом, приведенные результаты работают в общем случае. Мы обнаружили, что предложение 3.2 для $p=2$, т. е. $\operatorname{\text{ЛНД}}(2,2)$
$$
\begin{equation}
\|f\|_2 \leqslant C_2\biggl(\,\sum_{j=1}^{m}\frac{1}{m}\,|f({\xi}^j)|^2\biggr)^{1/2}\quad \forall\,f\in X_N,\quad m\leqslant C_1N,
\end{equation}
\tag{3.2}
$$
было получено независимо другим методом в недавней работе [1; теорема 6.2] (см. также [26; лемма 11]). Открытая проблема 3.1. При каком условии на $m$ произвольное $N$-мерное подпространство $X_N \subset {\mathcal C}(\Omega)$ обладает свойством $X_N\in\mathcal{LD}(m,p,\infty,D)$, где $2<p<\infty$ и $D=D(p)$, т. е. для подходящего множества точек $\{\xi^j\}_{j=1}^m$? Комментарий 3.1. Из теоремы 1.3 работы [19] о дискретизации равномерной нормы следует, что в открытой проблеме 3.1 мы всегда можем взять $m=9^N$, что растёт экспоненциально по $N$. Теорема 1.2 из [19] показывает, что для выполнения $\operatorname{\text{ЛНД}}(\infty)$ для подпространства ${\mathcal T}(\Lambda_N)$ (см. следствие 2.1) требуется $(N/e)\exp\{CN/D^2\}$ точек. Предложение 3.2 гарантирует, что мы можем взять $m$ порядка $N$ в случае $p\leqslant 2$. Из того же предложения 3.2 следует, что мы можем взять $m\leqslant C N^{p/2}\log{N}$ в случае $p>2$ и $m\leqslant CN^{p/2}$ для чётных $p$. Следующая теорема из [26] представляет собой $\operatorname{\text{ЛНД}}(p,2)$. Теорема 3.1 [26; теорема 13]. Пусть $2\leqslant p\leqslant \infty$. Существуют положительные постоянные $C_1=4$ и $C_2=83$ такие, что любое $N$-мерное подпространство $X_N \subset {\mathcal C}(\Omega)$ обладает свойством $X_N\in\mathcal{LD}(C_1N,p,2,C_2 N^{1/2-1/p})$, т. е. существует множество из $m\leqslant C_1N$ точек $\{\xi^j\}_{j=1}^m$ такое, что Некоторые результаты об ЛНД сформулированы в разделе 5: теоремы 5.C, 5.F, 5.5 и 5.G. 4. Матричная постановкаСледующий результат из работы [15] гарантирует, что для любого подпространства $X_N$ можно найти достаточно большое число $m_0\in\mathbb{N}$ такое, что $X_N\in\mathcal{LD}(m_0,p,K_1)$ и $X_N\in\mathcal{RD}(m_0,p,K_2)$. Предложение 4.A [15; предложение 6.1]. Пусть $1\leqslant p<\infty$, $(\Omega,\mu)$ – вероятностное пространство и $X_N\subset L_p(\Omega,\mu)$ – $N$-мерное подпространство. Тогда для любого $\varepsilon>0$ найдётся $m_0\in\mathbb{N}$ такое, что если $M\geqslant m_0$ и $\{\xi^j\}_{j=1}^M\subset \Omega$ – независимые случайные точки, то с вероятностью, не меньшей чем $1-\varepsilon$, имеют место неравенства Благодаря предложению 4.A задача о нахождении наименьшего $m$, для которого $X_N\in \mathcal{LD}(m,p,D)$ или $X_N\in\mathcal{RD}(m,p,D)$, может быть переформулирована в матричной постановке. Отметим, что похожие на предложение 4.A результаты с дополнительными предположениями об $X_N$ были получены в [6; теорема 2.2]. Пусть $X_N\in\mathcal{LD}(m_0,p,K_1)$:
$$
\begin{equation*}
\|f\|_p \leqslant K_1 \|S(f,\xi)\|_p,\quad \xi=\{\xi^j\}_{j=1}^{m_0}, \quad \forall\,f\in X_N.
\end{equation*}
\notag
$$
Рассмотрим пространство состоящее из векторов-выборок в $\mathbb{R}^{m_0}$ с $L_p^{m_0}$-нормой, см. (1.1). Если мы докажем ЛНД для этого пространства:
$$
\begin{equation}
\biggl(\frac{1}{m_0}\sum_{j=1}^{m_0}|y_j|^p\biggr)^{1/p} \leqslant D\biggl(\frac{1}{m}\sum_{j=1}^m |y_{i_j}|^p\biggr)^{1/p}\quad \forall\,{\mathbf y}=(y_1,\dots,y_{m_0})\in\widetilde{X}_N,
\end{equation}
\tag{4.2}
$$
то получим ЛНД и для исходного пространства:
$$
\begin{equation*}
\|f\|_p \leqslant K_1 \|S(f,\xi)\|_p \leqslant K_1 D \biggl(\frac{1}{m} \sum_{j=1}^m|f(\xi^{i_j})|^p\biggr)^{1/p}\quad \forall\,f\in X_N,
\end{equation*}
\notag
$$
т. е. $X_N\in\mathcal{LD}(m,p,K_1D)$. Случай ПНД аналогичен. Если $X_N\in\mathcal{RD}(m_0,p,K_2)$,
$$
\begin{equation}
\|S(f,\xi)\|_p \leqslant K_2 \|f\|_p,\quad \xi=\{\xi^j\}_{j=1}^{m_0}, \quad \forall\,f\in X_N,
\end{equation}
\tag{4.3}
$$
то ПНД для пространства $\widetilde{X}_N$ влечёт ПНД для исходного пространства. Таким образом, достаточно изучать задачи об ЛНД и ПНД для дискретных систем. Их можно формулировать в матричной постановке. В обзоре [20; M.1] было отмечено, что для произвольного конечномерного подпространства $L_2$ правое неравенство в теореме дискретизации типа Марцинкевича (т. е. ПНД) следует из работы [32] А. А. Лунина. Ниже (см. предложение 4.1) мы покажем, как это доказывается. Напомним, что для пространств, удовлетворяющих неравенству Никольского (1.8) с $p=2$, $q=\infty$, ПНД и ЛНД были получены в [30] с использованием глубоких результатов работы [33]. Удобно представлять пространство векторов-выборок в виде
$$
\begin{equation*}
\widetilde{X}_N=\{A{\mathbf x}\colon{\mathbf x}\in\mathbb{R}^N\}
\end{equation*}
\notag
$$
с подходящей $(m_0\times N)$-матрицей $A$. Существует естественный способ получения такой матрицы. Пусть система $\{u_i\}_{i=1}^N$ является базисом в $X_N$. Обозначим через $A$ матрицу со столбцами $(u_i(\xi^1),\dots,u_i(\xi^{m_0}))^\top$, $i=1,\dots,N$. Тогда для $f=x_1u_1+\dots+x_Nu_N$, ${\mathbf x}=(x_1,\dots,x_N)\in\mathbb{R}^N$, имеем $S(f,\xi)=A{\mathbf x}$. Пусть $A_1$ – это $(m\times N)$-подматрица матрицы $A$, образованная ее строками с номерами $i_1,\dots,i_m$ (здесь мы предполагаем, что индексы $i_j$ различны). Тогда (4.2) примет следующий вид:
$$
\begin{equation}
\|A{\mathbf x}\|_p\leqslant D \|A_1{\mathbf x}\|_p \quad \forall\,{\mathbf x}=(x_1,\dots,x_N)\in \mathbb{R}^N.
\end{equation}
\tag{4.4}
$$
Таким образом, чтобы получить ЛНД для дискретной системы, достаточно найти подматрицу $A_1$ (составленную из каких-то строк $A$), которая удовлетворяет неравенству (4.4), называемому поточечной оценкой (см. [20; разд. 3]). Единственное отличие задачи дискретизации (4.2) от матричной поточечной оценки (4.4) состоит в том, что подматрицы состоят из строк с разными $i_j$, а в дискретизации мы допускаем повторение $i_j$. Аналогично, ПНД для дискретной системы по сути эквивалентно задаче о нахождении подматрицы $A_1$ (из строк $A$) наименьшего возможного размера, для которой выполняется следующая поточечная оценка:
$$
\begin{equation}
\|A_1{\mathbf x}\|_p\leqslant D\|A{\mathbf x}\|_p \quad \forall\,{\mathbf x}=(x_1,\dots,x_N)\in \mathbb{R}^N.
\end{equation}
\tag{4.5}
$$
Подчеркнем, что в (4.4), (4.5) мы рассматриваем дискретные $L_p^m$-нормы (1.1), которые связаны с обычными $\ell_p^m$-нормами следующим образом:
$$
\begin{equation*}
\|{\mathbf z}\|_p=m^{-1/p}\|{\mathbf z}\|_{\ell_p^m}.
\end{equation*}
\notag
$$
Предложение 4.1. Пусть $X_N$ – подпространство $L_2(\Omega,\mu)$ размерности $N$. Тогда $X_N \in \mathcal{RD}(N,2,C)$ для некоторой абсолютной постоянной $C>0$. Доказательство. Из предложения 4.A следует, что при $p=2$ имеет место неравенство (4.3) для некоторого $m_0$ и $K_2=2$. Без ограничения общности можно считать, что $\dim\widetilde{X}_N=N$, см. определение (4.1) (если размерность меньше, чем $N$, мы получим более сильное ПНД с меньшим числом точек). Пусть $\widetilde{X}_N=\{A{\mathbf x}\colon {\mathbf x}\in\mathbb{R}^N\}$. При этом можно взять матрицу $A$ со столбцами, образующими в $L_2^{m_0}$ ортонормированную систему. Для получения ПНД докажем (4.5). По теореме 2 из [32] существует $(N\times N)$-подматрица $A_1$ матрицы $A$ такая, что для некоторой абсолютной постоянной $C>0$. Пользуясь тем, что в нашем случае $\|A{\mathbf x}\|_2=(x_1^2+\dots+x_N^2)^{1/2}=N^{1/2}\|{\mathbf x}\|_2$ для любого ${\mathbf x}\in\mathbb{R}^N$, получим: Значит, $X_N\in\mathcal{RD}(N,2,2C)$. Предложение доказано. Определим операторную $(r,p)$-норму $(M\times N)$-матрицы $A$ следующим образом:
$$
\begin{equation*}
\|A\|_{(r,p)}=\sup_{\|{\mathbf x}\|_{\ell_r^N}\leqslant 1} \|A{\mathbf x}\|_{\ell_p^M}.
\end{equation*}
\notag
$$
Отметим, что оценка (4.5) влечёт выполнение неравенства
$$
\begin{equation}
\|A_1\|_{(r,p)}^p\leqslant D^p\,\frac{m}{m_0}\,\|A\|_{(r,p)}^p\quad\text{для}\ \ r\geqslant 1.
\end{equation}
\tag{4.6}
$$
Первые результаты такого типа были получены Б. С. Кашиным в 1980 г. для операторных $(2,q)$-норм матриц при $1\leqslant q\leqslant 2$ (детали см. в [20; разд. 3]). Если известно, что для любой $(m\times N)$-подматрицы $A_1$ неравенство (4.6) не выполняется, то и (4.5) не имеет места. Поэтому есть надежда на то, что появятся отрицательные результаты о нормах подматриц, которые помогут установить нижние границы числа $m$ для дискретизации.
5. Приложение к восстановлению по выборкеРассмотрим сначала общую задачу восстановления функций из функционального класса и дадим некоторые характеристики оптимального восстановления. Напомним определение оператора выборки (1.2): для заданных $m$ и множества точек $\xi^1,\dots,\xi^m\in\Omega$ функции $f\colon\Omega\to{\mathbb C}$ ставится в соответствие вектор
$$
\begin{equation*}
S(f,\xi):=(f(\xi^1),\dots,f(\xi^m)) \in {\mathbb C}^m.
\end{equation*}
\notag
$$
Каждый линейный оператор $\Phi\colon {\mathbb C}^m\to L_p(\Omega,\mu)$ даёт линейную процедуру восстановления по выборке: Для функционального класса ${\mathbf F}\subset L_p(\Omega,\mu)$ положим
$$
\begin{equation*}
\varrho_m({\mathbf F},L_p):=\inf_{\xi;\, \text{линейные}\,\Phi}\, \sup_{f\in {\mathbf F}}\|f-\Phi(S(f,\xi))\|_p.
\end{equation*}
\notag
$$
Нелинейная модификация этой величины также представляет интерес. Разрешим любое отображение $\Phi\colon {\mathbb C}^m \to X_m\subset L_p(\Omega,\mu)$, где $X_m$ – линейное подпространство размерности $m$. Определим
$$
\begin{equation*}
\varrho_m^*({\mathbf F},L_p):=\inf_{\xi; \Phi; X_m}\, \sup_{f\in {\mathbf F}}\|f-\Phi(S(f,\xi))\|_p.
\end{equation*}
\notag
$$
В обоих случаях мы строим приближающий элемент, который приходит из линейного подпространства размерности $m$. Естественно сравнивать величины $\varrho_m({\mathbf F},L_p)$ и $\varrho_m^*({\mathbf F},L_p)$ с поперечниками по Колмогорову множества ${\mathbf F}$ в $L_p$:
$$
\begin{equation*}
d_m({\mathbf F}, L_p):=\inf_{X_m\subset L_p}\,\sup_{f\in {\mathbf F}}\, \inf_{g\in X_m}\|f-g\|_p.
\end{equation*}
\notag
$$
В определении колмогоровских поперечников для каждого $f\in {\mathbf F}$ в качестве приближающего элемента из $m$-мерного подпространства $X_m$ выбирается элемент наилучшего приближения $f$. Это означает, что в общем случае (т. е. когда $p\ne 2$) этот метод аппроксимации не является линейным. Имеют место следующие очевидные неравенства:
$$
\begin{equation*}
d_m ({\mathbf F}, L_p)\leqslant \varrho_m^*({\mathbf F},L_p)\leqslant \varrho_m({\mathbf F},L_p).
\end{equation*}
\notag
$$
Характеристики $\varrho_m$, $\varrho_m^*$ и их различные варианты хорошо изучены для многих конкретных классов функций. За обзором известных результатов мы отсылаем к книгам [49], [35], [13], [44], [36]–[38] и приведённым в них ссылкам. Определения характеристик $\varrho_m^*$ и $\varrho_m$ были навеяны понятиями поперечников по Колмогорову и линейных поперечников. По-видимому, $\varrho_m^*$ введено в [12], $\varrho_m$ – в [41], а вариант $\varrho_m^*$ без условия отображения в линейное подпространство был введён в [49]. Перейдём теперь к конкретным методам восстановления. Всюду далее в этом разделе $\Omega$ – компакт в $\mathbb{R}^d$; восстанавливаются непрерывные функции $f\in \mathcal{C}(\Omega)$; через $X_N$ обозначается некоторое $N$-мерное подпространство ${\mathcal C}(\Omega)$. Напомним, что мы рассматриваем дискретные нормы
$$
\begin{equation*}
\|S(f,\xi)\|_p:=\biggl(\frac{1}{m}\sum_{j=1}^m|f(\xi^j)|^p\biggr)^{1/p},\qquad 1\leqslant p<\infty,
\end{equation*}
\notag
$$
и Для положительного веса ${\mathbf w}:=(w_1,\dots,w_m)\in \mathbb{R}^m$ определим полунорму
$$
\begin{equation*}
\|S(f,\xi)\|_{p,{\mathbf w}}:= \biggl(\,\sum_{j=1}^m w_j |f(\xi^j)|^p\biggr)^{1/p},\qquad 1\leqslant p<\infty.
\end{equation*}
\notag
$$
Наилучшее приближение $f\in L_p(\Omega,\mu)$, $1\leqslant p\leqslant \infty$, элементами $X_N$ определяется как Приводимая ниже теорема 5.A была доказана в [45] при следующих предположениях. Условие A1 (дискретизация). Пусть $1\leqslant p\leqslant \infty$ и точки $\xi:=\{\xi^j\}_{j=1}^m\subset \Omega$ обеспечивают ВЛНД, т. е. в случае $p<\infty$ для любого $u\in X_N$ имеет место неравенство а в случае $p=\infty$ – неравенство с некоторой положительной постоянной $D$. Условие A2 (веса). Для положительной постоянной $W$ имеем $\displaystyle\sum_{j=1}^m w_j \leqslant W$. Рассмотрим следующий хорошо известный оператор (алгоритм) восстановления (см., например, [4]):
$$
\begin{equation*}
\begin{gathered} \, \ell p{\mathbf w}(\xi)(f):=\ell p{\mathbf w}(\xi,X_N)(f):= \arg\,\min_{u\in X_N}\|S(f-u,\xi)\|_{p,{\mathbf w}},\qquad 1\leqslant p<\infty, \\ \ell \infty(\xi)(f):=\ell \infty(\xi,X_N)(f):= \arg\,\min_{u\in X_N}\|S(f-u,\xi)\|_{\infty}. \end{gathered}
\end{equation*}
\notag
$$
Отметим, что алгоритм $\ell p{\mathbf w}(\xi)$ использует только значения $f(\xi^j)$, $j=1,\dots,m$, функции. В случае $p=2$ алгоритм линеен, это просто ортогональная проекция относительно полунормы $\|\,\cdot\,\|_{2,{\mathbf w}}$. Поэтому в случае $p=2$ ошибка приближения алгоритмом $\ell\,2{\mathbf w}(\xi)$ дает оценку сверху для $\varrho_m(\,\cdot\,,L_2)$. При $p\ne 2$ ошибка приближения алгоритмом $\ell p{\mathbf w}(\xi)$ дает оценку сверху для другой характеристики восстановления – для $\varrho_m^*(\,\cdot\,,L_p)$. Теорема 5.A [45; теорема 2.1]. При условиях A1 и A2 для любого $f\in {\mathcal C}(\Omega)$ имеем при $1\leqslant p<\infty$ Если выполнено условие A1, то для любого $f\in {\mathcal C}(\Omega)$ Докажем вариант теоремы 5.A об ошибке $\|f-\ell p{\mathbf w}(\xi)(f)\|_{\infty} $ при дополнительном предположении о выполнении неравенства Никольского. Теорема 5.1. Пусть $1\leqslant p<\infty$. Предположим, что выполнены условия A1, A2 и $X_N\in \operatorname{NI}(p,\infty,M)$. Тогда для любого $f\in {\mathcal C}(\Omega)$ Доказательство. Доказательство простое, оно повторяет доказательство теоремы 5.A. Обозначим $u:=\ell p{\mathbf w}(\xi)(f)$. Для произвольного $g \in X_N$ имеет место следующая цепочка неравенств:
$$
\begin{equation*}
\begin{aligned} \, \|f-u\|_\infty &\leqslant \|f-g\|_\infty+\|g-u\|_\infty \leqslant \|f-g\|_\infty +M\|g-u\|_p \\ &\leqslant \|f-g\|_\infty+MD\|S(g-u,\xi)\|_{p,{\mathbf w}} \\ &\leqslant \|f-g\|_\infty+MD\bigl(\|S(f-g,\xi)\|_{p,{\mathbf w}}+ \|S(f-u,\xi)\|_{p,{\mathbf w}}\bigr) \\ &\leqslant \|f-g\|_\infty+2MD\|S(f-g,\xi)\|_{p,{\mathbf w}} \\ &\leqslant \|f-g\|_\infty+2MDW^{1/p}\|S(f-g,\xi)\|_{\infty} \leqslant (1+ 2MDW^{1/p})\|f-g\|_\infty. \end{aligned}
\end{equation*}
\notag
$$
Переходя к минимуму по $g\in X_N$, завершаем доказательство теоремы. Далее мы докажем следующий аналог теоремы 5.A при более слабом предположении (5.1) вместо A1. Теорема 5.2. Пусть $p\in [1,\infty)$. Пусть подпространство $X_N\subset {\mathcal C}(\Omega)$ обладает свойством $X_N\in\mathcal{LD}(m,p,\infty,D)$, которое обеспечивается множеством $\xi=\{\xi^j\}_{j=1}^m$: для любого $u\in X_N$ Тогда для любого $f\in {\mathcal C}(\Omega)$ выполнено неравенство Доказательство. Пусть $h\in X_N$ – элемент наилучшего приближения к $f$ из $X_N$ по норме $L_\infty$. Имеем Ясно, что
$$
\begin{equation}
\|S(f-h,\xi)\|_\infty \leqslant \|f-h\|_\infty=d(f, X_N)_\infty.
\end{equation}
\tag{5.3}
$$
Из определения алгоритма $\ell \infty(\xi)$ получаем
$$
\begin{equation}
\|S(f-\ell \infty(\xi)(f),\xi)\|_{\infty} \leqslant \|S(f-h,\xi)\|_{\infty} \leqslant d(f, X_N)_\infty.
\end{equation}
\tag{5.4}
$$
Оценки (5.3) и (5.4) дают
$$
\begin{equation*}
\|S(h-\ell \infty(\xi)(f),\xi)\|_{\infty} \leqslant 2d(f,X_N)_\infty.
\end{equation*}
\notag
$$
Из предположения (5.1) о дискретизации следует, что
$$
\begin{equation}
\|h-\ell \infty(\xi)(f)\|_{p} \leqslant 2D d(f, X_N)_\infty.
\end{equation}
\tag{5.5}
$$
Используя оценки (5.2) и (5.5), получаем что завершает доказательство теоремы. Теоремы 5.A, 5.2 влекут за собой следующие неравенства для любого компакта ${\mathbf F} \subset {\mathcal C}(\Omega)$ и произвольной вероятностной меры $\mu$ на $\Omega$:
$$
\begin{equation}
\varrho_{m}^*({\mathbf F},L_p(\Omega,\mu)) \leqslant Cd_N({\mathbf F},L_\infty), \qquad C=2DW^{1/p}+1, \quad 1\leqslant p<\infty.
\end{equation}
\tag{5.6}
$$
Здесь значение $m$ таково, что в случае теоремы 5.A условия A.1 и A.2, а в случае теоремы 5.2 условие (5.1) выполняются для любого $N$-мерного подпространства ${\mathcal C}(\Omega)$. В случае $p=2$ известно следующее неравенство (см. [45]): существуют две положительные постоянные $b$ и $B$ такие, что для любого компакта $\Omega$ в $\mathbb{R}^d$, любой вероятностной меры $\mu$ на нём и любого компактного подмножества ${\mathbf F}$ в ${\mathcal C}(\Omega)$ имеет место неравенство
$$
\begin{equation}
\varrho_{bn}({\mathbf F},L_2(\Omega,\mu)) \leqslant Bd_n({\mathbf F},L_\infty).
\end{equation}
\tag{5.7}
$$
Известно (см. [20; D.20. A lower bound]), что для дискретизации $L_p$-нормы функций из $N$-мерного подпространства при $2<p<\infty$ необходимо $m> CN^{p/2}$ точек (то же вытекает из следствия 2.1). Таким образом, можно ожидать, что применение рассуждения, аналогичного теореме 5.A, не позволит получить для $m$ порядок лучший, чем $N^{p/2}$, в неравенстве (5.6) при $2<p<\infty$. Условие (5.1) слабее, чем совокупность условий A.1 и A.2. Поэтому есть надежда получить для $m$ порядок лучший, чем $N^{p/2}$, в неравенстве (5.6), используя теорему 5.2, если будет решена открытая проблема 3.1. Открытая проблема 5.1. Пусть $2<p<\infty$. Каков минимальный рост $m(N)$ по $N$, гарантирующий выполнение следующего свойства: для любого компакта ${\mathbf F} \subset {\mathcal C}(\Omega)$ и произвольной вероятностной меры $\mu$ на $\Omega$ Открытая проблема 5.2. Пусть $2<p<\infty$. Каков минимальный рост $m(N)$ по $N$, гарантирующий следующее свойство: для любого компакта ${\mathbf F} \subset {\mathcal C}(\Omega)$ и произвольной вероятностной меры $\mu$ на $\Omega$ Отметим, что из работы [45] (см. неравенство (5.7) выше) известно, что в случае $p=2$ (и поэтому для всех $1\leqslant p\leqslant 2$) можно взять $m(N)\leqslant CN$. Теорема 5.2 и предложение 3.2 при $p=2$ влекут следующий безусловный результат. Теорема 5.3. Существуют две абсолютные положительные постоянные $C_1$ и $C_2$ такие, что для любого $N$-мерного подпространства $X_N \subset {\mathcal C}(\Omega)$ существует множество точек $\{\xi^j\}_{j=1}^m$, $m\leqslant C_1N$, со следующим свойством: для любого $f\in {\mathcal C}(\Omega)$ имеет место неравенство Отметим, что из предложения 3.2 и теоремы 5.A при $p=2$ вытекает следующий результат. Теорема 5.4. Существуют две абсолютные положительные постоянные $C_1$ и $C_2$ такие, что для любого $N$-мерного подпространства $X_N \subset {\mathcal C}(\Omega)$ найдётся множество точек $\{\xi^j\}_{j=1}^m$, $m\leqslant C_1N$, обладающее следующим свойством: для любого $f\in {\mathcal C}(\Omega)$ выполнено неравенство Комментарий о восстановлении по выборке в равномерной нормеХорошо известно, что из результатов о дискретизации $L_2$-нормы по значениям в точках вытекают некоторые результаты о дискретизации в $L_\infty$-норме. Мы проиллюстрируем это явление на некоторых известных примерах. Вероятно, первым примером такого рода являются многомерные тригонометрические полиномы. Через $Q$ обозначим конечное подмножество $\mathbb{Z}^d$, и пусть $|Q|$ – число элементов в $Q$. Пусть
$$
\begin{equation*}
{\mathcal T}(Q):=\biggl\{f\colon f(\mathbf x)= \sum_{{\mathbf k}\in Q}c_{\mathbf k} e^{i({\mathbf k},{\mathbf x})},\ c_{\mathbf k}\in\mathbb{C}\biggr\}.
\end{equation*}
\notag
$$
Следующая теорема была доказана в [42]. Теорема 5.B [42; теорема 1.1]. Существуют три абсолютные положительные постоянные $C_1$, $C_2$ и $C_3$, обладающие следующими свойствами: для любого $d\in \mathbb{N}$ и любого $Q\subset \mathbb{Z}^d$ существует множество из $m \leqslant C_1|Q|$ точек $\xi^j\in {\mathbb T}^d$, $j=1,\dots,m$, такое, что для любого $f\in {\mathcal T}(Q)$ В работе [7] показано, как из теоремы 5.B следует результат о дискретизации $L_\infty$-нормы по значениям в точках. А именно, была доказана следующая теорема. Теорема 5.C [7; теорема 2.9]. Пусть $C_1$ и $C_2$ – две абсолютные положительные постоянные из теоремы 5.B. Тогда для любого $d\in \mathbb{N}$ и любого $Q\subset \mathbb{Z}^d$ существует множество $\xi$ из $m \leqslant C_1|Q|$ точек $\xi^j\in {\mathbb T}^d$, $j=1,\dots,m$, такое, что для любого $f\in {\mathcal T}(Q)$ выполнены неравенства Доказательство. Для удобства читателя мы приводим здесь однострочное доказательство из работы [7]. Мы используем набор точек, который дает теорема 5.B. Тогда $m\leqslant C_1|Q|$ и для любого $f\in{\mathcal T}(Q)$ выполнены неравенства Теорема доказана. Отметим, что в приведенном выше доказательстве помимо результата о дискретизации – теоремы 5.B – использовалось неравенство Никольского $\|f\|_\infty \leqslant |Q|^{1/2}\|f\|_2$. Следующие два результата о дискретизации по значениям в точках показывают, что неравенство Никольского гарантирует выполнение хороших неравенств дискретизации для общих подпространств. Теорема 5.D [30; теорема 1.1]. Пусть $\Omega\subset \mathbb{R}^d$ – непустое множество с вероятностной мерой $\mu$. Существует абсолютная постоянная $C_1$ такая, что для любого подпространства $X_N \in \operatorname{NI}(2,\infty,tN^{1/2})$ найдётся множество $\{\xi^j\}_{j=1}^m\subset\Omega$ из $m \leqslant C_1t^2 N$ точек со следующим свойством: для любого $f\in X_N$ где $C_2$ и $C_3$ – абсолютные положительные постоянные. Теорема 5.E [30; теорема 1.2]. Существуют три абсолютные положительные постоянные $C_1'$, $c_0'$, $C_0'$ такие, что для любого $N$-мерного подпространства $X_N$ комплексного пространства $L_2(\Omega,\mu)$ найдутся множество из $m\leqslant C_1'N$ точек $\xi^1,\dots, \xi^m\in\Omega$ и множество неотрицательных весов $\lambda_j$, $j=1,\dots,m$, такие, что Отметим, что теорема 5.E является обобщением на комплексный случай более раннего результата из [6], установленного для действительного случая. В работе [19] было показано, как из теоремы 5.E следует результат о дискретизации $L_\infty$-нормы по значениям в точках. А именно, была доказана следующая теорема. Теорема 5.F [19; теорема 6.6]. Существуют две абсолютные постоянные $C_1$ и $C_2$ такие, что для любого $X_N \in \operatorname{NI}(2,\infty,M)$ найдётся множество из $m\leqslant C_1N$ точек $\xi^1,\dots,\xi^m\in\Omega$ со следующим свойством: для любого $f\in X_N$ Отметим, что для $M=tN^{1/2}$ из доказательства теоремы 5.F, приведенного в работе [19], вытекает, что теорема 5.D влечёт следующий результат об одновременной дискретизации $L_\infty$- и $L_2$-норм по значениям в точках. Теорема 5.5. Пусть $\Omega\subset \mathbb{R}^d$ – непустое множество с вероятностной мерой $\mu$. Пусть $X_N \in \operatorname{NI}(2,\infty,tN^{1/2})$. Существуют три абсолютные положительные постоянные $C_1$, $C_2$, $C_3$ (те же, что в теореме 5.D) такие, что найдётся множество $\{\xi^j\}_{j=1}^m\subset \Omega$ из $m \leqslant C_1 t^2 N$ точек со следующим свойством: для любого $f\in X_N$ Более того, для любого $f\in X_N$ Теоремы 5.F и 5.5 представляют собой условные результаты: они выполняются при предположении о справедливости неравенства Никольского. Недавно стало понятно, как эти условные результаты можно преобразовать в безусловные (см. [26]). Этот прогресс основан на результате Дж. Кифера и Дж. Вольфовица [22], который гарантирует, что для любого конечномерного подпространства $X_N$ из ${\mathcal C}(\Omega)$ существует вероятностная мера $\mu$ на $\Omega$ такая, что для всех $f\in X_N$ имеет место неравенство
$$
\begin{equation}
\|f\|_\infty \leqslant N^{1/2}\|f\|_{L_2(\Omega,\mu)}.
\end{equation}
\tag{5.9}
$$
Другими словами, для любого $X_N$ в ${\mathcal C}(\Omega)$ при некоторой вероятностной мере $\mu$ имеет место включение $X_N \in \operatorname{NI}(2,\infty, N^{1/2})$. В замечании 6 работы [26] было указано, что “результат Кифера–Вольфовица представляет собой недостающую часть” для известных результатов, доказанных в предположении неравенства Никольского $X_N \in \operatorname{NI}(2,\infty,CN^{1/2})$. В [26] был доказан следующий результат. Теорема 5.G [26; теорема 2]. Существует абсолютная постоянная $C$ такая, что для любого подпространства $X_N$ в ${\mathcal C}(\Omega)$ найдется множество $\{\xi^j\}_{j=1}^m\subset \Omega$ из $m \leqslant 2 N$ точек со следующим свойством: для любого $f\in X_N$ Авторы работы [26] установили (5.10), используя результат Кифера–Вольфовица (5.9) (они также доказали его новый вариант, который представляет собой $\operatorname{\text{ВЛНД}}(\infty,2)$) и $\operatorname{\text{ЛНД}}(2,2)$-свойство (3.2) с $m=2N$ точками. Они также отметили, что из $\operatorname{\text{ЛНД}}(\infty,2)$-свойства (5.10) вытекает следующее $\operatorname{\text{ЛНД}}(\infty,\infty)$:
$$
\begin{equation}
\|f\|_\infty \leqslant C_2N^{1/2}\max_{1\leqslant j\leqslant m}|f(\xi^j)|, \qquad m\leqslant C_1N.
\end{equation}
\tag{5.11}
$$
Отметим, что неравенство (5.11) было приведено в [23]. Оно является прямым следствием теоремы 5.F и результата Кифера–Вольфовица. Замечание 5.1. Результат Кифера–Вольфовица (5.9) превращает первую половину теоремы 5.5 (неравенства (5.8)) при $t=1$ в безусловную, т. е. она выполняется для любого $X_N\subset {\mathcal C}(\Omega)$. Действительно, (5.8) не зависит от меры $\mu$ и можно взять меру из (5.9). Кроме того, теорема 5.5 при $t=1$ дает следующую полезную дискретизацию $L_2$-нормы для $\mu$, при которой $X_N \in \operatorname{NI}(2,\infty, N^{1/2})$ (в частности, для $\mu$ из (5.9)): Перейдем к обсуждению восстановления по выборке в равномерной норме. Неравенство (5.11) обеспечивает выполнение условия A1 о дискретизации с $p=\infty$ и $D=C_2N^{1/2}$. Поэтому из теоремы 5.A следует, что для любого подпространства $X_N\subset {\mathcal C}(\Omega)$ и любой функции $f\in {\mathcal C}(\Omega)$
$$
\begin{equation*}
\|f-\ell\infty(\xi)(f)\|_\infty \leqslant (2C_2N^{1/2}+1)d(f,X_N)_\infty.
\end{equation*}
\notag
$$
В свою очередь, отсюда вытекает, что для любого компакта ${\mathbf F} \subset {\mathcal C}(\Omega)$ имеет место неравенство
$$
\begin{equation}
\varrho_{bn}^*({\mathbf F},L_\infty) \leqslant Bn^{1/2}d_n({\mathbf F},L_\infty),
\end{equation}
\tag{5.12}
$$
где $b$ и $B$ – абсолютные положительные постоянные. Применим теперь теорему 5.1 при $p=2$. Используем теорему 5.E и замечание 3.1, чтобы обеспечить выполнение условий A1, A2, и применим результат Кифера–Вольфовица (5.9), чтобы гарантировать справедливость неравенства Никольского. В результате вместо неравенства (5.12) получаем его линейную версию:
$$
\begin{equation}
\varrho_{bn}({\mathbf F},L_\infty) \leqslant Bn^{1/2}d_n({\mathbf F},L_\infty).
\end{equation}
\tag{5.13}
$$
Отметим, что неравенство (5.13) было сформулировано в [26]. Подчеркнём, что неравенства (5.12) и (5.13) являются прямыми следствиями известных результатов, которые основаны на теоремах о дискретизации $L_2$-нормы по значениям в точках из [30], и результата Кифера–Вольфовица (5.9). Замечание 5.2. В [23; разд. 6] отмечается, что теоремы 5.E и 5.F справедливы для $m\leqslant bN$ с любым $b\in (1,2]$ и константами $c_0'$, $C_0'$ и $C_2$, зависящими от $b$. Отсюда следует, что неравенства (5.11), (5.12) и (5.13) справедливы для любых $C_1\in (1,2]$ и $b\in (1,2]$, при этом $C_2$ может зависеть от $C_1$, а $B$ – от $b$. 6. Универсальная дискретизация и нелинейное восстановлениеВ этом разделе мы получим некоторые результаты, непосредственно связанные с совсем недавними результатами из [8]–[11]. Напомним определение $v$-членного приближения по заданной системе ${\mathcal D}=\{g_i\}_{i=1}^\infty$ в банаховом пространстве $X$. Для $v\in\mathbb{N}$ через $\mathcal{X}_v({\mathcal D})$ обозначим набор всех линейных пространств, порождённых $g_j$, $j\in J$, где $J\subset \mathbb{N}$ и $|J|=v$. Обозначим через $\Sigma_v({\mathcal D})$ множество всех $v$-членных приближений по ${\mathcal D}$:
$$
\begin{equation*}
\Sigma_v({\mathcal D}):=\bigcup_{V\in\mathcal X_v({\mathcal D})} V.
\end{equation*}
\notag
$$
Определим величину
$$
\begin{equation*}
\sigma_v(f,{\mathcal D})_X:=\inf_{g\in\Sigma_v({\mathcal D})}\|f-g\|_X
\end{equation*}
\notag
$$
наилучшего $v$-членного приближения элемента $f\in X$ в норме пространства $X$ по отношению к ${\mathcal D}$. Для функционального класса ${\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
$$
В этой работе мы рассматриваем только конечные системы ${\mathcal D}_N=\{g_i\}_{i=1}^N$. Опишем результаты, полученные в работе [10]. В ней изучались следующие два алгоритма. Обозначим
$$
\begin{equation*}
\ell p(\xi,L):=\ell p{\mathbf w}_m(\xi,L),\qquad {\mathbf w}_m:=\biggl(\frac{1}{m}\,,\dots,\frac{1}{m}\biggr).
\end{equation*}
\notag
$$
Алгоритм $\ell p$. Для системы ${\mathcal D}_N$ и множества точек $\xi:=\{\xi^j\}_{j=1}^m\subset \Omega$ определим алгоритм Алгоритм $\ell p^s$. Для системы ${\mathcal D}_N$ и множества точек $\xi:=\{\xi^j\}_{j=1}^m\subset \Omega$ определим алгоритм Индекс ${\rm s}$ обозначает sample; он призван подчеркнуть, что указанный алгоритм использует только вектор-выборку $S(f,\xi)$. Ясно, что $\ell p^{\rm s}(\xi,\mathcal X_v({\mathcal D}_N))(f)$ – наилучшее $v$-членное приближение функции $f$ по системе ${\mathcal D}_N$ в пространстве $L_p(\xi)$ с нормой $\|S(f,\xi)\|_p$. Поэтому
$$
\begin{equation}
\|f-\ell p^{\rm s}(\xi,\mathcal X_v({\mathcal D}_N))(f)\|_{L_p(\xi)}= \sigma_v(f,{\mathcal D}_N)_{L_p(\xi)}.
\end{equation}
\tag{6.3}
$$
Заметим, что $\ell p^{\rm s}(\xi,\mathcal X_v({\mathcal D}_N))(f)$ может быть не единственным. В настоящей работе мы обсуждаем алгоритм $\ell p^{\rm s}$ и следующую версию алгоритма $\ell p$. Алгоритм $\ell(p,\infty)$. Для системы ${\mathcal D}_N$ и множества точек $\xi:=\{\xi^j\}_{j=1}^m\subset \Omega$ определим алгоритм В работе [10] использовалось следующее предположение об односторонней универсальной дискретизации для набора подпространств. Определение 6.1 [10]. Пусть $1\leqslant p <\infty$. Будем говорить, что множество $\xi:=\{\xi^j\}_{j=1}^m \subset\Omega$ даёт одностороннюю $L_p$-универсальную дискретизацию с параметром $D\geqslant 1$ для набора $\mathcal X:=\{X(n)\}_{n=1}^k$ конечномерных линейных подпространств $X(n)$, если В наших терминах условие (6.5) означает, что и точки $\{\xi^j\}_{j=1}^m$ обеспечивают это свойство. Поэтому мы будем говорить, что множество $\xi$ даёт универсальное $\operatorname{\text{ЛНД}}(p)$.В этой работе мы используем следующее несколько более слабое условие. Определение 6.2. Пусть $1\leqslant p <\infty$. Будем говорить, что множество $\xi:= \{\xi^j\}_{j=1}^m \subset \Omega$ даёт универсальное $\operatorname{\textrm{ЛНД}}(p,\infty)$ с параметром $D\geqslant 1$ для набора $\mathcal X:=\{X(n)\}_{n=1}^k$ конечномерных линейных подпространств $X(n)$, если $\xi$ обеспечивает выполнение свойства $\bigcup\limits_{n=1}^k X(n)\in \mathcal{LD}(m,p,\infty,D)$, т. е. В работе [10] были получены следующие неравенства типа неравенств Лебега для алгоритмов $\ell p$ и 2. Мы приводим здесь только те части теорем из [10], которые связаны с нашими результатами. Теорема 6.A. Пусть $m$, $v$, $N$ – натуральные числа, причём $v\leqslant N$. Пусть ${\mathcal D}_N\subset {\mathcal C}(\Omega)$ – система из $N$ элементов. Предположим, что множество $\xi:=\{\xi^j\}_{j=1}^m \subset \Omega$ даёт универсальное $\operatorname{\textrm{ЛНД}}(p)$-свойство (6.5) с $1\leqslant p<\infty$ для набора $\mathcal X_v({\mathcal D}_N)$. Тогда для любой функции $f \in {\mathcal C}(\Omega)$ имеет место неравенство Теорема 6.B. Пусть $m$, $v$, $N$ – натуральные числа, причём $2v\leqslant N$. Пусть ${\mathcal D}_N\subset{\mathcal C}(\Omega)$ – система из $N$ элементов. Предположим, что множество $\xi:=\{\xi^j\}_{j=1}^m \subset \Omega$ даёт универсальное $\operatorname{\textrm{ЛНД}}(p)$-свойство (6.5) с $1\leqslant p<\infty$ для набора $\mathcal X_{2v}({\mathcal D}_N)$. Тогда для любой функции $f \in {\mathcal C}(\Omega)$ выполнено неравенство Мы докажем два условных результата: теорему 6.1 для алгоритма 3 и теорему 6.2 для алгоритма $\ell\infty^s$. Теорема 6.1. Пусть $m$, $v$, $N$ – натуральные числа такие, что $v\leqslant N$. Пусть ${\mathcal D}_N\subset {\mathcal C}(\Omega)$ – система из $N$ элементов. Предположим, что существует множество $\xi:=\{\xi^j\}_{j=1}^m \subset \Omega $, которое даёт универсальное $\operatorname{\textrm{ЛНД}}(p,\infty)$-свойство (6.6) с $1\leqslant p<\infty$ для набора $\mathcal X_v({\mathcal D}_N)$. Тогда для любой функции $f \in {\mathcal C}(\Omega)$ имеет место неравенство Доказательство. Пусть $\xi:=\{\xi^j\}_{j=1}^m \subset \Omega $ – множество, обеспечивающее универсальное $\operatorname{\text{ЛНД}}(p,\infty)$ для набора $\mathcal X_v({\mathcal D}_N)$. Тогда условие (5.1) выполняется для всех $X(n)$ из набора $\mathcal X_v({\mathcal D}_N)$ с одной и той же постоянной $D$. Поэтому для каждого подпространства $X(n)$ мы можем применить теорему 5.2 с одним и тем же множеством точек $\xi$. Это влечёт для всех $n=1,\dots,k$, $k=\displaystyle\binom{N}{v}$, выполнение неравенства
Теорема доказана. Докажем следующий аналог теоремы 6.1 для алгоритма $\ell\infty^s$, который использует только значения функции в точках $\xi^1,\dots,\xi^m$. Теорема 6.2. Пусть $m$, $v$, $N$ – натуральные числа, причём $2v\leqslant N$. Пусть ${\mathcal D}_N\subset {\mathcal C}(\Omega)$ – система из $N$ элементов. Предположим, что множество $\xi:=\{\xi^j\}_{j=1}^m \subset \Omega$ обеспечивает универсальное $\operatorname{\textrm{ЛНД}}(p,\infty)$-свойство (6.6), где $1\leqslant p<\infty$, для набора $\mathcal X_{2v}({\mathcal D}_N)$. Тогда для любой функции $f \in {\mathcal C}(\Omega)$ имеем неравенство Доказательство. Мы выведем (6.12) из (6.3). Ясно, что
$$
\begin{equation*}
\sigma_v(f,{\mathcal D}_N)_{L_\infty(\xi)} \leqslant \sigma_v(f,{\mathcal D}_N )_\infty.
\end{equation*}
\notag
$$
Для краткости обозначим $u:=\ell \infty^{\rm s}(\xi,\mathcal X_v({\mathcal D}_N))(f)$, и пусть $h$ – элемент наилучшего приближения для $f$ по норме $L_\infty$ из $\Sigma_v({\mathcal D}_N)$. Тогда из (6.3) следует, что
$$
\begin{equation*}
\|h-u\|_{L_\infty(\xi)} \leqslant \|f-h\|_{L_\infty(\xi)}+ \|f-u\|_{L_\infty(\xi)} \leqslant 2\sigma_v(f,{\mathcal D}_N)_\infty.
\end{equation*}
\notag
$$
Пользуясь тем, что $h-u \in \Sigma_{2v}({\mathcal D}_N)$, из условия дискретизации (6.6) заключаем, что
$$
\begin{equation}
\|h-u\|_{L_p(\Omega,\mu)} \leqslant 2D \sigma_v(f,{\mathcal D}_N)_\infty.
\end{equation}
\tag{6.13}
$$
Наконец,
$$
\begin{equation*}
\|f-u\|_{L_p(\Omega,\mu)} \leqslant \|f-h\|_{L_p(\Omega,\mu)}+\|h-u\|_{L_p(\Omega,\mu)}.
\end{equation*}
\notag
$$
Отсюда и из (6.13) вытекает (6.12). Теорема доказана. Обсудим теперь приложение теоремы 6.2 к задаче оптимального восстановления по выборке. Разрешим любое отображение $\Psi\colon {\mathbb C}^m \to L_p(\Omega,\mu)$ и для функционального класса ${\mathbf F}\subset {\mathcal C}(\Omega)$ определим
$$
\begin{equation*}
\varrho_m^{\rm o}({\mathbf F},L_p):=\inf_{\xi}\,\inf_{\Psi}\, \sup_{f\in {\mathbf F}}\|f-\Psi(f(\xi^1),\dots,f(\xi^m))\|_p.
\end{equation*}
\notag
$$
Здесь индекс ${\rm o}$ означает оптимальность. Приводимая ниже теорема является прямым следствием теоремы 6.2. Теорема 6.3. Пусть $m$, $v$, $N$ – натуральные числа с условием $2v\leqslant N$. Пусть $1\leqslant p<\infty$. Предположим, что система ${\mathcal D}_N \subset {\mathcal C}(\Omega)$ такова, что существует множество $\xi:=\{\xi^j\}_{j=1}^m \subset \Omega$, дающее универсальное $\operatorname{\textrm{ЛНД}}(p,\infty)$-свойство (6.6) при $1\leqslant p<\infty$ для набора $\mathcal X_{2v}({\mathcal D}_N)$. Тогда для любого компакта ${\mathbf F}$ в ${\mathcal C}(\Omega)$ имеет место неравенство 7. Некоторые замечания о дискретизации в равномерной нормеДискретизация равномерной нормы является активно развивающейся областью исследований, недавние результаты по этой теме можно найти в работах [19], [23], [46], [26]. Пусть $\Phi:=\{\varphi_i\}_{i=1}^N$ – линейно независимая система действительных функций со свойством Для функции определим вектор Пусть $X_N:=\operatorname{span}(\varphi_1,\dots,\varphi_N)$ и
$$
\begin{equation*}
B_\Phi(L_\infty):=\{A(f)\colon f\in X_N, \ \|f\|_\infty \leqslant 1\} \subset \mathbb{R}^N.
\end{equation*}
\notag
$$
Здесь мы приводим некоторые результаты, аналогичные полученным в [21] (см. также [44], с. 344–345). Начнем со следующего условного утверждения. Теорема 7.1. Пусть система $\Phi$ удовлетворяет условию (7.1) и обладает следующими свойствами: Доказательство. Мы используем следующий результат Е. Д. Глускина из работы [16]. Здесь $\langle{\mathbf x}^1,{\mathbf x}^2\rangle=\displaystyle\sum x^1_ix^2_i$ означает обычное скалярное произведение, а $|{\mathbf x}|=|\langle{\mathbf x},{\mathbf x}\rangle|^{1/2}$ – стандартную евклидову норму.
Теорема 7.A. Пусть $Y=\{{\mathbf y}^1,\dots,{\mathbf y}^S\} \subset \mathbb{R}^N$, $|{\mathbf y}^j|=1$, $j=1,\dots,S$, $S\geqslant N$, Тогда Из свойства (7.3) следует, что $m\geqslant N$ и
$$
\begin{equation}
\{A(f)\colon f\in X_N,\ |f(\xi^j)|\leqslant D^{-1},\ j=1,\dots,m\} \subseteq B_\Phi(L_\infty).
\end{equation}
\tag{7.4}
$$
Далее, для каждого $\omega\in \Omega$
$$
\begin{equation*}
|f(\omega)|=|\langle A(f),{\mathbf z}(\omega)\rangle|,\qquad {\mathbf z}(\omega):=(\varphi_1(\omega),\dots,\varphi_N(\omega)) \in \mathbb{R}^N.
\end{equation*}
\notag
$$
Из (7.1) следует, что $|{\mathbf z}(\omega)|\leqslant(Nt^2)^{1/2}$. Ясно, что условие
$$
\begin{equation*}
|f(\omega)| \leqslant D^{-1}\quad \forall\,\omega\in\{\xi^j\}_{j=1}^m
\end{equation*}
\notag
$$
выполнено, если
$$
\begin{equation*}
|\langle A(f),{\mathbf z}(\xi^j)\rangle| \leqslant D^{-1}, \qquad j=1,\dots,m.
\end{equation*}
\notag
$$
Пусть теперь
$$
\begin{equation*}
{\mathbf y}^j:=\frac{{\mathbf z}(\xi^j)}{|{\mathbf z}(\xi^j)|}\,,\qquad Y:=\{{\mathbf y}^j,\ j=1,\dots, m\}.
\end{equation*}
\notag
$$
Тогда из теоремы 7.A при $S=m$ имеем
$$
\begin{equation}
\operatorname{vol}(W(Y))^{1/N} \geqslant C\biggl(1+\ln \frac{S}{N}\biggr)^{-1/2}.
\end{equation}
\tag{7.5}
$$
Если
$$
\begin{equation*}
|\langle A(f),{\mathbf y}^j\rangle|\leqslant N^{-1/2}t^{-1}D^{-1}, \qquad j=1,\dots,m,
\end{equation*}
\notag
$$
то
$$
\begin{equation*}
\begin{aligned} \, |\langle A(f),{\mathbf z}(\xi^j)\rangle|&= |\langle A(f),{\mathbf y}^j\rangle|\, |{\mathbf z}(\xi^j)| \\ &\leqslant (Nt^2)^{1/2} N^{-1/2}t^{-1}D^{-1}=D^{-1}, \qquad j=1,\dots,m. \end{aligned}
\end{equation*}
\notag
$$
Поэтому из (7.4) и (7.5) получаем
$$
\begin{equation*}
\operatorname{vol}(B_\Phi(L_\infty))^{1/N} \geqslant C'N^{-1/2}t^{-1}D^{-1}\biggl(1+\ln\frac{m}{N}\biggr)^{-1/2}.
\end{equation*}
\notag
$$
Пользуясь предположением (7.2), имеем
$$
\begin{equation*}
tKD \geqslant C'\biggl(1+\ln \frac{m}{N}\biggr)^{-1/2},
\end{equation*}
\notag
$$
что завершает доказательство теоремы. Перейдем к обсуждению одного следствия теоремы 7.1. Пусть $\Phi:=\{\varphi_i\}_{i=1}^N$ – равномерно ограниченная система Сидона:
$$
\begin{equation}
\beta\sum_{i=1}^N |a_i| \leqslant \biggl\|\,\sum_{i=1}^N a_i\varphi_i\biggr\|_\infty \qquad \forall\,\{a_i\}_{i=1}^N;\quad \|\varphi_i\|_\infty \leqslant B,\quad i=1,\dots,N.
\end{equation}
\tag{7.6}
$$
Следствие 7.1. Пусть система $\Phi$ удовлетворяет условиям (7.6), и пусть $X_N\in\mathcal{LD}(m,\infty,D)$. Тогда существует абсолютная постоянная $c>0$ такая, что Доказательство. Из (7.6) следует, что для системы $\Phi$ выполнено условие (7.1) с $t=B$ и
$$
\begin{equation*}
\operatorname{vol}(B_\Phi(L_\infty))^{1/N} \leqslant C_1\beta^{-1}N^{-1}
\end{equation*}
\notag
$$
с абсолютной постоянной $C_1$. Для завершения доказательства осталось применить теорему 7.1 с $t=B$, $K=C_1\beta^{-1}N^{-1/2}$ и $D$. Следствие доказано. Свойство Сидона связано с другими интересными свойствами систем функций. Это дает больше примеров с плохой $L_\infty$-дискретизацией. Напомним определение субгауссовой нормы:
$$
\begin{equation*}
\|\varphi\|_{\psi_2}:=\inf\biggl\{C>0\colon \int_\Omega\exp\biggl\{\frac{\varphi^2}{C^2}\biggr\}\,d\mu\leqslant 2\biggr\}.
\end{equation*}
\notag
$$
Назовём систему $\varphi_1,\dots,\varphi_n$ субгауссовой, если
$$
\begin{equation*}
\biggl\|\,\sum_{k=1}^n a_k \varphi_k\biggr\|_{\psi_2}\leqslant C\biggl(\,\sum_{k=1}^n a_k^2\biggr)^{1/2}
\end{equation*}
\notag
$$
для всех коэффициентов и некоторого фиксированного $C$. Пример 7.1. Для любой равномерно ограниченной ортонормированной субгауссовой системы $\{\varphi_i\}_{i=1}^N$ пространство $X_N:=\operatorname{span}\{\varphi_i\}_{i=1}^N$ требует экспоненциального числа точек для дискретизации нормы в $L_\infty$. В самом деле, в [2; теорема 1.7] было доказано, что такая система содержит подсистему Сидона размера $cN$. Напомним некоторые обозначения из теории вероятностей: $\mathsf{E}$ означает математическое ожидание, $\mathcal N(0,1)$ – стандартное нормальное распределение. Пример 7.2. Для любой равномерно ограниченной ортонормированной системы $\{\varphi_i\}_{i=1}^N$, являющейся сидоновой в среднем: для дискретизации нормы в $L_\infty$ пространства $X_N:=\operatorname{span}\{\varphi_i\}_{i=1}^N$ необходимо экспоненциальное число точек. Действительно, в [39] было доказано, что из сидоновости в среднем для системы $\Phi:=\{\varphi_i\}_{i=1}^N$ следует сидоновость $\Phi^{(4)}:= \{\varphi_i(x^1)\cdots\varphi_i(x^4)\}_{i=1}^N$. Если точки $\{\xi^j\}_{j=1}^m$ дискретизируют $\operatorname{span}\Phi$, то точки $\{(\xi^{j_1},\xi^{j_2})\}$ дискретизируют $\operatorname{span}\Phi^{(2)}$:
$$
\begin{equation*}
\begin{aligned} \, \biggl|\,\sum_{k=1}^N a_k \varphi_k(x)\varphi_k(y)\biggr|&= \biggl|\,\sum_{k=1}^N(a_k\varphi_k(y))\varphi_k(x)\biggr| \\ &\leqslant D \max_{1\leqslant j\leqslant m} \biggl|\,\sum_{k=1}^N(a_k\varphi_k(y))\varphi_k(\xi^j)\biggr| \\ &=D \max_{1\leqslant j\leqslant m} \biggl|\,\sum_{k=1}^N (a_k\varphi_k(\xi^j))\varphi_k(y)\biggr| \\ &\leqslant D^2\max_{1\leqslant j\leqslant m}\,\max_{1\leqslant l\leqslant m} \biggl|\,\sum_{k=1}^N a_k\varphi_k(\xi^j)\varphi_k(\xi^l)\biggr|. \end{aligned}
\end{equation*}
\notag
$$
Далее, точки $\{(\xi^{j_1},\xi^{j_2},\xi^{j_3},\xi^{j_4})\}$ дискретизируют систему Сидона $\operatorname{span}\Phi^{(4)}$, поэтому число точек экспоненциально по $N$. Третий автор благодарит Д. Крига, обратившего его внимание на статью [22].
Цитирование в формате AMSBIB
\RBibitem{LimMalTem24} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|