| Математические заметки |
|
|
|
|
|
Слабая сходимость жадного алгоритма и WN-свойство П. А. Бородинab a Московский государственный университет им. М. В. Ломоносова b Московский центр фундаментальной и прикладной математики
Англоязычная версия:
Mathematical Notes, 2023, Volume 113, Issue 4, Pages DOI: https://doi.org/10.1134/S0001434623030197 
Реферативные базы данных:
  Работа посвящена уточнению следующего утверждения. Теорема A [1; теорема 3.1]. Пусть $X$ – равномерно гладкое действительное банахово пространство, обладающее WN-свойством. Для всякого словаря $D\subset S(X)$ и всякого начального элемента остатки в слабом $X$-жадном алгоритме относительно $D$ сходятся к нулю в слабой топологии. Приведем определения, необходимые для понимания теоремы A. Пусть $S(X)$ – единичная сфера действительного банахова пространства $X$. Для всякого вектора $x\in X$ множество $J(x)=\{f\in S(X^*)\colon f(x)=\|x\|\}$ непусто по следствию из теоремы Хана–Банаха. Пространство $X$ называется гладким, если для всякого элемента $s\in S(X)$ множество $J(s)$ состоит из единственного функционала $F_s\in S(X^*)$. Гладкое пространство $X$ называется равномерно гладким, если для любого $\varepsilon>0$ найдется такое $\delta>0$, что для всяких $s\in S(X)$ и $y\in X$, $\|y\|<\delta$, выполнено неравенство WN-Свойство введено в [1]. Банахово пространство $X$ обладает $\mathrm{WN}$-свойством, если для всякой последовательности $s_n\in S(X)$ из того, что последовательность $F_{s_n}\in J(s_n)$ $*$-слабо сходится к нулю, следует, что $s_n$ слабо сходятся к нулю. Например, пространство $\ell_p$ обладает WN-свойством при $1<p<\infty$, а пространство $L_p[0,1]$ при тех же $p$ нет [1]. Подмножество $D$ единичной сферы $S(X)$ действительного банахова пространства $X$ называется словарем, если его линейная оболочка плотна в $X$. По каждому начальному элементу $x=x_0\in X$ слабый $X$-жадный алгоритм относительно словаря $D$ с параметром слабости $t\in (0,1]$ выдает последовательность где число $\lambda_{n+1}$ и элемент $g_{n+1}\in D$ выбираются из условия
$$
\begin{equation*}
\|x_n-\lambda_{n+1}g_{n+1}\|\leqslant (1-t)\|x_n\| +t\inf_{\lambda\in{\mathbb R}, g\in D}\|x_n-\lambda g\|.
\end{equation*}
\notag
$$
При $t=1$ это обычный $X$-жадный алгоритм [2], и для его работы необходимо, чтобы словарь $D$ дополнительно обладал тем свойством, что указанный $\inf$ достигается, т.е. множество
$$
\begin{equation*}
\Lambda(D)=\{\lambda g\colon \lambda\in{\mathbb R},\, g\in D\}
\end{equation*}
\notag
$$
является множеством существования в $X$.
Говорят, что жадный алгоритм (слабо) сходится для начального элемента $x_0$, если остатки $x_n$ (слабо) сходятся к нулю. О сходимости $X$-жадного алгоритма известно очень мало [2; гл. 6], [3], [4]. Нетрудно показать, что для сходимости $X$-жадного алгоритма по норме необходима гладкость пространства $X$, однако она не достаточна [5]. Неизвестно, сходится ли этот алгоритм слабо (тем более, по норме) во всяком равномерно гладком пространстве. Теорема A доставляет достаточное условие слабой сходимости: именно, WN-свойство равномерно гладкого пространства. Цель настоящей работы – распространить теорему A на более общие жадные приближения относительно произвольных множеств (теорема 1 ниже), и показать, что в контексте этих более общих жадных приближений WN-свойство действительно отвечает за слабую сходимость жадного алгоритма (теорема 2). Напомним алгоритм жадных приближений относительно множества [6]. Пусть $M$ – произвольное множество в $X$, уменьшающее норму: для всякого ненулевого элемента $x\in X$ выполнено неравенство $\rho(x,M)<\|x\|$ (здесь $\rho(x,M) =\inf_{y\in M}\|x-y\| $ – расстояние от $x$ до $M$). Слабый жадный алгоритм относительно $M$ с параметром слабости $t\in (0,1]$ сопоставляет каждому элементу $x=x_0\in X$ последовательность где элемент $y_{n+1}\in M$ выбирается из условия При $t=1$ для работы этого алгоритма необходимо, чтобы $M$ было множеством существования в $X$. Приведенный выше $X$-жадный алгоритм (2) относительно словаря $D$ совпадает с жадным алгоритмом относительно множества $\Lambda(D)$.В [6] исследуется сходимость жадного алгоритма относительно множества в гильбертовом пространстве при различных условиях на это множество. В частности, для всякого уменьшающего норму множества $M$ в гильбертовом пространстве $H$ и для всякого начального элемента $x_0\in H$ остатки $x_n$ в слабом жадном алгоритме (3) сходятся к нулю в слабой топологии (см. [6; теорема 2], формально доказательство проведено для параметра слабости $t=1/2$). Возникает естественный вопрос о справедливости аналога теоремы A для слабого жадного алгоритма относительно множества в банаховом пространстве. Ниже мы доказываем такой аналог при условии, что множество $M$ сильно уменьшает норму: для всякого ненулевого элемента $x$ найдутся такие $y_k\in M$, $y_k\to 0$, и константа $C(x)>0$, что Ясно, что для всякого словаря $D$ в равномерно гладком пространстве множество $\Lambda(D)$ сильно уменьшает норму.Теорема 1. Пусть $X$ – равномерно гладкое действительное банахово пространство, обладающее WN-свойством, множество $M\subset X$ сильно уменьшает норму. Тогда для всякого начального элемента $x_0\in X$ остатки в слабом жадном алгоритме относительно $M$ сходятся к нулю в слабой топологии. Непонятно, можно ли в этом утверждении заменить “сильно уменьшает норму” на “уменьшает норму”. Сходимость по норме в условиях теоремы 1 утверждать нельзя, как показано в [6; замечание 1]. Доказательство. Предположим, что для какого-то начального элемента последовательность $x_n$ жадных остатков не сходится к нулю слабо. Нормы $\|x_n\|$ убывают к некоторому числу $R>0$. Функционалы $f_n\in J(x_n)$ не могут сходиться слабо к 0 в силу WN-свойства ($*$-слабая сходимость в $X^*$ совпадает со слабой в силу рефлексивности равномерно гладкого пространства $X$ [7; гл. 2]). Пользуясь теоремами Банаха–Алаоглу и Эберлейна–Шмульяна [6; гл. 6] выберем подпоследовательность $\Lambda \subset {\mathbb N}$ номеров $n$, по которой $f_n$ имеет слабый предел $f\not=0$. Возьмем элемент $s\in S(X)$, для которого $f(s)=\|f\|$ (пользуемся рефлексивностью $X$ и теоремой Джеймса [7; гл. 1]). Для этого $s$ зафиксируем последовательность $y_k\in M$, $y_k\to 0$, со свойством (5). Имеем
$$
\begin{equation*}
1-C(s)\|y_k\|=\|s\|-C(s)\|y_k\|> \|s-y_k\|\geqslant \frac{f( s-y_k)}{\|f\|}=1-\frac{f(y_k)}{\|f\|},
\end{equation*}
\notag
$$
так что
$$
\begin{equation}
f(y_k)\geqslant C(s)\|f\|\|y_k\|, \qquad k=1,2,\dotsc\,.
\end{equation}
\tag{6}
$$
Далее, для всякого $n$ и всякого $\varepsilon>0$ в силу (4) и (1) имеем
$$
\begin{equation}
\begin{aligned} \, \notag \|x_{n+1}\| &\leqslant (1-t)\|x_n\|+t\|x_n-y_k\| =(1-t)\|x_n\|+t\|x_n\|\biggl\|\frac{x_n}{\|x_n\|} -\frac{y_k}{\|x_n\|}\biggr\| \\ &\leqslant\|x_n\|-tf_n(y_k)+t\varepsilon\|y_k\| \end{aligned}
\end{equation}
\tag{7}
$$
при
$$
\begin{equation*}
\frac{\|y_k\|}{\|x_n\|}\leqslant \frac{\|y_k\|}{R}\leqslant \delta,
\end{equation*}
\notag
$$
где $\delta=\delta(\varepsilon)$ берется из определения равномерной гладкости. Возьмем $\varepsilon< C(s)\|f\|/4$ и зафиксируем такое $k$, что $\|y_k\|<R \delta$ для соответствующего $\delta$. Из (7) получаем неравенство
$$
\begin{equation}
\|x_{n+1}\|\leqslant \|x_n\|-tf_n(y_k)+\frac{tC(s)\|f\|\,\|y_k\|}{4},
\end{equation}
\tag{8}
$$
верное при всех $n$. Теперь выберем такое большое $n\in \Lambda$, что
$$
\begin{equation*}
\|x_n\|<R+\frac{tC(s)\|f\|\,\|y_k\|}{4}, \qquad f_n(y_k)\geqslant \frac{C(s)\|f\|\,\|y_k\|}{2}
\end{equation*}
\notag
$$
(последнее возможно в силу слабой сходимости $f_n$ к $f$ при $n\in \Lambda$ и (6)). Из этих неравенств и (8) получаем $\|x_{n+1}\|<R$, что невозможно. Теорема доказана. Теорема 2. Во всяком действительном сепарабельном банаховом пространстве $X$, не обладающем WN-свойством, найдется такое сильно уменьшающее норму множество $M$, что остатки в жадном алгоритме относительно $M$ для некоторого начального элемента не сходятся слабо к нулю. Доказательство. 1. По условию найдутся такие элементы $z_n\in S(X)$ и функционалы $f_n\in J(z_n)$, что $f_n$ $*$-слабо сходятся к нулю, но $z_n$ не сходятся слабо к нулю. Выбирая, если надо, подпоследовательность, можем считать, что для некоторого $F\in S(X^*)$. Кроме того, можно считать (выбирая, если надо, подпоследовательность с помощью диагонального процесса), что для всякого $k=1,2,\dots$ существует предел 2. Пусть $\{s_k\}_{k=1}^\infty$ – всюду плотное множество на сфере $S(X)$. Дополнительно проредим $z_n$ и $f_n$ так, чтобы для всякого $m=0,1,2,\dots$ выполнялись следующие соотношения:
$$
\begin{equation}
|f_{n_m}(s_k)|<2^{-m-1} \qquad \text{при}\quad k\leqslant m,
\end{equation}
\tag{11}
$$
$$
\begin{equation}
|f_{n_m}(z_{n_k})|<2^{-m-3} \qquad \text{при}\quad k< m,
\end{equation}
\tag{12}
$$
$$
\begin{equation}
|f_{n_k}(z_{n_m})-\alpha_{n_k}|<2^{-m-3} \qquad \text{при}\quad k< m.
\end{equation}
\tag{13}
$$
Выбор последовательности $\{n_m\}_{m=0}^\infty$ происходит индуктивно. Номер $n_0$ выберем произвольно (условия (11)–(13) не накладывают никаких ограничений при $m=0$). Если уже выбраны $n_1,\dots,n_{m-1}$, то $n_m$ выбирается из условий (11) и (12) (элементы $s_1,\dots,s_m,z_{n_1},\dots,z_{n_{m-1}}$ фиксированы, а $f_n$ $*$-слабо сходятся к 0) и условий (13) (функционалы $f_{n_1},\dots,f_{n_{m-1}}$ и числа $\alpha_{n_1},\dots,\alpha_{n_{m-1}}$ фиксированы, $f_k(z_n)\to \alpha_k$ при $n\to\infty$ для всякого $k$). 3. Положим $x_{n_m}=y_m\in S(X)$, $f_{n_m}=g_m\in J(y_m)$, $\alpha_{n_m}=\beta_m$, $m=0,1,2,\dots$, и перепишем условия (9)–(13) в новых обозначениях:
$$
\begin{equation}
|g_m(s_k)|<2^{-m-1} \qquad \text{при}\quad k\leqslant m,
\end{equation}
\tag{15}
$$
$$
\begin{equation}
|g_k(y_m)-\beta_k|<2^{-m-3} \qquad \text{при}\quad k< m.
\end{equation}
\tag{17}
$$
4. Положим
$$
\begin{equation*}
M=\biggl\{ \frac{s_n}{2^{n+1}}, \,v_n:=(1+2^{1-n})y_{n-1}- (1+2^{-n})y_n\colon n=1,2,\dots\biggr\}.
\end{equation*}
\notag
$$
Покажем, что $M$ сильно уменьшает норму. Действительно, для всякого ненулевого элемента $x$ найдется такая подпоследовательность $\Lambda$ номеров $n$, что $s_n\to x/\|x\|$, $n\in \Lambda$, $n\to \infty$. Следовательно, при больших $n\in \Lambda$ имеем
$$
\begin{equation*}
\begin{aligned} \, \biggl\|x-\frac{s_n}{2^{n+1}}\biggr\| &\leqslant \biggl\|x-\frac{x}{2^{n+1}\|x\|}\biggr\| +\biggl\| \frac{x}{2^{n+1}\|x\|} -\frac{s_n}{2^{n+1}} \biggr\| \\ &\leqslant \|x\|-\frac{1}{2^{n+1}}+\frac{1}{2^{n+2}}=\|x\|-\frac{1}{2^{n+2}} = \|x\|-\frac{1}{2}\biggl\| \frac{s_n}{2^{n+1}}\biggr\|, \end{aligned}
\end{equation*}
\notag
$$
где элементы $s_n/2^{n+1}$ принадлежат $M$ и стремятся к 0 по норме. 5. Докажем, что для начального элемента $x_0=2y_0$ жадный алгоритм (3) с параметром $t=1$ относительно $M$ выдает остатки $x_n=(1+2^{-n})y_n$, которые не сходятся слабо к нулю в силу (14). Для этого достаточно показать, что если $x_n=(1+2^{-n})y_n$, то Имеем Покажем, что все остальные элементы множества $M$ расположены дальше от $x_n$.Если $1\leqslant k\leqslant n$, то
$$
\begin{equation*}
\begin{aligned} \, \biggl\| x_n-\frac{s_k}{2^{k+1}}\biggr\| &\geqslant g_n \biggl( x_n-\frac{s_k}{2^{k+1}} \biggr) \\ &\geqslant 1+2^{-n}-|g_n(s_k)|2^{-k-1}\geqslant 1+2^{-n}-2^{-n-k-2}> 1+2^{-n-1}, \end{aligned}
\end{equation*}
\notag
$$
где в предпоследнем неравенстве использовалось (15). Если $k>n$, то
$$
\begin{equation*}
\biggl\| x_n-\frac{s_k}{2^{k+1}}\biggr\| \geqslant 1+2^{-n}-2^{-n-2}> 1+2^{-n-1}.
\end{equation*}
\notag
$$
Если $k<n$, то
$$
\begin{equation*}
\begin{aligned} \, \| x_n-v_k\| &\geqslant g_n(x_n-v_k)=1+2^{-n}-g_n(v_k)\geqslant 1+2^{-n}-2|g_n(y_{k-1})|-2|g_n(y_k)| \\ &>1+2^{-n}-2\cdot 2^{-n-3}-2\cdot 2^{-n-3}=1+2^{-n}-2^{-n-1}=1+2^{-n-1}, \end{aligned}
\end{equation*}
\notag
$$
где в последнем неравенстве использовалось (16). Для $k=n$ имеем
$$
\begin{equation*}
\begin{aligned} \, \| x_n-v_k\| &=\|2(1+2^{-n})y_n-(1+2^{1-n})y_{n-1}\| \\ &\geqslant 2(1+2^{-n})-(1+2^{1-n})|g_n(y_{n-1})|>2(1+2^{-n})-(1+2^{1-n})2^{-n-3}>2, \end{aligned}
\end{equation*}
\notag
$$
где в предпоследнем неравенстве опять использовалось (16). Наконец, если $k\geqslant n+2$, то
$$
\begin{equation*}
\begin{aligned} \, \| x_n-v_k\| &\geqslant g_n(x_n-v_k)=1+2^{-n}-(1+2^{1-k})g_n(y_{k-1})+(1+2^{-k})g_n(y_k) \\ &=1+2^{-n}-(1+2^{1-k})(g_n(y_{k-1})-\beta_n) \\ &\qquad+(1+2^{-k})(g_n(y_k)-\beta_n)+\beta_n(2^{-k}-2^{1-k}) \\ &\geqslant 1+2^{-n}-(1+2^{1-k})2^{-k-2}-(1+2^{-k})2^{-k-3}-2^{-k} \end{aligned}
\end{equation*}
\notag
$$
(в последнем неравенстве использовалось $k-1>n$ и (17))
$$
\begin{equation*}
>1+2^{-n}-2^{-k-1}-2^{-k-2}-2^{-k}>1+2^{-n}-2^{-k+1}\geqslant 1+2^{-n-1}.
\end{equation*}
\notag
$$
Таким образом, равенство (18) доказано, а вместе с ним и теорема 2. 
Цитирование в формате AMSBIB
\RBibitem{Bor23} |
|
||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|