Фреймы с полным спарком в теореме Чеботар¨ева и их применение в восстановлении сигнала

1.    Фреймы с полным спарком в теореме Чеботар¨ева

Пусть m ^ n и Ф = { ^ i }™ i — набор векторов в F n , где F обозначает одно из числовых полей R или C . Оператор Cx := {^ x,^ i )}™ i называется оператором анализа. Если (т х п)-матрица оператора C имеет полный ранг, то Ф называется фреймом для пространства F n . Другими словами, Ф является полной системой в F n , т. е. span Ф = F n .

Эквивалентное определение фрейма: существуют константы 0 < A ^ B < ж такие, что для всех x g F n ,

• ^# Работа выполнена в рамках реализации программы развития Научно-образовательного математического центра Приволжского федерального округа, соглашение № 075-02-2025-1791.

m

Allxll2 < £ l(x,^i>|2 < B llxll2-i=1

Таким образом, оператор анализа C устанавливает изоморфизм между F ⁿ и n-мерным подпространством Im C C F ^m . Если границы фрейма A и B могут быть выбраны так, что A = B = 1, то фрейм называют фреймом Парсеваля. Самый простой способ получить такой фрейм состоит в удалении m — n строк из унитарной m х m-матрицы [1]. При этом, конечно, нормы столбцов оставшейся прямоугольной матрицы становятся разными. Возможность построения равномерных фреймов Парсеваля в R ⁿ впервые доказал А. И. Мальцев [1]. Фрейм называется равномерным , если все его элементы имеют равные нормы (equal-norm в англоязычных статьях).

С публикации работы [2] начались активные исследования фреймов с полным спар-ком, такие фреймы оказались удобными в качестве измерительных векторов для восстановления сигналов по неполным данным. Понятие спарка можно ввести для произвольной системы векторов в конечномерном пространстве F ⁿ .

Определение 1. Спарком s системы векторов Ф называется минимальное количество ее линейно зависимых элементов. Система Ф C F n имеет полный спарк, если каждое ее подмножество из n элементов линейно независимо, т. е. s = n + 1. Представляя систему Ф в n-мерном пространстве над полем F в виде n х m-матрицы так называемого оператора синтеза m

D : F m ^ F n , Dy := £ y(i)^ i , i =1

столбцы которой являются векторами системы Ф, имеем:

s(Ф) = min{||x||o : x G Fm, Dx = 0, x = 0}, где ||x||o — количество ненулевых координат вектора x.

Стандартный метод получения фреймов с полным спарком использует классические m х m-матрицы Вандермонда, из которых удаляются последние m — n строк. Если ставить задачу получения равномерных фреймов Парсеваля с полным спарком, то она становится довольно сложной, причем в пространстве R ⁿ сложнее, чем в C ⁿ . В C ⁿ основным источником равномерных фреймов Парсеваля с полным спарком оказалась матрица дискретного преобразования Фурье (ДПФ). Удаление из m х m-ДПФ-матрицы последних m — n строк решает задачу. А можно ли удалять не последние, а произвольные строки? Простые примеры показывают, что не всегда. В (4 х 4)-матрице ДПФ

11  1  1

1 —i — 1 i

1 — 11   — 1

1 i —1 —i нулевая и вторая строки содержат нулевой минор.

Н. Г. Чеботар¨ев доказал следующую теорему [3].

Теорема 1 (Чеботар¨ев) . Для простого числа m все миноры матрицы Вандермонда (e jk ) m - ₌1₀ , E = exp ( 2т ) , отличны от нуля.

Удаляя из этой матрицы произвольные m — n строк, получаем (n х m)-матрицу, столбцы которой образуют равномерный фрейм Парсеваля с полным спарком. Таким образом,

Н. Г. Чеботар¨ева надо считать первооткрывателем равномерных фреймов Парсеваля с полным спарком. Как заметила В. В. Севостьянова в устном сообщении, если каждый минор m х m-матрицы ДПФ отличен от нуля, то число m простое.

2.    Фреймы с полным спарком в восстановлении сигнала по модулям измерений

Посмотрим на векторы фрейма Ф = {p i } m=i как на измерительные, а скалярные произведения вида (x,p i ) будем рассматривать как результаты измерений неизвестного сигнала x G R n . В такой модели восстановления сигнала по модулям измерений активно используется нелинейный оператор

A :           ■ R m ;  x ^{|( x,pЯ}^.

Доказано, что A инъективен тогда и только тогда, когда для любого разбиения Ф на два подмножества по крайней мере одно из них оказывается полным в R ⁿ [4, 5] (свойство альтернативной полноты (АП)).

Инъективность оператора A позволяет восстановить сигнал x c точностью до знака. В этом случае говорят, что фрейм Ф обладает свойством восстановления по модулям измерений (ВМИ). Таким образом, оказалось, что в пространстве R ⁿ свойства (АП) и (ВМИ) эквивалентны.

Обозначим через B R n единичный шар пространства R ⁿ . Будем говорить о свойстве ВМИ B , если оператор A инъективен только на векторах из B R n .

Теорема 2. Свойства ВМИ в и (АП) эквивалентны в R n .

• <1 Сначала заметим, что если Ф G ВМИ в , то Ф — полная система. Если это не так, то найдется h G R n , h = 0, (h, p i ) = 0 для любого i. Равенства

( W ,^i) = ^{l( 0,}^i ^ i = 1, ²,’”

противоречат ВМИ B .

Предположим, что система Ф не обладает свойством альтернативной полноты. Пусть множество индексов I С N такое, что {p i } i ^ l и {p i } i ^ i — неполные системы. Найдем

О

два ненулевых элемента f,g GB \{ 0 } такие, что (f,P i ) =0, i G I, и (g,p i ) =0, i G I.

О

Подбираем e >  0 так, чтобы f ± eg GB . Простая проверка показывает, что

^{|( f} + eg,P i Я = ^{|( f -} eg,P i )l ,   i = 1,²,...

Следовательно, существует к = ± 1 такое, что f — eg = K(f + eg). Если к =1, то g = 0. Если к = — 1, то f = 0. Оба этих заключения противоречат выбору элементов f и g. >

Минимальное количество измерений для восстановления сигнала из R ⁿ по модулям измерений вещественными измерительными векторами равно 2n — 1. Если m G 2п — 2, то система Ф разбивается на две подсистемы, в каждой из которых n — 1 элемент, и эти подсистемы не полны.

Лемма 1. Если количество измерительных векторов минимально, то

Ф = { p i } ² =₁ ¹ G ( ВМИ ) в R n О Ф имеет полный спарк.

• < Предположим, что спарк системы Ф строго меньше n + 1. Это означает существование множества индексов I с мощностью n такого, что {pi}iel не полна в Rn. С другой

3.    Фреймы с полным спарком в теории нейронных сетей

стороны, мощность дополнения I c равна n — 1, и система {^ i } i ^ i c не полна в R n . Получено противоречие со свойством альтернативной полноты. >

Фреймы с полным спарком нашли применение и в теории нейронных сетей, которая широко использует (нелинейную) функцию активации (Rectified Linear Unit), которая определяется равенством ReLU(s) = max(0,s), s G R [6].

Функция активации определяет так называемый ReLU-слой (ReLU-layer):

L a : R n ^ R m ; x н { ReLU( ( x, ^ i ) — a i)}^

для вектора смещения (bias) a G R m .

Для x G R n и a G R m определяется множество индексов

• I X := { 1 <  i <  m : ( x, ^ i ) >  a i } .

Для фиксированного i : 1 C i ^ m, определяется множество векторов

Q “ := { x g R n : ( x, ^ i ) >  a i } .

Определение 2. Фрейм Ф называется a-выпрямляющим на множестве K С R n для вектора a G R m , если для всех x G K подмножество Ф 1 а := { ^ i } i _e i a полно в R n .

Теорема 3. Пусть Ф = { ^ i } m=₁ С R n , a G R m ; 0 = K — открытое или строго выпуклое подмножество в R ⁿ . Оператор L _α инъективен на K тогда и только тогда, когда Ф — a-выпрямляющий фрейм на K.

Определение 3. Множество U называется строго выпуклым, если для всех x,y G U О         о и A G (0,1), xa := (1 — A)x + Ay G U, где U — внутренность U.

• <1 Необходимость. Предположим, что Ф не является a-выпрямляющим. Существует x G K такой, что (^ i ) i e i a не фрейм. Значит, существует

⁰ = r ^g span ⁽^ i ^a .

Если K открыто, то при достаточно малых е > 0

y ± := x ± er G K, у ₊ = у - .

При этом L a У + = L _a y - , инъективности нет.

Предположим, что Ф не является a-выпрямляющим. Существует x G K такой, что (^i)iela не фрейм. Используя определение строгой выпуклости, находим z G K : z = x, xa = (1 — A)x + Az GK, A G (0,1).

Заметим, что для любого i

|( xa ,^ i ) — ( x,^ i )| <  A | x — z|| VB.

При соответствующем выборе λ доказательство для открытого множества переносится на выпуклое заменой x на x λ .

Достаточность. Пусть фрейм Ф a-выпрямляющий на множестве K, т. е. для любого x g K, Ф 1 а — фрейм. Если L _a x = L _a у для x,y G K, то

(x,P i ) = (у, P i ) , i G I x И I y .

• 1)    K — открытое множество в R n . Выберем e > 0 так, чтобы открытый шар B ^ (x) С K. Предположим, что x = у. Если 0 < 5 <  ^x—y^ , то

x s := (1 — 5)x + 5у G B ^ (x) С K.

Пусть i G I xl , т. е. ( x s ,P i ) ^ a i . Интервал, которому принадлежит ( x s ,p i ) , находится правее точки α i . Поэтому

• •    если ( x s ,P i ) >  a i , то ( x, p i ) > a i и (y,p i ) >  a i ;

• •    если (x s ,p i ) = a i , то (x,p i ) = ( у, ^ i > = a i .

Следовательно, I xl С I x И I^.

Так как xs G K, то Ф a — фрейм ^ Ф апа — фрейм. x_δ                      x y

Для всех i G Т £ И I y имеем равенства (x,p i ) = (y,P i ) , из которых следует, что x = у.

• 2)    K — выпуклое множество в R n . Для X G (0,1) имеем

x\ = (1 — X)x + Xy G K, поэтому Ф/а — фрейм.

xλ

Повторяя рассуждения 1), получаем, что I ^y С Iy И I y , отсюда Ф /аша — фрейм ^ x = у. >

Следствие. Пусть K — выпуклое или открытое множество в R n . Если фрейм Ф имеет полный спарк, то Ф является a-выпрямляющим на K тогда и только тогда, когда | I y | ^ n для всех x G K.

В отличие от ситуации теоремы 2, α -выпрямляющие фреймы зависят от множества K.

Теорема 4. Если Ф = { p i } т=1 — a-выпрямляющий фрейм в R n , то m ^ 2n.

Для единичного шара любой нормированный фрейм является α-выпрямляющим, если a = — (1,..., 1) t .

Нормированный базис α-выпрямляющий для единичного тогда и только тогда, когда a = —(1,..., 1) t .

<1 Выберем x G R n так, чтобы (x, p i ) = 0 для всех i, и a G R ^m . Определим разбиение множества индексов:

Ix ^:= ^{{ i : ( x,}P i > >  ^{0 }} , I — ^:= ^{{ i : ( x,}P i > <  ^{0 }} .

Пусть

t * := max -—i—- . i p t p m (x, P i )

Для t > t ^* >  0 имеем равенства

У +          I t = и -t = .

Найдено два вектора u := tx и v := —tx в R n такие, что I y И I vy = 0 . Если Ф — a-выпрямляющий фрейм в R n , то Ф / а и Ф / а должны быть полными в R n , поэтому | Ф ! « | ^ n и | Ф / а | ^ n, m ^ 2n.

Если все векторы фрейма Ф = { ^ i } m=i имеют единичную норму (такой фрейм называют нормированным), и x G B R n , то ( x, p i ) ^ — 1, i = 1, 2,.. .m.

Если нормированный базис a-выпрямляющий для B R n , то I y = { 1,2,...,n } , ( x, w ) ^ a i для любого x G B R и для i = 1, 2,... , n. В частности, (— p i , P i ) = — 1 ^ a i . >

4.    Переполненные системы в бесконечномерном гильбертовом пространстве

В бесконечномерном сепарабельном гильбертовом пространстве H фрейм определяется как система элементов Ф = { ^ i } i=i такая, для которой существуют константы 0 < A С B < ж такие, что для всех x G H

∞

A » x « 2 С£|( х.^ )| ² С B « х » ² .

i=1

Если для некоторой системы векторов выполняется только правое неравенство в определении фрейма, то ее называют бесселевой системой.

Бесконечномерным аналогом систем с полным спарком являются так называемые переполненные системы. Система элементов гильбертова пространства H называется переполненной , если каждая ее бесконечная подсистема полна в H таком, что span { ^ n _k } = H . Существование такой системы доказывалось несколько раз [7, 8].

Если в конечномерном пространстве каждая система с полным спарком оказывается фреймом, то в гильбертовом пространстве переполненные системы и большая часть фреймов оказываются непересекающимися семействами. Каждый фрейм является полной системой, но далеко не каждая полная система оказывается фреймом.

Приведем известную серию примеров переполненных систем.

Теорема 5 [9] . Пусть a >  0 и { A _n }^ i — бесконечная последовательность попарно различных точек в C . Тогда {e^l ^ ^nt } n =i — переполненная система в L 2 (0, a) О sup n | A _n | <  от .

Если числа A n G R , n = 1, 2,... , то переполненная система { e ^iAn t } n=i не может быть бесселевой (а тем более, фреймом), так как из правого неравенства в определении фрейма следует, что { A _n } “=i не имеет точек сгущения [10].

Справедливо и более общее утверждение:

Теорема 6 [5] . Бесселева система Ф = {^ n } n= , » ^ _n || ^ 5 >  0 не может быть переполненной системой в гильбертовом пространстве.

<1 Система Ф допускает представление в виде конечного объединения базисных последовательностей Рисса Ф = Ф 1 U Ф 2 U ... U Ф _т . Это один из вариантов проблемы Ка-дисона — Зингера, которая была решена в [11]. Если система Φ переполненная, то хотя бы одна из последовательностей, например, Φ 1 будет базисом Рисса в H . Бесконечная собственная подсистема Ф о ^ Ф 1 порождает собственное подпространство span Ф о ^ H , что противоречит тому, что система переполненная. >

Замечание. Теорема 6 оставляет два вопроса: 1) существуют ли переполненные фреймы общего вида?

• 2)    как доказать теорему, не ссылаясь на гипотезу Кадисона — Зингера?

Базисом Рисса называется полная в H система {^ n } “₌₁ , для которой существуют константы A,B> 0 такие, что для каждого конечного набора скаляров {c n } имеем:

A Еы² С || Е ■ЧГ С в ЕЫ² -

Если в только что приведенном определении опустить слово «полная», то получится определение базисной последовательности Рисса.

Базис Рисса является фреймом, а фрейм является базисом Рисса только если он точный (exact), т. е. перестает быть фреймом после удаления произвольного элемента [10].

Каждая подпоследовательность базиса Рисса является базисной последовательностью Рисса.

Если из фрейма удалить один элемент, то он либо остается фреймом, либо становится неполной системой.

Фрейм Рисса — это фрейм, каждая подпоследовательность которого является фреймовой последовательностью с теми же границами A и B, что и у самого фрейма. Каждый фрейм Рисса содержит базис Рисса [10].

Существуют ли фреймы {^ k } k= такие, что {^ Nk } k=i также образуют фрейм для каждого N G N ?

Для фрейма Габора вида

EmbTnag(x) := е2пгтЬхg(x - na), a,b > 0, g G L2(R), m,n G Z, необходимое условие ab С 1. Поэтому подпоследовательности вида {EmbTnNag}m,nez или {EmNbTnNag}m,nez не могут быть фреймами при достаточно больших N G N.

Вейвлет-фреймы

DajTkb^(x) := aj/2^(ajx — kb), a > 1, b > 0, ф G L2(R), существуют для произвольных a > 1, b > 0. Возможность построить фреймы вида {DaNj Tkb^}j,kez для произвольного N G N остается. Известные конструкции с изменением параметров a, b изменяют функцию ψ.

В [12] впервые были построены фреймы вида {T ^к ^ } к=о для ограниченного линейного оператора T на гильбертовом пространстве H . В построении использовано условие Карлесона: { Л к } С D := {z : | z | < 1 } С C :

inf п neN 11 k=n

| ^Л k — ^Лп |

| ^{1 — Л} k ^Л п |

> 0.

Теорема 7 [12] . Пусть { Л к } С D удовлетворяет условию Карлесона; {e k } — ОНБ в ГП H ; линейный оператор T : H ^ H определяется как Te k = Л к e k , к G N ; {m k } — числовая последовательность такая, что 0 < c i С | m k | С С 2 < ж; ^ : = £ь 1 m- k V¹ — | Л k| ² e k . Тогда {T ^k ^ }^ ₀ — фрейм для H.

Подпоследовательность фрейма Карлесона вида {T ^Nk } £=о образует фрейм для любого N G N [13].

С другой стороны, в отличие от базисов Рисса, в каждом фрейме существует подпоследовательность, которая не является фреймом.

Теорема 8 [13] . В каждом фрейме гильбертова пространства существует бесконечная последовательность, которая не является фреймом.

5.    Равномерные фреймы Парсеваля в бесконечномерном пространстве

Фрейм Парсеваля имеет границы, равные 1. В n -мерном пространстве границы фрейма и нормы элементов фрейма взаимосвязаны.

Фрейм {^ j } j =i называется равномерным, если существует c > 0 такое, что ||^j ||² = с, j = 1,... ,m.

Для равномерного фрейма Парсеваля имеем:

m n m.

n = trace(Icn) = trace(ФФ*) = trace(Ф*Ф) = ^ ||^j |2 = mc, j=1

Согласно следующей теореме, всякий нормированный фрейм Парсеваля является ор-тонормированным базисом.

Теорема 9. Пусть {e k } ^1 С H , ||ek|| = 1 для любого k. Тогда {e k } ^1 — ОНБ о 52 fc=i \( f, e k >\ 2 = Ilf 112, f ^ H • Таким образом, нормированный фрейм Парсеваля — это ортонормированный базис!

< ( ^ ) f = Е C k e k . Фиксируем j € N .

f^,e j > = (E c k e k ^,e j) = c j •

If I2 = < E«ek T.~kek)  ''■J    -

( ^ ) Последовательность { e k } k=i — бесселева, поэтому g := E(f, e k > e k хорошо определена. Если f ± e k для любого k, то f = 0, т. е. { e k } полная.

(f - g, ej> = ff - E^f, ek)ek, j = 0 (j если {ek} ОНС. В этом случае получаем равенство f = g. Докажем, что {ek} является ОНС.

• 1    = I e j II² = Е Ke j ,e k >\ ² = 1 + Е Ke j , e k Г

Таким образом, { e k} — ОНБ. >

Тем не менее в бесконечномерных гильбертовых пространствах существуют равномерные фреймы Парсеваля. Приведем пример.

Пример. Пусть a € (0, 2 ), ^(x) = ^81П( ПП ^Ха) € L ² ( R ).

Последовательность { ^(x — k) } ke Z образует равномерный фрейм Парсеваля в замыкании своей линейной оболочки [10].