close

Вход

Забыли?

вход по аккаунту

?

О жестких фреймах специального вида.

код для вставкиСкачать
УДК 512.643
Вестник СПбГУ. Сер. 1, 2009, вып. 3
О ЖЕСТКИХ ФРЕЙМАХ СПЕЦИАЛЬНОГО ВИДА∗
Н. А. Соловьева
С.-Петербургский государственный университет,
аспирантка, vinyo@mail.ru
В линейном комплексном пространстве Cn наряду с базисами существуют фреймы — избыточные системы векторов, по которым стандартным образом можно разложить любой вектор из Cn . В обзорных статьях [1, 2] приведены основные понятия и
результаты теории фреймов вместе с приложениями к вопросам обработки и передачи
информации.
Нас интересуют жесткие фреймы, в определенном смысле близкие к ортогональным базисам. Ранее были исследованы различные классы жестких фреймов: гармонические и обобщенные гармонические фреймы, фреймы Мерседес-Бенц, равноугольные
жесткие фреймы и т. д. Мы рассматриваем системы векторов специального вида, в которых каждый вектор получается из предыдущего умножением на унитарную матрицу.
В теореме 1 установлено, когда такие системы образуют жесткие фреймы. В теореме 2
выяснена связь между рассматриваемыми фреймами и обобщенными гармоническими
фреймами. В частности, показано, как преобразовать фрейм Мерседес-Бенц в обобщенный гармонический фрейм.
1. Пусть U — унитарная матрица порядка n с собственными числами λ1 , . . . , λn , по
модулю равными единице, и соответствующими ортонормированными собственными
векторами p1 , . . . , pn . Возьмем единичный вектор ϕ0 ∈ Cn и построим при m ≥ n
систему векторов
ϕ0 , U ϕ0 , U 2 ϕ0 , . . . , U m−1 ϕ0 .
(1)
Когда система (1) будет жестким фреймом?
Теорема 1. Для того чтобы система (1) была жестким фреймом, необходимо и
достаточно, чтобы выполнялись два условия:
(i) собственные числа λ1 , . . . , λn матрицы U суть попарно различные корни степени
m из некоторого числа c ∈ C, |c| = 1;
(ii) |hϕ0 , pk i| =
√1
n
при всех k ∈ 1 : n.
2. Напомним [1], что система ненулевых векторов {ϕ0 , ϕ1 , . . . , ϕm−1 } из Cn при m ≥
n называется жестким фреймом с константой фрейма A, если выполнено одно из трех
эквивалентных условий:
x=
m−1
1 X
hx, ϕk iϕk
A
k=0
m−1
X
k=0
∗ Работа
c
hx, ϕk i2 = A x2
при всех x ∈ Cn ;
(2)
при всех x ∈ Cn ;
выполнена под руководством проф. В. Н. Малоземова.
Н. А. Соловьева, 2009
79
Φ Φ∗ = A In ,
где Φ — матрица со столбцами ϕ0 , ϕ1 , . . . , ϕm−1 и In — единичная матрица порядка n.
Если kϕk k = 1 при всех k ∈ 0 : m − 1, то константа фрейма A необходимо равна
m/n.
3. При доказательстве теоремы 1 важную роль будет играть приводимая ниже лемма.
Лемма 1. Если система (1) образует жесткий фрейм, то найдется число c ∈ C,
|c| = 1, такое, что
U m = cIn .
Этот результат установлен в [3]. Мы дадим упрощенное его доказательство.
Обозначим ϕk = U k ϕ0 . При всех k ∈ 0 : m − 1 векторы ϕk имеют единичную длину.
Разложим векторы ϕm−1 и U ϕm−1 по фрейму (1). Согласно (2)
m−2
n X
ϕm−1 =
hϕm−1 , ϕk iϕk + ϕm−1 ,
m
k=0
m−1
X
n
∗
U ϕm−1 =
hU ϕm−1 , ϕ0 iϕ0 +
hϕm−1 , U ϕk iϕk .
m
(3)
k=1
∗
∗
Приняв во внимание, что U ϕk = U U ϕk−1 = ϕk−1 при k ∈ 1 : m − 1, перепишем
последнее равенство в виде
!
m−1
X
n
∗
U ϕm−1 =
hU ϕm−1 , ϕ0 i U U ϕ0 +
hϕm−1 , ϕk−1 i U ϕk−1 =
m
k=1
!
m−1
X
n
∗
=
hϕm−1 , ϕk−1 iϕk−1 .
U hU ϕm−1 , ϕ0 i U ϕ0 +
m
k=1
Отсюда следует, что
ϕm−1
n
=
m
∗
hU ϕm−1 , ϕ0 i U ϕ0 +
m−2
X
k=0
hϕm−1 , ϕk iϕk
!
.
(4)
Вычтем (4) из (3). После сокращения на общий множитель получим
ϕm−1 = hU ϕm−1 , ϕ0 i U ∗ ϕ0
и
U m ϕ0 = hU ϕm−1 , ϕ0 iϕ0 .
(5)
U m ϕ0 = c ϕ0 .
(6)
Обозначим c = hU ϕm−1 , ϕ0 i = hU m ϕ0 , ϕ0 i. Тогда формула (5) примет вид
Равенство норм kcϕ0 k = kU m ϕ0 k = kϕ0 k гарантирует, что |c| = 1.
80
Далее, согласно (6)
Значит,
U m ϕk = U m U k ϕ0 = U k U m ϕ0 = c ϕk .
U m − c In ϕk = O при k ∈ 0 : m − 1.
В силу (2) линейная оболочка элементов жесткого фрейма совпадает с Cn , поэтому
равенство (U m − c In ) x = O выполняется для всех x ∈ Cn . Взяв в качестве x последовательно все единичные орты, придем к требуемой формуле U m = cIn . Лемма доказана.
4. Запишем спектральное разложение матрицы U :
U = P Λ P ∗,
где P — унитарная матрица со столбцами p1 , . . . , pn и Λ — диагональная матрица, Λ =
diag(λ1 , . . . , λn ). Имеем
ϕk = U k ϕ0 = P Λk P ∗ ϕ0 .
√
√
Обозначим g0 = n P ∗ ϕ0 ; gk = n P ∗ ϕk = Λk g0 , k ∈ 1 : m − 1. По определению
√
g0 (j) = n hϕ0 , pj i =: bj , j ∈ 1 : n ;
gk (j) = bj λkj ,
j ∈ 1 : n, k ∈ 1 : m−1.
(7)
Последнее равенство справедливо и при k = 0.
Приходим к такому результату.
Лемма 2. Векторы ϕk = U k ϕ0 допускают представление
ϕk =
√1
n
P gk ,
k ∈ 0 : m−1,
(8)
где gk определяются формулой (7).
5. Обратимся к доказательству теоремы 1.
Необходимость. Пусть система (1) образует жесткий фрейм. Согласно (8) и (7)
1
1
hϕk , pj i = √ hP gk , pj i = √ hgk , P ∗ pj i =
n
n
1
1
= √ gk (j) = √ bj λkj ,
n
n
√
поэтому |hϕk , pj i| = 1/ n |bj |, j ∈ 1 : n. По определению жесткого фрейма
m−1
2
2 2
n X 1 = pj =
hpj , ϕk i = bj ,
m
k=0
j ∈ 1 : n.
(9)
Вспоминая определение bj , заключаем, что выполняется условие (ii).
Далее, из леммы 1 и спектрального разложения матрицы U следует, что λm
j = c при
всех j ∈ 1 : n, то есть λj действительно являются корнями степени m из комплексного
числа c, по модулю равного единице. Покажем, что эти корни попарно различны.
Обозначим через Φ и G матрицы√со столбцами ϕ0 , ϕ1 , . . . , ϕm−1 и g0 , g1 , . . . , gm−1
соответственно. Согласно (8), Φ = 1/ n P G. По определению жесткого фрейма, состоящего из единичных векторов, Φ Φ∗ = m/nIn . Значит,
GG∗ = n P ∗ Φ Φ∗ P = m In .
81
В частности, (GG∗ )[j, s] = 0 при j 6= s. Вместе с тем, согласно (7)
m−1
m−1
X
X
k
GG∗ [j, s] =
gk (j) gk (s) = bj bs
λj λs .
k=0
(10)
k=0
Учитывая (9), при j 6= s получаем
m−1
X
λj λs
k=0
k
= 0.
Это равенство гарантирует, что λj 6= λs при j 6= s.
Видим, что условие (i) также выполнено.
√
Достаточность. Покажем, что Φ Φ∗ = m/n In . Как отмечалось, Φ = 1/ n P G,
поэтому
1
Φ Φ∗ = P GG∗ P ∗ .
n
Остается проверить, что√GG∗ = mIn .
Напомним, что bj = nhϕ0 , pj i. В силу условия (ii) имеем |bj | = 1 при всех j ∈ 1 : n.
Теперь воспользуемся формулой (10). При j = s получаем (GG∗ )[j, j] = m. При j 6= s
согласно условию (i) числа λj и λs суть различные корни степени m из комлексного
числа c, по модулю равного единице. В частности, λj λs = λj λ−1
s 6= 1 и
m−1
X
λj λs
k=0
k
=
1 − (λj λs )m
= 0.
1 − λj λs
Отсюда и из (10) следует, что (GG∗ )[j, s] = 0 при j 6= s.
Теорема доказана.
6. Приведем три примера. Будем использовать стандартное обозначение ωm =
exp(2πi/m).
Пример 1 [фрейм Мерседес-Бенц]. Рассмотрим три единичных вектора
√3 1 T
√3 1 T
T
,−
,−
ϕ0 = 0, 1 , ϕ1 = −
, ϕ1 =
.
2
2
2
2
Нетрудно проверить, что ϕ1 = U ϕ0 , ϕ2 = U ϕ1 , где
√ 

1
3
−
−
2 
U =  √2
.
3
1
−
2
2
Матрица U — унитарная с собственными числами
√
√
1
3
1
3
λ1 = − + i
= ω3 , λ2 = − − i
= ω32
2
2
2
2
и собственными векторами
1
p1 = √
2
82
1
,
−i
1
p2 = √
2
1
.
i
Оба условия теоремы 1 выполнены (при c = 1), поэтому система {ϕ0 , ϕ1 , ϕ2 } является
жестким фреймом.
Конечно, этот факт хорошо известен [1] и может быть получен проще, исходя из
условия Φ Φ∗ = 3/2 I2 , где
√
√ 

3
3
0
−


2
2
Φ=
.
1
1
1 −
−
2
2
Однако пример 1 хорошо демонстрирует содержание теоремы 1.
Фрейм {ϕ0 , ϕ1 , ϕ2 } называется фреймом Мерседес-Бенц.
Пример 2 [нарушено условие (ii)]. Пусть n = 2, m = 3. Рассмотрим унитарную
матрицу U второго порядка с собственными числами λ1 = 1, λ2 = ω3 и ортонормированными собственными векторами
1
0
p1 =
,
p2 =
.
(11)
0
1
В этом случае
U=
1 0
.
0 ω3
Возьмем начальный вектор ϕ0 = (1, 0)T .
hϕ0 , p1 i = 1 ,
то есть условие (ii) нарушено. Далее,
1
ϕ1 = U ϕ0 =
,
0
Для него
hϕ0 , p2 i = 0 ,
1
ϕ2 = U ϕ1 =
.
0
Векторы ϕ0 = ϕ1 = ϕ2 = ( 10 ) не образуют жесткого фрейма.
Пример 3 [нарушено условие (i)]. Рассмотрим унитарную матрицу U второго порядка с собственными числами λ1 = 1, λ2 = i и ортонормированными собственными
векторами (11). В этом случае
1 0
U=
.
0 i
Возьмем начальный вектор ϕ0 =
√1
2
( 11 ). Для него
hϕ0 , p1 i = hϕ0 , p2 i = √1 ,
2
то есть условие (ii) выполнено. Найдем векторы ϕ1 и ϕ2 :
1 1
1
1
ϕ1 = √
,
ϕ2 = √
.
i
−1
2
2
У матрицы
1 1
Φ= √
2 1
1 1
i −1
строки не ортогональны. Значит, система {ϕ0 , ϕ1 , ϕ2 } не является жестким фреймом.
83
Причина в том, что нарушено условие (i), поскольку λ31 6= √
λ32 .
1
Если к системе {ϕ0 , ϕ1 , ϕ2 } добавить вектор ϕ3 = U ϕ2 = 1/ 2 −i
, то расширенная
система {ϕ0 , ϕ1 , ϕ2 , ϕ3 }, как легко проверить, будет жестким фреймом. Это соответствует теореме 1.
7. Покажем, что систему (1) можно преобразовать в обобщенный гармонический
фрейм. Возьмем комплексное число c, |c| = 1, и обозначим через c1 , . . . , cn попарно
различные корни степени m из c. Возьмем также n комплексных чисел b1 , . . . , bn , по
модулю равных единице. Напомним, что система {ψ0 , ψ1 , . . . , ψm−1 }, состоящая из единичных векторов с компонентами
ψk (j) =
√1
n
bj ckj ,
j ∈ 1 : n,
называется обобщенным гармоническим фреймом [3]. При c = 1 и b1 = · · · = bn = 1
получаем гармонический фрейм.
Нетрудно проверить, что обобщенный гармонический фрейм является жестким
фреймом. Действительно, обозначим через Ψ матрицу со столбцами ψ0 , ψ1 , . . . , ψm−1
и покажем, что Ψ Ψ ∗ = m/n In . Имеем
m−1
X
Ψ Ψ ∗ [j, s] =
ψk (j) ψk (s) =
k=0
1
n
bj bs
m−1
X
cj cs
k=0
k
.
В частности, (Ψ Ψ ∗ )[j, j] = m/n при всех j ∈ 1 : n. При j 6= s будет cj cs = cj c−1
s 6= 1,
поэтому
1 − (cj cs )m
1
Ψ Ψ ∗ [j, s] = bj bs
= 0.
n
1 − cj cs
Вернемся к последовательности (1). Наряду с векторами ϕk = U k ϕ0 рассмотрим
единичные векторы
ηk = P ∗ ϕk ,
k ∈ 0 : m−1,
(12)
где P — унитарная матрица, столбцами которой являются ортонормированные собственные векторы p1 , . . . , pn матрицы U .
Теорема 2. Для того чтобы система {η0 , η1 , . . . , ηm−1 } была обобщенным гармоническим фреймом, необходимо и достаточно, чтобы выполнялись условия (i) и (ii)
из теоремы 1.
Доказательство. Обозначим через H матрицу со столбцами η0 , η1 , . . . , ηm−1 . Согласно (12), H = P ∗ Φ. Система {η0 , η1 , . . . , ηm−1 } как обобщенный гармонический
фрейм является жестким фреймом. В этом случае HH ∗ = m/nIn . Отсюда следует,
что
m
Φ Φ∗ = P HH ∗ P ∗ =
In ,
n
то есть система (1) также является жестким фреймом. Остается сослаться на теорему 1.
Достаточность. Согласно (12), (8) и (7)
1
1
ηk (j) = √ gk (j) = √ bj λkj ,
n
n
j ∈ 1 : n, k ∈ 0 : m−1,
причем условие (i) гарантирует, что λ1 , . . . , λn — попарно различные корни степени m
из некоторого числа c ∈ C, |c| = 1. Далее, ϕ0 = P η0 , поэтому
1
hϕ0 , pj i = hη0 , P ∗ pj i = η0 (j) = √ bj .
n
84
В силу условия (ii) получаем |bj | = 1 при всех j ∈ 1 : n. Значит, система {η0 , η1 ,
. . . , ηm−1 } — обобщенный гармонический фрейм.
Теорема доказана.
8. Покажем, как фрейм Мерседес-Бенц из примера 1 преобразовать в обобщенный
гармонический фрейм. Имеем
1
1 1 i
1 1
P = √
,
P∗ = √
,
2 −i i
2 1 −i
1
i
∗
η0 = P ϕ0 = √
,
−i
2
 √

3 1
1 − 2 − 2i
1
i ω3
η1 = P ∗ ϕ1 = √  √
= √
2 ,
3 1
2
2 −i ω3
−
+ i
2
2
√

3 1
1  2 − 2 i
1
i ω32
∗
√
η2 = P ϕ2 = √ 
= √
4 .
3 1
2
2 −i ω3
+ i
2
2
Система {η0 , η1 , η2 } образует обобщенный гармонический фрейм с b1 = i, b2 = −i,
λ1 = ω3 , λ2 = ω32 .
Литература
1. Kovačević J., Chebira A. Life beyond bases: The advent of frames (Part ) // IEEE Signal
Processing Magazine. 2007. Vol. 24. N 4. P. 86–104.
2. Kovačević J., Chebira A. Life beyond bases: The advent of frames (Part ) // IEEE Signal
Processing Magazine. 2007. Vol. 24. N 5. P. 115–125.
3. Casazza P. G., Kovačević J. Uniform Tight Frames with Erasures // Adv. Comp. Math. 2003.
Vol. 18. N 2–4. P. 387–430.
Статья поступила в редакцию 12 марта 2009 г.
85
Документ
Категория
Без категории
Просмотров
5
Размер файла
232 Кб
Теги
фрейман, вида, специальное, жесткий
1/--страниц
Пожаловаться на содержимое документа