| Известия Российской академии наук. Серия математическая |
|
|
|
|
|
Равномерные жесткие фреймы Мальцева С. Я. Новиков, В. В. Севостьянова Самарский национальный исследовательский университет имени академика С. П. Королева
Англоязычная версия:
Izvestiya: Mathematics, 2022, Volume 86, Issue 4, Pages DOI: https://doi.org/10.4213/im9137e 
Реферативные базы данных:
    § 1. ВведениеПусть $n$ и $d$ – натуральные числа, $n\geqslant d$. Фрейм в пространстве $\mathbb{R}^d$ – это полное семейство, состоящее из $n$ векторов в $d$-мерном евклидовом пространстве, обобщающее понятие базиса; в определении нет требования линейной независимости векторов. Подробнее, семейство векторов $\{\varphi_j\}_{j=1}^n$ называется фреймом пространства $\mathbb{R}^d$, если существуют константы $0<a\leqslant b< \infty$ такие, что для всех $ \mathbf{x}\in \mathbb{R}^d$
$$
\begin{equation*}
a\|\mathbf{x}\|^2\leqslant \sum_{j=1}^n|\langle \mathbf{x},\varphi_j\rangle |^2\leqslant b\|\mathbf{x}\|^2.
\end{equation*}
\notag
$$
Числа $a$ и $b$ называются фреймовыми границами, они определены неоднозначно, обычно имеют в виду оптимальные границы, т. е. минимум $b$ и максимум $a$. Для конечномерного пространства понятие фрейма эквивалентно полноте системы векторов, т. е. $\operatorname{span}\{\varphi_j\}_{j=1}^n=\mathbb{R}^d$. Этот и другие известные факты о фреймах изложены в [1]. Оператор синтеза конечного набора векторов $\{\varphi_j\}_{j=1}^n$ из $\mathbb{R}^d$ определяется как $\mathbf{\Phi} \colon \mathbb{R}^n \to \mathbb{R}^d$, $\mathbf{\Phi} \mathbf{x} :=\sum_{j=1}^n \mathbf{x}(j)\varphi_j$, где $\mathbf{x}(j)$ обозначает $j$-ю координату $\mathbf{x}\in \mathbb{R}^n$. Сопряженным к оператору синтеза является оператор анализа $\mathbf{\Phi}^* \colon \mathbb{R}^d \to \mathbb{R}^n$, определяемый как $(\mathbf{\Phi}^*\mathbf{y})(j) = \langle \varphi_j,\mathbf{y}\rangle$ для $j = 1,\dots,n$. Композиция операторов анализа и синтеза $\mathbf{\Phi}^*\mathbf{\Phi}\colon\mathbb{R}^n \to \mathbb{R}^n$ определяет матрицу Грама: $(n\times n)$-матрицу, $(j,j')$-й элемент которой $(\mathbf{\Phi}^*\mathbf{\Phi})(j,j') = \langle\varphi_j,\varphi_{j'}\rangle$. Композиция этих операторов в другом порядке $\mathbf{\Phi}\mathbf{\Phi}^* \colon \mathbb{R}^d\to \mathbb{R}^d$ определяет фреймовый оператор $\mathbf{\Phi}\mathbf{\Phi}^*\mathbf{y} =\sum_{j=1}^n\langle\varphi_j,\mathbf{y}\rangle\varphi_j$. Известно, что последовательности $\{\varphi_j\}_{j=1}^n$ и $\{\widehat{\varphi}_j\}_{j=1}^n$ в $\mathbb{R}^d$ имеют одинаковые матрицы Грама тогда и только тогда, когда существует унитарный оператор $\mathbf{U}$ такой, что $\mathbf{U}\varphi_j=\widehat{\varphi}_j$ для всех $j = 1,\dots,n$. Для отдельно взятого вектора $\{\varphi_j\}$ операторы синтеза и анализа представляются в виде
$$
\begin{equation*}
\varphi_j\colon \mathbb{R}\to\mathbb{R}^d,\quad \varphi_j x = x\varphi_j;\qquad \varphi_j^*\colon \mathbb{R}^d\to\mathbb{R},\quad \varphi_j^*\mathbf{y} = \langle\varphi_j, \mathbf{y} \rangle.
\end{equation*}
\notag
$$
Используя такое представление, фреймовый оператор может быть записан в виде $\mathbf{\Phi}\mathbf{\Phi}^*=\sum_{j=1}^n\varphi_j\varphi_j^*$. Таким образом, матричное представление оператора синтеза $\mathbf{\Phi}$ выглядит как $(d\times n)$-матрица, столбцами которой являются координаты векторов фрейма $\{\varphi_j\}_{j=1}^n$. В частности, если фреймовые границы равны между собой, то фреймовый оператор представляется диагональной матрицей $\mathbf{\Phi}\mathbf{\Phi^*}{=}\, a \mathbf{I}_{\mathbb{R}^d}$ с $a>0$, и это представление позволяет получить весьма простое фреймовое представление вектора или сигнала:
$$
\begin{equation*}
\mathbf{x}=\frac 1a\mathbf{\Phi}\mathbf{\Phi^*}\mathbf{x} =\frac1{a}\sum_{j=1}^n\langle\varphi_j,\mathbf{x}\rangle\varphi_j , \qquad \mathbf{x}\in \mathbf{R}^d.
\end{equation*}
\notag
$$
Такой фрейм называется жестким или $a$-жестким; $1$-жесткий фрейм называют фреймом Парсеваля. Особый интерес представляют жесткие фреймы, векторы которых имеют одинаковые нормы. Такие фреймы называются равномерными. Подробнее, фрейм $\{\varphi_j\}_{j=1}^n$ называется равномерным, если существует $c>0$ такое, что $\|\varphi_{j}\|^2=c$, $j=1,\dots,n$. Если $a$-жесткий фрейм является равномерным, то между введенными выше величинами $d$, $c$ и $a$ существуют зависимости:
$$
\begin{equation*}
da=\operatorname{trace}(a\,\mathbf{I}_{\mathbb{R}^d}) =\operatorname{trace}(\mathbf{\Phi}\mathbf{\Phi^*}) =\operatorname{trace}(\mathbf{\Phi^*}\mathbf{\Phi})= \sum_{j=1}^n\|\varphi_j\|^2=nc.
\end{equation*}
\notag
$$
В частности, для фрейма Парсеваля имеем $d=nc$, поэтому равномерный фрейм Парсеваля имеет нормы $\leqslant 1$.
§ 2. Теорема Наймарка и ее матричные следствияСледующий результат М. А. Наймарка [2] оказался основой для численных конструкций фреймов и постоянно цитируется в статьях, посвященных фреймам и их многочисленным приложениям. Теорема 1. Если $\mathbf{\Phi}= \{\varphi_j\}_{j=1}^n$ – фрейм Парсеваля в $\mathbb{R}^d$, то существует ортонормированный базис $\{\mathbf{b}_j\}_{j=1}^n$ пространства $\mathbb{R}^n$ такой, что $\varphi_j=\mathbf{P}_{\mathbb{R}^d} \mathbf{b}_j$ для всех $j$, где $\mathbf{P}_{\mathbb{R}^d}$ обозначает ортогональный проектор из пространства $\mathbb{R}^n$ на $\mathbb{R}^d$. Обратное утверждение также справедливо и легко доказывается. Теорема 2. Если $\{\mathbf{b}_j\}_{j=1}^n$ – ортонормированный базис в $\mathbb{R}^n$, то $\mathbf{\Phi}= \{\mathbf{P}_{\mathbb{R}^d} \mathbf{b}_j\}_{j=1}^n$ является фреймом Парсеваля в $\mathbb{R}^d$, здесь $\mathbf{P}_{\mathbb{R}^d}$ – ортогональный проектор в $\mathbb{R}^n$ на $\mathbb{R}^d$. Доказательство. Пусть $\varphi_j=\mathbf{P}_{\mathbb{R}^d} \mathbf{b}_j$, $j=1,\dots, n$. Если $\mathbf{x}\in \mathbb{R}^d$, то
$$
\begin{equation*}
\|\mathbf{x}\|^2=\|\mathbf{P}_{\mathbb{R}^d} \mathbf{x}\|^2=\sum_{j=1}^n|\langle \mathbf{P}_{\mathbb{R}^d} \mathbf{x},\mathbf{b}_j\rangle |^2 =\sum_{j=1}^n|\langle \mathbf{x},\mathbf{P}_{\mathbb{R}^d}\mathbf{b}_j\rangle|^2 =\sum_{j=1}^n|\langle \mathbf{x},\varphi_j\rangle |^2,
\end{equation*}
\notag
$$
таким образом, $\mathbf{\Phi}$ оказывается фреймом Парсеваля. Теорема доказана. Теоремы 1 и 2 обобщены в работе [3] на фреймы общего вида, которые оказались проекциями базисов Рисса. Проекции общих ортогональных систем, вообще говоря, неполных, рассмотрены в [4]. Пусть матрица оператора синтеза есть $(d\times n)$-матрица, в которой столбцами являются координаты векторов фрейма $\{\varphi_j\}_{j=1}^n$ в стандартном базисе.Теорема 3. Пусть $\{\varphi_j\}_{j=1}^n$ – фрейм в $\mathbb{R}^d$. Тогда координаты векторов $\varphi_j$ могут рассматриваться как первые $d$ координат векторов в $\mathbb{R}^n$, которые образуют базис в $\mathbb{R}^n$. Если $\{\varphi_j\}_{j=1}^n$ – жесткий фрейм, то координаты векторов $\varphi_j$ являются первыми $d$ координатами некоторых векторов, которые образуют ортогональный базис пространства $\mathbb{R}^n$. Доказательство. Пусть $\{\varphi_j\}_{j=1}^n$ – произвольный фрейм в пространстве $\mathbb{R}^d$. Оператор анализа $\Phi^*\colon \mathbb{R}^d\to \mathbb{R}^n$ имеет матрицу
Если $\Phi^*\mathbf{x}=\mathbf{0}$, то
$$
\begin{equation*}
0=\|\Phi^*\mathbf{x}\|^2=\sum_{j=1}^n|\langle \varphi_j,\mathbf{x}\rangle |^2.
\end{equation*}
\notag
$$
Так как $\operatorname{span}\{\varphi_j\}_{j=1}^n=\mathbb{R}^d$, то $\mathbf{x}=\mathbf{0}$, и, таким образом, $\Phi^*$ – инъекция. Поэтому оператор $\Phi^*$ может быть продолжен до биекции $\widetilde{\Phi}^*\colon \mathbb{R}^n\to \mathbb{R}^n$, например, следующим образом. Если $\{\mathbf{e}_j\}_{j=1}^n$ – стандартный базис в $\mathbb{R}^n$, то, выделяя некоторый базис $\{\mathbf{b}_j\}_{j=d+1}^n$ в ортогональном дополнении образа $\mathcal{R}_{\Phi^*}$ в $\mathbb{R}^n$, полагаем по определению $\widetilde{\Phi}^*\mathbf{e}_j:=\mathbf{b}_j$, $j= d+1,\dots, n$. Матрица $\widetilde{\Phi}^*$ является $(n\times n)$-матрицей, в которой первые $d$ столбцов совпадают с матрицей $\Phi^*$: Так как $\widetilde{\Phi}^*$ по построению – сюръекция, то столбцы этой матрицы полны в $\mathbb{R}^n$. Следовательно, и строки матрицы $\widetilde{\Phi}^*$ полны в $\mathbb{R}^n$, они линейно независимы и образуют базис в $\mathbb{R}^n$. Если векторы $\{\varphi_j\}_{j=1}^n$ образуют $a$-жесткий фрейм в $\mathbb{R}^d$, то, как было замечено выше, $\Phi\Phi^*{=}\,a I$. Это значит, что строки матрицы оператора $\Phi$ ортогональны, если рассматривать их как векторы пространства $\mathbb{R}^n$. Добавляя к этой матрице $n\,{-}\,d$ строк так, чтобы расширенная таким образом матрица имела ортогональные строки, получаем $(n\,{\times}\,n)$-матрицу с ортогональными строками. Следовательно, и столбцы расширенной матрицы ортогональны. Теорема доказана. § 3. Матрица Мальцева. Равноугольные фреймы. Фреймы с полным спаркомВ 1947 г. опубликована заметка А. И. Мальцева [5], в которой он, отвечая на вопрос из статьи [6], построил матрицу, строки которой, как векторы (вещественного) евклидова пространства, ортогональны и имеют единичную длину, а столбцы этой матрицы, как векторы, имеют одинаковую длину. Такие матрицы мы называем матрицами Мальцева. Фактически, впервые построен равномерный фрейм Парсеваля. Работа Наймарка, о которой мы упомянули в § 2, часто цитируется в статьях о фреймах, а работа Мальцева осталась незамеченной. Современные конструкции равномерных жестких фреймов в $\mathbb{R}^d$ стали появляться только в начале XXI в. [7]. Рассмотрим подробнее построение матрицы Мальцева. Обоснуем сначала возможность рассмотрения только случая $d<n/2$. Лемма 1. Пусть $\{\varphi_j\}_{j=1}^{n}$ – $a$-жесткий фрейм в $\mathbb{R}^d$, и $d<n$. Тогда $(n\times n)$-матрица $(1/a)\mathbf{\Phi}^* \mathbf{\Phi}$ является матрицей ортогонального проектора на $d$-мерное подпространство $\mathbb{R}^n$. Матрица Грама $\mathbf{\Phi}^* \mathbf{\Phi}$ имеет собственные значения $a$ кратности $d$ и $0$ кратности $n-d$. Доказательство. Так как $\{\varphi_j\}_{j=1}^{n}$ – $a$-жесткий фрейм, имеем
$$
\begin{equation*}
\varphi_l=\frac{1}{a}\sum_{j=1}^n\langle\varphi_j, \varphi_l\rangle\varphi_j, \qquad l=1,\dots, n.
\end{equation*}
\notag
$$
Отсюда для любых $k$, $l$ получаем, что или Если $\mathbf{P}:=(1/a)\mathbf{\Phi}^* \mathbf{\Phi}$, то $\mathbf{P}=\mathbf{P}^2$. Учитывая, что оператор $\mathbf{P}$ самосопряженный, получаем, что $\mathbf{P}$ является ортогональным проектором на $d$-мерное подпространство. Матрица ортогонального проектора имеет $d$ собственных значений, равных $1$, и $n-d$ нулевых собственных значений, $\operatorname{trace} \mathbf{P} =\operatorname{rank} \mathbf{P} = d$. Следовательно, $\mathbf{\Phi}^* \mathbf{\Phi}= a\mathbf{P}$ имеет $d$ собственных значений, равных $a$, и $n-d$ нулевых собственных значений, Лемма доказана.Теорема 4. Каждый $a$-жесткий фрейм $\{\varphi_j\}_{j=1}^{n}$ в $\mathbb{R}^d$ имеет дополнительный по Наймарку фрейм $\{\psi_j\}_{j=1}^{n}$ со следующими свойствами: (i) $\{\psi_j\}_{j=1}^{n}$ является $a$-жестким фреймом для $\mathbb{R}^{(n-d)}$; (ii) матрица Грама $\mathbf{\Psi}^* \mathbf{\Psi}=a \mathbf{I}_{\mathbb{R}^n} - \mathbf{\Phi}^* \mathbf{\Phi}$; (iii) $\mathbf{\Phi}\mathbf{\Psi}^*=\mathbf{0}$. Доказательство. (i) Непосредственно проверяется, что матрица $\mathbf{Q}:=\mathbf{I}_{\mathbb{R}^n}-(1/a)\mathbf{\Phi}^*\mathbf{\Phi}$ удовлетворяет равенству $\mathbf{Q}=\mathbf{Q}^*=\mathbf{Q}^2$ и ее собственные значения – $1$ и $0$ с кратностями $n-d$ и $d$ соответственно. Это означает, что столбцы матрицы $\mathbf{Q}$, $\widetilde{\psi}_j:=\mathbf{Q}\mathbf{e}_j$, $j=1,\dots, n$, где $\{\mathbf{e}_j\}_{j=1}^{n}$ – ортонормированный базис в $\mathbb{R}^n$, определяют $\operatorname{span}\bigl(\{\widetilde{\psi}_j\}_{j=1}^{n}\bigr)=\mathbb{R}^{(n-d)}$. Если $\mathbf{f}\in \operatorname{span}\bigl(\{\widetilde{\psi}_j\}_{j=1}^{n}\bigr)$, то $\mathbf{Q}\mathbf{f}=\mathbf{f}$,
$$
\begin{equation*}
\mathbf{f}=\mathbf{Q}\biggl(\sum_{j=1}^n\langle\mathbf{Q} \mathbf{f}, \mathbf{e}_j\rangle \mathbf{e}_j\biggr)=\sum_{j=1}^n\langle \mathbf{f}, \mathbf{Q}\mathbf{e}_j\rangle \mathbf{Q} \mathbf{e}_j=\sum_{j=1}^n\langle \mathbf{f}, \widetilde{\psi}_j\rangle \widetilde{\psi}_j,
\end{equation*}
\notag
$$
т. е. набор векторов $\{\widetilde{\psi}_j\}_{j=1}^{n}$ образует фрейм Парсеваля для $\operatorname{span}\bigl(\{\widetilde{\psi}_j\}_{j=1}^{n}\bigr)$. (ii) Векторы $\psi_j= \sqrt{a} \widetilde{\psi}_j$, $j=1,\dots, n$, образуют $a$-жесткий фрейм для $\operatorname{span}(\{\psi_j\}_{j=1}^{n}) =\operatorname{span}\bigl(\{\widetilde{\psi}_j\}_{j=1}^{n}\bigr)$ и $\mathbf{\Psi}^*\mathbf{\Psi}=a\mathbf{I}_{\mathbb{R}^n}-\mathbf{\Phi}^*\mathbf{\Phi}$. (iii) По лемме имеем
$$
\begin{equation*}
(\mathbf{\Psi}\mathbf{\Phi}^*)^*(\mathbf{\Psi}\mathbf{\Phi}^*) =\mathbf{\Phi}\mathbf{\Psi}^*\mathbf{\Psi}\mathbf{\Phi}^* =\mathbf{\Phi}(a\mathbf{I}-\mathbf{\Phi}^*\mathbf{\Phi})\mathbf{\Phi}^* =a\mathbf{\Phi}\mathbf{\Phi}^*-(\mathbf{\Phi}\mathbf{\Phi}^*)^2=\mathbf{0}.
\end{equation*}
\notag
$$
Норма Фробениуса матрицы
$$
\begin{equation*}
\|\mathbf{\Psi}\mathbf{\Phi}^*\|^2_{\mathrm{Fro}}= \operatorname{trace}\bigl((\mathbf{\Psi}\mathbf{\Phi}^*)^*(\mathbf{\Psi}\mathbf{\Phi}^*)\bigr) =\operatorname{trace}\mathbf{0}=0.
\end{equation*}
\notag
$$
Следовательно, $\mathbf{\Psi}\mathbf{\Phi}^*=\mathbf{0}$, и сопряженная к ней $\mathbf{\Phi}\mathbf{\Psi}^*=\mathbf{0}$. Теорема доказана. Теорема 4 утверждает, что к $(d\times n)$-матрице $\mathbf{\Phi}$ оператора синтеза равномерного жесткого фрейма с векторами пространства $\mathbb{R}^d$ могут быть добавлены $n-d$ строк так, чтобы таким образом расширенная $(n\times n)$-матрица была ортогональной. При этом добавленные строки образуют $((n-d)\times n)$-матрицу оператора синтеза $\mathbf{\Psi}$ равномерного жесткого фрейма пространства $\mathbb{R}^{(n-d)}$. Для $d=n/2$ в качестве $\mathbf{\Phi}$ можно взять пару ортогональных $(d\times d)$-матриц, умноженных на $1/\sqrt{2}$ и поставленных рядом. Рассмотрим конструкцию Мальцева для $d<n/2$. Для полноты изложения, следуя [5], напоминаем конструкцию матриц Сильвестра–Уолша, которые образуют подмножество множества матриц Адамара. Замечание 1. Для каждого натурального $m$ существует $(2^m\times 2^m)$-матрица $\mathbf{H}_{2^m}$, все элементы которой равны $\pm 1$, со взаимно ортогональными строками и столбцами. Действительно, для $m=1$ матрица имеет вид
$$
\begin{equation*}
\mathbf{H}_2= \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}.
\end{equation*}
\notag
$$
Матрицы более высоких порядков определяются следующим образом: $2\leqslant m\in \mathbb{N}$, где $\otimes$ обозначает произведение Кронекера.Матрицы Сильвестра–Уолша тесно связаны с дискретными функциями Уолша, которые имеют много полезных приложений [8]. В качестве следствия к доказанному замечанию получаем, что для каждого натурального $m$ и для любого натурального $k\leqslant 2^m$ существуют $k$ взаимно ортогональных строк длины $2^m$ c числами $\pm 1$. Число $n$, обозначающее количество столбцов строящейся матрицы $\mathbf{\Phi}$, представим в виде
$$
\begin{equation*}
n= 2^{m_1}+\dots + 2^{m_t},\qquad 0\leqslant m_1<\dots< m_t.
\end{equation*}
\notag
$$
Найдется число $s$ такое, что $1\leqslant s\leqslant t-1$ и $2^{m_s}< d\leqslant 2^{m_{s+1}}$. Построение матрицы оператора синтеза равномерного жесткого фрейма $\mathbf{\Phi}$ будет проведено в два этапа. На первом мы построим матрицу с ортогональными строками из чисел $\pm 1$ и нулей, а на втором, не нарушая ортогональности строк, проведем требуемую условиями задачи нормировку. Матрица первого этапа имеет следующую структуру: Все ненулевые блоки заполняются сначала числами $\pm 1$. Блок $A_{1,1}$ – это $(2^{m_1}\times 2^{m_1})$-матрица с ортогональными строками, блок $A_{2,2}$ – это $((2^{m_2}-2^{m_1})\times 2^{m_2})$-матрица с ортогональными строками, $\dots$, блок $A_{s,s}$ – это $((2^{m_s}- 2^{m_{s-1}})\times 2^{m_s})$-матрица с ортогональными строками. Таким образом, левая часть матрицы $\mathbf{\Phi}$ состоит из $2^{m_s}$ строк и $2^{m_1}+\dots + 2^{m_s}$ столбцов. Все блоки со вторым индексом $s+1$ состоят из $p:= 2^{m_{s+1}}+\dots + 2^{m_t}$ столбцов. Каждый блок $A_{i,s+1}$, $i=1, \dots, s$, имеет столько же строк, как и блок $A_{i,i}$, $i=1, \dots, s$, а блок $A_{s+1,s+1}$ состоит из $d-2^{m_s}$ строк и $p$ столбцов. В каждом блоке $A_{i,i}$, $i=1, \dots, s$, количество строк $2^{m_i}-2^{m_{i-1}}\leqslant 2^{m_i}$ и в силу замечания ортогональные строки длины $2^{m_i}$ возможны. Рассмотрим подробнее правую часть матрицы. Разобьем блок на $t-s$ блоков $B_j$ размерами $d\times 2^{m_j}$, $j=s+1,\dots,t$. Заметим, что в каждом блоке $B_j$ число строк $d\leqslant 2^{m_j}$, и, следовательно, блоки $B_j$ можно заполнить $\pm1$ так, чтобы строки длины $2^{m_j}$ были взаимно ортогональны. Заметим, что объединяя строки блоков $B_j$, получаем ортогональные строки длины $p$. Рассматривая построенную таким образом матрицу целиком, видим, что это $(d\times n)$-матрица из $\pm 1$ и нулей с попарно ортогональными строками.Переходим к нормировке элементов построенной матрицы. Все элементы блоков $A_{i,i}$, $i=1,\dots,s$, умножаем на числа $\alpha_i$, $i=1,\dots,s$, элементы блоков $A_{j,s+1}$, $j=1,\dots,s+1$, на числа $\beta_j$, $j=1,\dots,s+1$, таким образом, чтобы длина любой вектор-строки была равна $1$, длина любого вектор-столбца – $\sqrt{d/n}$. Заметим, что при умножении блоков на любые числа строки матрицы останутся ортогональными. Для выбора чисел $\alpha_i$ и $\beta_j$ вычислим суммы квадратов элементов каждого столбца вновь построенной матрицы $\Phi$:
$$
\begin{equation}
\alpha_1^2\cdot2^{m_1}=\frac{d}{n},\quad \alpha_2^2\cdot(2^{m_2}-2^{m_1})=\frac{d}{n},\quad \dots,\quad \alpha_s^2\cdot(2^{m_s}-2^{m_{s-1}})=\frac{d}{n},
\end{equation}
\tag{3.1}
$$
$$
\begin{equation}
\beta_1^2\cdot2^{m_1}+\beta_2^2\cdot(2^{m_2}-2^{m_1})+\dots+ \beta_s^2\cdot(2^{m_s}-2^{m_{s-1}})+ \beta_{s+1}^2\cdot(d-2^{m_{s}})=\frac{d}{n}.
\end{equation}
\tag{3.2}
$$
Из уравнений (3.1) получаем значения
$$
\begin{equation*}
\alpha_1^2=\frac{d}{n\cdot2^{m_1}},\qquad \alpha_i^2=\frac{d}{n\cdot(2^{m_i}-2^{m_{i-1}})},\quad i=2,\dots,s.
\end{equation*}
\notag
$$
Условия нормировки строк дают
$$
\begin{equation}
\begin{aligned} \, &\alpha_1^2\cdot2^{m_1}+\beta_1^2\cdot(2^{m_{s+1}}+\dots+2^{m_t})=1, \\ &\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots\dots, \\ &\alpha_s^2\cdot2^{m_s}+\beta_s^2\cdot(2^{m_{s+1}}+\dots+2^{m_t})=1, \\ &\beta_{s+1}^2\cdot(2^{m_{s+1}}+\dots+2^{m_t})=1. \end{aligned}
\end{equation}
\tag{3.3}
$$
Подставив найденные значения $\alpha_i^2$ в (3.3), получим
$$
\begin{equation}
\begin{aligned} \, \beta_1^2 &=\frac{1}{2^{m_{s+1}}+\dots+2^{m_t}}\biggl(1-\frac{d}{n}\biggr), \\ \beta_j^2 &=\frac{1}{2^{m_{s+1}}+\dots+2^{m_t}} \biggl(1-\frac{d\cdot2^{m_j}}{n(2^{m_j}-2^{m_{j-1}})}\biggr),\qquad j=2,\dots,s, \\ \beta_{s+1}^2 &=\frac{1}{2^{m_{s+1}}+ \dots+2^{m_t}}. \end{aligned}
\end{equation}
\tag{3.4}
$$
Условие $d<n/2$ влечет
$$
\begin{equation*}
\begin{aligned} \, &1-\frac{d\cdot2^{m_j}}{n(2^{m_j}-2^{m_{j-1}})}> 1-\frac{\frac{n}{2}\cdot2^{m_j}}{n(2^{m_j}-2^{m_{j-1}})} \\ &\qquad=\frac{(2^{m_j}-2^{m_{j-1}})-2^{m_j-1}}{2^{m_j}-2^{m_{j-1}}} =\frac{2^{m_j-1}-2^{m_{j-1}}}{2^{m_j}-2^{m_{j-1}}}\geqslant0. \end{aligned}
\end{equation*}
\notag
$$
Таким образом, правые части равенств (3.4) положительны, что гарантирует существование чисел $\beta_j$. Легко убедиться, что найденные $\alpha_i$ и $\beta_j$ удовлетворяют равенству (3.2). Полученные таким образом системы векторов будем называть равномерными жесткими фреймами Мальцева. Приведем примеры матриц Мальцева. Пример 1. Рассмотрим случай $d=3$, $n=7$. Число $n$ представим в виде $n=2^0+2^1+2^2$, тогда матрица оператора синтеза будет иметь вид Из условий нормировки строк и столбцов находим значения $\alpha_i$ и $\beta_j$: Пример 2. Пусть $d=7$, $n=15$. Так как $15=2^0+2^1+2^2+2^3$, то где Пример 3. Матрица Адамара порядка $16$, построенная по алгоритму Мальцева, выглядит следующим образом: Напомним, что равномерный фрейм $\{\varphi_j\}_{j=1}^n$ называется равноугольным, если существует число $\gamma\geqslant 0$ такое, что $|\langle\varphi_{j},\varphi_{j^{'}}\rangle|=\gamma$ для всех $j\neq j'$. Матрица, состоящая из строк матрицы (3.5) с номерами $1$, $9$, $5$, $3$, $2$ и $16$, является матрицей оператора синтеза равноугольного фрейма. Другой способ выбора равноугольного жесткого фрейма приведен в [9]. Это строки с номерами $2$, $3$, $4$, $6$, $11$, $16$. Существуют ли другие способы выбора строк для получения равноугольного фрейма, нам неизвестно. Для $n\neq 2^k$ фреймы Мальцева не могут быть равноугольными, так как векторы-столбцы левой части матрицы ортогональны друг другу, а среди векторов из правой части найдется хотя бы одна пара неортогональных. В работах по теории сжатых измерений большое внимание уделяется так называемому спарку системы (см. [10]). Определение 1. Спарком $(d\times n)$-матрицы $\mathbf{\Phi}$ называется наименьшее количество линейно зависимых столбцов $\mathbf{\Phi}$. Если $\operatorname{spark}(\Phi)=d+1$, то любая группа из $d$ векторов-столбцов состоит из линейно независимых векторов, в этом случае говорят о фрейме с полным спарком. Предложение 1. В равномерном жестком фрейме Мальцева с $n\geqslant 4$ существуют $4$ линейно зависимых вектора. Доказательство. Если $\{\varphi_i\}_{i=1}^n$ – жесткий фрейм Мальцева, и $n\geqslant4$, то в двоичном представлении $n$ участвуют степени $2^t$ с $t\geqslant2$. Считая, что $t$ – максимальное число такое, что $2^t\leqslant n$, в $(d\times n)$-матрице $\Phi$ последний блок $B_t$ имеет размеры $d\times 2^t$. Покажем, что среди вектор-столбцов блока $B_t$ всегда найдутся $4$ линейно зависимых вектора. Перенумеруем векторы фрейма так, чтобы $\varphi_1,\dots,\varphi_{2^t}$ образовывали последние $2^t$ столбцов матрицы $\Phi$, т. е. блок $B_t$. Согласно алгоритму построения фрейма Мальцева блок $B_t$ получается удалением в матрице
$$
\begin{equation*}
\mathbf{H}_{2^t}=\left( \begin{array}{c|c} \rule{0pt}{14pt}\mathbf{H}_{2^{t-1}}&\mathbf{H}_{2^{t-1}}\\ \hline \rule{0pt}{14pt}\mathbf{H}_{2^{t-1}}&-\mathbf{H}_{2^{t-1}} \end{array}\right)
\end{equation*}
\notag
$$
любых $2^t-d$ строк. Пусть блок $B$ является результатом удаления из матрицы $\mathbf{O}_{t-1}$ некоторых $2^{t-1}-p$ строк, а $B'$ – результатом удаления из $\mathbf{O}_{t-1}$ некоторых $2^{t-1}-d+p$ строк, тогда $B$ имеет размер $p\times2^{t-1}$, а $B'$ – размер $(d-p)\times2^{t-1}$:
$$
\begin{equation*}
B_t=\left( \begin{array}{c|c} \rule{0pt}{14pt}B & B\\ \hline \rule{0pt}{14pt}B' & -B' \end{array}\right).
\end{equation*}
\notag
$$
Для любого $i=1,\dots,2^{t-1}$ сумма вектор-столбцов блока $B_t$ с номерами $i$ и $k_i=2^{t-1}+i$ равна вектору
$$
\begin{equation*}
\varphi_{i}+\varphi_{k_i}= \left(\begin{array}{c} 2\beta_1\\ \dots\\ 2\beta_p\\0\\ \dots\\0\\ \end{array}\right) \begin{array}{l} \hspace{0pt}\left.\begin{array}{c} \\\\\\ \end{array}\right\} p\\ \hspace{0pt}\left.\begin{array}{c} \\\\\\ \end{array} \right\}d-p \end{array},
\end{equation*}
\notag
$$
где $\beta_j$ – некоторые числа, на которые при построении фрейма Мальцева были умножены строки блока $B_t$. Таким образом, для любых $i$, $j$ выполняется Поскольку в блоке $B_t$ не менее четырех столбцов, можно заключить, что среди векторов фрейма существуют четыре линейно зависимых вектора. Предложение доказано. Следовательно, жесткий фрейм Мальцева может быть фреймом с полным спарком только при условии $\operatorname{spark}(\Phi)=d+1\leqslant4$. Предположим, что $\{\varphi_i\}_{i=1}^n$ – жесткий фрейм Мальцева с полным спарком, тогда, как было показано, $d\leqslant3$. Поскольку при построении матрицы $\Phi$ умножение блоков $A_{i,j}$ на ненулевые числа $\alpha_i$ и $\beta_j$ не меняет ортогональность векторов-строк и линейную зависимость и независимость векторов-столбцов матрицы $\Phi$, будем считать, что все ненулевые элементы матрицы $\Phi$ равны $\pm1$. Найдем, какие размеры может иметь блок $B_t$. Всегда можно умножить строки и столбцы матрицы $\Phi$ на $\pm1$ так, чтобы все элементы в первой строке и первом столбце блока $B_t$ были равны $1$. Предположим, что $d=2$ и в блоке $B_t$ больше двух столбцов. Тогда, так как $\varphi_1=\begin{pmatrix}1\\ 1\\\end{pmatrix}$ и первые координаты векторов $\varphi_2$ и $\varphi_3$ равны $1$, при любом выборе вторых координат в $\varphi_2$ и $\varphi_3$ получим два одинаковых вектора во фрейме, что противоречит равенству полноты спарка $\operatorname{spark}(\Phi)=3$. Таким образом, фрейм Мальцева с полным спарком в $\mathbb{R}^2$ возможен только для $n=3$. Такой фрейм однозначно определяется описанным выше алгоритмом: Для $d=3$ несложным перебором получаем единственный с точностью до перестановки столбцов вариант блока
$$
\begin{equation*}
B_t=\left(\begin{array}{cccc} 1&1&1&1\\ 1&1&-1&-1\\ 1&-1&-1&1\\ \end{array}\right).
\end{equation*}
\notag
$$
Отсюда получаем ограничения на количество столбцов блока $B_t$ и на общее количество векторов фрейма: $n\leqslant2^0+2^1+2^2=7$. Рассматривая значения $n=5,6,7$, замечаем, что ни один из фреймов Мальцева не будет фреймом с полным спарком. Следовательно, представленная матрица $B_2$ доставляет единственно возможный фрейм Мальцева с полным спарком в $\mathbb{R}^3$.
Цитирование в формате AMSBIB
\RBibitem{NovSev22} |
|
||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|