| Математические заметки |
|
|
|
|
|
Эта публикация цитируется в 1 научной статье (всего в 1 статье) Краткие сообщения Эффективный алгоритм разложения вектора на два вектора с малой равномерной нормой Б. С. Кашинab, Д. Г. Ромскийc a Математический институт им. В. А. Стеклова Российской академии наук, г. Москва b Московский центр фундаментальной и прикладной математики c Московский государственный университет им. М. В. Ломоносова
Англоязычная версия:
Mathematical Notes, 2023, Volume 114, Issue 6, Pages DOI: https://doi.org/10.1134/S0001434623110755 
Реферативные базы данных:
 Ниже $\langle \,\cdot\,{,}\,\cdot\,\rangle$ – скалярное произведение в $\mathbb{R}^N$, $N=1,2,\dots$, $\mathrm{O}^N$ – группа ортогональных преобразований $\mathbb{R}^N$ с мерой Хаара $\mu_H$. Пусть также $B_p^N$, $1 \leqslant p \leqslant \infty$, – единичный шар пространства $\ell_p^N$, а $S^{N-1}$ – единичная сфера в $\ell_2^N$. В работе [1], посвященной в основном оценкам поперечников, были установлены следующие результаты, первый из которых мы приведем в двух двойственных формулировках. Утверждение A. Существует постоянная $\gamma > 0$ такая, что для всех преобразований $T \in \mathrm{O}^N$, $N=1,2,\dots$, за исключением множества $V \subset \mathrm{O}^N$ меры $\mu_H(V) \leqslant 2^{-N}$ имеет место включение Утверждение A'. При $N=1,2,\dots$ для всех ортогональных преобразований $T \in \mathrm{O}^N$ за исключением множества $V \subset \mathrm{O}^N$, $\mu_H(V) \leqslant 2^{-N}$, имеет место неравенство где $c > 0$ – абсолютная постоянная. Утверждение B. Для любого $\varepsilon>0$ существуют постоянная $c_{\varepsilon}>0$ и подпространство $L \subset \mathbb{R}^N$, $N=1,2,\dots$, размерности $n \geqslant N(1-\varepsilon)$ такие, что В работе Любарского и Вершинина [2] было предложено использовать утверждение B в прикладных вопросах обработки сигналов. Точнее, как показано в [2], утверждение B позволяет для произвольного вектора $x\in B_2^n$ и фиксированного случайного жесткого фрейма $\{u_i\}^N_{i=1}$, $u_i\in \mathbb{R}^n$, $i=1,2,\dots$, $N\leqslant (1+\varepsilon)n$, построить разложение
$$
\begin{equation}
x=\sum^{N}_{i=1} a_i u_i, \qquad |a_i| \leqslant \frac{c_{\varepsilon}}{\sqrt{N}}\,, \quad i=1,\dots,N.
\end{equation}
\tag{4}
$$
Такое представление затем использовалось рядом авторов, в том числе в задачах оптимальной квантизации сигналов и федеративного обучения (federated learning) (см., например, [3]–[5]). При этом в [2] был предложен эффективный алгоритм представления произвольного вектора в виде (4). Аналогично, в настоящей заметке построен эффективный алгоритм $A(x,T)$ реализации включения (1) и приведены результаты численного эксперимента по его реализации. Пусть $V_N$ – множество вершин куба $B_{\infty}^{N}$. Указанный алгоритм – жадный алгоритм (см. [6]) в евклидовом пространстве со словарем $W=V_N \cup T^*V_N$, где $T \in \mathrm{O}^N$ – произвольное преобразование, удовлетворяющее соотношению (2), а $T^*$ – обратное к $T$ преобразование. Пусть задан произвольный вектор $x \in \mathbb{R}^N$. Легко проверить, что максимум скалярного произведения вектора $x$ с элементами из $W$ равен левой части неравенства (2). Поэтому неравенство (2) позволяет оценить сверху расстояние от произвольного вектора $x$ до ближайшей к нему полупрямой $l$ вида $\lambda w$, $\lambda > 0$, где $w$ – элемент словаря: здесь $P_l$ – оператор ортогонального проектирования на $l$, $\widetilde{c} < 1$ – универсальная постоянная. Применяя описанный шаг алгоритма к $x-P_l(x)$ и так далее, получим представление
$$
\begin{equation}
x=\sum_{k=1}^{\infty}\lambda_k w_k, \qquad w_k \in W, \quad 0 \leqslant \lambda_k \leqslant \frac{(\widetilde{c})^{k-1}}{\sqrt{N}}\|x\|_2.
\end{equation}
\tag{6}
$$
Отсюда следует, что жадный алгоритм сходится линейно по логарифмической шкале.
Таким образом, имеет место Теорема 1. Пусть при $N=2,3,\dots$ матрица $T \in \mathrm{O}^N$ удовлетворяет соотношению (2). Жадный алгоритм, задающий разложение (6), для любого $x \in B^{N}_{2}$ за $k$ шагов, $k=1,2,\dots$, строит векторы $u_k$ и $v_k$ такие, что где $\gamma < 1$ и C – абсолютные постоянные. Для численных экспериментов ортогональная матрица генерировалось с помощью следующего известного результата (см. [7; теорема 4]): Теорема 2. Пусть $\boldsymbol{v}_1,\dots,\boldsymbol{v}_N$ – случайные независимые равномерно распределенные векторы на $S^0,\dots,S^{N-1}$ соответственно. Переопределим функцию знака $\operatorname{sgn}$ в нуле, положив $\operatorname{sgn} 0=1$. Определим для данного $\boldsymbol{v}_m \in S^{m-1}$ матрицу отражений $\mathring{H}_m(\boldsymbol{v}_m)$ следующим равенством: Для численного эксперимента генерировалось 100 случайных ортогональных матриц размерности $N=1024$, и на каждой из них алгоритм был применен для 200 случайных разреженных векторов единичной нормы с мощностью носителя $\operatorname{supp} x=32$ и точностью разложения $\|x-u-v\|_2 \leqslant 10^{-6}$. Были проанализированы следующие величины:
$$
\begin{equation*}
\sqrt{N}\,\max(\|u(x)\|_{\infty},\|Tv(x)\|_{\infty}), \qquad \sqrt{N}\,(\|u(x)\|_{\infty}+\|Tv(x)\|_{\infty}),
\end{equation*}
\notag
$$
где $u(x)$, $v(x)$ – векторы, которые получаются в результате работы алгоритма.
Выявлено несколько особенностей: первая величина имеет плотность распределения с тремя различными локальными максимумами в точках 1.61, 1.67 и 1.76, что может свидетельствовать о нетривиальных геометрических свойствах отображения $x \mapsto (u,Tv)$ (см. рис. 1). Еще одной особенностью является устойчивость второй величины по выбору случайной ортогональной матрицы (см. рис. 2). Среднее значение второй величины, сосчитанной отдельно для каждой матрицы, колебалось около отметки 2.078, а максимальные и минимальные значения отличаются от средних не более чем на 0.1. Алгоритм был также запущен на матрице Уолша для сравнения эффективности со случайной матрицей. Для этого было сгенерировано 20000 разреженных векторов единичной нормы с мощностью носителя $\operatorname{supp}x=32$. Результаты показали, что среднее значение величины $\sqrt{N}\,\max(\|u(x)\|_{\infty},\|Tv(x)\|_{\infty})$ для матрицы Уолша составило 2.36, а максимальное – 4.03, что гораздо хуже чем аналогичные показатели для случайных матриц. Из этого можно сделать вывод, что выбор матрицы Уолша в качестве входной матрицы для алгоритма, несмотря на вычислительную простоту, негативно влияет на качественные характеристики получаемого разложения. 
Цитирование в формате AMSBIB
\RBibitem{KasRom23} |
|
||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|