Аннотация:
Получены условия на словарь в гильбертовом пространстве, необходимые или достаточные для совпадения чисто жадного и ортогонального жадного алгоритмов относительно этого словаря.
Библиография: 3 названия.
Пусть $H$ – действительное гильбертово пространство со скалярным произведением $\langle \cdot, \cdot \rangle$ и нормой $\|\cdot\|$, $D$ – словарь, т.е. подмножество единичной сферы $S(H)$, линейные комбинации элементов которого плотны в $H$ [1; гл. 2, § 1]. Также нам понадобится дополнительное условие на словарь:
$$
\begin{equation}
\forall\, x \in H \quad \exists\, g(x) \in D\colon \sup_{p \in D} |\langle x, p \rangle|= |\langle x, g(x) \rangle|.
\end{equation}
\tag{1}
$$
Для всякого вектора $x \in H$ определена последовательность наименьших $m$-членных уклонений относительно словаря $D$ [1; гл. 1, § 1]:
Словарь $D$ можно считать симметричным: при замене $D$ на $D \cup (-D)$ так определенные жадные алгоритмы не изменятся.
Известно, что все эти алгоритмы сходятся, т.е. $x_n \to 0$, $x_n^{\mathrm o} \to 0$ и $x_n^r \to 0$ при $n \to \infty$ [1; гл. 2, § 2], [2; теорема 3.1].
Отметим, что указанные алгоритмы могут реализовываться по-разному, в силу неоднозначности выбора элементов $g(x_n)$, $g(x_n^{\mathrm o})$ и $g(x_n^r)$. В дальнейшем под последовательностью $x_n$, $x_n^{\mathrm o}$ или $x_n^r$ подразумевается произвольная реализация соответствующего алгоритма.
Будем говорить, что два жадных алгоритма работают одинаково до $n$-го шага, если для любого начального вектора $x$ из равенств $g(x_k^1)=g(x_k^2)$ при $0 \leqslant k \leqslant n- 1$ следуют равенства $x_k^1=x_k^2$ при $1 \leqslant k \leqslant n$.
Будем говорить, что два жадных алгоритма работают одинаково, если для любого натурального $n$ они работают одинаково до $n$-го шага.
Все три указанных выше жадных алгоритма работают одинаково до 1-го шага, более того, на первом шаге они дают наилучшее 1-членное приближение, т.е. для любого $x \in H$ справедливы равенства
При $n \geqslant 2$ нормы $n$-х остатков во всех указанных алгоритмах уже вообще говоря больше или равны $\sigma_n(x)$. Также из определения ортогонального жадного алгоритма и жадного алгоритма со свободной релаксацией видно, что они работают одинаково до 2-го шага.
Данная работа является продолжением работы автора [3], в которой описывались словари $D$ с условием $\|x_n\|=\sigma_n(x)$ при всех $x \in H$ и натуральных $n$, где $x_n$ – произвольная последовательность чисто жадных остатков вектора $x$ относительно словаря $D$.
Цель настоящей работы – найти условия на словарь $D$, необходимые или достаточные для одинаковой работы чисто жадного и ортогонального жадного алгоритмов. Более того, показывается, что при выполнении найденных достаточных условий все три жадных алгоритма работают одинаково и реализуют наилучшие $m$-членные приближения, т.е. справедливы равенства $\|x_n\|=\|x_n^{\mathrm o}\|= \|x_n^r\|=\sigma_n(x)$ при всех $x \in H$ и натуральных $n$. Хорошо известно, что эти равенства выполнены в случае, когда $D$ состоит из элементов произвольного ортонормированного базиса в $H$.
2. Двумерный случай
В случае двумерного евклидова пространства $H=\mathbb{R}^2$ нетрудно полностью описать словари с указанным свойством. Пусть $a, b \in S(\mathbb{R}^2)$ и $a \neq -b$. Обозначим через $\widehat{(a,b)}$ меньшую открытую дугу окружности $S(\mathbb{R}^2)$ с концами в точках $a$ и $b$. Для вектора $a \in \mathbb{R}^2$ обозначим за $R(a)$ вектор, ортогональный $a$ и определенный с точностью до знака.
Предложение 1. Пусть $D \subset S(\mathbb{R}^2)$ – замкнутое симметричное множество, содержащее не менее 4 точек, $S(\mathbb{R}^2) \setminus D=\bigcup_{k=1}^N \widehat{(a_k,b_k)}$, где $N \leqslant \infty$. Тогда следующие условия эквивалентны:
2) $\Leftrightarrow$ 3), так как ортогональный жадный алгоритм и жадный алгоритм со свободной релаксацией работают одинаково до 2-го шага.
2) $\Rightarrow$ 4). Возьмем произвольное $k$ и элемент $x_0=2a_k/3+b_k/3$. Элемент $g(x_0)=a_k$ выбирается однозначно, и $x_1=x_1^{\mathrm o}=x_0-\langle x_0, a_k \rangle a_k$. Так как $x_2^{\mathrm o}=0$, то $x_2=0$, следовательно,
$$
\begin{equation*}
g(x_1)=g(x_1^{\mathrm o})=\frac{x_1}{\|x_1\|} \in D.
\end{equation*}
\notag
$$
Поскольку $\langle x_1, a_k \rangle=0$, имеем $R(a_k)=\pm x_1/ \|x_1\| \in D$ в силу симметричности словаря. Для $b_k$ рассуждения аналогичны.
4) $\Rightarrow$ 1). Если $x_0 / \|x_0\| \in D$, то
а значит, $\|x_n\|=\|x_n^{\mathrm o}\|=\|x_n^r\|=\sigma_n(x)=0$ для всякого $n \geqslant 1$.
Пусть $x_0 / \|x_0\| \notin D$, т.е. $x_0 / \|x_0\| \in \widehat{(a_k,b_k)}$ для некоторого $k$. Без ограничения общности можно считать, что $g(x_0)=a_k$ и $x_1=x_0-\langle x_0, a_k \rangle$. Все три жадных алгоритма работают одинаково до 1-го шага, и выполнено равенство (2). Поскольку $\langle x_1, a_k \rangle=0$, то $x_1 / \|x_1\|=\pm R(a_k) \in D$. Тогда
В случае $\operatorname{dim}H \geqslant 3$ задача полного описания словарей, для которых чистый жадный и ортогональный жадный алгоритмы работают одинаково, представляется довольно трудной. Ниже в следствии 1 мы получим такое описание для дискретных словарей.
Параметром когерентности [1; гл. 2, § 6] словаря $D$ называется величина
$$
\begin{equation*}
M(D):=\sup\bigl\{|\langle g, h \rangle|\colon g \neq \pm h,\, g, h \in D\bigr\}.
\end{equation*}
\notag
$$
Теорема 1. Пусть $D \subset S(H)$ – симметричный словарь, удовлетворяющий условию (1), $M(D) < 1$ и $\operatorname{dim}H \geqslant 3$. Если чисто жадный и ортогональный жадный алгоритмы работают одинаково до 2-го шага, то пространство $H$ представляется в виде $H=\bigoplus^{\perp}_{\alpha \in A}H_{\alpha}$ такой прямой суммы попарно ортогональных подпространств ($A$ – некоторое подмножество индексов), что $D \subset \bigcup_{\alpha \in A} H_{\alpha}$, $\operatorname{dim}H_{\alpha} \in \{1, 2\}$ и для всех $\alpha$ выполнено условие
Здесь $N(\alpha)$ – конечное число, свое для каждого двумерного $H_{\alpha}$, $e_{\alpha}, e_{\alpha}^k, f_{\alpha}^k$ – единичные векторы соответствующего подпространства $H_{\alpha}$.
Замечание 1. В силу одинаковой работы ортогонального жадного алгоритма и жадного алгоритма со свободной релаксацией до 2-го шага, в условии теоремы ортогональный жадный алгоритм можно заменить на жадный алгоритм со свободной релаксацией.
Лемма 1. Пусть выполнены условия теоремы 1. Тогда для любого начального вектора $x_0 \in H$ при любом выборе $g(x_0)$ и $g(x_1)$ справедливо равенство
Доказательство. Пусть выполнены равенства $g(x_0)=g(x_0^{\mathrm o})$ и $g(x_1)=g(x_1^{\mathrm o})$. Так как чисто жадный и ортогональный жадный алгоритмы работают одинаково до 2-го шага, то $x_2=x_2^{\mathrm o}$. Тогда
Следовательно, $\langle g(x_0), g(x_1) \rangle=0$, так как $\langle x_1, g(x_1) \rangle \neq 0$.
Лемма доказана.
Лемма 2. Пусть выполнены условия теоремы 1. Тогда для любого элемента $d \in D$, начального вектора $x_0 \in H$ с условием $\langle x_0 , d \rangle=0$ равенство $\langle g(x_0), d \rangle=0$ выполнено при любом выборе $g(x_0)$.
Доказательство. Рассмотрим начальный вектор $y=d+\varepsilon x_0$, где $\varepsilon > 0$ таково, что $g(y)=d$. Такое $\varepsilon$ существует в силу условия $M(D) < 1$. Тогда $y_1=\varepsilon x_0$ и в качестве $g(y_1)$ можно взять $g(x_0)$. Применяя лемму 1 к начальному вектору $y$, получаем $\langle g(x_0), d \rangle=0$.
Лемма доказана.
На множестве $H \setminus \{0\}$ введем отношение эквивалентности: $d \sim h$, если $\operatorname{span}\{d\}=\operatorname{span}\{h\}$. Множество всех классов эквивалентности обозначим $P(H)$, класс эквивалентности элемента $d$ обозначим $[d]$, также будем отождествлять $[d]$ и $\operatorname{span}\{d\}$. Для произвольного подмножества $K \subset H \setminus \{0\}$ положим $[K]:=\{[d]\colon d \in K\}$.
Лемма 3. Пусть выполнены условия теоремы 1. Тогда для любых различных $[d], [h] \in [D]$ элементы $[d_1], [h_1]$, определенные условиями
Доказательство. Возьмем начальный вектор $x$ с условием $\langle x, d \rangle\,{=}\,\langle x, h \rangle\,{=}\,0$. Обозначим $e_1=g(x)$ (любой из элементов удовлетворяющих этому условию); тогда по лемме 2 имеем $\langle e_1, d \rangle=\langle e_1, h \rangle=0$.
В общем случае, пусть есть система $\{d, h, e_{\alpha}\colon \alpha \in A\} \subset D$ такая, что все элементы системы попарно ортогональны, кроме пары элементов $d$ и $h$. Если данная система не является базисом в $H$, то найдется вектор $y$, ортогональный всем элементам данной системы, тогда по лемме 2 данную систему можно расширить, добавив к ней элемент $g(y)$. В итоге получим базис $\{d, h, e_{\alpha}\colon \alpha \in A\} \subset D$, в котором все элементы попарно ортогональны, кроме пары элементов $d$ и $h$. Теперь применим лемму 2 к начальному вектору $d_1$ и элементам $\{d, e_{\alpha}\colon \alpha \in A\} \subset D$, получим что $d_1$ и $g(d_1)$ ортогональны всем элементам $\{d, e_{\alpha}\colon \alpha \in A\} \subset D$; следовательно, $[d_1]=[g(d_1)] \in [D]$. Аналогично с вектором $h_1$.
Лемма доказана.
Лемма 4. Пусть $X_3 \subset H$ – трехмерное подпространство, $D \subset S(H)$ – словарь, замкнутый относительно операции $\Delta$, и $\operatorname{span}\{D_3\}=X_3$, где $D_3=D \cap X_3$. Тогда найдется такой класс $[d] \in [D_3]$, что $\langle d, h \rangle=0$ для всех $[h] \in [D_3]$, $[h] \neq [d]$.
Лемма 4 идентична лемме 2 из [3] (последняя сформулирована в [3] несколько иначе, но фактически в ней рассматриваются словари, замкнутые относительно операции $\Delta$).
Доказательство теоремы 1. Возьмем произвольный элемент $[g_1] \in [D]$.
Если для всех $[h] \in [D]$ и $[h] \neq [g_1]$ верно $\langle g_1, h \rangle=0$, то положим $H_{[g_1]}:=\operatorname{span}\{g_1\}$.
Если найдется такой $[g_2] \neq [g_1]$, что $[g_2] \in [D]$ и $\langle g_1, g_2 \rangle \neq 0$, то положим $H_{[g_1]}:=\operatorname{span}\{g_1, g_2\}$. Для всех $[h] \in [D] \setminus [(H_{[g_1]})]$ верно $\langle g_1, h \rangle=\langle g_2, h \rangle=0$ по лемме 4, примененной к $X_3=\operatorname{span}\{g_1,g_2,h\}$. Заметим, что
в силу полноты словаря. Также для любых $[h_1], [h_2] \in [D]$ либо $H_{[h_1]}=H_{[h_2]}$, либо $H_{[h_1]} \cap H_{[h_2]}=\{0\}$ и $H_{[h_1]} \perp H_{[h_2]}$. Таким образом,
Теорема 2. Пусть $D \subset S(H)$ – симметричный словарь. Пусть пространство $H$ представляется в виде $H=\bigoplus^{\perp}_{\alpha \in A}H_{\alpha}$ такой прямой суммы попарно ортогональных подпространств ($A$ – некоторое подмножество индексов), что $D \subset \bigcup_{\alpha \in A} H_{\alpha}$, $\operatorname{dim}H_{\alpha} \in \{1, 2\}$ и для всех $\alpha$ выполнено условие:
Здесь $D_{\alpha}$ – словарь в плоскости $H_{\alpha}$ такой, что $S(H_{\alpha}) \setminus D_{\alpha}=\bigcup_{k=1}^{N_{\alpha}} \widehat{(a_k^{\alpha},b_k^{\alpha})}$, где $N_{\alpha} \leqslant \infty$, и удовлетворяющий условию $R_{\alpha}(a_k^{\alpha}), R_{\alpha}(b_k^{\alpha}) \in D_{\alpha}$, где $R_{\alpha}(a)$ – вектор, лежащий в плоскости $H_{\alpha}$ и ортогональный $a$ (определенный с точностью до знака). Тогда чисто жадный алгоритм, ортогональный жадный алгоритм и жадный алгоритм со свободной релаксацией работают одинаково и реализуют наилучшие $m$-членные приближения, т.е. $\|x_n\|=\|x_n^{\mathrm o}\|=\|x_n^r\|=\sigma_n(x)$ при всех натуральных $n$.
Доказательство. По произвольному элементу $x \in H$ построим ортонормированную систему. Пусть $\alpha \in A$ и $P_{\alpha}(x)$ – ортогональная проекция вектора $x$ на подпространство $H_{\alpha}$. Рассмотрим только те $\alpha \in A$, для которых $P_{\alpha}(x) \neq 0$.
В случае $\operatorname{dim}H_{\alpha}=1$ положим $\lambda_{\alpha}=|\langle x, h_{\alpha} \rangle|$, $e_{\alpha}=\operatorname{sgn}\langle x, h_{\alpha} \rangle h_{\alpha}$.
В случае $\operatorname{dim}H_{\alpha}=2$ положим $\lambda_{\alpha}'=\max_{g \in D_{\alpha}}\langle x, g \rangle=\langle x, e_{\alpha}'\rangle$, где $e_{\alpha}' \in D_{\alpha}$ (выбираем любой вектор, реализующий указанный максимум). Если $P_{\alpha}(x)/ \|P_{\alpha}(x)\| \neq e_{\alpha}'$, то полагаем $e_{\alpha}''=\pm R(e_{\alpha}')$, где знак плюс или минус выбирается так, чтобы $\lambda_{\alpha}''=\langle x, e_{\alpha}''\rangle \geqslant 0$. Имеем $e_{\alpha}'' \in D$ так как $R_{\alpha}(a_k^{\alpha}), R_{\alpha}(b_k^{\alpha}) \in D_{\alpha}$ при всех $k$.
Таким образом, $\{e_{\alpha}, e_{\alpha}', e_{\alpha}''\}$ – не более чем счетная ортонормированная система, $\{\lambda_{\alpha}, \lambda_{\alpha}', \lambda_{\alpha}''\}$ – соответствующие неотрицательные коэффициенты Фурье элемента $x$. Упорядочим элементы системы по невозрастанию соответствующих коэффициентов Фурье (такое упорядочивание не единственное), получим разложение $x=\sum_{k=0}^{\infty}\lambda_k e_k$. По построению ортонормированной системы имеем
для последовательности чисто жадных остатков в случае, когда чисто жадный алгоритм на каждом шаге выбирает $e_n$ в качестве $g(x_n)$. При этом при любой другой работе чисто жадного алгоритма нормы $\|x_n\|$ будут такими же, а в качестве $g(x_n)$ выбираются векторы этой же системы в другом порядке.
для всех натуральных $m$. Действительно, пусть $y=\sum_{k=1}^{m}\mu_k h_k$ – $m$-членная комбинация элементов словаря $D$. Не ограничивая общности, пусть $h_1 \neq e_k$ при всех $k$ и $h_1 \in H_{\alpha}$.
Если $P_{\alpha}(x)=0$, то заменим в $m$-членной комбинации все $\mu_k h_k \in H_{\alpha}$ на нулевые элементы.
Если $P_{\alpha}(x)/\|P_{\alpha}(x)\| \in H_{\alpha} \cap D$, то заменим в $m$-членной комбинации $\mu_1 h_1$ на $P_{\alpha}(x)$, а все остальные $\mu_k h_k \in H_{\alpha}, k \neq 1$, на нулевые элементы.
В случае $P_{\alpha}(x)/\|P_{\alpha}(x)\| \notin H_{\alpha} \cap D$ рассмотрим два варианта. Если $h_k \notin H_{\alpha}$ при $2 \leqslant k \leqslant m$, то заменим в $m$-членной комбинации $\mu_1 h_1$ на $\langle x, e_{\alpha}' \rangle e_{\alpha}'$. В противном случае, не ограничивая общности можно считать, что $h_2 \in H_{\alpha}$. Тогда заменим в $m$-членной комбинации $\mu_1 h_1$ и $\mu_2 h_2$ на $\langle x, e_{\alpha}' \rangle e_{\alpha}'$ и $\langle x, e_{\alpha}'' \rangle e_{\alpha}''$, а все остальные $\mu_k h_k \in H_{\alpha}$, $k > 2$, на нулевые элементы.
При таких заменах норма $\|x-y\|$ не увеличится. Таким образом, доказано неравенство $\sigma_m(x,D) \geqslant \sigma_m(x,\{e_k\})$. Обратное неравенство следует из включения $\{e_k\} \subset D$.
Осталось вспомнить хорошо известное равенство [1; гл. 1, § 1]
В итоге показано, что $\|x_n\|=\sigma_n(x)$ для любого $n$ и любой реализации чисто жадного алгоритма, и $\{g(x_n)\}_0^{\infty}$ – ортонормированная система. Осталось показать, что чисто жадный алгоритм, ортогональный жадный алгоритм и жадный алгоритм со свободной релаксацией работают одинаково. Докажем это по индукции. Пусть для всех $k \leqslant n$ выполнены равенства
Здесь $N(\alpha)$ – конечное число, свое для каждого двумерного $H_{\alpha}$, $e_{\alpha}, e_{\alpha}^k, f_{\alpha}^k$ – единичные векторы соответствующего подпространства $H_{\alpha}$.
Автор благодарен П. А. Бородину за постановку задачи и помощь в работе над статьей.