| Математический сборник |
|
|
|
|
|
Эта публикация цитируется в 4 научных статьях (всего в 4 статьях) Поперечники и жесткость Ю. В. Малыхинab a Математический институт им. В. А. Стеклова Российской академии наук, г. Москва b Московский государственный университет имени М. В. Ломоносова
Англоязычная версия:
Sbornik: Mathematics, 2024, Volume 215, Issue 4, Pages DOI: https://doi.org/10.4213/sm9958e 
Реферативные базы данных:
     § 1. ВведениеВ настоящей работе мы рассматриваем колмогоровские поперечники конечных систем функций. Напомним, что поперечник по Колмогорову $d_n(K,X)$ определяется как минимальное расстояние $\sup_{x\in K}\rho(x,Q_n)_X$ от множества $K$ до всевозможных $n$-мерных подпространств $Q_n$ пространства $X$. Это классическое определение было дано в работе [1] А. Н. Колмогорова в 1936 г. Поперечники – фундаментальная аппроксимативная характеристика множеств, поведение последовательности $(d_n(K,X))_{n=1}^\infty$ активно изучалось для многих функциональных классов и конечномерных множеств. Гл. 13, 14 книги [2], а также книга [3] посвящены этой тематике, cм. также недавний обзор [4; п. 4.3]. Не давая формального определения, будем называть множество жестким, если его нельзя хорошо приблизить пространствами малой размерности. Отправной точкой для нас является известный результат о том, что любая ортонормированная система функций $\varphi_1,\dots,\varphi_N$ является жесткой в $L_2(0,1)$ (конечно, это справедливо в любом евклидовом пространстве):
$$
\begin{equation}
d_n(\{\varphi_1,\dots,\varphi_N\},L_2)=\sqrt{1-\frac nN}.
\end{equation}
\tag{1}
$$
(Это равенство для поперечников впервые использовал С. Б. Стечкин, см. подробности в обзоре [5].) Ситуация меняется, если мы переходим к более слабым метрикам. Теорема A (см. [6]). Пусть $w_1,w_2,\dots$ – система Уолша в нумерации Пэли. Для любого $p\in[1,2)$ найдется $\delta=\delta(p)>0$ такое, что при достаточно больших $N$ имеет место неравенство Эта теорема получена с помощью конструкции, возникшей в теории сложности в связи с близкой задачей о жесткости матриц. Функция жесткости матрицы $A$ определяется как расстояние Хэмминга от $A$ до множества матриц заданного ранга:
$$
\begin{equation*}
\operatorname{Rig}(A,n) :=\min_{\operatorname{rank} B\leqslant n} \#\{(i,j)\colon A_{i,j}\ne B_{i,j}\}.
\end{equation*}
\notag
$$
Эта величина была введена Вэлиантом в 1977 г. как способ получения нижних оценок на схемную сложность (скажем, неравенство $\operatorname{Rig}(A_N,\varepsilon N)\geqslant N^{1+\varepsilon}$ с некоторым фиксированным $\varepsilon>0$ обеспечивает суперлинейную оценку схемной сложности), см. обзор [7]. Недавно был получен достаточно неожиданный результат в [8]: Алман и Виллиамс доказали, что семейство матриц Уолша–Адамара не является жестким – их ранг может быть значительно уменьшен путем изменения небольшого количества элементов. Теорема A использует их конструкцию. В этой работе мы получим достаточные условия для жесткости систем функций в метриках более слабых, чем $L_2$. Усредненный поперечник и $L_1$-жесткостьНаши нижние оценки поперечников основаны на аппроксимационных свойствах случайных векторов в $\mathbb{R}^N$. Пусть $\xi_1,\dots,\xi_N$ – независимые случайные величины с $\mathsf{E}\xi_i=0$ и $\mathsf{E}|\xi_i|=1$. Мы докажем, что для любого $n$-мерного пространства $Q_n\subset\mathbb{R}^N$:
$$
\begin{equation*}
\mathsf{E}\rho(\xi,Q_n)_{\ell_1^N} \geqslant c(\varepsilon)N \quad\text{при }\ n\leqslant N(1-\varepsilon).
\end{equation*}
\notag
$$
Введем обозначение
$$
\begin{equation*}
d_n^{\mathrm{avg}}(\xi,X) :=\inf_{\dim Q_n\leqslant n}\mathsf{E}\rho(\xi,Q_n)_{X}
\end{equation*}
\notag
$$
и назовем эту величину усредненным колмогоровским поперечником случайного вектора $\xi$. Впервые такие поперечники рассматривались С. М. Ворониным и Н. Т. Темиргалиевым в [9]. В дальнейшем они изучались В. Е. Майоровым в [10], Я. Кройцигом в [11] и другими. Мы обсудим свойства усредненных поперечников и обозначение $d_n^{\mathrm{avg}}$ в п. 2.2. Простое равенство
$$
\begin{equation*}
d_n^{\mathrm{avg}}(\xi,\ell_1^N)=Nd_n^{\mathrm{avg}}(\{\xi_1,\dots,\xi_N\},L_1(\Omega))
\end{equation*}
\notag
$$
связывает жесткость случайных векторов в конечномерном пространстве и жесткость конечных систем функций. Отметим, что усреднение в правой части происходит по элементам $L_1$, т.е. мы минимизируем $\frac1N\sum_{k=1}^N\rho(\xi_k,Q_n)$ по подпространствам $L_1$. Итак, мы можем утверждать, что независимость влечет жесткость. Теорема 1.1. Пусть $\xi_1,\dots,\xi_N$ – независимые случайные величины с $\mathsf{E}\xi_i{=}\, 0$ и $\mathsf{E}|\xi_i|=1$. Тогда Конечно, этот результат дает жесткость и для обычных поперечников, так как $d_n \geqslant d_n^{\mathrm{avg}}$. Классический пример независимой системы – система Радемахера. Тот же результат справедлив с заменой независимости на безусловность распределения: $\operatorname{Law}(\xi_1,\dots,\xi_N)=\operatorname{Law}(\pm\xi_1,\dots,\pm\xi_N)$. Аппроксимация в пространстве измеримых функцийРассмотрим пространство $L_0(\mathcal X,\mu)$ всех измеримых функций в некотором пространстве с мерой $(\mathcal X,\mu)$. Сходимость по мере эквивалентна сходимости по различным метрикам, таким как $\displaystyle\int_{\mathcal X}\frac{|f-g|}{1+|f-g|}\,d\mu$ или $\sup\{\varepsilon\colon \mu(|f-g|\geqslant\varepsilon)\geqslant\varepsilon\}$. Для определенности мы используем вторую. Ясно, что метрика в $L_0$ слабее, чем обычные $L_p$-метрики. Приближение в $L_0$ намного менее изучено, чем в $L_p$, однако, как нам представляется, в этой тематике есть много интересных вопросов. В п. 3.2 мы докажем, что независимость влечет жесткость даже в случае $L_0$. Теорема 1.2. Для любого $\varepsilon\in(0,1)$ существует $\delta>0$ такое, что если случайные величины $\xi_1,\dots,\xi_N$ независимы и $\inf_{c\in\mathbb{R}}\|\xi_i-c\|_{L_0}\geqslant\varepsilon$, $i=1,\dots,N$, то Эта теорема также следует из конечномерного результата, а именно, из экспоненциальной оценки
$$
\begin{equation*}
\mathsf{P}(\rho(\xi,Q_n)_{L_0^N} \leqslant \delta)\leqslant 2\exp(-\delta N), \qquad\dim Q_n\leqslant n.
\end{equation*}
\notag
$$
Отметим в связи с этим недавний результат Б. С. Кашина (см. [12]). Теорема B. Существуют абсолютные постоянные $0<\gamma_0<1$, $c_1,c_2>0$ такие, что для $N=1,2,\dots$ и любого ортонормированного базиса $\Psi=\{\psi_k\}_{k=1}^N$ в $\mathbb{R}^N$ и любого линейного подпространства $Q\subset\mathbb{R}^N$, $\dim Q\leqslant c_1 N$, справедливо неравенство Известно, что лакунарные системы $\varphi(k_jx)$ ведут себя похоже на независимые случайные величины, см., например, [13]. Свойство жесткости не является исключением. Мы докажем, что лакунарные системы $\{\varphi(k_1x),\dots,\varphi(k_Nx)\}$ являются жесткими в $L_0$, если $\min k_{j+1}/k_j$ достаточно велико, см. утверждение 3.3. Другой источник жестких систем – случайные матрицы. Хорошо известно, что случайная $(N\times N)$-матрица знаков $\mathcal E$ с высокой вероятностью является очень жесткой: $\operatorname{Rig}(\mathcal E,\delta N)\geqslant \delta N^2$. Мы отмечаем, что это верно и для более слабой метрики $L_0$:
$$
\begin{equation*}
\mathsf{P}\Bigl(\,\min_{\operatorname{rank} B\leqslant\delta N}\|\mathbf{\mathcal E}-B\|_{L_0^{N\times N}}<\delta\Bigr)\leqslant 2\exp(-\delta N^2).
\end{equation*}
\notag
$$
Это дает пример $L_0$-жесткой ортонормированной системы $\{\varphi_1,\dots,\varphi_N\}$ функций, кусочно постоянных на интервалах $((j-1)/N, j/N)$. В $L_0(\mathcal X,\mu)$ есть другая метрика: $\mu\{x\colon f(x)\ne g(x)\}$. Будем обозначать ее через $L_{\mathrm{H}}$; расстояние $\|f-g\|_{L_{\mathrm{H}}}$ является аналогом расстояния Хэмминга. (В теории вероятностей используется термин “индикаторное расстояние”). Метрика $L_{\mathrm{H}}$ возникает в теории функций в контексте теорем об “исправлении”. Так, теорема Лузина утверждает, что $C$ плотно в метрике $L_{\mathrm{H}}$, а теорема Меньшова – что множество функций с равномерно сходящимся рядом Фурье плотно в $L_{\mathrm{H}}$. Наконец, отметим, что функция жесткости матриц является частным случаем усредненного колмогоровского поперечника в нормированной метрике Хэмминга $L_{\mathrm{H}}^N$. Пусть $A$ – вещественная $(M\times N)$-матрица и $W_A=\{A_1,\dots,A_M\}\subset\mathbb{R}^N$ – это множество ее строк. Тогда
$$
\begin{equation*}
\operatorname{Rig}(A,n)=MN d_n^{\mathrm{avg}}(W_A,L_{\mathrm{H}}^N).
\end{equation*}
\notag
$$
Некоторые наши результаты можно сформулировать на языке матриц; иногда он оказывается более удобным. Однако в настоящей работе мы предпочитаем теоретико-функциональный язык. См. также [14]. $S_{p'}$-системыДля случая $1<p<2$ мы получаем менее ограничительные достаточные условия жесткости. Теорема 1.3. Пусть $\varphi_1,\dots,\varphi_N$ – ортонормированная система в $L_2(\mathcal X,\mu)$, $\mu(\mathcal X)=1$. Пусть $1<p<2$ и предположим, что $\{\varphi_k\}$ обладает $S_{p'}$-свойством, т.е. для некоторого $B\geqslant1$ имеем Тогда эта система является жесткой в $L_p$: Известная теорема Бургейна (см. [15]) утверждает, что из любой равномерно ограниченной ортонормированной системы можно выделить $S_{p'}$-подсистему размера $N^{2/p'}$; эта подсистема будет жесткой в $L_p$. Следовательно, для $o(1)$-аппроксимации равномерно ограниченной ОНС в $L_p$ требуется размерность $n\geqslant N^{2/p'}/2$. В частности, зависимость между $n$ и $N$ в теореме A действительно должна быть полиномиальная. Аналог теоремы 1.1 также справедлив при $1<p<2$ (мы не приводим доказательство этого утверждения в работе), однако не имеет места при $p>2$. Положительные результаты об аппроксимацииПусть $G$ – конечная абелева группа; через $\widehat{G}$ обозначим двойственную группу характеров $\chi\colon G\,{\to}\,\mathbb C^*$. В [16] было доказано, что характеры не являются жесткими в $L_{\mathrm{H}}$:
$$
\begin{equation*}
d_n(\widehat{G},L_{\mathrm{H}})\leqslant N^{-1+c\varepsilon} \quad\text{при }\ n\geqslant N\exp(-c(\varepsilon)\log^{c_2}N), \quad N:=|G|.
\end{equation*}
\notag
$$
В контексте результатов Валианта о схемной сложности естественно добиваться малой погрешности аппроксимации, $N^{-1+c\varepsilon}$. Мы же, однако, будем рассматривать и другие “режимы”. В частности, мы докажем, что специальные системы характеров (Фурье и Уолша) допускают приближение пространствами очень малой размерности. Теорема 1.4. Справедливы неравенства Известно, что в $L_p$ при $p<1$ гармоника может быть приближена другими гармониками. Теорема C (см. [17]). Для любого $0<p<1$ равномерно по $M$ и $N\geqslant M$ Мы оценим тригонометрический поперечник $d_n^{\mathrm{T}}$ первых $N$ тригонометрических функций, т.е. приблизим их подпространствами вида $Q_n{=}\,\{\sum_{k\in \Lambda}c_ke(kx)\}$, $|\Lambda|=n$. Теорема 1.5. Для любого $p\in(0,1)$ и достаточно больших $N$ имеем Структура работыВ § 2 мы приведем необходимые определения и используемые факты. В § 3–§ 5 мы докажем результаты, сформулированные во введении, а также некоторые дополнительные результаты. В § 6 мы обсудим остающиеся открытыми вопросы. БлагодарностиАвтор признателен Константину Сергеевичу Рютину, Сергею Владимировичу Асташкину и Борису Сергеевичу Кашину за многочисленные полезные обсуждения материала этой статьи, а также анонимному рецензенту за ряд замечаний. § 2. Предварительные сведения2.1. МетрикиПусть $(\mathcal X,\mu)$ – пространство с конечной мерой, $\mu(\mathcal X)<\infty$. Как обычно, мы отождествляем функции (или случайные величины), отличающиеся на множестве нулевой меры. Мы будем использовать классические $L_p$-пространства для $0<p<\infty$:
$$
\begin{equation*}
\|f\|_p :=\|f\|_{L_p} :=\biggl(\int_{\mathcal X}|f|^p\,d\mu\biggr)^{1/p}.
\end{equation*}
\notag
$$
Пространство $L_0(\mathcal X,\mu)$ состоит из всех измеримых функций. Сходимость по мере в $L_0$ может быть задана различными метриками. Мы будем использовать так называемую метрику Ки–Фаня:
$$
\begin{equation*}
\|f\|_{L_0} :=\sup\bigl\{\varepsilon\geqslant0\colon \mu\{x\colon |f(x)|\geqslant\varepsilon\}\geqslant\varepsilon\bigr\}.
\end{equation*}
\notag
$$
Тогда $\|f-g\|_{L_0}$ является метрикой. Также мы используем обозначение Отметим, что $\|f\|_p \geqslant \|f\|_{L_0}^{1+1/p}$ и $\|f\|_{L_{\mathrm{H}}}\geqslant\|f\|_{L_0}$. Пусть $N\in\mathbb N$. Пространство $\mathbb{R}^N$ с обычной нормой $\ell_p^N$ соответствует считающей мере на $\{1,\dots,N\}$:
$$
\begin{equation*}
\|x\|_p :=\|x\|_{\ell_p^N} :=\biggl(\sum_{k=1}^N |x_k|^p\biggr)^{1/p}.
\end{equation*}
\notag
$$
Единичный шар в этом пространстве обозначим через $B_p^N$. Смысл обозначения $\|\cdot\|_p$ будет ясен из контекста: это либо $\|\cdot\|_{L_p}$-норма, если аргумент – функция, либо $\|\cdot\|_{\ell_p^N}$-норма, если аргумент – конечномерный вектор. В евклидовом случае используется обозначение $|\cdot|$. Через $L_p^N$ мы обозначаем $L_p$-пространство для нормированной (вероятностной) меры на $\{1,\dots,N\}$. Другими словами, $\|x\|_{L_p^N}=N^{-1/p}\|x\|_{\ell_p^N}$, $0<p\leqslant\infty$. Величина $\|x\|_{L_{\mathrm{H}}^N}$ равна доле ненулевых координат вектора, соответствующее расстояние есть нормированное расстояние Хэмминга. Отметим, что $\lim_{p\to+0}\|x\|_p^p=\#\{k\colon x_k\ne0\}=N\|x\|_{L_{\mathrm{H}}^N}$. В случае $p=0$ мы не рассматриваем пространство $\ell_0^N$, только $L_0^N$:
$$
\begin{equation*}
\|x\|_{L_0^N}=\max\bigl\{\varepsilon\colon \#\{i\colon |x_i|\geqslant \varepsilon\} \geqslant \varepsilon N\bigr\}.
\end{equation*}
\notag
$$
Обозначение $\|\cdot\|_0$ не используется. 2.2. ПоперечникиПусть $X$ – линейное пространство с метрикой (или более общим функционалом расстояния) $\rho$. Напомним определение колмогоровского поперечника множества $K\subset X$ размерности $n\in\mathbb Z_+$:
$$
\begin{equation*}
d_n(K,X) :=\inf_{Q_n\subset X} \sup_{x\in K}\rho(x,Q_n)_X,
\end{equation*}
\notag
$$
где $\rho(x,Q)_X :=\inf_{y\in Q} \rho(x,y)$ и инфимум берется по всевозможным линейным подпространствам в $X$ размерности не выше $n$. Обычно $X$ является нормированным пространством с расстоянием $\rho(x,y)=\|x-y\|_X$, однако в оригинальной работе Колмогорова этого не требуется; мы так же будем рассматривать поперечники и в более общей ситуации. Усредненный поперечникПусть $X$ – линейное пространство с метрикой, $\mu$ – борелевская мера на $X$. Для $p\in(0,\infty)$ определим $p$-усредненный поперечник по Колмогорову меры $\mu$ в $X$ следующим образом:
$$
\begin{equation*}
d_n^{\mathrm{avg}}(\mu,X)_p :=\inf_{Q_n\subset X} \biggl(\int_X \rho(x,Q_n)_X^p \,d\mu(x)\biggr)^{1/p}.
\end{equation*}
\notag
$$
При $p=1$ пишем просто $d_n^{\mathrm{avg}}(\mu,X)$. Всюду далее мы будем предполагать, что мера $\mu$ вероятностная. Эквивалентным образом мы можем рассматривать поперечники (борелевских) случайных векторов $\xi$ со значениями в $X$:
$$
\begin{equation*}
d^{\mathrm{avg}}_n(\xi, X)_p :=\inf_{Q_n\subset X} (\mathsf{E} \rho(\xi,Q_n)_X^p)^{1/p}.
\end{equation*}
\notag
$$
Если $K$ – это подмножество в $X$ и из контекста понятно, что означает “случайная точка в $K$”, то под поперечником $d_n^{\mathrm{avg}}(K,X)_p$ будем понимать поперечник для этой случайной точки. Так, для конечного множества $K$ естественно определить
$$
\begin{equation*}
d^{\mathrm{avg}}_n(\{x_1,\dots,x_N\}, X)_p :=\inf_{Q_n\subset X} \biggl(\frac1N \sum_{i=1}^N \rho(x_i,Q_n)_X^p\biggr)^{1/p}.
\end{equation*}
\notag
$$
ОбозначениеОбсудим обозначение $d_n^{\mathrm{avg}}(\xi,X)_p$; оно является новым. Некоторые авторы пишут $d_n^{(\mathrm{a})}$ вместо $d_n^{\mathrm{avg}}$; это может создать путаницу, так как через $d_n^{\mathrm{a}}$ также обозначаются абсолютные поперечники (см. [18]). Использование обозначения $\mathrm{avg}$ общепринято в постановках задач о приближении “в среднем” (average case setting) в основанной на информации теории сложности (information-based complexity), см. [19]. Часто аргументы записывают в другом порядке: $d_n^{(\mathrm{a})}(X,\mu)$; однако, по аналогии с классическим поперечником на первое место резонно ставить объект, поперечник которого считается, поэтому для случайных векторов наш вариант предпочтительнее. СвойстваПрежде всего отметим, что усредненный поперечник дает оценку снизу обычного поперечника:
$$
\begin{equation*}
d_n(K,X) \geqslant d_n^{\mathrm{avg}}(\xi,X)_p,\quad\text{если $\mathsf{P}(\xi\in K)=1$.}
\end{equation*}
\notag
$$
Следующее неравенство вытекает из выпуклости $L_p$-нормы:
$$
\begin{equation}
d_{n_1+n_2}^{\mathrm{avg}}(\xi_1+\xi_2,X)_p \leqslant d_{n_1}^{\mathrm{avg}}(\xi_1,X)_p+ d_{n_2}^{\mathrm{avg}}(\xi_2,X)_p, \qquad 1\leqslant p<\infty.
\end{equation}
\tag{2}
$$
Нам также понадобится Утверждение 2.1. Пусть $\xi_1,\dots,\xi_N\colon\Omega \to \mathbb{R}$ – случайные величины, и пусть $\mathsf{E}|\xi_i|^p< \infty$ при всех $i$. Для $p\in[1,\infty)$ и $n\in\mathbb Z_+$ имеет место равенство В левой части равенства усреднение проводится по конечному множеству “точек” $\xi_1,\dots,\xi_N$ в пространстве $L_p(\Omega)$; в правой части равенства – поперечник случайного вектора $\xi=(\xi_1,\dots,\xi_N)$ в $\mathbb{R}^N$. В случае конечного множества $\Omega$ равенство (3) сразу следует из равенства размерностей пространства строк и пространства столбцов матрицы. Для полноты изложения мы приведем доказательство в общем случае. Доказательство. Рассмотрим погрешность аппроксимации случайных величин $\xi_k\approx \eta_k$:
$$
\begin{equation}
\sum_{k=1}^N \|\xi_k-\eta_k\|_{L_p(\Omega)}^p=\sum_{k=1}^N \mathsf{E}|\xi_k-\eta_k|^p=\mathsf{E} \|\xi-\eta\|_{\ell_p^N}^p.
\end{equation}
\tag{4}
$$
Заметим, что случайные величины $\eta_1,\dots,\eta_N$ лежат в подпространстве $L_p(\Omega)$ размерности не выше $n$ тогда и только тогда, когда найдется подпространство $Q\subset\mathbb{R}^N$, $\dim Q\leqslant n$, для которого
$$
\begin{equation*}
\eta=(\eta_1,\dots,\eta_N)\in Q \quad \text{почти наверное}.
\end{equation*}
\notag
$$
Следовательно,
$$
\begin{equation*}
\mathsf{E} \|\xi-\eta\|_{\ell_p^N}^p \geqslant \mathsf{E}\rho(\xi,Q)_{\ell_p^N}^p \geqslant d_n^{\mathrm{avg}}(\xi,\ell_p^N)_p^p.
\end{equation*}
\notag
$$
Это обеспечивает “$\geqslant$” в (3).
Для доказательства обратного неравенства нужно построить $\eta$ по (почти) оптимальному подпространству $Q\subset\mathbb{R}^N$. Для любого $\varepsilon>0$ найдется борелевское (например, кусочно постоянное) отображение $\pi\colon\mathbb{R}^N\to Q$ такое, что
$$
\begin{equation*}
\|x-\pi(x)\|_{\ell_p^N} \leqslant \rho(x,Q)_{\ell_p^N}+\varepsilon, \qquad x\in\mathbb{R}^N.
\end{equation*}
\notag
$$
Тогда $\eta :=\pi(\xi)$ является (борелевским) случайным вектором. Кроме того, $\eta\in Q$ п.н., поэтому $\eta_1,\dots,\eta_N$ порождают пространство размерности не выше $n$ в $L_p(\Omega)$. Подставим $x=\xi$ в неравенство выше, возьмем $p$-среднее и применим равенство (4), завершая доказательство утверждения. Усредненный поперечник в гильбертовом пространствеПриведем формулу для 2-усредненного поперечника случайного вектора в гильбертовом пространстве. Эта формула является непосредственным обобщением теоремы Эккарта–Юнга о приближении матриц в норме Фробениуса и, по существу, переформулировкой теоремы Исмагилова (см. [20]). Однако используемая нами терминология представляется весьма удобной и естественной и такая формулировка может быть полезна. Доказательство следует работе Исмагилова и приводится для полноты изложения. Пусть $H$ – сепарабельное гильбертово пространство (возможно, конечномерное), $\xi$ – случайный вектор в $H$ и $\mathsf{E}|\xi|^2<\infty$. Рассмотрим корреляционный оператор $A$ этого случайного вектора, определяемый равенством $\langle Au,v\rangle=\mathsf{E}\langle\xi,u\rangle\langle\xi,v\rangle$. Известно, что $A$ – самосопряженный положительный компактный оператор (см., например, [21; гл. 3, § 2]). Его собственные значения $(\lambda_n)$ характеризуются тем, что существует ортонормированный базис $\{\varphi_n\}$, в котором выполнены равенства
$$
\begin{equation}
\mathsf{E}\langle\xi,\varphi_k\rangle^2=\lambda_k, \qquad \mathsf{E}\langle\xi,\varphi_k\rangle\langle\xi,\varphi_l\rangle=0 \quad\text{при }\ k\ne l.
\end{equation}
\tag{5}
$$
(Ясно, что $\{\varphi_n\}$ — собственный базис оператора $A$.) Условимся записывать собственные значения в невозрастающем порядке: $\lambda_1\geqslant\lambda_2\geqslant\dots\geqslant0$. Доказательство. Зафиксируем базис (5); положим $\xi_k:=\langle\xi,\varphi_k\rangle$. Оценим поперечник снизу; пусть $Q_n$ – приближающее пространство с ортонормированным базисом $\{\psi_1,\dots,\psi_n\}$. Тогда
$$
\begin{equation*}
\mathsf{E}\rho(\xi,Q_n)^2=\mathsf{E}|\xi|^2 - \mathsf{E}|P_{Q_n}\xi|^2.
\end{equation*}
\notag
$$
Поскольку $\mathsf{E}|\xi|^2=\sum_{k\geqslant1}\mathsf{E}\xi_k^2=\sum_{k\geqslant 1}\lambda_k$, достаточно оценить сверху норму проекции:
$$
\begin{equation*}
\begin{aligned} \, \mathsf{E}|P_{Q_n}\xi|^2 &=\sum_{j=1}^n \mathsf{E}\langle \xi,\psi_j\rangle^2= \sum_{j=1}^n\mathsf{E} \biggl(\sum_{k\geqslant 1}\xi_k\langle \psi_j,\varphi_k\rangle\biggr)^2 \\ &=\sum_{j=1}^n \sum_{k\geqslant1} \lambda_k \langle \psi_j,\varphi_k\rangle^2=\sum_{k\geqslant 1}\lambda_k \mu_k, \quad\text{где }\ \mu_k :=\sum_{j=1}^n \langle\psi_j,\varphi_k\rangle^2. \end{aligned}
\end{equation*}
\notag
$$
Заметим, что числа $(\mu_k)$ неотрицательны, не превосходят единицы и в сумме равны $n$. В силу монотонности $\lambda_n$ сумма $\sum_{k\geqslant1}\lambda_k\mu_k$ будет максимальна при $\mu_k=1$, $k\leqslant n$, и $\mu_k=0$, $k>n$. Оценка поперечника снизу получена. Равенство достигается на пространстве $Q_n=\operatorname{span}\{\varphi_1,\dots,\varphi_n\}$.
Утверждение доказано. Часто вместо собственных чисел работают с сингулярными числами $\sigma_k:=\lambda_k^{1/2}$. Можно переписать (5) в виде разложения Шмидта:
$$
\begin{equation*}
\xi=\sum_{k\geqslant 1}\sigma_k \eta_k \varphi_k, \qquad \mathsf{E}\eta_k\eta_l=\delta_{k,l}, \qquad\langle\varphi_k,\varphi_l\rangle=\delta_{k,l}.
\end{equation*}
\notag
$$
Тогда $d_n^{\mathrm{avg}}(\xi,H)_2=(\sum_{k>n}\sigma_k^2)^{1/2}$. Для конечных множеств мы получаем теорему Эккарта–Юнга. Пусть матрица $X$ составлена из столбцов $x^1,\dots,x^N\in\mathbb{R}^M$, тогда
$$
\begin{equation*}
d_n^{\mathrm{avg}}(\{x^1,\dots,x^N\},\ell_2^M)_2= N^{-1/2}\biggl(\sum_{k>n}\sigma_k(X)^2\biggr)^{1/2}.
\end{equation*}
\notag
$$
Действительно, сингулярное разложение $X$ дает базис $\{\varphi_k\}_{k=1}^M$, в котором векторы с координатами $(\langle x^1,\varphi_k\rangle,\dots,\langle x^N,\varphi_k\rangle)$ ортогональны и имеют длину $\sigma_k(X)$. Если $\xi$ – случайно выбранный вектор среди $x^i$, то $\mathsf{E}\langle\xi,\varphi_k\rangle^2=N^{-1}\sigma_k^2(X)$ и $\mathsf{E}\langle\xi,\varphi_k\rangle\langle\xi,\varphi_l\rangle=0$, т.е. $\sigma_k(\xi)= N^{-1/2}\sigma_k(X)$. Наконец, любая ортонормированная система $\varphi_1,\dots,\varphi_N$ в евклидовом пространстве $E$ соответствует единичной матрице $X$ (в подходящих координатах), поэтому имеем (см. также (1))
$$
\begin{equation*}
d_n(\{\varphi_1,\dots,\varphi_N\},E)= d_n^{\mathrm{avg}}(\{\varphi_1,\dots,\varphi_N\},E)_2=\sqrt{1-\frac nN}.
\end{equation*}
\notag
$$
Тригонометрический поперечникПусть $\Phi$ – некоторое семейство элементов в $X$. Приближая подпространствами, натянутыми на элементы $\Phi$, мы приходим к понятию $\Phi$-поперечника
$$
\begin{equation*}
d_n^\Phi(K,X) :=\inf_{\varphi_1,\dots,\varphi_n\in\Phi}\sup_{x\in K}\rho(x,\operatorname{span}\{\varphi_i\}_{i=1}^n)_X.
\end{equation*}
\notag
$$
Нам, впрочем, понадобится частный случай, когда $\Phi$ – тригонометрическая система $\{e(kx)\}_{k\in\mathbb Z}$ в непрерывном случае и $\{e(kx/N)\}_{k\in\mathbb Z_N}$ в дискретном. Такой поперечник называется тригонометрическим поперечником и обозначается $d_n^{\mathrm{T}}$. Обычно мы рассматриваем вещественные пространства и размерность понимаем над полем $\mathbb R$. При приближении комплекснозначных функций можно рассматривать линейные пространства над $\mathbb C$. Для нас это отличие не играет роли, так как в тех вопросах, где приближаются комплексные функции, речь о размерности $n$ идет с точностью до порядка. 2.3. РазноеМатериал этого пункта содержится, например, в книге [22; § 2.2, 2.8, 8.8]. ВероятностьМы используем стандартные обозначения из теории вероятностей: $\mathsf{P}$ обозначает вероятность; $\mathsf{E}$ – математическое ожидание; $\operatorname{Law}$ – распределение, $\mathbf{1}\{\dots\}$ – индикатор события. Используется также условное математическое ожидание $\mathsf{E}(\xi\mid \eta)$, хотя только в случае, когда $\eta$ принимает конечное число значений. Нам потребуются стандартные оценки вероятностей больших уклонений. Пусть случайные величины $X_i$ независимы и $\mathsf{E} X_i=0$. Неравенство Хёфдинга. Пусть $a_i\leqslant X_i\leqslant b_i$ п.н., тогда
$$
\begin{equation*}
\mathsf{P}\biggl(\biggl|\sum_{i=1}^k X_i\biggr| \geqslant \lambda \sigma\biggr) \leqslant2\exp(-2\lambda^2), \qquad \sigma^2 :=\sum_{i=1}^k (b_i-a_i)^2.
\end{equation*}
\notag
$$
Неравенство Бернштейна. Пусть $|X_i|\leqslant M$ п.н., тогда
$$
\begin{equation*}
\mathsf{P}\biggl(\biggl|\sum_{i=1}^k X_i\biggr| \geqslant t\biggr) \leqslant 2\exp\biggl(-\frac{t^2/2}{\sigma^2+Mt/3}\biggr), \qquad \sigma^2 :=\sum_{i=1}^n \mathsf{E} X_i^2.
\end{equation*}
\notag
$$
$\operatorname{vc}$-размерностьНапомним здесь определение комбинаторной размерности класса $\mathcal F$ функций $f\colon I\to\mathbb{R}$. Скажем, что множество $J\subset I$ является $t$-раздробленным ($t>0$) классом $\mathcal F$, если существует функция $h\colon J\to\mathbb{R}$ такая, что для любого выбора знаков $\sigma\colon J\to\{-1,1\}$ найдется $f_\sigma\in\mathcal F$ с условием Комбинаторная размерность $\operatorname{vc}(\mathcal F,t)$ – это максимальная мощность множества, $t$-раздробленного классом $\mathcal F$.Если класс $\mathcal F$ выпуклый и центрально-симметричный, то можно считать $h(x)\equiv 0$. Действительно, в этом случае мы можем заменить $\{f_\sigma\}$ на $\{\frac12(f_\sigma- f_{-\sigma})\}$. Мы будем использовать следующий простой (и известный) факт:
$$
\begin{equation}
\text{если }\ \operatorname{vc}(\mathcal F,t)> n, \quad\text{то }\ d_n(\mathcal F,\ell_\infty(I))\geqslant t.
\end{equation}
\tag{7}
$$
Действительно, пусть $t$-раздроблено множество $J$ из $n+1$ точки, но есть аппроксимация функциями из $n$-мерного подпространства: $\mathcal F\ni f\approx g$, $g\in Q_n$, $\|f-g\|_\infty < t$. Существует нетривиальный линейный функционал $\Lambda(f) :=\sum_{x\in J}\lambda(x)f(x)$ такой, что $\Lambda(g)\equiv 0$ для $g\in Q_n$. Предположим, $\Lambda(h)\geqslant 0$, где $h$ из (6). Выберем функцию $f$, для которой $\operatorname{sign}(\lambda(x))(f(x)-h(x))\geqslant t$ для всех $x\in J\colon \lambda(x)\ne0$. Но тогда для приближающей функции $g$ имеем $\operatorname{sign}(\lambda(x))(g(x)-h(x))>0$, и, значит, $\Lambda(g)=\Lambda(g-h)+\Lambda(h)>0$. Противоречие. Случай $\Lambda(h)\leqslant0$ аналогичен. Также мы используем классическую $\mathrm{VC}$-оценку для классов $\mathcal F\colon I\to\{-1,1\}^k$ (т.е., по существу, семейств подмножеств):
$$
\begin{equation}
|\mathcal F|>\binom{k}{0}+\binom{k}{1}+\dots+\binom{k}{d} \quad\Longrightarrow\quad \operatorname{vc}(\mathcal F,1) > d.
\end{equation}
\tag{8}
$$
Таким образом, при выполнении левого неравенства в (8) проекция класса на некоторое множество $J$, $|J|>d$, даст весь куб $\{-1,1\}^J$. Для оценки биномиальных коэффициентов нам пригодится следующее неравенство:
$$
\begin{equation}
\binom{k}{0}+\dots+\binom{k}m \leqslant \biggl(\frac{ek}m\biggr)^m, \qquad 0\leqslant m \leqslant k.
\end{equation}
\tag{9}
$$
Отметим, что функция $(ek/x)^x$ возрастает при $x\in(0,k]$. Часто мы будем рассматривать $1$-периодические функции, т.е. функции на окружности $\mathbb T:=\mathbb R/\mathbb Z$. Используется обозначение $e(\theta):=\exp(2\pi i\theta)$. Через $c,c_1,c_2,C,\dots$ мы обозначаем некоторые положительные постоянные. Если есть зависимость от параметров, мы указываем ее явно: $c_p,c(\varepsilon),\dots$ . § 3. Достаточные условия жесткости в слабых метриках3.1. Жесткость в $L_1$Для определенности положим $\operatorname{sign}(x)=1$ для $x\geqslant 0$ и $\operatorname{sign}(x)=-1$ для $x<0$. Теорема 3.1. Пусть $\xi=(\xi_1,\dots,\xi_N)$ – случайный вектор в $\mathbb{R}^N$ и $\mathsf{E}|\xi_i|\geqslant1$ для всех $i$. Если $\varepsilon\in(0,1)$ и $n\leqslant N(1-\varepsilon)$, то Перед доказательством теоремы отметим, что расстояние в $\ell_1^N$ от вектора $x\in\mathbb{R}^N$ до подпространства $Q_n\subset\mathbb{R}^N$ может быть записано в двойственном виде:
$$
\begin{equation*}
\rho(x,Q_n)_1=\sup_{z\in K} \langle x,z\rangle, \qquad K :=B_\infty^N \cap Q_n^\perp.
\end{equation*}
\notag
$$
Поэтому центральные сечения куба $B_\infty^N$ играют здесь важную роль. Докажем лемму. Лемма 3.1. Пусть $K$ – это центральное $m$-мерное сечение куба $B_\infty^N$ и $m\geqslant \varepsilon N$. Тогда $\operatorname{vc}(K,c_1(\varepsilon)) \geqslant c_2(\varepsilon)N$. Доказательство леммы опирается на два важных результата. Теорема D (см. [23]). Любое $m$-мерное центральное сечение куба единичного объема имеет объем не меньше единицы: На самом деле, для наших целей достаточно более простой оценки
$$
\begin{equation*}
\operatorname{Vol}_m(B_\infty^N\cap L_m)\geqslant c^m.
\end{equation*}
\notag
$$
Теорема E (см. [24]). Пусть $\mathcal F$ – некоторый класс функций, заданных на множестве $I$ и ограниченных по модулю единицей. Для любой вероятностной меры $\mu$ на $I$ где $C$ и $c$ – положительные абсолютные постоянные. Через $N_\delta(K,X)$ обозначается размер минимальной $\delta$-сети для множества $K$ в пространстве $X$. Доказательство леммы 3.1. Обозначим $K=L_m\cap B_\infty^N$. Из теоремы D мы получаем оценку $\operatorname{Vol}_m(K)\geqslant 2^m$. Используя стандартные оценки энтропии через объемы, получим
$$
\begin{equation*}
\begin{aligned} \, N_r(K,\ell_2^N)&=N_r(K,\ell_2^N\cap L_m) \\ &\geqslant \frac{\operatorname{Vol}_m(K)}{\operatorname{Vol}_m(r B_2^m)} \geqslant \frac{2^m}{(cr m^{-1/2})^m}\geqslant 2^m \quad\text{для }\ r=c_1m^{1/2}. \end{aligned}
\end{equation*}
\notag
$$
Осталось применить (11) ко множеству $K$ (отметим, что по построению $\|z\|_\infty{\leqslant}\, 1$ для $z\in K$) в пространстве $L_2^N$ и $t=N^{-1/2}r\asymp \varepsilon^{1/2}$:
Лемма доказана. Теперь мы готовы доказать теорему 3.1. Доказательство теоремы 3.1. По двойственности, имеем
Лемма 3.1 дает множество координат $\Lambda\subset\{1,\dots,N\}$, $|\Lambda|\geqslant c(\varepsilon)N$, и число $v\geqslant c(\varepsilon)$ такие, что для любого выбора знаков $\sigma\colon\Lambda\to\{-1,1\}$ найдется вектор $z^\sigma\in K$, (Напомним, что в силу выпуклости и центрально-симметричности $K$ мы можем считать, что $z^\sigma$ осциллирует вокруг нуля.)Из (12) мы выведем оценку
$$
\begin{equation}
\mathsf{E} \max_\sigma \langle \xi,z^\sigma \rangle \geqslant v \sum_{i\in\Lambda} \mathsf{E}|\xi_i| - \sum_{i\notin\Lambda} \|\mathsf{E}(\xi_i\mid \{\operatorname{sign}\xi_j\}_{j\in\Lambda})\|_{L_1}.
\end{equation}
\tag{13}
$$
Зафиксируем выбор знаков $\sigma^*\colon\Lambda\to\{-1,1\}$, и пусть $\mathsf{E}^*$ обозначает условное математическое ожидание $\mathsf{E}^*(\cdot)=\mathsf{E}(\cdot\mid \operatorname{sign}\xi_i=\sigma_i^*,\,i\in\Lambda)$. Имеем
$$
\begin{equation*}
\begin{aligned} \, \mathsf{E}^*\max_\sigma\langle\xi,z^\sigma\rangle &\geqslant \mathsf{E}^*\langle\xi,z^{\sigma^*}\rangle \\ &=\mathsf{E}^*\sum_{i\in\Lambda}\xi_i z^{\sigma^*}_i+\sum_{i\notin\Lambda}\xi_i z^{\sigma^*}_i \geqslant v\sum_{i\in\Lambda}\mathsf{E}^*|\xi_i| - \sum_{i\notin\Lambda}|\mathsf{E}^*\xi_i|. \end{aligned}
\end{equation*}
\notag
$$
Здесь мы использовали, что $\|z^{\sigma^*}\|_\infty\leqslant 1$. Усредним по $\sigma^*$ и получим (13).
Теорема следует из неравенства (13), поскольку первая сумма в нем не меньше $v|\Lambda|\geqslant c_\varepsilon N$, а каждое слагаемое во второй сумме можно оценить так:
$$
\begin{equation*}
\|\mathsf{E}(\xi_i\mid\{\operatorname{sign}\xi_j\}_{j\in\Lambda})\|_{L_1} \leqslant \|\mathsf{E}(\xi_i\mid \{\operatorname{sign}\xi_j\}_{j\ne i})\|_{L_1}.
\end{equation*}
\notag
$$
Теорема доказана. Приведем некоторые следствия теоремы 3.1 для случая $\mathsf{E}(\xi_i\mid\{\operatorname{sign}\xi_j\}_{j\ne i})\,{\equiv}\,0$. Следствие 3.1. Пусть случайные величины $\xi_1,\dots,\xi_N$ независимы, $\mathsf{E}\xi_i=0$ и $\mathsf{E}|\xi_i|\geqslant 1$. Тогда для любых случайных величин $\eta_1,\dots,\eta_n$, $n\leqslant N(1-\varepsilon)$, и любого набора коэффициентов $A=(a_{i,j})$ имеем В терминах поперечников То же справедливо, если заменить требование независимости на безусловность распределения: $\operatorname{Law}(\xi_1,\dots,\xi_N)=\operatorname{Law}(\pm\xi_1,\dots,\pm\xi_N)$. 3.2. Жесткость в $L_0$Теорема 3.2. Для любого $\varepsilon\in(0,1)$ существует $\delta>0$ такое, что если случайные величины $\xi_1,\dots,\xi_N$ независимы и то для любого подпространства $Q_n\subset\mathbb{R}^N$ размерности не выше $n\leqslant \delta N$, имеем где $\xi=(\xi_1,\dots,\xi_N)$. Условие $\|\xi_i-c\|_{L_0}\geqslant\varepsilon$ существенно, поскольку оно запрещает аппроксимацию вектора $\xi$ константным вектором. Это условие позволяет в некотором смысле “отделить” значения $\xi_i$. Лемма 3.2. Пусть $\varepsilon,\tau\in(0,1]$, случайная величина $\zeta$ удовлетворяет условию $\inf_{c\in\mathbb{R}}\|\zeta-c\|_{L_0}\geqslant\varepsilon$. Тогда найдутся числа $a<b$ такие, что Доказательство. Рассмотрим квантили Отметим, что $\mathsf{P}(\zeta\leqslant q_-)\geqslant \varepsilon/3$ и $\mathsf{P}(\zeta\geqslant q_+)\geqslant \varepsilon/3$. Видно, что $|q_+-q_-|\geqslant\varepsilon$, поскольку в противном случае $\|\zeta-c\|_{L_0}\leqslant2\varepsilon/3$ для $c=(q_-+q_+)/2$. Положим $k:=\lceil1/\tau\rceil$, разделим $[q_-,q_+]$ на $k$ равных интервалов и выберем в качестве $(a,b)$ интервал с наименьшей вероятностью $\mathsf{P}(a<\zeta<b)$. Тогда эта вероятность не превосходит $1/k\leqslant\tau$. Наконец, $|b-a|\geqslant |q_+-q_-|/k \geqslant \tau\varepsilon/2$.
Лемма доказана. Перейдем теперь к доказательству теоремы. Доказательство теоремы 3.2. Пусть $\delta>0$ достаточно мало (уточним выбор позже); оценим $\mathsf{P}(\rho(\xi,Q_n)_{L_0^N}<\delta)$, где $\dim Q_n\leqslant n\leqslant \delta N$. Рассмотрим (почти) наилучшую $L_0^N$ аппроксимацию вектора $(\xi_1,\dots,\xi_N)$ случайным вектором $(y_1,\dots,y_N)$ из подпространства $Q_n$. Обозначим через множество (случайное) координат с плохой аппроксимацией. Если $\|\xi-y\|_{L_0^N} {<}\, \delta$, то $|\Lambda|<\delta N$; поэтому нам достаточно оценить вероятность события $\{|\Lambda| \leqslant \delta N\}$.
Применим лемму 3.2 к $\tau :=5\delta/\varepsilon$ и $\xi_k$, получим интервалы $(a_k,b_k)$ такие, что
$$
\begin{equation*}
\begin{gathered} \, \mathsf{P}(a_k<\xi_k<b_k)\leqslant \tau,\quad |b_k-a_k|\geqslant\frac{\tau\varepsilon}2 =\frac{5\delta}2, \\ \max\{\mathsf{P}(\xi_k\leqslant a_k),\mathsf{P}(\xi_k\geqslant b_k)\}\leqslant1-\frac{\varepsilon}3. \end{gathered}
\end{equation*}
\notag
$$
Обозначим через множество координат с “промежуточными” значениями. Имеем $\mathsf{E}|\Gamma|\leqslant \tau N$; по неравенству Бернштейна $\mathsf{P}(|\Gamma|\leqslant 2\tau N)\geqslant 1-2\exp(-c\tau N)$ и, следовательно,
$$
\begin{equation}
\mathsf{P}(|\Lambda|\leqslant \delta N) \leqslant \mathsf{P}(|\Lambda|\leqslant \delta N, \, |\Gamma|\leqslant 2\tau N)+2\exp(-c\tau N).
\end{equation}
\tag{15}
$$
Зафиксируем некоторые множества координат $\Lambda^\circ,\Gamma^\circ\subset\{1,\dots,N\}$ размера $|\Lambda^\circ|\leqslant\delta N$, $|\Gamma^\circ|\leqslant 2\tau N$ и рассмотрим событие $\{\Lambda=\Lambda^\circ,\,\Gamma=\Gamma^\circ\}$. Положим $N'=N-|\Lambda^\circ\cup\Gamma^\circ|$; тогда $N'\geqslant N/2$. Для $x\in\mathbb{R}^N$ будем использовать обозначение $x'\in\mathbb{R}^{N'}$, означающее вектор $x$ без координат из множества $\Lambda^\circ\cup\Gamma^\circ$. Тогда $\|\xi'-y'\|_{\ell_\infty^{N'}} \leqslant \delta$, причем $y'\in Q_n'$. Следовательно,
$$
\begin{equation}
d_n(K,\ell_\infty^{N'})\leqslant\delta, \quad\text{где }\ K:=\bigl\{\xi'(\omega)\colon \Lambda(\omega)=\Lambda^\circ, \, \Gamma(\omega)=\Gamma^\circ\bigr\}.
\end{equation}
\tag{16}
$$
Рассмотрим случайный вектор $\pi$ с координатами $\pi_k :=-1$ при $\xi_k\leqslant a_k$; $\pi_k :=0$ при $a_k<\xi_k<b_k$; $\pi_k :=1$ при $\xi_k\geqslant b_k$. По построению $\pi'\in\{-1,1\}^{N'}$. Докажем, что множество $S :=\{\pi'(\omega)\colon \Lambda(\omega)=\Lambda^\circ,\,\Gamma(\omega)=\Gamma^\circ\}$ возможных значений $\pi'$ имеет мощность не больше $(eN'/n)^{n}$. Действительно, в противном случае из (8), (9) следует, что $S$ содержит “куб” размерности $n+1$ и поэтому
$$
\begin{equation*}
\operatorname{vc}(K,t)\geqslant n+1, \qquad t:=\frac12\min(b_k-a_k)\geqslant \frac{5\delta}{4},
\end{equation*}
\notag
$$
откуда в силу (7) имеем $d_n(K,\ell_\infty^{N'})\geqslant 5\delta/4$, что противоречит (16). Для любого $s\in S$ в силу выбора $a_k,b_k$ и независимости координат имеем $\mathsf{P}(\pi'=s)\leqslant(1-\varepsilon/3)^{N'}$, откуда
$$
\begin{equation*}
\mathsf{P}(\Lambda=\Lambda^\circ,\,\Gamma=\Gamma^\circ) \leqslant \biggl(\frac{eN}{n}\biggr)^n\biggl(1-\frac{\varepsilon}3\biggr)^{N/2}.
\end{equation*}
\notag
$$
Теперь мы можем оценить вероятность в (15):
$$
\begin{equation*}
\begin{aligned} \, \mathsf{P}(|\Lambda|\leqslant \delta N,\,|\Gamma|\leqslant 2\tau N) &=\sum_{|\Lambda^\circ|\leqslant\delta N,\,|\Gamma^\circ|\leqslant 2\tau N}\mathsf{P}(\Lambda=\Lambda^\circ,\,\Gamma=\Gamma^\circ) \\ &\leqslant \biggl(\frac{eN}{\delta N}\biggr)^{\delta N} \biggl(\frac{eN}{2\tau N}\biggr)^{2\tau N} \biggl(\frac{eN}{n}\biggr)^{n} \biggl(1-\frac{\varepsilon}{3}\biggr)^{N/2}. \end{aligned}
\end{equation*}
\notag
$$
Остается выбрать параметр $\delta$ достаточно малым, чтобы гарантировать экспоненциальную оценку для этого выражения.
Теорема 3.2 доказана. Приведем следствие для наилучших $n$-членных приближений по словарю:
$$
\begin{equation*}
\sigma_n(x,\Phi)_X := \inf_{\substack{\varphi_1,\dots,\varphi_n\in\Phi\\c_1,\dots,c_n\in\mathbb{R}}} \biggl\|x-\sum_{k=1}^n c_k\varphi_k \biggr\|_X.
\end{equation*}
\notag
$$
Следствие 3.2. В условиях теоремы 3.2 для любого словаря $\Phi\subset\mathbb{R}^N$, $|\Phi|\leqslant AN$ и $n<\delta N$, мы имеем Действительно, количество $n$-мерных подпространств, натянутых на элементы словаря, оценивается экспоненциально и за счет выбора меньшего $\delta=\delta(A,\varepsilon)$ вероятность можно сделать экспоненциально малой. Для дальнейшего нам потребуется модификация утверждения 2.1. Доказательство. Пусть $d_n^{\mathrm{avg}}(\{\xi_1,\dots,\xi_N\},L_0) \leqslant \varepsilon\leqslant 1$. Тогда для некоторых случайных величин $\eta_1,\dots,\eta_N$ из $n$-мерного подпространства $L_0$ мы имеем $\sum\|\xi_k-\eta_k\|_{L_0}\leqslant N\varepsilon$. Определим случайные множества $\Lambda_t :=\{k\colon |\xi_k-\eta_k|\geqslant t\}$; ясно, что $\|\xi-\eta\|_{L_0^N}\geqslant t$ тогда и только тогда, когда $|\Lambda_t|\geqslant tN$.
Возьмем $\delta :=\sqrt\varepsilon$ и оценим
$$
\begin{equation*}
\begin{aligned} \, \mathsf{E}|\Lambda_\delta| &=\sum_{k=1}^N \mathsf{P}(|\xi_k-\eta_k|\geqslant\delta) \leqslant \delta N+ \bigl|\{k\colon\mathsf{P}(|\xi_k-\eta_k|\geqslant\delta)\geqslant\delta\}\bigr| \\ &\leqslant \delta N+\bigl|\{k\colon \|\xi_k-\eta_k\|_{L_0}\geqslant\delta\}\bigr| \leqslant \delta N+ \frac{\varepsilon N}\delta=2\delta N. \end{aligned}
\end{equation*}
\notag
$$
Далее, для $\gamma :=\sqrt{2\delta}$ мы имеем
$$
\begin{equation*}
\mathsf{P}(\|\xi-\eta\|_{L_0^N}\geqslant\gamma) \leqslant \mathsf{P}(|\Lambda_\gamma|\geqslant \gamma N) \leqslant \frac{\mathsf{E}|\Lambda_\gamma|}{\gamma N} \leqslant \frac{\mathsf{E}|\Lambda_\delta|}{\gamma N} \leqslant \frac{2\delta N}{\gamma N}=\gamma.
\end{equation*}
\notag
$$
Следовательно, $\mathsf{E}\|\xi-\eta\|_{L_0^N} \leqslant 2\gamma$.
Доказательство второго неравенства аналогично. Лемма доказана. Следствие 3.3. В условиях теоремы 3.2 мы имеем 3.3. Случайные множестваПусть $A$ – сигнум-матрица, т.е. матрица с элементами $\pm1$. Определим сигнум-ранг матрицы, $\operatorname{rank}_\pm A$, как минимальный ранг матриц $B$ с $\operatorname{sign}B_{i,j}\equiv A_{i,j}$ ($B_{i,j}\ne0$). Известна оценка на количество $(N\times N)$-сигнум-матриц с сигнум-рангом не выше $r$, см. [25], а также, например, [26], [6]:
$$
\begin{equation*}
|\{A\in\{-1,1\}^{N\times N}\colon \operatorname{rank}_\pm A \leqslant r\}| \leqslant \biggl(\frac{4eN}{r}\biggr)^{2rN}.
\end{equation*}
\notag
$$
При $r=cN$ получаем оценку вида $2^{bN^2}$, где $b=b(c)\to0$ при $c\to0$. Следовательно, при малых $c$ есть очень мало сигнум-матриц таких, что $\operatorname{rank}_\pm A\leqslant cN$. Более того, почти все сигнум-матрицы далеки от таких матриц в метрике Хэмминга. Отсюда следует, что почти все сигнум-матрицы далеки от матриц $\operatorname{rank} B\leqslant cN$ в метрике $L_0$. Сформулируем следствие в терминах случайных (все знаки равновероятны) сигнум-матриц. Утверждение 3.1. Пусть $\mathbf{\mathcal E}$ – случайная $(N\times N)$-матрица с независимыми $\pm1$ элементами. Тогда Обозначим через $D_N(a,b)$ множество кусочно постоянных на $(a,b)$ функций с $N$ интервалами постоянства
$$
\begin{equation*}
\biggl(a+\frac{(b-a)(j-1)}{N},\, a+\frac{(b-a)j}{N}\biggr),\qquad j=1,\dots,N.
\end{equation*}
\notag
$$
Утверждение 3.2. Пусть $\mathbf{\varphi}_1,\dots,\mathbf{\varphi}_N$ – случайная система функций в $D_N(0,1)$, где $\varphi_{k,j} :=\varphi_k|_{((j-1)/N,j/N)}$ суть независимые случайные $\pm1$ величины. Тогда с вероятностью не менее $1-2\exp(-cN^2)$ мы имеем Отметим, что, хотя для построения $\varphi_k$ используются независимые случайные величины, сами функции $\{\varphi_k\}_1^N$ не образуют независимую систему. Доказательство утверждения 3.2. Докажем, что если $\{\varphi_k\}$ не жесткая в $L_0(0,1)$, то матрица $\Phi :=(\varphi_{k,j})$ хорошо приближается в $L_0^{N\times N}$, что будет противоречить утверждению 3.1.
Рассмотрим аппроксимацию $\varphi_k\approx g_k$ в $L_0$ функциями из $n$-мерного подпространства. Здесь есть небольшая техническая трудность: мы не можем сразу считать, что $g_k\in D_N$ (усреднить по отрезку нельзя – этот оператор не определен в $L_0$). Воспользуемся леммой 3.3: из нее видно, что жесткость системы $\xi_k :=\varphi_k$ равносильна жесткости случайного вектора $(\xi_1,\dots,\xi_N)$ и определяется распределением его значений. Поэтому можно считать, что мера пространства $(0,1)$, на котором все определено, состоит из “атомов” $((j-1)/N,j/N)$. Итак, если $\varphi_k\approx g_k$, $g_k\in D_N$, и среднее значение $\|\varphi_k - g_k\|_{L_0}$ не больше $\delta$, то $\|\varphi_k-g_k\|_{L_0}\leqslant \gamma :=\delta^{1/2}$ для всех, кроме, быть может, $\gamma N$ индексов. Отсюда $\|\Phi-G\|_{L_0^{N\times N}} \leqslant 2\gamma$. Утверждение доказано. Следствие 3.4. Существует ортонормированная система $\varphi_1,\dots,\varphi_N\in D_N(0,1)$, жесткая в $L_0$: Доказательство. Построим систему $\varphi_1,\dots,\varphi_N$ в пространстве $D_{2N}(0,2)$. Определим $\varphi_1,\dots,\varphi_N$ на $(0,1)$, используя случайные значения $\varphi_i|_{((j-1)/N,j/N)}\,{=} {\pm}\delta$, где $\delta$ выберем позже. С большой вероятностью система будет жесткой в $L_0$.
Продолжим систему на $(0,2)$, сделав ее ортонормированной. Критерий существования такого продолжения хорошо известен (см., например, [27; гл. 8]):
$$
\begin{equation*}
\max_{|a|=1}\biggl\|\sum_{k=1}^N a_k\varphi_k\biggr\|_{L_2(0,1)} \leqslant 1.
\end{equation*}
\notag
$$
Если $\delta$ достаточно мало, то это условие выполнено с большой вероятностью, поскольку спектральная норма случайной $\pm1$ матрицы есть $O(N^{1/2})$, см., например, [22; гл. 4].
Ясно также, что можно считать функции $\varphi_k|_{(1,2)}$ лежащими в произвольном $N$-мерном подпространстве (важны только величины $\displaystyle\int_1^2\varphi_k\varphi_l$), в частности, $D_N(1,2)$. Следствие доказано. 3.4. Лакунарные системыПусть $\lambda>1$. Будем говорить, что последовательность натуральных чисел $k_1,\dots,k_N$ является $\lambda$-лакунарной, если $k_{j+1}/k_j\geqslant \lambda$ при $j=1,\dots,N-1$. Утверждение 3.3. Пусть $\varphi$ – борелевская интегрируемая по Риману функция на $\mathbb{T}$ и $\mu\{x\in\mathbb{T}\colon \varphi(x)\ne a\}>0$ для всех $a\in\mathbb{R}$. 1. Существует $\lambda=\lambda(\varphi)>1$ такое, что для любой $\lambda$-лакунарной последовательности $k_1,\dots,k_N$ имеем
$$
\begin{equation*}
d_n^{\mathrm{avg}}\bigl(\{\varphi(k_1x),\dots,\varphi(k_Nx)\},L_0(\mathbb{T})\bigr)\geqslant c(\varphi) \quad\textit{при }\ n\leqslant c(\varphi) N.
\end{equation*}
\notag
$$
2. Для любого $\varepsilon>0$ существует $\lambda=\lambda(\varphi,\varepsilon)>1$ такое, что для всякой $\lambda$-лакунарной последовательности $k_1,\dots,k_N$, имеем Мы используем следующий количественный результат. Теорема F (см. [28; теорема 4.3]). Пусть $(k_j)$ – возрастающая последовательность натуральных чисел. Существует последовательность $(g_j)$ измеримых функций $(0,1)$, независимых и равномерно распределенных на $(0,1)$, для которых Перейдем к доказательству. Доказательство утверждения 3.3. Начнем со случая $L_1$. Мы можем сдвинуть и нормировать функцию $\varphi$ так, что $\displaystyle\int_\mathbb{T}\varphi(x)\,dx=0$, $\displaystyle\int_\mathbb{T}|\varphi(x)|\,dx\,{=}\,1$. Рассмотрим $\lambda$-лакунарную последовательность $k_1,\dots,k_N$ для некоторого $\lambda\,{>}\,1$. Применяя теорему F, получим функции $g_1,\dots,g_N$, для которых $\|\{k_j x\}-g_j(x)\|_{L_0} \leqslant 2/\lambda$.
Положим $f_j(x):=\varphi(g_j(x))$. Тогда $f_j$ независимы, $\displaystyle\int f_j=0$, $\displaystyle\int|f_j|=1$. Следствие 3.1 обеспечивает жесткость $\{f_j\}$. Для доказательства жесткости $\{\varphi(k_jx)\}$ достаточно оценить $\|\varphi(k_jx)-f_j\|_1$:
$$
\begin{equation*}
\begin{aligned} \, &\int_\mathbb{T}|\varphi(k_jx)-f_j(x)|\,dx \\ &\qquad=\int_A|\varphi(k_jx)-\varphi(g_j(x))|\,dx+ \int_{\mathbb{T}\setminus A}|\varphi(k_jx)-\varphi(g_j(x))|\,dx, \end{aligned}
\end{equation*}
\notag
$$
где $A\,{=}\,\{x\colon |\{k_j x\}-g_j(x)|\,{>}\,2/\lambda\}$. Первый интеграл не превосходит $2\|\varphi\|_\infty\mu(A) \,{\leqslant} 4\|\varphi\|_\infty/\lambda$. Второй интеграл не больше
$$
\begin{equation*}
\int_{\mathbb T}\sup_{|x-t|\leqslant 2/\lambda}|\varphi(t)-\varphi(x)|\,dx=: \tau\biggl(\varphi,\frac{4}\lambda\biggr),
\end{equation*}
\notag
$$
где $\tau$ – усредненный модуль непрерывности. Известно, что для интегрируемых по Риману функций $\lim_{h\to 0}\tau(\varphi,h)=0$. Следовательно, для достаточно больших $\lambda$ значение $\|\varphi(k_jx)-\varphi(g_j(x))\|_1$ достаточно мало. Случай $L_1$ разобран.
В случае $L_0$ мы можем применить неравенство
$$
\begin{equation*}
\|\varphi(k_jx)-f_j(x)\|_{L_0} \leqslant \|\varphi(k_jx)-f_j(x)\|_1^{1/2}
\end{equation*}
\notag
$$
и воспользоваться следствием 3.3.
Утверждение доказано. 3.5. Дополняемые подпространстваВ этом пункте мы наметим подход к доказательству жесткости функций, основанный на свойстве дополняемости. Пусть $f_1,\dots,f_N$ – ортонормированная система в $L_2(0,1)$. Допустим, мы хотим установить жесткость $\{f_j\}$ в большем пространстве $X\supset L_2$. Предположим, существует ограниченный линейный оператор $\pi\colon X\to L_2$, оставляющий систему на месте: $\pi f_j=f_j$, $j=1,\dots,N$. Тогда мы получаем жесткость в $X$:
$$
\begin{equation*}
\|\pi\|_{X\to L_2} d_n^{\mathrm{avg}}(\{f_1,\dots,f_N\},X)_2 \geqslant d_n^{\mathrm{avg}}(\{f_1,\dots,f_N\},L_2)_2=\biggl(1-\frac nN\biggr)^{1/2}.
\end{equation*}
\notag
$$
Запишем следствие в виде отдельного утверждения. Утверждение 3.4. Пусть $\{f_j\}_1^\infty$ – ортонормированная система в $X\supset L_2$ и выполнены два свойства. (1) Система порождает пространство $\ell_2$:
$$
\begin{equation*}
\biggl\|\sum_{j\geqslant 1}c_jf_j\biggr\|_X\asymp \biggl\|\sum_{j\geqslant1}c_jf_j\biggr\|_2.
\end{equation*}
\notag
$$
(2) Система дополняема, т.е. существует ограниченный проектор $\pi\colon X\twoheadrightarrow F_X :=\overline{\operatorname{span}}\,\{f_j\}_{j=1}^\infty$. Тогда для любых $i_1<i_2<\dots<i_N$.Следствие 3.5. Хаос Радемахера $\{r_ir_j\}_{1\leqslant i<j<\infty}$ является жестким в пространстве $L\log L$: для любого набора пар $\Lambda$ имеем Доказательство. Пусть $X$ – некоторое симметричное пространство. Критерием выполнения свойства (1) для хаоса Радемахера является непрерывное вложение $X\supset H$, см. [29; теорема 6.4]. Критерием дополняемости является двойное вложение $H\subset X\subset H'$, см. [29; теорема 6.7], где $H$ – это замыкание $L_\infty$ в пространстве Орлича $L_{\varphi_1}$, $\varphi_1(t)=e^t-1$. Следовательно, для $X=H'$ оба условия выполнены. Пространство $H'$ совпадает с пространством Лоренца $\Lambda(\psi_1)$ функций, для которых $\displaystyle\int_0^1 f^*(t)\log(2/t)\,dt<\infty$ (см. [29; п. 2.2, п. 2.4]), которое, в свою очередь, совпадает (см., например, [30; теорема D]) с пространством $L\log L$: $\displaystyle\int_0^1 |f|\log(2+|f|)\,dt<\infty$.
Следствие доказано. § 4. Жесткость в $L_p$, $1<p<2$4.1. $S_{p'}$-свойствоМы начнем с конечномерного результата. Доказательство следует работе Е. Д. Глускина [31]. Теорема 4.1. Пусть $1<p<2$ и $N\in\mathbb N$. Предположим, что случайный вектор $\xi=(\xi_1,\dots,\xi_N)$ в $\mathbb{R}^N$ является изотропным: $\mathsf{E}\xi_i^2=1$, $\mathsf{E}\xi_i\xi_j=0$, $i\ne j$, и выполнены два условия: Доказательство. Обозначим через $P$ ортопроектор на пространство $Q_n^\perp$, тогда
Рассмотрим $\eta :=\langle\xi,P\xi\rangle$ – числитель в (19):
$$
\begin{equation*}
\mathsf{E}\eta=\mathsf{E}\Bigl\langle\sum\xi_i e_i,\sum \xi_i Pe_i\Bigr\rangle= \sum \langle e_i,Pe_i\rangle=\operatorname{tr} P=N -n \geqslant \varepsilon N.
\end{equation*}
\notag
$$
С другой стороны,
$$
\begin{equation*}
\begin{aligned} \, \mathsf{E}\eta &\leqslant \frac12\, \varepsilon N+\mathsf{E}\eta\, \mathbf{1} \biggl\{\eta\geqslant\frac12\,\varepsilon N\biggr\} \\ &\leqslant \frac12\,\varepsilon N+ (\mathsf{E}|\eta|^{1+\gamma/2})^{2/(2+\gamma)}\mathsf{P} \biggl(\eta\geqslant\frac12\,\varepsilon N\biggr)^{\gamma/(2+\gamma)}. \end{aligned}
\end{equation*}
\notag
$$
Поскольку $|\eta|=|\langle\xi,P\xi\rangle|\leqslant|\xi|^2$, мы имеем $\mathsf{E}|\eta|^{1+\gamma/2}\leqslant (AN^{1/2})^{2+\gamma}$ и, следовательно,
$$
\begin{equation}
\mathsf{P}\biggl(\eta \geqslant \frac12\, \varepsilon N\biggr)\geqslant t := \biggl(\frac{\varepsilon}{2A^2}\biggr)^{(2+\gamma)/\gamma}.
\end{equation}
\tag{20}
$$
Далее, знаменатель в (19):
$$
\begin{equation*}
\mathsf{E}\|P\xi\|_{p'}^{p'}=\sum_{k=1}^N \mathsf{E}|\langle P\xi,e_k\rangle|^{p'}= \sum_{k=1}^N \mathsf{E}|\langle \xi,Pe_k\rangle|^{p'} \leqslant NB^{p'}.
\end{equation*}
\notag
$$
С помощью неравенства Маркова мы оценим вероятность:
$$
\begin{equation}
\mathsf{P}(\|P\xi\|_{p'}^{p'} \geqslant 2t^{-1} NB^{p'})\leqslant \frac12\, t.
\end{equation}
\tag{21}
$$
Комбинируя (20) и (21), получим требуемую оценку
$$
\begin{equation*}
\rho(\xi,Q_n)_p \geqslant \frac{\langle \xi,P\xi\rangle}{\|P\xi\|_{p'}} \geqslant \frac{\varepsilon N/2}{2^{1/p'}t^{-1/p'}N^{1/p'}B} \geqslant \frac14 \, \varepsilon t^{1/2} N^{1/p}B^{-1}
\end{equation*}
\notag
$$
с вероятностью не менее $t/2$.
Теорема доказана. Замечание 4.1. Отметим, что если условие (18) выполняется, то (17) также выполнено с параметрами $A:=B$, $\gamma:=p'-2$, см. доказательство теоремы 4.2. Однако в некоторых случаях нам важна зависимость $(\cdots)B^{-1}$ оценки снизу от параметра $B$. Сформулируем следствие в теоретико-функциональных терминах. Теорема 4.2. Пусть $\varphi_1,\dots,\varphi_N$ – ортонормированная система в $L_2(\mathcal X,\mu)$, $\mu(\mathcal X)=1$. Пусть $1<p<2$, и предположим, что $\{\varphi_k\}$ обладает $S_{p'}$-свойством, т.е. для некоторого $B\geqslant1$ Тогда эта система является жесткой в $L_p$: Доказательство. Действительно, возьмем случайную точку $x$ в пространстве $\mathcal X$ и рассмотрим случайный вектор $\xi=(\varphi_1(x),\dots,\varphi_N(x))$. Условие (18) теоремы 4.1 – это в точности $S_{p'}$-свойство. Проверим, что условие (17) выполнено с параметрами $A:=B$ и $\gamma=p'-2$. Действительно,
$$
\begin{equation*}
\begin{gathered} \, \|\varphi_k^2\|_{1+\gamma/2} =\|\varphi_k\|_{2+\gamma}^2=\|\varphi_k\|_{p'}^2 \leqslant B^2, \\ \biggl\|\biggl(\sum_{k=1}^N \varphi_k^2\biggr)^{1/2}\biggr\|_{2+\gamma}^2= \|\varphi_1^2+\dots+\varphi_N^2\|_{1+\gamma/2} \leqslant \sum_{k=1}^N \|\varphi_k^2\|_{1+\gamma/2} \leqslant B^2N. \end{gathered}
\end{equation*}
\notag
$$
Поэтому поперечник $d_n^{\mathrm{avg}}(\xi,\ell_p^N)_p$ оценивается снизу. Остается воспользоваться утверждением 2.1.
Теорема доказана. Следствие 4.1. Пусть $\varphi_1,\dots,\varphi_N$ – равномерно ограниченная ортонормированная система в $L_2(\mathcal X,\mu)$, $\mu(\mathcal X)=1$: $\|\varphi_k\|_\infty\leqslant A$. Тогда для любого $1\,{<}\,p\,{<}\,2$ имеем Доказательство. Действительно, по теореме Бургейна (см. [15]) в системе $\{\varphi_k\}$ можно найти $S_{p'}$-подсистему размера $\lfloor N^{2/p'}\rfloor$. Остается применить следствие 3.5 для этой подсистемы.
Следствие доказано. 4.2. Дополнительные замечанияЯвные конструкции жестких множествПредыдущие результаты позволяют нам дать конструктивные примеры $\ell_p$-жестких множеств в $\{-1,1\}^N$ полиномиального размера. Утверждение 4.1. Для любого $p\in(1,2)$ и всех достаточно больших $N$ существует конструктивный пример множества $V\subset\{-1,1\}^N$ размера $|V|\leqslant N^{C(p)}$ такого, что $d_{N/2}(V,\ell_p^N)\geqslant c(p) N^{1/p}$. Доказательство. Достаточно построить $N$ характеров $\chi_1,\dots,\chi_N\in \widehat{\mathbb Z_2^k}$ (с подходящим $k$), которые образуют $S_{p'}$-систему. Затем применим теорему 4.2: $d_{N/2}^{\mathrm{avg}}(\{\chi_1,\dots,\chi_N\},L_p)_p\geqslant c$; следовательно, мы можем взять $V:=\{(\chi_1(x),\dots,\chi_N(x))\colon x\in \mathbb Z_2^k\}$.
В работе [32] приведена конструкция системы $2^n$ характеров в $\mathbb Z_2^{mn}$, обладающих $S_{2m}$-свойством, поэтому для завершения доказательства остается положить $2^n\approx N$, $m=\lceil p'/2\rceil$, $k=mn$. Утверждение доказано. Независимость в $L_p$Аналог теоремы 3.1 с нормализацией в $L_p$ также справедлив при $1<p\leqslant 2$. Из теоремы 4.1 нетрудно вывести жесткость независимой системы функций (с дополнительным логарифмическим множителем), однако этот вопрос составит содержание отдельной статьи. Аналог теоремы о $L_1$-жесткости независимых функций не верен при $p>2$. Утверждение 4.2. Для любого $p\in(2,\infty)$ существует $\delta>0$ такое, что для достаточно больших $N$ найдется последовательность $\xi_1,\dots,\xi_N$ независимых одинаково распределенных случайных величин, нормированных: $\mathsf{E}\xi_i=0$, $\mathsf{E}|\xi_i|^p=1$, для которых Доказательство. Мы используем аппроксимацию октаэдра $B_1^N$ в $\ell_\infty^N$ (см. [33]). Положим $n=N^{1-\beta}$, где $\beta$ выберем позже, и пусть $Q_n^*$ – экстремальное $n$-мерное подпространство для октаэдра в $\ell_\infty$: Мы приблизительно “эмулируем” вершины октаэдра $B_1^N$ случайными векторами. Возьмем малое $\varepsilon>0$, и пусть $\xi_1$ – это следующая случайная величина: где $K$ определено из условия $\mathsf{E}|\xi_1|^p=1$; т.е. $\varepsilon K^p=1$. Рассмотрим независимые копии $\xi_2,\dots,\xi_N$ величины $\xi_1$ и объединим их в вектор $\xi=(\xi_1,\dots,\xi_N)$. Мы построим приближение этого вектора случайным вектором $\eta$, лежащим в $Q_n^*$ (следовательно, $\eta_1,\dots,\eta_N$ лежат в $n$-мерном подпространстве $L^p$).
Рассмотрим три события: $\mathcal{A}_0=\{\xi=0\}$, $\mathcal{A}_1$ – ровно одна координата вектора $\xi$ не равна нулю и $\mathcal{A}_{2}$ – по крайней мере две координаты $\xi$ не равны нулю. Положим $\eta(\omega):=0$ для $\omega\in \mathcal{A}_0\cup \mathcal{A}_{2}$, и пусть $\eta(\omega)$ – это наилучшее приближение из $Q_n^*$ вектора $\xi(\omega)$ в случае $\omega\in \mathcal{A}_1$. Отметим, что в последнем случае $\|\xi-\eta\|_\infty \leqslant K\rho(B_1^N,Q_n^*)_\infty$. В силу симметрии достаточно оценить $\mathsf{E}|\xi_1-\eta_1|^p$:
$$
\begin{equation*}
\mathsf{E}|\xi_1-\eta_1|^p \leqslant \mathsf{P}(\mathcal{A}_1) K^p\rho(B_1^N,Q_n^*)_\infty^p+ \mathsf{P}(\mathcal{A}_2) K^p.
\end{equation*}
\notag
$$
Первое слагаемое оценивается
$$
\begin{equation*}
N\varepsilon K^p C(\beta)^p n^{-p/2} \ll N^{1-(1-\beta)p/2} \ll N^{-\delta},
\end{equation*}
\notag
$$
если $\beta$ достаточно мало. Второе слагаемое не превосходит $N^2\varepsilon^2K^p= N^2\varepsilon$, и его можно сделать сколь угодно малым, устремив $\varepsilon$ к нулю.
Утверждение доказано. § 5. Приближение функций Уолша и тригонометрических функцийНапомним обозначения. Пусть $G$ – конечная абелева группа. Через $\widehat{G}$ обозначаем группу характеров $\chi\colon G\to\mathbb C$. На $G$ задана естественная вероятностная мера $\mu_G(A)=|A|/|G|$, поэтому мы можем говорить о метриках $L_{\mathrm{H}}$ и $L_0$ в пространстве функций, заданных на $G$ (см. п. 2.1). Нас интересуют два случая: $G=\mathbb Z_2^k$ и $G=\mathbb Z_N$. В первом случае характеры вещественны и представляются в виде $W_x\colon y\mapsto (-1)^{\langle x,y\rangle}$, $x,y\in\mathbb Z_2^k$. Эти характеры можно отождествить с функциями классической ортонормированной системы Уолша $w_0\equiv1, w_1,w_2,\dots$ в нумерации Пэли. А именно, для $n<2^k$ имеем $w_n\bigl(\sum_{j\geqslant 1}y_j2^{-j}\bigr)=W_x(y)$, где $x=(x_1,\dots,x_k)\in\{0,1\}^k$, $y=(y_1,\dots,y_k)\in\{0,1\}^k$, $n=\sum_{j=1}^kx_j2^{j-1}$. Во втором случае мы получаем дискретную тригонометрическую систему: характеры имеют вид $y\mapsto e(xy/N)$, где $e(\theta):=\exp(2\pi i\theta)$. 5.1. Колмогоровские поперечникиНапомним следующий известный факт (см., например, [34; § 2.1]). Лемма 5.1. Пусть $G$ – конечная абелева группа, $A,B\subset G$ и $|A|+|B|>|G|$. Тогда $A+B=\{a+b\colon a\in A,\,b\in B\}=G$. Из него немедленно вытекает следствие. Следующая теорема доказывается с использованием методов [8]. Это модификация теоремы 1.2 из той работы. Теорема 5.1. Пусть $k\in\mathbb N$. Для любого $1\leqslant \lambda\leqslant \frac14 \sqrt{k}$ справедливо неравенство Доказательство. Мы отождествляем $\mathbb Z_2^k\equiv\{0,1\}^k$ и обозначаем характеры через $W_x$:
$$
\begin{equation*}
W_x\colon y\mapsto (-1)^{\langle x,y\rangle}, \qquad x,y\in\{0,1\}^k.
\end{equation*}
\notag
$$
Наша цель – приблизить функции $\{W_x\}$ в метрике Хэмминга. Пусть $\mathcal X$ – множество векторов $x$ таких, что $\bigl|\sum_{i=1}^k x_i-k/2\bigr|\leqslant\sqrt{k}$. Стандартное неравенство Хёфдинга дает $|\mathcal X|>2^{k-1}$, поэтому достаточно приблизить $W_x$ для $x\in\mathcal X$ (а затем воспользоваться леммой 5.2).
Зафиксируем $x\in\mathcal X$. Обозначим $I:=\{i\colon x_i=1\}$,
$$
\begin{equation*}
Y_I :=\biggl\{y\in\{0,1\}^k\colon \biggl|\sum_{i\in I} y_i - \frac{|I|}2\biggr| \leqslant \lambda|I|^{1/2}\biggr\}.
\end{equation*}
\notag
$$
Тогда $2^{-k}|Y_I| \geqslant 1-2\exp(-2\lambda^2)$. Кроме того, для всех $y\in Y_I$ имеем
$$
\begin{equation*}
\begin{aligned} \, \biggl|\langle x,y\rangle-\frac{k}{4}\biggr| &=\biggl|\sum_{i\in I}y_i - \frac k4\biggr| \leqslant\biggl|\sum_{i\in I}y_i-\frac{|I|}2\biggr| +\biggl|\frac{|I|}2-\frac k4\biggr| \\ &\leqslant\lambda\sqrt{|I|}+\frac{\sqrt{k}}2 \leqslant\lambda\sqrt{\frac k2+\sqrt{k}}+\frac{\sqrt{k}}2 \leqslant 2\lambda\sqrt{k}. \end{aligned}
\end{equation*}
\notag
$$
Рассмотрим полином $q(t)$, интерполирующий функцию $(-1)^t$ для $t\in\mathbb Z\cap[k/4-2\lambda\sqrt{k},k/4+2\lambda\sqrt{k}]$. Его степень $d$ не превосходит $4\lambda\sqrt{k}$; отметим, что $4\lambda\sqrt{k}\leqslant k$. Тогда $W_x(y)=q(\langle x,y\rangle)$ для всех $y\in Y_I$, поэтому
$$
\begin{equation*}
\|W_x - q(\langle x,\cdot\rangle)\|_{L_{\mathrm{H}}} \leqslant 2\exp(-2\lambda^2).
\end{equation*}
\notag
$$
Оценим линейную размерность семейства функций $\{q(\langle x,\cdot\rangle)\}_x$ (тут достаточно брать $x\in\mathcal X$, но нам проще рассмотреть все $x\in\{0,1\}^k$). Размерность равна рангу матрицы $(q(\langle x,y\rangle))_{x,y\in\{0,1\}^k}$, где $x$ индексирует строки, а $y$ столбцы. Этот ранг не превосходит количества мономов в полиноме $q(x_1y_1+\dots+x_ky_k)$, поскольку каждый моном дает одноранговую матрицу. Моном – это произведение некоторых $x_iy_i$, и их количество оценивается:
$$
\begin{equation*}
\operatorname{rank}(q(\langle x,y\rangle)_{x,y\in\{0,1\}^k}) \leqslant \binom{k}{0}+\dots+\binom{k}{d} \leqslant \biggl(\frac{ek}d\biggr)^d \leqslant \biggl(\frac{\sqrt{k}}\lambda\biggr)^{4\lambda\sqrt{k}}.
\end{equation*}
\notag
$$
Для завершения доказательства остается воспользоваться леммой 5.2.
Теорема доказана. Доказательство. Наша задача – приблизить характеры $y\mapsto e(xy/2^k)$. Запишем $x=\sum_{i=0}^{k-1}x_i2^i$, $y=\sum_{j=0}^{k-1}y_j2^j$ и идентифицируем $x,y\in\mathbb Z_{2^k}$ с двоичными векторами $(x_0,\dots,x_{k-1})$, $(y_0,\dots,y_{k-1})$. Пользуясь 1-периодичностью функции $e(\cdot)$, получим
Зафиксируем число $s_0\leqslant\sqrt{k}$ и оценим “хвост” суммы:
$$
\begin{equation*}
\sum_{s>s_0}2^{-s}\sum_{i+j=k-s}x_iy_j\leqslant k\sum_{s>s_0}2^{-s}\leqslant k2^{-s_0}.
\end{equation*}
\notag
$$
Поскольку функция $e(\cdot)$ $2\pi$-липшицева, имеет место равномерное приближение
$$
\begin{equation}
\biggl|e\biggl(\frac{xy}{2^k}\biggr) - \psi_x(y)\biggr| \leqslant 2\pi k2^{-s_0}, \quad \psi_x(y) :=e\biggl(\sum_{s=1}^{s_0}2^{-s}\sum_{i+j=k-s}x_iy_j\biggr).
\end{equation}
\tag{22}
$$
Следовательно, достаточно приблизить функции $\psi_x$.
Так же, как и в предыдущем доказательстве, сперва мы рассмотрим векторы, лежащие во множестве $\mathcal X:=\bigl\{x\colon \bigl|\sum_{i=0}^{k-1}x_i-k/2\bigr|\leqslant\sqrt{k}\,\bigr\}$. Зафиксируем $x\in\mathcal X$. Пусть $s\in\{1,\dots,s_0\}$. Имеем
$$
\begin{equation*}
\biggl|\sum_{i=0}^{k-s}x_i-\frac{k}2\biggr|\leqslant\sqrt{k}+s\leqslant2\sqrt{k}.
\end{equation*}
\notag
$$
Обозначим $J_s=\{j\in\{0,\dots,k-s\}\colon x_{k-s-j}=1\}$, тогда $|\,|J_s|-k/2|\leqslant2\sqrt{k}$. Для случайного вектора $y\in\{0,1\}^k$ с вероятностью не менее $1-2\exp(-2\lambda^2)$ выполнено неравенство
$$
\begin{equation*}
\biggl|\sum_{j\in J_s}y_j-\frac12|J_s|\biggr|\leqslant\lambda|J_s|^{1/2}.
\end{equation*}
\notag
$$
Для таких $y$ имеем:
$$
\begin{equation*}
\begin{aligned} \, \biggl|\sum_{i+j=k-s}x_iy_j-\frac{k}{4}\biggr| &=\biggl|\sum_{j\in J_s}y_j-\frac{k}{4}\biggr| \leqslant \biggl|\sum_{j\in J_s}y_j-\frac{|J_s|}{2}\biggr|+\biggl|\frac{|J_s|}{2}-\frac{k}{4}\biggr| \\ &\leqslant \lambda\sqrt{\frac{k}{2}+2\sqrt{k}}+\sqrt{k}\leqslant 2\lambda\sqrt{k}. \end{aligned}
\end{equation*}
\notag
$$
(Здесь мы использовали, что можно считать $k$ достаточно большим.)
Далее воспользуемся техникой интерполяции. Существует полином $q_s$ степени $d\leqslant 4\lambda\sqrt{k}$, который интерполирует функцию $t\mapsto e(2^{-s}t)$ в точках $\mathbb Z\cap [k/4-2\lambda\sqrt{k},k/4+2\lambda\sqrt{k}]$. Тогда функция $e\bigl(2^{-s}\sum_{i+j=k-s}x_iy_j\bigr)$ приближается функцией $q_s(\langle x,y\rangle)$ в метрике Хэмминга с погрешностью не более $2\exp(-2\lambda^2)$; при этом $\dim\{q_s(\langle x,\cdot\rangle)\}_x \leqslant (ek/d)^d \leqslant (\sqrt{k}/\lambda)^{4\lambda\sqrt{k}}$. Заметим, что приближаемая функция представляет собой произведение:
$$
\begin{equation}
\psi_x(y)=\prod_{s=1}^{s_0} e\biggl(2^{-s}\sum_{i+j=k-s}x_iy_j\biggr).
\end{equation}
\tag{23}
$$
Мы приблизим это произведение произведением соответствующих полиномов. При этом погрешность в метрике Хэмминга не превосходит $2s_0\exp(-2\lambda^2)$. Ранг произведения не превосходит произведения рангов, т.е. $(\sqrt{k}/\lambda)^{4s_0\lambda\sqrt{k}}$.
Далее, используем лемму 5.2, чтобы приблизить $\psi_x$ в $L_{\mathrm{H}}$ для всех $x$. Наконец, неравенство (22) дает приближение исходных характеров в $L_0$ с погрешностью $2\pi k2^{-s_0}+4s_0\exp(-2\lambda^2)$, используя размерность не более $(k/\lambda^2)^{4s_0\lambda\sqrt{k}}$. Остается положить $s_0\asymp\lambda^2$. Теорема доказана. Для аппроксимации непрерывных функций мы сначала дискретизируем их, приблизив кусочно постоянными с достаточно мелким дроблением на $2^k$ отрезков, а затем приближаем полученную матрицу (дискретного преобразования Фурье), пользуясь доказанным утверждением. 5.2. Тригонометрические поперечники в $L_p$, $p<1$Напомним, что тригонометрический поперечник $d_n^{\mathrm{T}}$ соответствует аппроксимации подпространствами, натянутыми на функции тригонометрической системы. Мы рассмотрим два случая параллельно: непрерывный случай с гармониками $e(kx)$ на окружности $\mathbb{T}$, и дискретный случай с гармониками $e(kx/N)$ на циклической группе $\mathbb Z_N$. Для краткости мы обозначаем через $L_p^N$ подпространство $L_p(\mathbb Z_N)$ c с обычной (квази)нормой
$$
\begin{equation*}
\|f\|_{L_p^N}=\biggl(\frac1{N}\sum_{x\in\mathbb Z_N}|f(x)|^p\biggr)^{1/p}.
\end{equation*}
\notag
$$
Теорема 5.3. Для любого $p\in(0,1)$ и всех достаточно больших $N$ справедливы неравенства Нам потребуются пространства тригонометрических полиномов порядка не выше $m$:
$$
\begin{equation*}
\mathcal T_m :=\biggl\{\sum_{k=-m}^m c_k e(kx)\biggr\}, \qquad \mathcal T_m^N :=\biggl\{\sum_{k=-m}^m c_k e\biggl(\frac{kx}N\biggr)\biggr\}.
\end{equation*}
\notag
$$
Лемма 5.3. Для любого $p\in(0,1)$ существует $\delta=\delta(p)>0$ такое, что для всех $m,N\in\mathbb N$, $N\geqslant m$ имеем Для доказательства достаточно взять ядро Фейера и воспользоваться хорошо известным неравенством $|K_{m-1}(x)|\leqslant \min(m,c/(mx^2))$. Лемма 5.4. Пусть $m,N\in\mathbb N$, $N \geqslant C m^4$. $\bullet$ Существует множество $\Lambda\subset\mathbb Z$ со следующим свойством. Для любого $k\in\{-N,\dots,N\}$ найдется $h\in\mathbb Z$, $h\ne0$, такое, что $k\pm lh\in\Lambda$ для $l=1,\dots,m$. $\bullet$ Существует множество $\Lambda\subset\mathbb Z_N$ со следующим свойством. Для любого $k\in\mathbb Z_N$ найдется $h\in\mathbb Z_N^*$ такое, что $k\pm lh\in\Lambda$ для $l=1,\dots,m$. Кроме того, в обоих случаях Докажем теорему 5.3. Мы рассмотрим дискретный случай; непрерывный случай полностью аналогичен. Доказательство теоремы 5.3. Возьмем некоторое число $m$, применим лемму 5.4 и получим множество $\Lambda$, а с помощью леммы 5.3 получим полином $T\in\mathcal T_m^N$. Для аппроксимации $e(kx/N)$ подпространством $\mathcal T(\Lambda)$ тригонометрических полиномов со спектром в $\Lambda$, мы возьмем $h\in\mathbb Z_N^*$, для которого $k\pm h,\dots,k\pm mh\in\Lambda$. Рассмотрим полином Он равен $e(kx/N)+s(x)$, где $\operatorname{supp}\widehat{s}\subset\Lambda$, поэтому нам достаточно оценить $\|t\|_{L_p^N}$. Заметим, что $t(x)=e(kx/N)T_m(hx)$, Наконец, положим $m\asymp \log^{1/2} N$, это даст $|\Lambda|\leqslant N\exp(-(\log N)^{1/2+o(1)})$.
Теорема доказана. Теперь мы докажем лемму 5.4. Доказательство леммы 5.4. Начнем с дискретного случая. Пусть $\Lambda\subset\mathbb Z_N$ – случайное множество, каждая точка попадает в $\Lambda$ независимо от остальных с некоторой вероятностью $\tau\in(0,1)$.
Скажем, что шаг $h\in\mathbb Z_N^*$ допустим для $k\in \mathbb Z_N$, если $k\pm lh\in\Lambda$ при $l=1,\dots,m$. Имеем Назовем элемент $k$ “плохим”, если для него нет допустимых шагов. Предположим, что для любого $k$ есть как минимум $S$ шагов $h_1,\dots,h_S\in\mathbb Z_N^*$ таких, что прогрессии $k\pm lh_i$, $l=1,\dots,m$, не пересекаются (скоро мы оценим $S$). Тогда события “шаг $h_i$ допустим для $k$” независимы для различных $i$. Следовательно, вероятность того, что $k$ плохой, не превосходит вероятности того, что все $h_i$ недопустимы, т.е. $(1-\tau^{2m})^S$.Ожидаемое количество плохих $k$ не превосходит $N(1-\tau^{2m})^S {<}\, N\exp(-S\tau^{2m})$, поэтому с вероятностью $\geqslant2/3$ это количество не превосходит $3N\exp(-S\tau^{2m})$. Далее, $\mathsf{E}|\Lambda|=N\tau$, поэтому с вероятностью $\geqslant2/3$ имеем $|\Lambda|\leqslant 3N\tau$. Следовательно, существует множество $\Lambda$, для которого оба неравенства справедливы. Если $\tau$ достаточно мал, так что выполнено неравенство то плохих $k$ вообще не будет и $\Lambda$ и есть наше искомое множество.Остается оценить $S$ снизу. Всего есть $|\mathbb Z_N^*|\gg N/\log N$ возможных шагов. Шаг $h_1$ запрещает другие шаги $h$, которые являются решениями $2m^2$ уравнений $lh=\pm l_1h_1\pmod{N}$; $l,l_1\in\{1,\dots,m\}$. Каждое уравнение имеет не более $\mathrm{gcd}(N,l)\leqslant m$ решений, поэтому мы можем взять Наконец, для выполнения неравенства (26) мы положим
$$
\begin{equation*}
\tau=\biggl(\frac{\ln(4N)}{S}\biggr)^{1/(2m)} \ll \biggl(\frac{\log^2N}{N}\biggr)^{1/(2m)}.
\end{equation*}
\notag
$$
Непрерывный случай аналогичен. В нем $\Lambda$ – это случайное подмножество в $\{-2N,\dots,2N\}$, мы рассматриваем точки $k\in\{-N,\dots,N\}$. Чтобы обеспечить дизъюнктность прогрессий $\{k\pm lh,\,l=1,\dots,m\}$, в качестве шагов $h$ мы берем простые числа из интервала $(m,N/m]$; следовательно, $S \asymp m^{-1}N/\log N$. Лемма доказана. § 6. Дальнейшая работаВ наиболее интересном случае $L_1$-нормы остается много вопросов. Вопрос 6.1. Является ли тригонометрическая система $\{e(kx)\}_{1\leqslant k\leqslant N}$ жесткой в $L_1$? Очевидно, что $d_n(\{\varphi_1,\dots,\varphi_N\},L_1)\geqslant A^{-1} d_n(B_1^N,\ell_\infty^N)$ для равномерно ограниченной ($\|\varphi_k\|_\infty\leqslant A$) ортонормированной системы. Поэтому хорошая аппроксимация невозможна при $n\leqslant c\log N$. Можно ли улучшить эту оценку? Вопрос 6.2. Докажите, что $d_n(\{w_1,\dots,w_N\},L_1)\geqslant c$ для последовательности $n=n(N)$, для которой $n/\log N\to\infty$. Независимость (безусловность) достаточна для $L_1$-жесткости, однако это условие очень ограничительно. Можно ли получить более слабое достаточное условие жесткости или хотя бы доказать жесткость конкретных систем? Вопрос 6.3. Является ли хаос Радемахера $\{r_i(t)r_j(t)\}_{1\leqslant i < j\leqslant N}$ жестким в $L_1$? Ср. с утверждением 3.4. Этот вопрос связан со следующим (см. также утверждение 4.1). Вопрос 6.4. Приведите явные примеры $\ell_1$-жестких множеств $V\subset \{-1,1\}^N$ полиномиального (или хотя бы субэкспоненциального) размера. В работе [16] нежесткость матрицы дискретного преобразования Фурье была связана с нежесткостью циркулянтов. В терминах поперечников получаем следующий вопрос. Перейдем к случаю $L_0$. Вопрос 6.6. Постройте равномерно ограниченную ортонормированную систему $\varphi_1,\dots,\varphi_N\in D_N(0,1)$, являющуюся $L_0$-жесткой. Вопрос 6.7. Верно ли, что для любой конечной абелевой группы $G$ множество характеров допускает хорошую аппроксимацию очень маломерными пространствами:
Цитирование в формате AMSBIB
\RBibitem{Mal24} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|