Полнота - Overcompleteness

Чрезмерная полнота - это концепция из линейной алгебры, которая широко используется в математике, информатике, инженерии и статистике (обычно в форме избыточных фреймов ). Он был представлен RJ Duffin и AC Schaeffer в 1952 году.

Формально, подмножество векторов одного банахового пространства , иногда называют «системой», является полным , если каждый элемент может быть сколь угодно хорошо аппроксимировать в норме конечных линейных комбинациями элементов . Такая полная система считается переполненной, если удаление из системы приводит к тому, что система (т. Е. ) Все еще является завершенной. ${\ Displaystyle \ {\ phi _ {я} \} _ {я \ в J}}$ ${\ displaystyle X}$${\ displaystyle X}$${\ Displaystyle \ {\ phi _ {я} \} _ {я \ в J}}$ ${\ displaystyle \ phi _ {j}}$${\ Displaystyle \ {\ phi _ {я} \} _ {я \ in J \ обратная косая черта \ {j \}}}$

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

Связь между неполнотой и фреймами

Переполнение обычно обсуждается как свойство переполненных кадров. Теория репера берет начало в работе Даффина и Шеффера о негармонических рядах Фурье. Фрейм определяется как набор ненулевых векторов, таких что для произвольного , ${\ Displaystyle \ {\ phi _ {я} \} _ {я \ в J}}$${\ displaystyle f \ in {\ mathcal {H}}}$

${\ displaystyle A \ | f \ | ^ {2} \ leq \ sum _ {i \ in J} | \ langle f, \ phi _ {i} \ rangle | ^ {2} \ leq B \ | f \ | ^ {2}}$

где обозначает внутреннее произведение, а - положительные константы, называемые границами кадра. Когда и можно выбрать такое , что рама называется плотной рамой. ${\ Displaystyle \ langle \ cdot, \ cdot \ rangle}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A = B}$

Видно что . Пример кадра можно привести следующим образом. Пусть каждый из и является ортонормированным базисом , тогда ${\ displaystyle {\ mathcal {H}} = \ operatorname {span} \ {\ phi _ {i} \}}$${\ Displaystyle \ {\ альфа _ {я} \} _ {я = 1} ^ {\ infty}}$${\ Displaystyle \ {\ beta _ {я} \} _ {я = 1} ^ {\ infty}}$${\ displaystyle {\ mathcal {H}}}$

${\ displaystyle \ {\ phi _ {i} \} _ {i = 1} ^ {\ infty} = \ {\ alpha _ {i} \} _ {i = 1} ^ {\ infty} \ cup \ { \ beta _ {i} \} _ {i = 1} ^ {\ infty}}$

это рамка с границами . ${\ displaystyle {\ mathcal {H}}}$${\ Displaystyle А = В = 2}$

Позвольте быть кадровым оператором, ${\ displaystyle S}$

${\ Displaystyle Sf = \ сумма _ {я \ in J} \ langle f, \ phi _ {i} \ rangle \ phi _ {i}}$

Фрейм, который не является базисом Рисса , и в этом случае он состоит из набора функций больше, чем базис, называется переполненным. В этом случае он может иметь различную декомпозицию в зависимости от кадра. Кадр, приведенный в приведенном выше примере, является переполненным. ${\ displaystyle f \ in {\ mathcal {H}}}$

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

Учитывая терпимость и рамки в , для любой функции , определяет множество всех функций , аппроксимирующих , которые удовлетворяют условие${\ displaystyle \ epsilon}$${\ Displaystyle F = \ {\ phi _ {я} \} _ {я \ in J}}$${\ Displaystyle L ^ {2} (\ mathbb {R})}$${\ Displaystyle е \ в L ^ {2} (\ mathbb {R})}$${\ Displaystyle \ | е - {\ шляпа {f}} \ | <\ epsilon}$

${\ displaystyle N (f, \ epsilon) = \ {{\ hat {f}}: {\ hat {f}} = \ sum _ {i = 1} ^ {k} \ beta _ {i} \ phi _ {i}, \ | f - {\ hat {f}} \ | <\ epsilon \}}$

Тогда пусть

${\ displaystyle k_ {F} (f, \ epsilon) = \ inf \ {k: {\ hat {f}} \ in N (f, \ epsilon) \}}$

${\ Displaystyle к (е, \ эпсилон)}$указывает на экономию использования фрейма для приближения . Разные могут иметь разные в зависимости от твердости, которая должна быть приближена к элементам в раме. Наихудший случай оценки функции определяется как ${\ displaystyle F}$${\ displaystyle f}$${\ displaystyle f}$${\ displaystyle k}$${\ Displaystyle L ^ {2} (\ mathbb {R})}$

${\ Displaystyle к_ {F} (\ epsilon) = \ sup _ {е \ in L ^ {2} (\ mathbb {R})} \ {k_ {F} (f, \ epsilon) \}}$

Для другого кадра , если , то кадр лучше, чем кадр на уровне . И если есть то , что есть у нас , то это лучше, чем в целом. ${\ displaystyle G}$${\ Displaystyle к_ {F} (\ эпсилон) <к_ {G} (\ эпсилон)}$${\ displaystyle F}$${\ displaystyle G}$${\ displaystyle \ epsilon}$${\ displaystyle \ gamma}$${\ displaystyle \ epsilon <\ gamma}$${\ Displaystyle к_ {F} (\ эпсилон) <к_ {G} (\ эпсилон)}$${\ displaystyle F}$${\ displaystyle G}$

Полнокомплектные кадры обычно строятся тремя способами.

1. Комбинируйте набор базисов, таких как базис вейвлетов и базис Фурье, чтобы получить переполненный кадр.
2. Увеличьте диапазон параметров в каком-либо кадре, например, в кадре Габора и кадре вейвлета , чтобы получить переполненный кадр.
3. Добавьте некоторые другие функции к существующей полной основе, чтобы получить переполненный фрейм.

Пример переполненного кадра показан ниже. Собранные данные находятся в двухмерном пространстве, и в этом случае основа с двумя элементами должна быть в состоянии объяснить все данные. Однако, когда в данные включается шум, базис может быть не в состоянии выразить свойства данных. Если для выражения данных используется переполненный кадр с четырьмя элементами, соответствующими четырем осям на рисунке, каждая точка может иметь хорошее выражение в переполненном кадре.

• 

  Пример переполненного кадра

Гибкость переполненного кадра - одно из его ключевых преимуществ при использовании для выражения сигнала или аппроксимации функции. Однако из-за этой избыточности функция может иметь несколько выражений в переполненном кадре. Когда шкала конечна, разложение может быть выражено как

${\ displaystyle f = Ax}$

где - функция, которую нужно аппроксимировать, - матрица, содержащая все элементы в кадре, и - коэффициенты при представлении . Без каких-либо других ограничений рама выберет подачу с минимальной нормой в . Исходя из этого, при решении уравнения можно также учитывать некоторые другие свойства, такие как разреженность. Поэтому разные исследователи работали над решением этого уравнения, добавляя другие ограничения в целевую функцию. Например, при решении этого уравнения можно использовать ограничение минимизации нормы в . Это должно быть эквивалентно регрессии Лассо в статистическом сообществе. Байесовский подход также используется для устранения избыточности в переполненном кадре. Левицки и Сейновски предложили алгоритм для переполненного кадра, рассматривая его как вероятностную модель наблюдаемых данных. Недавно переполненный фрейм Габора был объединен с методом выбора байесовской переменной для достижения как малых коэффициентов расширения нормы, так и разреженности элементов. ${\ displaystyle f}$${\ displaystyle A}$${\ displaystyle x}$${\ displaystyle f}$${\ displaystyle A}$${\ displaystyle x}$${\ Displaystyle L ^ {2} (\ mathbb {R})}$${\ displaystyle x}$${\ Displaystyle L ^ {1} (\ mathbb {R})}$${\ Displaystyle L ^ {2} (\ mathbb {R})}$

Примеры переполненных кадров

В современном анализе в области обработки сигналов и других областях техники предлагаются и используются различные переполненные кадры. Здесь представлены и обсуждаются два часто используемых кадра, кадры Габора и кадры вейвлетов.

Рамки Gabor

При обычном преобразовании Фурье функция во временной области преобразуется в частотную область. Однако преобразование показывает только частотное свойство этой функции и теряет информацию во временной области. Если оконная функция , которая имеет ненулевое значение только в небольшом интервале, умножается на исходную функцию перед выполнением преобразования Фурье, информация как во временной, так и в частотной областях может оставаться в выбранном интервале. Когда в преобразовании используется последовательность преобразования, информация о функции во временной области сохраняется после преобразования. ${\ displaystyle g}$${\ displaystyle g}$

Пусть операторы

${\ Displaystyle T_ {a}: L ^ {2} (R) \ rightarrow L ^ {2} (R), (T_ {a} f) (x) = f (xa)}$

${\ Displaystyle E_ {b}: L ^ {2} (R) \ rightarrow L ^ {2} (R), (E_ {b} f) (x) = e ^ {2 \ pi ibx} f (x) }$

${\ displaystyle D_ {c}: L ^ {2} (R) \ rightarrow L ^ {2} (R), (D_ {c} f) (x) = {\ frac {1} {\ sqrt {c} }} f \ left ({\ frac {x} {c}} \ right)}$

Габор кадра ( по имени Дениса Габора , а также называют Вейль - Гейзенберга кадр) в определяются как форма , где и является фиксированной функцией. Впрочем, не для каждого и образует рамку . Например, когда , это не рамка для . Когда , может быть фрейм, и в этом случае это базис Рисса. Таким образом, возможна ситуация , когда кадр является переполненным . Семейство Gabor также является рамой и имеет те же границы рамки, что и${\ Displaystyle L ^ {2} (R)}$${\ displaystyle \ {E_ {mb} T_ {na} g \} _ {m, n \ in Z}}$${\ displaystyle a, b> 0}$${\ Displaystyle г \ в L ^ {2} (R)}$${\ displaystyle a}$${\ displaystyle b}$ ${\ displaystyle \ {E_ {mb} T_ {na} g \} _ {m, n \ in Z}}$${\ Displaystyle L ^ {2} (R)}$${\ displaystyle ab> 1}$${\ Displaystyle L ^ {2} (R)}$${\ displaystyle ab = 1}$${\ displaystyle \ {E_ {mb} T_ {na} g \} _ {m, n \ in Z}}$${\ displaystyle \ {E_ {mb} T_ {na} g \} _ {m, n \ in Z}}$${\ displaystyle ab <1}$${\ displaystyle \ {E_ {mb / c} T_ {nac} g_ {c} \} _ {m, n \ in Z}}$${\ displaystyle \ {E_ {mb} T_ {na} g \} _ {m, n \ in Z}.}$

В рамке Габора могут использоваться различные виды оконных функций . Здесь показаны примеры трех оконных функций, а условие для соответствующей системы Габора, являющейся фреймом, показано следующим образом. ${\ displaystyle g}$

• 

  Три оконные функции, используемые при генерации фреймов Gabor.

(1) , представляет собой раму , когда ${\ Displaystyle г (х) = е ^ {- х ^ {2}}}$${\ displaystyle \ {E_ {mb} T_ {na} g \} _ {m, n \ in Z}}$${\ displaystyle ab <0,994}$

(2) , представляет собой раму , когда ${\ displaystyle g (x) = {\ frac {1} {cosh (\ pi x)}}}$${\ displaystyle \ {E_ {mb} T_ {na} g \} _ {m, n \ in Z}}$${\ displaystyle ab <1}$

(3) , где - индикаторная функция. Ситуация для того, чтобы быть рамкой, выглядит следующим образом. ${\ displaystyle g (x) = I _ {[0, c)} (x)}$${\ Displaystyle I (х)}$${\ displaystyle \ {E_ {mb} T_ {na} g \} _ {m, n \ in Z}}$

1) или , а не фрейм ${\ displaystyle a> c}$${\ displaystyle a> 1}$

2) а , а не каркас ${\ displaystyle c> 1}$${\ displaystyle a = 1}$

3) , представляет собой каркас ${\ Displaystyle а \ leq с \ leq 1}$

4) и является иррациональным, а , является каркасом ${\ displaystyle a <1}$${\ Displaystyle с \ в (1,2)}$

5) , и являются относительно простыми числами , а не рамкой ${\ displaystyle a = {\ frac {p} {q}} <1}$${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle 2 - {\ frac {1} {q}} <c <2}$

6) и , где и - натуральное число, а не рамка ${\ displaystyle {\ frac {3} {4}} <а <1}$${\ Displaystyle с = L-1 + L (1-а)}$${\ displaystyle L \ geq 3}$

7) , , , где является самым большим целое число , не превышающее , является кадром. ${\ displaystyle a <1}$${\ displaystyle c> 1}$${\ displaystyle | c- [c] - {\ frac {1} {2}} | <{\ frac {1} {2}} - a}$${\ displaystyle [c]}$${\ displaystyle c}$

Вышеупомянутое обсуждение является кратким изложением главы 8 в.

Кадры вейвлета

Набор вейвлетов обычно относится к набору функций, основанных на ${\ displaystyle \ psi}$

${\ displaystyle \ {2 ^ {\ frac {j} {2}} \ psi (2 ^ {j} xk) \} _ {j, k \ in Z}}$

Это составляет ортонормированную основу для . Однако, когда может принимать значения , набор представляет собой переполненный кадр и называется базисом недесиммированного вейвлета. В общем случае фрейм вейвлета определяется как фрейм для вида ${\ Displaystyle L ^ {2} (R)}$${\ displaystyle j, k}$${\ displaystyle R}$${\ Displaystyle L ^ {2} (R)}$

${\ displaystyle \ {a ^ {\ frac {j} {2}} \ psi (a ^ {j} x-kb) \} _ {j, k \ in Z}}$

где , , и . Верхнюю и нижнюю границы этого кадра можно вычислить следующим образом. Пусть - преобразование Фурье для${\ displaystyle a> 1}$${\ displaystyle b> 0}$${\ displaystyle \ psi \ in L ^ {2} (R)}$${\ Displaystyle {\ шляпа {\ psi}} (\ gamma)}$${\ Displaystyle \ psi \ в L ^ {1} (R)}$

${\ Displaystyle {\ шляпа {\ psi}} (\ gamma) = \ int _ {R} \ psi (x) e ^ {- 2 \ pi ix \ gamma} dx}$

Когда зафиксированы, определите ${\ displaystyle a, b}$

${\ displaystyle G_ {0} (\ gamma) = \ sum _ {j \ in Z} | {\ hat {\ psi}} (a ^ {j} \ gamma) | ^ {2}}$

${\ displaystyle G_ {1} (\ gamma) = \ sum _ {k \ neq 0} \ sum _ {j \ in Z} | {\ hat {\ psi}} (a ^ {j} \ gamma) {\ шляпа {\ psi}} (a ^ {j} \ gamma + {\ frac {k} {b}}) |}$

потом

${\ displaystyle B = {\ frac {1} {b}} \ sup _ {| \ gamma | \ in [1, a]} (G_ {0} (\ gamma) + G_ {1} (\ gamma)) <\ infty}$

${\ displaystyle A = {\ frac {1} {b}} \ inf _ {| \ gamma | \ in [1, a]} (G_ {0} (\ gamma) -G_ {1} (\ gamma)) > 0}$

Кроме того, когда

${\ displaystyle \ sum _ {j \ in Z} | {\ hat {\ psi}} (2 ^ {j} \ gamma) | ^ {2} = A}$

${\ displaystyle \ sum _ {j = 0} ^ {\ infty} {\ hat {\ psi}} (2 ^ {j} \ gamma) {\ overline {{\ hat {\ psi}} (2 ^ {j } (\ gamma + q))}} = 0}$, для всех нечетных целых чисел ${\ displaystyle q}$

сгенерированный фрейм представляет собой плотный фрейм. ${\ displaystyle \ {\ psi _ {j, k} \} _ {j, k \ in Z}}$

Обсуждение в этом разделе основано на главе 11 в.

Приложения

Сверхполные кадры Габора и кадры вейвлета использовались в различных областях исследований, включая обнаружение сигналов, представление изображений, распознавание объектов, уменьшение шума , теорию выборки, теорию операторов , гармонический анализ , нелинейное разреженное приближение, псевдодифференциальные операторы , беспроводную связь, геофизику, квантовые вычисления, и банки фильтров .

использованная литература