| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье) Сравнение чисто жадного и ортогонального жадного алгоритмов К. С. Вишневецкийab a Московский государственный университет им. М. В. Ломоносова b Московский центр фундаментальной и прикладной математики
Англоязычная версия:
Mathematical Notes, 2024, Volume 115, Issue 1, Pages DOI: https://doi.org/10.1134/S0001434624010048 
Реферативные базы данных:
  1. ВведениеПусть H – действительное гильбертово пространство со скалярным произведением ⟨⋅,⋅⟩ и нормой ‖⋅‖, D – словарь, т.е. подмножество единичной сферы S(H), линейные комбинации элементов которого плотны в H [1; гл. 2, § 1]. Также нам понадобится дополнительное условие на словарь: Для всякого вектора x \in H определена последовательность наименьших m-членных уклонений относительно словаря D [1; гл. 1, § 1]:
\begin{equation*}
\sigma_m(x, D)=\sigma_m(x):=\inf \biggl\{\biggl\|x-\sum_{j=1}^m \lambda_j h_j\biggr\|\colon h_j \in D, \lambda_j \in \mathbb{R}\biggr\}.
\end{equation*}
\notag
Если словарь D удовлетворяет условию (1), то корректно определены жадные алгоритмы относительно словаря D [1; гл. 2, § 1], выдающие по каждому элементу x \in H последовательности жадных остатков. Чисто жадный алгоритм:
\begin{equation*}
x_0:=x, \qquad x_{n+1}:=x_n-\langle x_n, g(x_n) \rangle g(x_n)=x_n-P_{\operatorname{span}\{g(x_n)\}}(x_n), \quad n=0, 1, 2, \dots,
\end{equation*}
\notag
где P_L(x) – ортогональная проекция вектора x на подпространство L \subset H. Ортогональный жадный алгоритм:
\begin{equation*}
x_0^{\mathrm o}:=x, \qquad x_{n+1}^{\mathrm o}:=x-P_{\operatorname{span}\{g(x_0^{\mathrm o}), g(x_1^{\mathrm o}), \dots, g(x_n^{\mathrm o})\}}(x), \quad n=0, 1, 2, \dots\,.
\end{equation*}
\notag
Жадный алгоритм со свободной релаксацией:
\begin{equation*}
x_0^r:=x, \qquad x_{n+1}^r:=x-P_{\operatorname{span}\{x_0^r-x_n^r, g(x_n^r)\}}(x), \quad n=0, 1, 2, \dots\,.
\end{equation*}
\notag
Словарь 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. Тогда следующие условия эквивалентны:
Доказательство. Так как пространство двумерное, для всех x \in \mathbb{R}^2 справедливы равенства
Импликация 1) \Rightarrow 2) очевидна. 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, следовательно, Поскольку \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. Тогда а значит, \|x_n\|=\|x_n^{\mathrm o}\|=\|x_n^r\|=\sigma_n(x)=0 для всякого n \geqslant 2.Предложение 1 доказано. 3. Необходимое условие для дискретных словарейВ случае \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 выполнено условие
\begin{equation*}
H_{\alpha} \cap D= \begin{cases} \{\pm e_{\alpha}\} ,& \operatorname{dim}H_{\alpha}=1, \\ \displaystyle \bigcup_{k=1}^{N(\alpha)} \{ \pm e_{\alpha}^{k}, \pm f_{\alpha}^k\} , & \operatorname{dim}H_{\alpha}=2, \textit{ где } e_{\alpha}^k \perp f_{\alpha}^k. \end{cases}
\end{equation*}
\notag
Здесь 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}. Тогда
\begin{equation*}
\begin{aligned} \, & - \langle x_1, g(x_1) \rangle \langle g(x_1), g(x_0) \rangle=\langle x_1, g(x_0) \rangle- \langle x_1, g(x_1) \rangle \langle g(x_1), g(x_0) \rangle \\ &\qquad =\bigl\langle x_1-\langle x_1, g(x_1) \rangle g(x_1), g(x_0) \bigr\rangle=\langle x_2, g(x_0) \rangle=\langle x_2^{\mathrm o}, g(x_0) \rangle=0. \end{aligned}
\end{equation*}
\notag
Следовательно, \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], определенные условиями принадлежат [D].В дальнейшем будем использовать обозначения Доказательство. Возьмем начальный вектор 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\}. Заметим, что следовательно,
\begin{equation*}
H=\overline{\operatorname{span}\{H_{[h]}\colon [h] \in [D]\}}
\end{equation*}
\notag
в силу полноты словаря. Также для любых [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]}. Таким образом, где суммирование ведется только по тем [h] \in [D], у которых H_{[h]} различны.
Условие
\begin{equation*}
H_{\alpha} \cap D= \begin{cases} \{\pm e_{\alpha}\}, & \operatorname{dim}H_{\alpha}=1, \\ \displaystyle \bigcup_{k=1}^{N(\alpha)} \{ \pm e_{\alpha}^{k}, \pm f_{\alpha}^k\}, & \operatorname{dim}H_{\alpha}=2, \text{ где } e_{\alpha}^k \perp f_{\alpha}^k, \end{cases}
\end{equation*}
\notag
выполнено в силу леммы 3 и симметричности словаря D.
Теорема 1 доказана. 4. Достаточное условиеТеорема 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 выполнено условие:
\begin{equation*}
H_{\alpha} \cap D= \begin{cases} \{\pm h_{\alpha}\}, & \operatorname{dim}H_{\alpha}=1, \\ D_{\alpha}, & \operatorname{dim}H_{\alpha}=2. \end{cases}
\end{equation*}
\notag
Здесь 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. По построению ортонормированной системы имеем
\begin{equation*}
x_n=\sum_{k=n}^{\infty}\lambda_k e_k, \qquad \|x_n\|^2=\sum_{k=n}^{\infty}\lambda_k^2
\end{equation*}
\notag
для последовательности чисто жадных остатков в случае, когда чисто жадный алгоритм на каждом шаге выбирает 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]
\begin{equation*}
\sigma_n(x, \{e_k\})^2=\|x_n\|^2=\sum_{k=n}^{\infty}\lambda_k^2.
\end{equation*}
\notag
В итоге показано, что \|x_n\|=\sigma_n(x) для любого n и любой реализации чисто жадного алгоритма, и \{g(x_n)\}_0^{\infty} – ортонормированная система. Осталось показать, что чисто жадный алгоритм, ортогональный жадный алгоритм и жадный алгоритм со свободной релаксацией работают одинаково. Докажем это по индукции. Пусть для всех k \leqslant n выполнены равенства
\begin{equation*}
x_k=x_k^{\mathrm o}=x_k^r, \qquad g(x_k)=g(x_k^{\mathrm o})=g(x_k^r).
\end{equation*}
\notag
Так как системы \{g(x_k)\}_0^{n}, \{g(x_k^{\mathrm o})\}_0^{n}, \{g(x_k^r)\}_0^{n} совпадают, а \{g(x_k)\}_0^{n} – ортонормирована, имеем
\begin{equation*}
\begin{aligned} \, x_{n+1} &=x_n-P_{\operatorname{span}\{g(x_n)\}}(x_n), \\ x_{n+1}^{\mathrm o} &=x-P_{\operatorname{span}\{g(x_0^{\mathrm o}), g(x_1^{\mathrm o}), \dots, g(x_n^{\mathrm o})\}}(x) \\ &=x-P_{\operatorname{span}\{g(x_0^{\mathrm o}), g(x_1^{\mathrm o}), \dots, g(x_{n-1}^{\mathrm o})\}}(x)-P_{\operatorname{span}\{g(x_n)\}}(x_n) \\ &=x_n^{\mathrm o}-P_{\operatorname{span}\{g(x_n)\}}(x_n)=x_{n+1}, \\ x_{n+1}^r &=x-P_{\operatorname{span}\{x_0^r-x_n^r, g(x_n^r)\}}(x)=x-P_{\operatorname{span}\{x_0^r-x_n^r\}}(x)- P_{\operatorname{span}\{g(x_n)\}}(x) \\ &=x_n^r-P_{\operatorname{span}\{g(x_n)\}}(x_n)=x_{n+1}. \end{aligned}
\end{equation*}
\notag
Таким образом x_{n+1}=x_{n+1}^{\mathrm o}=x_{n+1}^r, что и требовалось.
Теорема доказана. Следствие 1. Пусть D \subset S(H) – симметричный словарь, удовлетворяющий условию (1), и M(D) < 1. Следующие условия эквивалентны:
Автор благодарен П. А. Бородину за постановку задачи и помощь в работе над статьей. 
Цитирование в формате AMSBIB
\RBibitem{Vis24}
Эта публикация цитируется в следующих 1 статьяx:
|
|
||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|