# Preconditioning Filter Bank Decomposition Using Structured Normalized Tight Frames

Authors: Martin Ehler
Journal: Journal of Applied Mathematics
 (2015)

---

## Abstract

We turn a given filter bank into a filtering scheme that provides perfect reconstruction, synthesis is the adjoint of the analysis part (so-called unitary filter banks), all filters have equal norm, and the essential features of the original filter bank are preserved. Unitary filter banks providing perfect reconstruction are induced by tight generalized frames, which enable signal decomposition using a set of linear operators. If, in addition, frame elements have equal norm, then the signal energy is spread through the various filter bank channels in some uniform fashion, which is often more suitable for further signal processing. We start with a given generalized frame whose elements allow for fast matrix vector multiplication, as, for instance, convolution operators, and compute a normalized tight frame, for which signal analysis and synthesis still preserve those fast algorithmic schemes.


---

## Body

## 1. Introduction

Increasingly detailed data are acquired in all sorts of measurements nowadays, so that fast algorithms are an important factor for successful signal processing. The concept of generalized frames has a long tradition in signal processing and many unitary filter bank schemes with the perfect reconstruction property are induced by tight generalized frames. Frames themselves are basis-like systems that span a vector space but allow for linear dependency. The inherent redundancy of frames can yield advantageous features unavailable within the basis concept [1–4]. If the frame istight and its elements haveunit norm, then it resembles the concept of an orthonormal basis, with the add-on of useful redundancy, and frame coefficients measure the signal energy in a uniform fashion. Generalized frames were introduced in [5] as a tool for signal decomposition using a set of linear operators. In [6], collections of orthogonal projectors were considered under the name fusion frames, fusion frame filter banks have been considered in [7], and the concept of tight p-fusion frames was developed in [8]. As convolution operators are linear, most filter banks can be thought of as pairs of generalized frames, one for analysis and the other for synthesis. Hence, in view of filter banks, it is not sufficient to deal with frames but we must inevitably consider their generalized counterpart. Tightness of a generalized frame means that the induced unitary filter bank provides perfect reconstruction. As with frames, we seek unit norm tight generalized frames because signal energy is then spread through the various channels in a more uniform fashion. The latter was used in [9] to verify robustness of tight fusion frames against erasures, meaning that it is beneficial to have tight fusion frames with equal norm when dealing with distortions and loss of data. To keep the filter bank perspective, we will focus on generalized frames consisting of convolution operators enabling fast algorithms.In the present paper we start with a generalized frame, whose elements allow for fast matrix vector multiplications (e.g., convolution operators) and construct a unit norm tight generalized frame that induces a filter bank scheme preserving those fast algorithms. The latter is related to the so-called Paulsen problem for frames, where one is given a unit norm frame and one asks for the closest tight frame with unit norm and for an algorithm to find it. This problem for frames has been partially solved in [10–12]. Note that if we are given a unit norm generalized frame, whose elements allow for fast matrix vector multiplications, then the closest tight generalized frame with unit norm may not provide such fast algorithmic schemes in general. Here, we aim to find a related tight unit norm generalized frame in such a way that signal analysis and synthesis can still benefit from the underlying fast matrix vector multiplications.We should point out that we used the term filter bank beyond sets of convolution operators similar to [7], where weighted orthogonal projectors are considered. Nonetheless, if the starting generalized frame consists of convolution operators, then the resulting scheme still represents convolution operators in each channel, but we require one additional linear operator for global pre- and postmultiplication. As this operator has a special structure being the inverse of a convolution frame operator, there are still fast computation schemes available [13].Our construction is inspired by pseudocovariance estimators of elliptical distributions in [14]; see also [15, 16]. We derive an iterative algorithm on positive definite matrices, for which we prove convergence, so that we obtain a positive definite matrix Γ that enables us to construct the tight unit norm generalized frame.For related research topics, such as the optimal rescaling of filter banks, we refer to [17, 18]. Preconditioning in the context of Gabor frames is addressed in [19]. In order to assess the benefits of our approach in image analysis, we suggest the use of the structural similarity proposed in [20].The outline is as follows: In Section2, we introduce the concept of generalized frames and motivate the construction of unit norm tight generalized frames. In Section 3, we present our iterative algorithm, for which we verify convergence, enabling us to construct tight generalized frames with unit norm that preserve fast analysis and synthesis due to their special structure. In Section 4 we provide few examples of random matrices whose samples satisfy the convergence assumptions needed. We also point out examples for convolution operators and further operators enabling fast matrix vector multiplications. In Section 5, we discuss the structure of our construction when the underlying generalized frame is a sample from an elliptical distribution. Some concluding remarks are contained in Section 6.


## 2. Generalized Frames

LetK denote either R or C. We follow [5] and call a collection {
T
j
}
j
=
1
n
⊂
K
d
×
r ageneralized frame (or a g-frame for short) if there are two constants 0
<
A
≤
B
<
∞ such that(1)
A
x
2
≤
∑
j
=
1
N
T
j
∗
x
2
≤
B
x
2
,
∀
x
∈
K
d
.If the constants can be chosen 0
<
A
=
B, then {
T
j
}
j
=
1
n is called atight
g
-frame and it is called aParseval
g-frame if 0
<
A
=
B
=
1. For r
=
1, we have T
j
∗
x
=
〈
T
j
,
x
〉, so that we recover the concept of frames (cf. [1]). It turns out that a collection {
T
j
}
j
=
1
n
⊂
K
d
×
r is a g-frame if and only if ⋃
j
=
1
n
‍
r
a
n
g
e
(
T
j
) spans K
d.If{
T
j
}
j
=
1
n is a g-frame, then theanalysis operator
F
:
K
d
→
K
n
×
r is given by x
↦
(
x
∗
T
j
)
j
=
1
n. Its adjoint is thesynthesis operator
F
∗
:
K
n
×
r
→
K
d, defined by (
c
j
)
j
=
1
n
↦
∑
j
=
1
n
‍
T
j
c
j
∗, such that the generalized frame operator is (2)
S
=
F
∗
F
:
K
d
⟶
K
d
,
x
⟼
∑
j
=
1
n
T
j
T
j
∗
x
.The collection {
S
-
1
T
j
}
j
=
1
n is called thecanonical dual
g
-frame and yields the expansion (3)
x
=
∑
j
=
1
n
T
j
S
-
1
T
j
∗
x
=
∑
j
=
1
n
S
-
1
T
j
T
j
∗
x
,
∀
x
∈
K
d
,which simply follows from S
S
-
1
=
S
-
1
S
=
I
d, where I
d denotes the d
×
d identity matrix.Proposition 1.
If{
T
j
}
j
=
1
∞
⊂
K
d
×
r is a g-frame with g-frame operator S, then {
S
-
1
/
2
T
j
}
j
=
1
n is a Parseval g-frame and, for any other Parseval g-frame {
R
j
}
j
=
1
∞
⊂
K
d
×
r, one has(4)
∑
j
=
1
n
T
j
-
S
-
1
/
2
T
j
H
S
2
≤
∑
j
=
1
n
T
j
-
R
j
H
S
2
.Equality holds if and only if R
j
=
S
-
1
/
2
T
j, for j
=
1
,
…
,
n.Here,·
H
S denotes the Hilbert-Schmidt (Frobenius) norm. Most parts of the proof of Proposition 1 can follow the lines in [21], where r
=
1 is considered, so we omit the proof.Remark 2.
We have supposed that the linear operators of ag-frame have all the same dimensions, which simplifies notation but is not necessary. The entire paper could also deal with sets of linear operators {
T
j
}
j
=
1
n, where T
j
∈
K
d
×
r
j, for j
=
1
,
…
,
n. Then T
j
T
j
∗
∈
K
d
×
d and this is all we need.Tight frames are desirable because synthesis is simply the adjoint of the analysis part. For signal processing purposes, we are interested in tightg-frames that additionally have unit norm, because those more resemble orthonormal bases, and {
T
j
∗
x
}
j
=
1
n then has more information about the signal energy in the direction of a particular frame element; see [22] for r
=
1.Given someg-frame, say with unit norm elements, let us seek a tight g-frame with equal norm elements that is nearby. If we give up the equal norm requirement and S is the frame operator of some g-frame {
T
j
}
j
=
1
n, then the collection {
S
-
1
/
2
T
j
}
j
=
1
n is a Parseval frame closest to {
T
j
}
j
=
1
n; see Proposition 1. In general, however, {
S
-
1
/
2
T
j
}
j
=
1
n may not have equal norms. The search for the closest Parseval frame with equal norm elements has become known as the Paulsen problem. It is essentially the same problem if we restrict ourselves to the sphere; that is, given a unit norm g-frame, we aim for the closest unit norm tight g-frame. For r
=
1, this problem was partially solved in [10–12].Suppose now that we are given ag-frame {
T
j
}
j
=
1
n that allows for fast matrix vector multiplications for each T
j and T
j
∗. The closest equal norm Parseval g-frame may not preserve such features. From a computational point of view, it would be preferable to find an equal norm Parseval g-frame that still allows for fast analysis and synthesis schemes, and this is indeed our topic in the subsequent sections.


## 3. Constructing Unit Norm Tightg-Frames That Preserve Fast Algorithms

Theg-frame operator S of some g-frame {
T
j
}
j
=
1
n and hence also S
-
1 are positive definite and Proposition 1 yields the tight g-frame {
S
-
1
/
2
T
j
}
j
=
1
n that may not have unit norm, and {
S
-
1
/
2
T
j
/
S
-
1
/
2
T
j
H
S
}
j
=
1
n has unit norm but may not be tight. To construct a unit norm tight g-frame that preserves fast matrix vector multiplications, we get inspired by Proposition 1 and aim to find a positive definite matrix Γ such that(5)
Γ
1
/
2
T
j
Γ
1
/
2
T
j
H
S
j
=
1
nis a unit norm tight g-frame. As opposed to Proposition 1, we replace S
-
1 with Γ and normalize. The unit norm g-frame (5) is tight if and only if(6)
I
d
=
Γ
1
/
2
d
n
∑
j
=
1
n
T
j
T
j
∗
Γ
1
/
2
T
j
H
S
2
Γ
1
/
2
.Signal analysis and synthesis requires pre- and postmultiplication by Γ
1
/
2 but in-between we can use n times the fast algorithms provided by T
j
∗ and T
j (cf. Figure 1). Now, T
j
∗
Γ
1
/
2
/
Γ
1
/
2
T
j
H
S has unit norm, so that the signal energy better relates to the magnitudes of {
T
j
∗
Γ
1
/
2
x
/
Γ
1
/
2
T
j
H
S
}
j
=
1
n. Thus, the special structure (5) can be advantageous over other unit norm tight g-frames that can be closer to the original one.Figure 1
Analysis and synthesis scheme, in which fast matrix vector multiplication ofT
j
∗ and T
j can still be used after and before pre- and postmultiplication by Γ
1
/
2, respectively.Remark 3.
The filtering scheme in Figure1 can preserve many properties of the original g-frame {
T
j
}
j
=
1
n, which can go beyond fast matrix vector multiplications, such as being orthogonal projectors and sparse matrices, as long as the application of Γ
1
/
2 is implemented separately and we do not use Γ
1
/
2
T
j directly.Remark 4.
We point out that structure (5) is different from the approach in [23], where rescalings are sought to derive tight frames. The authors in [24] discuss the setting when a linear operator exists that maps a frame into a unit norm tight frame. We are more general here, because we are joining both and we apply a linear operator and allow for rescaling.Note that (6) is equivalent to(7)
Γ
=
d
n
∑
j
=
1
n
T
j
T
j
∗
trace
T
j
∗
Γ
T
j
-
1
.Thus, Γ is the inverse of the generalized frame operator of {
d
/
n
Γ
1
/
2
T
j
H
S
2
T
j
}
j
=
1
n. Since this equation is invariant under scalings, we can look for a solution Γ with t
r
a
c
e
(
Γ
)
=
1. Let P be the collection of hermitian positive definite matrices in K
d
×
d and denote by P
1 the same space with the additional requirement that the trace is 1. The fixed point equation (7) gives rise to an iterative scheme that was already considered in [14, 15] for r
=
1 to estimate the covariance of elliptical distributions. As initialization we choose Γ
0
:
=
(
1
/
d
)
I
d
∈
P
1 and define(8)
Γ
k
+
1
≔
d
/
n
∑
j
=
1
n
T
j
T
j
∗
/
trace
T
j
∗
Γ
k
T
j
-
1
trace
d
/
n
∑
j
=
1
n
T
j
T
j
∗
/
trace
T
j
∗
Γ
k
T
j
-
1
.Note that Γ
1
=
S
-
1
/
t
r
a
c
e
(
S
-
1
), and, to verify convergence, we will follow the ideas of the technical procedure used in [14, 15] for r
=
1. For analysis purposes, we will introduce the mapping(9)
M
:
P
⟶
P
,
M
Γ
≔
d
n
∑
j
=
1
n
Γ
1
/
2
T
j
T
j
∗
Γ
1
/
2
trace
T
j
∗
Γ
T
j
,
M
k
≔
M
Γ
k
,so that(10)
Γ
k
+
1
=
Γ
k
1
/
2
M
k
-
1
Γ
k
1
/
2
trace
Γ
k
M
k
-
1
,
Γ
0
≔
1
d
I
d
.We will first check that the mapping M is injective up to scalings, which generalizes [14, Theorem 2.1] from r
=
1 to the general case.Lemma 5.
Let{
T
j
}
j
=
1
n
⊂
K
d
×
r be a g-frame and let Γ
a
,
Γ
b
∈
K
d be positive definite. Then M
(
Γ
a
)
=
M
(
Γ
b
) if and only if there is a positive constant c
>
0 such that Γ
a
=
c
Γ
b.Proof.
Without loss of generality, we can assume thatΓ
b
=
I
d. Otherwise, replace {
T
j
}
j
=
1
n with {
Γ
b
-
1
/
2
T
j
}
j
=
1
n. Let γ
1 be the largest eigenvalue of Γ
a and let P
1 be the associated eigenprojector. Moreover, let {
P
i
}
i
=
2
s be one-dimensional eigenprojectors of Γ
a associated with eigenvalues {
γ
i
}
i
=
2
s such that γ
1
>
γ
i, for i
=
2
,
…
,
s, and ∑
i
=
1
s
‍
γ
i
P
i
=
Γ
a. Note that γ
2
,
…
,
γ
s do not need to be pairwise distinct. Since Γ
a
1
/
2
P
1
Γ
a
1
/
2
=
γ
1
P
1 and ∑
i
=
1
s
‍
P
i
=
I
d, we obtain (11)
trace
P
1
M
Γ
a
=
d
n
∑
j
=
1
n
trace
P
1
Γ
a
1
/
2
T
j
T
j
∗
Γ
a
1
/
2
trace
T
j
∗
Γ
a
T
j
=
γ
1
d
n
∑
j
=
1
n
trace
T
j
∗
P
1
T
j
trace
T
j
∗
Γ
a
T
j
=
γ
1
d
n
∑
j
=
1
n
trace
T
j
∗
P
1
T
j
∑
i
=
1
s
γ
i
trace
T
j
∗
P
i
T
j
≥
γ
1
d
n
∑
j
=
1
n
trace
T
j
∗
P
1
T
j
γ
1
trace
T
j
∗
T
j
=
trace
P
1
M
I
d
.Now, M
(
Γ
a
)
=
M
(
I
d
) implies that either trace
(
T
j
P
i
T
j
∗
)
=
0, for all j
=
1
,
…
,
n and i
=
2
,
…
,
r, or P
1
=
I
d and, hence, Γ
a
=
γ
1
I
d. Since {
T
j
}
j
=
1
n is a generalized frame, trace
(
T
j
∗
P
i
T
j
) cannot vanish simultaneously for all j
=
1
,
…
,
n, so that, indeed, Γ
a is a nonzero multiple of the identity.The following result says that if we find a proper tightg-frame with unit norm based on (5), then this tight g-frame is unique.Proposition 6.
Let{
T
j
}
j
=
1
n be a g-frame and suppose that there are two positive definite matrices Γ
a and Γ
b such that both {
Γ
a
1
/
2
T
j
/
Γ
a
1
/
2
T
j
H
S
}
j
=
1
n and {
Γ
b
1
/
2
T
j
/
Γ
b
1
/
2
T
j
H
S
}
j
=
1
n are tight. Then those two tight g-frames are identical.Proof.
The tightness assumptions imply thatM
(
Γ
a
)
=
M
(
Γ
b
)
=
I. According to Lemma 5, there is a positive constant c such that Γ
a
=
c
Γ
b. Therefore, the two tight g-frames are identical.Next, we use scheme (10) to compute a unit norm tight g-frame.Theorem 7.
Let{
T
j
}
j
=
1
n
⊂
K
d
×
r satisfy the following points:(i)
{
T
j
}
j
=
1
n is a g-frame.
(ii)
If{
1
,
…
,
n
}
=
N
1
∪
N
2 and N
1
∩
N
2
=
∅, then ⋃
j
∈
N
i
‍
r
a
n
g
e
(
T
j
) spans K
d for either i
=
1 or i
=
2.
(iii)
IfL is a proper linear subspace of K
d, then #
{
j
:
r
a
n
g
e
(
T
j
)
⊂
L
}
<
n
/
d.
(iv)
IfL is a proper linear subspace of K
d, then #
{
j
:
r
a
n
g
e
(
T
j
)
⊂
L
}
<
d
i
m
(
L
)
/
α, where α
:
=
m
a
x
1
≤
j
≤
n
t
r
a
c
e
(
T
j
∗
S
-
1
T
j
) and S is the g-frame operator of {
T
j
}
j
=
1
n.Then the recursive scheme (10) with Γ
0
=
(
1
/
d
)
I
d converges towards a positive definite Γ and {
R
j
}
j
=
1
n defined by(12)
R
j
≔
Γ
1
/
2
T
j
Γ
1
/
2
T
j
H
Sis a tight g-frame.This theorem generalizes results in [14, 15], where convergence is verified for r
=
1. The conditions in Theorem 7 are redundant. Condition (ii) clearly implies (i). For d
≥
2, (iii) yields (ii). In fact, conditions (i), (ii), and (iii) depend on the range of each T
j but not on their norm. Note that condition (iii) can only be satisfied by some {
T
j
}
j
=
1
n if n
/
d
>
⌊
(
d
-
1
)
/
r
⌋, which yields n
>
d
⌊
(
d
-
1
)
/
r
⌋. Condition (iv) is independent of global scalings since multiplication of all T
j by some constant c means that the inverse frame operator needs to be divided by c
2. It requires α
<
r, which is, in fact, quite weak.Proposition 8.
Suppose that{
T
j
}
j
=
1
n
⊂
K
d
×
r is a g-frame. One then has t
r
a
c
e
(
T
j
∗
S
-
1
T
j
)
≤
r, for all j
=
1
,
…
,
n, and if there is j with t
r
a
c
e
(
T
j
∗
S
-
1
T
j
)
=
r, then T
j does not have any zero columns and r
a
n
g
e
(
S
-
1
/
2
T
k
)
⊥
r
a
n
g
e
(
S
-
1
/
2
T
j
), for all k
≠
j.Proof of Proposition8.
We first choose an orthonormal basis{
e
i
}
i
=
1
r for K
r and define, for some 1
≤
j
≤
n, the index set I
j
:
=
{
i
:
1
≤
i
≤
r
,
S
-
1
/
2
T
j
e
i
≠
0
}. We apply Proposition 1  r-times to derive (13)
r
≥
∑
i
∈
I
j
∑
k
=
1
n
T
k
∗
S
-
1
/
2
S
-
1
/
2
T
j
e
i
S
-
1
/
2
T
j
e
i
2
=
∑
i
∈
I
j
1
S
-
1
/
2
T
j
e
i
2
∑
j
=
1
n
∑
l
=
1
r
S
-
1
/
2
T
k
e
l
,
S
-
1
/
2
T
j
e
i
2
≥
∑
i
∈
I
j
1
S
-
1
/
2
T
j
e
i
2
S
-
1
/
2
T
j
e
i
,
S
-
1
/
2
T
j
e
i
2
=
∑
i
∈
I
j
S
-
1
/
2
T
j
e
i
2
=
S
-
1
/
2
T
j
H
S
2
=
trace
T
j
∗
S
-
1
T
j
.The assumptiont
r
a
c
e
(
T
j
∗
S
-
1
T
j
)
=
r implies that the two above inequalities become equalities, which yield the required statements.Note that Proposition8 bounds the worst case scenario. Since I
d
=
S
-
1
S, taking the trace on both sides yields that d
=
∑
j
=
1
n
‍
t
r
a
c
e
(
T
j
∗
S
-
1
T
j
). If {
T
j
}
j
=
1
n has unit norm and is close to being tight meaning S
≈
n
/
d
I
d, then α
≈
d
/
n. If {
T
j
}
j
=
1
n is sufficiently generic or in sufficient general position, then (i)–(iv) are satisfied for sufficiently large n.If{
T
j
}
j
=
1
n is a sample of a continuous distribution on K
d
×
r and n is sufficiently large, then with probability one all of the assumptions in Theorem 7 are satisfied.Proof of Theorem7.
Since{
T
j
}
j
=
1
n is a g-frame, the sequence {
Γ
k
}
k
=
1
∞ is well defined. It is also clear that Γ
k is hermitian positive definite and t
r
a
c
e
(
Γ
k
)
=
1, for all k
=
0,1
,
2
,
…. If we suppose that {
Γ
k
}
k
=
1
∞ converges towards Γ, then M
(
Γ
)
=
I
d must hold, and a direct computation yields that {
R
j
}
j
=
1
n is a tight g-frame with R
j
H
S
=
1, for j
=
1
,
…
,
n.
It remains to verify convergence, which we check in two steps.
Step
1 (refers to Lemma 2.1 in [14]). Let λ
1
,
k and λ
d
,
k be the largest and smallest eigenvalues of M
k, respectively. We observe(14)
I
d
=
d
n
∑
j
=
1
n
M
k
-
1
/
2
Γ
k
1
/
2
T
j
T
j
∗
Γ
k
1
/
2
M
k
-
1
/
2
trace
T
j
∗
Γ
k
T
j
.The positive definite square root of Γ
k
1
/
2
M
k
-
1
Γ
k
1
/
2 has the form Q
k
M
k
-
1
/
2
Γ
k
1
/
2, where Q
k is an orthogonal matrix. Since Q
k
Q
k
∗
=
I
d, we obtain(15)
I
d
=
d
n
∑
j
=
1
n
Q
k
M
k
-
1
/
2
Γ
k
1
/
2
T
j
T
j
∗
Γ
k
1
/
2
M
k
-
1
/
2
Q
k
∗
trace
T
j
∗
Γ
k
T
j
.According to (10), we have (16)
Γ
k
+
1
1
/
2
=
Γ
k
1
/
2
M
k
-
1
Γ
k
1
/
2
1
/
2
trace
Γ
k
M
k
-
1
=
Q
k
M
k
-
1
/
2
Γ
k
1
/
2
trace
Γ
k
M
k
-
1
,which yields (17)
I
d
=
d
n
∑
j
=
1
n
Γ
k
+
1
1
/
2
T
j
T
j
∗
Γ
k
+
1
1
/
2
trace
T
j
∗
Γ
k
T
j
trace
Γ
k
M
k
-
1
=
d
n
·
∑
j
=
1
n
Γ
k
+
1
1
/
2
T
j
T
j
∗
Γ
k
+
1
1
/
2
trace
T
j
∗
Γ
k
+
1
T
j
·
trace
T
j
∗
Γ
k
+
1
T
j
trace
Γ
k
M
k
-
1
trace
T
j
∗
Γ
k
T
j
.According to (10), we have the identity t
r
a
c
e
(
T
j
∗
Γ
k
+
1
T
j
)
=
t
r
a
c
e
(
T
j
∗
Γ
k
1
/
2
M
k
-
1
Γ
k
1
/
2
T
j
)
/
t
r
a
c
e
(
Γ
k
M
k
-
1
), so that(18)
I
d
=
d
n
∑
j
=
1
n
Γ
k
+
1
1
/
2
T
j
T
j
∗
Γ
k
+
1
1
/
2
trace
T
j
∗
Γ
k
+
1
T
j
·
trace
T
j
∗
Γ
k
1
/
2
M
k
-
1
Γ
k
1
/
2
T
j
trace
T
j
∗
Γ
k
T
j
=
d
n
·
∑
j
=
1
n
Γ
k
+
1
1
/
2
T
j
T
j
∗
Γ
k
+
1
1
/
2
trace
T
j
∗
Γ
k
+
1
T
j
M
k
-
1
/
2
Γ
k
1
/
2
T
j
H
S
2
Γ
k
1
/
2
T
j
H
S
2holds. Since each of the matrices Γ
k
+
1
1
/
2
T
j
T
j
∗
Γ
k
+
1
1
/
2
/
t
r
a
c
e
(
T
j
∗
Γ
k
+
1
T
j
) is positive semidefinite, the definition of M
k
+
1 in (9) with its largest and smallest eigenvalues implies (19)
λ
d
,
k
-
1
M
k
+
1
≥
I
d
≥
λ
1
,
k
-
1
M
k
+
1
.The left inequality yields λ
d
,
k
+
1
/
λ
d
,
k
≥
1 and the right inequality implies λ
1
,
k
+
1
/
λ
1
,
k
≤
1. Thus, as required, the sequence (
λ
d
,
k
)
k
=
1
∞ is increasing, (
λ
1
,
k
)
k
=
1
∞ is decreasing, and both converge towards λ
d
≤
1 and λ
1
≥
1, respectively.
Step
2 (refers to Theorem 2.2 and Corollary 2.2 in [14]). Since Γ
k is positive definite with trace 1, there is a subsequence (
Γ
k
m
)
m
=
1
∞ that converges towards some positive semidefinite matrix Γ. We must now verify that Γ is positive definite and that the entire sequence converges.
IfΓ
T
j
=
0, then let θ
j
∈
K
d
×
r be such that (20)
Γ
k
m
1
/
2
T
j
trace
T
j
∗
Γ
k
m
T
j
⟶
θ
j
.For J
≔
{
j
:
Γ
T
j
≠
0
}, we observe that the subsequence (
M
k
m
)
m
=
1
∞ converges to(21)
M
=
d
n
∑
j
∈
J
Γ
1
/
2
T
j
T
j
∗
Γ
1
/
2
trace
T
j
∗
Γ
T
j
+
∑
j
∉
J
θ
j
θ
j
∗
.Step 1 ensures that M is invertible since its smallest eigenvalue is positive. Let Q
k
m be the orthogonal matrices in Step 1, so that Q
k
m
→
Q and (
Γ
1
/
2
M
-
1
Γ
1
/
2
)
1
/
2
=
Q
M
-
1
/
2
Γ
1
/
2 is satisfied. According to definition (10), (
Γ
k
m
+
1
)
m
=
1
∞ converges towards (22)
Γ
0
=
Γ
1
/
2
M
-
1
Γ
1
/
2
trace
M
-
1
Γand a short calculation yields that the sequence (
M
k
m
+
1
)
m
=
1
∞ converges to (23)
M
0
=
d
n
∑
j
∈
J
Γ
0
1
/
2
T
j
T
j
∗
Γ
0
1
/
2
trace
T
j
∗
Γ
0
T
j
+
∑
j
∉
J
ϕ
j
ϕ
j
∗
,where ϕ
j
=
Q
M
1
/
2
θ
j
/
t
r
a
c
e
(
θ
j
∗
M
-
1
θ
j
).
Manipulations as in Step1 applied to the formulas for M and M
0 imply that(24)
I
d
=
d
n
∑
j
∈
J
M
-
1
/
2
Γ
1
/
2
T
j
T
j
∗
Γ
1
/
2
M
-
1
/
2
trace
T
j
∗
Γ
T
j
+
∑
j
∉
J
M
-
1
/
2
θ
j
θ
j
∗
M
-
1
/
2as well as(25)
I
d
=
1
λ
1
M
0
+
d
n
·
∑
j
∈
J
Γ
0
1
/
2
T
j
T
j
∗
Γ
0
1
/
2
trace
T
j
∗
Γ
0
T
j
trace
T
j
∗
Γ
1
/
2
M
-
1
Γ
1
/
2
T
j
trace
T
j
∗
Γ
T
j
-
1
λ
1
+
d
n
∑
j
∉
J
ϕ
j
ϕ
j
∗
trace
θ
j
∗
M
-
1
θ
j
-
1
λ
1
.
According to Step1, the largest and smallest eigenvalue of both M and M
0 are λ
1 and λ
d, respectively. Let P and P
0 be the eigenprojectors of M and M
0, respectively, associated with λ
1 and s
=
r
a
n
k
(
P
) and s
0
=
r
a
n
k
(
P
0
). As in [14], without loss of generality, we can suppose s
0
≥
s.
By multiplying both sides from the left and the right byP
0, the relations P
0
2
=
P
0 and (
1
/
λ
1
)
P
0
M
P
0
=
P
0 yield(26)
0
=
∑
j
∈
J
P
0
Γ
0
1
/
2
T
j
T
j
∗
Γ
0
1
/
2
P
0
trace
T
j
∗
Γ
0
T
j
trace
T
j
∗
Γ
1
/
2
M
-
1
Γ
1
/
2
T
j
trace
T
j
∗
Γ
T
j
-
1
λ
1
+
∑
j
∉
J
P
0
ϕ
j
ϕ
j
∗
P
0
trace
θ
j
∗
M
-
1
θ
j
-
1
λ
1
.
Thus, forj
∈
J, we either have (27)
P
0
Γ
0
1
/
2
T
j
T
j
∗
Γ
0
1
/
2
P
0
=
0
or
trace
T
j
∗
Γ
1
/
2
M
-
1
Γ
1
/
2
T
j
trace
T
j
∗
Γ
T
j
=
1
λ
1
.The first option yields P
0
Q
M
-
1
/
2
Γ
1
/
2
T
j
=
0. The second option implies 〈
P
,
Γ
1
/
2
T
j
T
j
∗
Γ
1
/
2
〉
=
〈
I
,
Γ
1
/
2
T
j
T
j
∗
Γ
1
/
2
〉, which yields after some computations P
Γ
1
/
2
T
j
=
Γ
1
/
2
T
j.
Forj
∉
J, we obtain (28)
P
0
ϕ
j
ϕ
j
∗
P
0
=
0
or  trace
θ
j
∗
M
-
1
θ
j
-
1
λ
1
=
0
.Similar to the above considerations, the first option yields P
0
Q
M
-
1
/
2
θ
j
=
0. The second option implies P
θ
j
=
θ
j.
We now premultiply both sides of (24) by P
0
Q and postmultiply by I
-
P. The above four options and using that P and M
-
1
/
2 commute imply P
0
Q
(
I
-
P
)
=
0, which is equivalent to Q
∗
P
0
Q
=
Q
∗
P
0
Q
P. Since s
0
≥
s, we obtain P
=
Q
∗
P
0
Q, so that Q
P
=
P
0
Q. The latter implies with the above that, for j
∈
J, either (29)
P
Γ
1
/
2
T
j
=
0
or
P
Γ
1
/
2
T
j
=
Γ
1
/
2
T
j
.Hence, we can split {
1
,
…
,
n
} into two disjoint index sets N
1 and N
2 such that (30)
P
Γ
1
/
2
T
j
=
0
,
j
∈
N
1
Γ
1
/
2
T
j
,
j
∈
N
2
.Condition (ii) yields that s
p
a
n
(
r
a
n
g
e
(
T
j
)
:
j
∈
N
i
) equals K
d for either i
=
1 or i
=
2. If this holds for i
=
1, then we must have P
Γ
1
/
2
=
0. If it holds for i
=
2, then we derive P
Γ
1
/
2
=
Γ
1
/
2.
Suppose now thatP
Γ
1
/
2
=
0 holds. The same arguments as in the previous paragraph yield, for j
∈
J, that either P
θ
j
=
0 or P
θ
j
=
θ
j; see also [14]. Pre- and postmultiplying both sides in (21) by P yields(31)
λ
1
P
=
d
n
∑
j
∈
J
0
θ
j
θ
j
∗
,where J
0
:
=
{
j
:
j
∉
J
,
P
θ
j
=
θ
j
}. Next, we take the trace on both sides and use that trace
(
θ
j
∗
θ
j
)
=
1 to derive (32)
λ
1
s
≤
d
n
n
1
,where n
1 is the number of T
j whose range is contained in the null space of Γ. Condition (iii) yields λ
1
≤
d
n
1
/
s
n
<
1, which is a contradiction to the results of Step 1. Thus, we must have P
Γ
1
/
2
=
Γ
1
/
2, so that(33)
P
=
d
n
λ
1
∑
j
∈
J
Γ
1
/
2
T
j
T
j
∗
Γ
1
/
2
trace
T
j
∗
Γ
T
j
+
d
n
λ
1
∑
j
∈
J
0
θ
j
θ
j
∗
.Since the ranks of the two summations in (21) are additive (see also [14]) the ranks of the two summations in (33) are additive. Hence, the two terms themselves must be orthogonal projections. According to condition (i), the rank of the first term equals r
a
n
k
(
Γ
). If r
a
n
k
(
Γ
)
<
s, then taking the trace of the second term implies with condition (iii) that λ
1
<
1
/
(
s
-
r
a
n
k
Γ
)
≤
1, which is a contradiction to Step 1. Therefore, J
0 is empty and s
=
r
a
n
k
(
Γ
). Taking the trace of the first term in (33) yields(34)
λ
1
=
d
n
-
n
1
n
s
.
We obtaind
=
trace
(
M
)
≥
s
λ
1
+
(
d
-
s
)
λ
d, so that (34) implies(35)
λ
d
≤
d
n
1
n
d
-
s
.
At this point, we claim that assumption (iv) implies for at least onek that(36)
λ
d
,
k
>
d
n
#
j
:
range
T
j
⊂
L
dim
⁡
Lholds, for all proper linear subspaces L
⊂
K
d, but postpone the verification to the end of this proof.
Sinceλ
d
,
k is an increasing sequence, (36) implies d
(
n
1
/
n
d
-
s
)
<
λ
d if d
>
s. This violates (35), so that M and hence Γ must have full rank and, therefore, Γ is positive definite. Also, P must have full rank implying λ
1
=
λ
d
=
1 and M
=
I
d. Since the eigenvalues are monotone, the entire sequence (
M
k
)
k
=
1
∞ converges towards I
d. The latter can be used with Banach’s fixed point theorem to verify that also (
Γ
k
)
k
=
1
∞ must converge, hence, towards Γ. By continuity, we obtain M
(
Γ
)
=
I
d.
We still need to verify (36). We observe Γ
1
=
S
-
1
/
trace
(
S
-
1
) and define W
j
:
=
Γ
1
1
/
2
T
j, which yields ∑
j
=
1
n
‍
W
j
W
j
∗
=
I
d
/
trace
(
S
-
1
). By using α
=
m
a
x
1
≤
j
≤
n
trace
(
T
j
∗
S
-
1
T
j
) as in (iv), this implies M
1
⪰
d
/
n
α
I
d, so that(37)
λ
d
,
1
≥
d
n
α
>
d
n
#
j
:
range
T
j
⊂
L
dim
⁡
L
,where the last inequality is due to (iv). This concludes the proof.Remark 9.
The inversion ofM
k in iterative scheme (10) is numerically stable because there is a lower positive bound on the smallest eigenvalues of M
k. Therefore, we can expect that our scheme is quite stable overall.Let us have a look at few pathological examples first.Example 10.
(
1
) If {
T
j
}
j
=
1
n is already a unit norm tight g-frame, then Γ
1
=
Γ
=
(
1
/
d
)
I
d and {
R
j
}
j
=
1
n
=
{
T
j
}
j
=
1
n.
(
2
) If the g-frame consists of a single matrix T
∈
K
d
×
r, hence, r
=
d and T is regular, then Γ
1
=
Γ
=
T
T
∗ and (12) yields R
=
(
1
/
d
)
(
T
T
∗
)
-
1
/
2
T, which is a unit norm tight g-frame.Next, we illustrate Theorem7 with few numerical examples.Example 11.
Letd
=
2, r
=
1, and n
=
3. We pick α
1
,
α
2
,
α
3 from a uniform distribution on [
0,2
π
] and define T
j
=
c
o
s
(
α
j
)
s
i
n
(
α
j
), j
=
1,2
,
3. By multiplication by -
1 and rotation of all 3 vectors, we can restrict the angles to lie between 0 and (
2
/
3
)
π. For each random choice {
T
j
}
j
=
1
3, we compute a unit norm tight frame {
R
j
}
j
=
1
3 using our proposed algorithm. Up to rotations U
θ
=
c
o
s
(
θ
)
-
s
i
n
(
θ
)
s
i
n
(
θ
)
c
o
s
(
θ
) and multiplication by -
1, there is only one single unit norm tight frame with three elements. We choose {
Y
j
}
j
=
1
3, where Y
j
=
c
o
s
(
β
j
)
s
i
n
(
β
j
) and β
1
=
0, β
2
=
1
/
3
π, and β
3
=
2
/
3
π. Therefore, to find the tight frame with unit norm that is closest to {
T
j
}
j
=
1
3, we minimize the distance to {
T
j
}
j
=
1
3 over all rotations, that is, (38)
θ
^
≔
a
r
g
min
θ
∈
-
2
/
3
π
,
2
/
3
π
⁡
∑
j
=
1
3
U
θ
Y
j
-
T
j
2
,and define the closest tight frame by {
Z
j
}
j
=
1
3
≔
{
U
θ
^
Y
j
}
j
=
1
3. Note that we can suppress the multiplication by -
1 because the angles of {
T
j
}
j
=
1
3 only run in [
0
,
2
/
3
π
]. The average error of ∑
j
=
1
n
‍
Z
j
-
R
j
2 over 1000 realizations is ≈
0.0016
=
1
/
625; see also Figure 2 for a visualization of few examples. In our numerical experiments, we observed that our proposed algorithm finds a tight frame that is almost identical to the closest tight frame if all pairs T
i and T
j, for i
≠
j, are far enough from each other.Figure 2
Original frame{
T
j
}
j
=
1
3 in blue, optimal frame {
Z
j
}
j
=
1
3
=
{
U
θ
^
Y
j
}
j
=
1
3 in green, and our proposed algorithm finds {
Γ
1
/
2
T
j
/
Γ
1
/
2
T
j
}
j
=
1
3 in red. (Green and red lines are sometimes right on top of each other.)Example 12.
For0
≤
t
≤
1
/
2, define (39)
T
1
t
=
1
-
t
0
0
t
,
T
2
t
=
t
t
0
1
-
2
t
,
T
3
t
=
1
-
t
2
0
0
1
+
t
2
,and let S
(
t
) denote the associated g-frame operator. Note that {
T
j
(
t
)
}
j
=
1
3 satisfies the assumptions of Theorem 7, for all 0
≤
t
≤
1
/
2. If t
=
0, then we have a tight generalized frame with unit norms. Our algorithm provides a Parseval g-frame {
2
/
3
R
j
(
t
)
}
j
=
1
3 with equal H
S-norm; see Figure 3 for the errors ∑
j
=
1
3
‍
T
j
(
t
)
-
2
/
3
R
j
(
t
)
H
S
2 and ∑
j
=
1
3
‍
T
j
(
t
)
-
S
(
t
)
-
1
/
2
T
j
(
t
)
H
S
2.Figure 3
t versus the distance (blue) ∑
j
=
1
3
‍
T
j
(
t
)
-
2
/
3
R
j
(
t
)
H
S
2 and (red) ∑
j
=
1
3
‍
T
j
(
t
)
-
S
(
t
)
-
1
/
2
T
j
(
t
)
H
S
2 in Example 12. Note that {
T
j
(
0
)
}
j
=
1
3 is tight but needs rescaling to become the Parseval generalized frame {
2
/
3
T
j
(
0
)
}
j
=
1
3. It is clear that R
j
(
0
)
=
T
j
(
0
) and 2
/
3
T
j
(
0
)
=
T
j
(
0
)
S
(
0
)
-
1
/
2 holds, and we have ∑
j
=
1
3
‍
T
j
(
0
)
-
2
/
3
T
j
(
0
)
H
S
2
=
0.1010. The latter explains why the distance plots do not start at 0.Example 13.
We choose each entry of each element in{
T
j
}
j
=
1
3
⊂
R
2
×
2 independently according to a uniform distribution on [
0,1
] and normalize so that T
j
H
S
=
1. All numbers in the following are averaged over 10,000 realizations, and let S denote the generalized frame operator of {
T
j
}
j
=
1
3. According to Proposition 1, {
S
-
1
/
2
T
j
}
j
=
1
3 is the Parseval generalized frame that is closest to {
T
j
}
j
=
1
3, and we compute ∑
j
=
1
3
‍
T
j
-
S
-
1
/
2
T
j
H
S
2
≈
0.61. However, the elements of {
S
-
1
/
2
T
j
}
j
=
1
3 may not have equal norm. Based on Theorem 7, the collection {
R
~
j
}
j
=
1
3
=
{
2
/
3
R
j
}
j
=
1
3 is a Parseval generalized frame, its elements have equal norm, and we compute ∑
j
=
1
3
‍
T
j
-
R
~
j
H
S
2
≈
0.71. Thus, the additional property of having equal norm costs ≈
0.10
=
0.71
-
0.61. It remains open though if there are other Parseval generalized frames whose elements have equal norm and that are closer to {
T
j
}
j
=
1
3.Let us also illustrate when the algorithm fails to converge.Example 14.
Fort
=
0, the collection {
T
j
(
t
)
}
j
=
1
3, where (40)
T
1
t
=
1
0
0
0
,
T
2
t
=
1
t
0
0
,
T
3
t
=
0
0
0
1
,violates the conditions in Theorem 7, and, indeed, the iterative scheme does not converge towards a positive definite matrix Γ. For t
>
0, on the other hand, we observe convergence numerically.The subsequent sections are dedicated to provide some examples of random samples satisfying the assumptions of Theorem7. We will also provide examples that allow for fast matrix vector multiplications such as convolution operators and we support the intuition that Γ is close to the identity if the sample is close to being tight.


## 4. Examples of Random Matrices Satisfying the Assumptions for Convergence

We first fuse the concepts of generalized frames and probabilistic frames as developed in [5] and [4], respectively, see also [25].Definition 15.
Letp
≥
1 be an integer. One says that a random matrix T
∈
K
d
×
r is arandom
g
-frame of order
p if there are positive constants A
p and B
p
>
0 such that(41)
A
p
x
2
p
≤
E
T
∗
x
2
p
≤
B
p
x
2
p
,
∀
x
∈
K
d
.A random g-frame T of order p is calledtight if we can choose A
p
=
B
p.Following the lines of the proof for rank one projectors considered in [2] yields that any random g-frame T of order 1 satisfies A
1
≤
(
1
/
d
)
E
T
(
ω
)
H
S
2
≤
B
1. Similar to finite frames, if T is a random g-frame of order p, then therandom
g
-frame operator
(42)
S
:
K
d
⟶
K
d
,
x
⟼
E
T
T
∗
xis positive, self-adjoint, and invertible. Thus, we obtain the reconstruction formula(43)
x
=
E
T
S
-
1
T
∗
x
.Moreover, T is a tight random g-frame of order 1 if and only if S
=
A
I
d, where A
=
1
/
d
E
T
H
S
2.Note that the caser
=
1 of the following result is already explicitly contained in [26] and see [27] for related results on orthogonal projectors.Theorem 16.
Let{
T
j
}
j
=
1
n be independent copies of a tight random g-frame T
∈
K
d
×
r of order 1 with T
H
S
2
=
R for some positive constant R. For fixed ɛ
∈
(
0,1
], there are positive constants γ
ɛ and c
ɛ
>
0 such that, for all n
≥
c
ɛ
d
ln
⁡
(
d
), the g-frame operator S
n of the scaled collection {
d
/
n
R
T
j
}
j
=
1
n satisfies I
d
-
S
n
∞
<
ɛ with probability at least 1
-
e
-
γ
ɛ
n
/
d.Proof.
Letλ
m
i
n
(
S
n
) and λ
m
a
x
(
S
n
) denote the smallest and largest eigenvalue of S
n, respectively. The matrix Chernoff bounds as stated in [28] yield, for all 0
≤
ɛ
≤
1, (44)
P
λ
m
i
n
S
n
≤
1
-
ɛ
≤
d
e
-
ɛ
1
-
ɛ
1
-
ɛ
n
/
d
,
P
λ
m
i
n
S
n
≥
1
+
ɛ
≤
d
e
ɛ
1
+
ɛ
1
+
ɛ
n
/
d
.Some calculus yields (45)
1
+
ɛ
1
+
ɛ
1
-
ɛ
ɛ
-
1
≤
e
2
ɛ
,
∀
ɛ
∈
0,1
,so that we derive(46)
P
I
d
-
∑
j
=
1
n
d
n
R
T
j
∗
T
j
∞
≥
ɛ
≤
2
d
e
ɛ
1
+
ɛ
1
+
ɛ
n
/
d
.We can further compute (47)
2
d
e
ɛ
1
+
ɛ
1
+
ɛ
n
/
d
=
2
d
e
-
n
/
d
1
+
ɛ
ln
⁡
1
+
ɛ
-
ɛ
=
e
-
n
/
d
1
+
ɛ
l
n
1
+
ɛ
-
ɛ
-
d
/
n
ln
⁡
2
ln
⁡
d
.Since (
1
+
ɛ
)
l
n
(
1
+
ɛ
)
-
ɛ
>
0, for all ɛ
∈
(
0,1
], we can find a suitable constant γ
ɛ
>
0 if n is sufficiently large.Remark 17.
The constantsγ
ɛ and c
ɛ in Theorem 16 can be explicitly computed. By using a
ɛ
:
=
(
1
+
ɛ
)
l
n
(
1
+
ɛ
)
-
ɛ
>
0, we can choose c
ɛ
>
l
n
(
2
)
/
a
ɛ and γ
ɛ
=
a
ɛ
-
l
n
(
2
)
/
c
ɛ.Next, we discuss a few examples.Example 18 (Gaussian matrices).
Let1
≤
k
<
d and consider the d
×
r random matrix T whose entries are i.i.d. Gaussian. Its joint element density is(48)
M
⟼
1
2
π
k
d
/
2
e
x
p
-
1
2
M
H
S
2
.The resulting self-adjoint matrix T
T
∗
∈
R
d
×
d is a singular Wishart-matrix (cf. [29]). According to (48) the distribution of T is invariant under orthogonal transformations, so that T is a tight random g-frame of order p, for all integers p. By using the moments of the chi-squared distribution, we see that the bounds satisfy A
p
=
B
p
=
k
(
k
+
2
)
⋯
(
k
+
2
p
-
2
).Example 19 (fusion frames).
If the columns of a matrixT
∈
K
d
×
r, r
<
d, have orthonormal columns, then we can identify T with a subspaces V
∈
G
r
,
d
(
K
), where G
r
,
d
(
K
) denotes the Grassmann space, that is, the collection of r-dimensional subspaces of K
d. The Haar measure on G
r
,
d
(
K
) then induces a random g-frame of order p for all integers p.Example 20 (Gabor).
Time-frequency structured matrices were considered in [30] in relation to compressed sensing, in which some window vector is modulated and shifted. We use cyclic shifts, which can be performed by applying a matrix C having ones in the lower secondary diagonal, another one in the upper right corner, and zeros anywhere else. The modulation operator on C
d is given by (49)
M
=
diag
⁡
1
,
e
2
π
i
/
d
,
…
,
e
2
π
i
d
-
1
/
d
.For any nonzero g
∈
C
d, the full Gabor system {
M
l
C
k
g
:
l
,
k
=
0
,
…
,
d
-
1
} has cardinality d
2 and forms a tight frame for C
d (cf. [31]). We will use the d
2
×
d matrix T, whose rows are formed by the tight frame vectors. A short computation yields that if g is chosen at random as the Rademacher sequence, then T is a tight random g-frame of order 1. Moreover, each T
T
∗ is an orthogonal projector, so that T
T
∗ corresponds to a tight random fusion frame. The same holds when g is the Steinhaus sequence; that is, each entry is uniformly distributed on the complex unit circle.Next, we have an example that indeed allows for fast matrix vector multiplication.Example 21 (circulant matrices).
Given a vectorx
=
(
x
1
,
…
,
x
d
)
⊤
∈
R
d, the corresponding circulant matrix is (50)
T
~
=
x
1
x
d
⋯
x
2
x
2
⋱
⋱
⋮
⋮
⋱
⋱
x
d
x
d
⋯
x
2
x
1
.Each column of T
~ is a cyclic shift of the previous one. The left d
×
k block T of the matrix T
~ was used as a compressed sensing measurement matrix in [32]. If the entries of x are i.i.d. with zero mean and nonvanishing second moments, then T is a tight random g-frame of order 1 with A
1
=
k
E
(
x
i
2
). For instance, if x is the Rademacher sequence, that is, entries are independent and equal to ±
1 with probability 1
/
2, then T is tight of order 1 but not of order 2 in general. It is well known that the discrete Fourier matrices diagonalize circulant matrices, so that fast matrix vector multiplications are available. In fact, the terms “filter bank” and “filterning” are usually associated with the application of convolution operators, so that each channel corresponds to a circulant matrix with potentially some subsampling involved.Remark 22.
Samples of all of the above examples satisfy the conditions (i)–(iv) with high probability for sufficiently large sample size. The circulant matrices represent convolution operators and hence correspond to a proper filter bank scheme. They enable fast matrix vector multiplications; hence, the circulant samples in Example21 are indeed suitable for our construction in Section 3 that preserves this fast algorithmic scheme using the filter bank shown in Figure 1. Each channel corresponds to filtering, but we require one additional linear operator for pre- and postmultiplication.It must be mentioned that filter banks usually involve some subsampling. Let the matrixT
∈
K
r
~
×
r, r
~
≥
r, be a random matrix with a single one in each column, whose position is chosen independently at random in a uniform fashion. Then each matrix of the sample {
T
j
}
j
=
1
n corresponds to a sampling operator, so that we derive n samplings of length r. Indeed, T is a tight random g-frame, but it may not satisfy all other conditions in Theorem 7. Nonetheless, subsampling operators in a filter bank are used in combination with more sophisticated filters, say {
R
j
}
j
=
1
n
⊂
K
d
×
r
~, so that it is possible that the conditions are satisfied by {
R
j
T
j
}
j
=
1
n
⊂
K
d
×
r.


## 5. Closeness to the Originalg-Frame

To relate the algorithm of the previous section to the Paulsen problem, we would need estimates on the distance between the original and the resultingg-frame. In particular, if the original unit norm g-frame is close to being tight, then we aim to verify that the computed unit norm tight g-frame is nearby. We do not derive any estimates for fixed n but will provide some framework for random samples that supports such intuition.Theorem 23.
LetT be a random matrix continuously distributed on the set of matrices in K
d
×
r and {
T
j
}
j
=
1
n an associated i.i.d. sample with Γ
(
n
) being the corresponding limit of the iterative algorithm (10). Then Γ
(
n
) converges almost surely towards some positive definite Γ, so that Σ
≔
Γ
-
1 satisfies(51)
Σ
=
d
E
T
T
∗
t
r
a
c
e
T
∗
Σ
-
1
T
.Before we shall provide the proof, we have some discussion. As in [14], we observe that results of the previous section applied to a continuously distributed random matrix T yield that (51) has a solution Σ among the symmetric positive definite matrices and is unique up to multiplication by a positive constant.For elliptical distributions, (51) has a very special meaning. Here, we call a probability distribution on K
d
×
r
elliptical if it has a density f with respect to the standard volume element d
T on K
d
×
r and (52)
f
T
=
d
e
t
Σ
-
1
/
2
g
trace
T
-
T
¯
∗
Σ
-
1
T
-
T
¯
,where Σ
∈
K
d
×
d is hermitian positive definite, T
¯
∈
K
d
×
r, and g is some nonnegative function not dependent on T
¯ and Σ with ∫
K
d
×
r
‍
g
(
t
r
a
c
e
(
T
∗
T
)
)
d
T
=
1. For instance, the Gaussian random matrix in Example 18 is elliptically distributed. A direct computation yields that the matrix Σ of an elliptically distributed random matrix T with T
¯
=
0 satisfies (51). For simplicity, we will restrict ourselves to the case T
¯
=
0 and point out that general T
¯ can be handled in a similar fashion; see [14] for r
=
1.Theorem23 directly implies the following.Corollary 24.
IfT is elliptically distributed with T
¯
=
0 and Σ is a multiple of the identity, then, for any sample {
T
j
}
j
=
1
n, the associated matrices Γ
(
n
), for n
→
∞, converge towards 1
/
d
I.To verify Theorem23, we follow the ideas in [14], where r
=
1 was considered, so we need some notation and two lemmas. Let us define (53)
M
n
Γ
=
d
n
∑
j
=
1
n
Γ
1
/
2
T
j
T
j
∗
Γ
1
/
2
trace
T
j
∗
Γ
T
j
,
M
Γ
=
d
E
Γ
1
/
2
T
T
∗
Γ
1
/
2
trace
T
∗
Γ
T
,and we denote h
n
(
Γ
)
≔
trace
(
M
n
(
Γ
)
2
) and h
(
Γ
)
≔
trace
(
M
(
Γ
)
2
).Lemma 25.
LetC
⊂
K
d
×
d be a compact set of positive definite matrices with R
∈
C implying t
r
a
c
e
(
R
-
1
)
=
1 and t
r
a
c
e
(
R
)
≤
K with some fixed K
>
1. Then(54)
sup
R
∈
C
⁡
h
n
R
-
h
R
⟶
0holds almost surely.Lemma 26.
The hermitian positive definite matrixR
∈
K
d
×
d is a critical value of h
n if and only if M
n
(
R
)
=
I
d.Proof of Theorem23.
Simple arithmetics yield thattrace
(
M
n
(
R
)
)
=
trace
(
M
(
R
)
)
=
d implies d
≤
h
n
(
R
), h
(
R
)
≤
d
2, for all positive definite matrices R
∈
K
d
×
d. Furthermore, h
n
(
R
)
=
d or h
(
R
)
=
d if and only if M
n
(
R
)
=
I or M
(
R
)
=
I
d, respectively.
As mentioned above, (51) has a solution Σ among the symmetric positive definite matrices and is unique up to multiplication by a positive constant; see also [14]. Without loss of generality, we can assume that Σ
=
d
I, which implies M
(
Σ
-
1
)
=
M
(
1
/
d
I
)
=
I
d. Choose C as in Lemma 25 with 1
/
d
I
d being contained in its interior. For all R
∈
C with R
≠
1
/
d
I
d, we must have d
=
h
(
1
/
d
I
d
)
<
h
(
R
). Since h is continuous, Lemma 25 yields that, for any R on the boundary of C, we have h
n
(
1
/
d
I
d
)
<
h
n
(
R
) with probability one if n is sufficiently large.
Note thatM
n
(
Γ
(
n
)
)
=
I
d, so that Lemmas 5 and 26 imply that Γ
(
n
) is eventually contained in C for sufficiently large n. Since C can be chosen arbitrarily small, it follows that Γ
(
n
)
→
1
/
d
I
d
=
Σ
-
1 almost surely, which concludes the proof.It remains to prove the two Lemmas25 and 26.Proof of Lemma25.
We follow [14, Proof of Statement (
3.2
)]. For 0
≠
T
∈
K
d
×
r, we define (55)
G
T
,
R
≔
R
1
/
2
T
T
∗
R
1
/
2
trace
T
∗
R
T
.
As already mentioned in [14] for r
=
1, G is equicontinuous on C meaning that, for ɛ
>
0, there is δ
ɛ
>
0 not dependent on T
≠
0 nor on R
1, R
2
∈
C, such that R
1
-
R
2
<
δ
ɛ implies G
(
T
,
R
1
)
-
G
(
T
,
R
2
)
H
S
<
ɛ. Next, the same covering argument for C as in [14] used with the equicontinuity and the strong law of large numbers implies (54). We omit the details.Proof of Lemma26.
We can simply follow the lines of [14, Proof of Statement (
3.3
)], where r
=
1 is discussed. A first order expansion of h
n with the frame property and Kantorovich’s inequality yields Lemma 26. No new ideas are involved when dealing with r
>
1, so we refer to [14] for the details.


## 6. Some Concluding Remarks

For some signal processing aspects, the most attractive filter bank schemes are those that provide perfect reconstruction, synthesis is the adjoint of the analysis scheme (so-called unitary filter banks), and filters have equal norm. Tight fusion frames, for instance, correspond to perfect reconstruction filter banks, in which each channel corresponds to an orthogonal projection, and it was verified in [9] that robustness of tight fusion frames against distortions and erasures is maximized when the tight fusion frame has equal norm elements. Our aim was to turn a given filter bank into such more attractive schemes and preserve the essential features of the original filtering process. In terms of frames, we turned a given generalized frame into a tight g-frame with unit norm by rescaling and then applying the inverse square root of the new g-frame operator. Due to our special focus on filter banks, we started with a generalized frame consisting of convolution operators, hence, allowing for fast matrix vector multiplications. Through some iterative scheme, we constructed a generalized tight frame with unit norm, which induced a filter bank that preserved the convolution structure, hence, the fast algorithmic scheme, in each channel. Only one additional global pre- and postmultiplication by Γ
1
/
2 is necessary. Naturally, the application of Γ
1
/
2 needs special care because it may be structured but not exactly a convolution operator.We observed that the assumptions of our algorithm are satisfied by any sufficiently large sample drawn from any continuous distribution or drawn from random convolution operators. Fields of application are filter banks, in which the additional computation costs of the application ofΓ
1
/
2 or Γ, respectively, can be tolerated, as, for instance, when the number of channels is large or when computations are completely offline.Our findings provide a tool to design new filter banks with improved properties on a theoretical level. Substantial numerical verification goes beyond the scope of the present paper and will be provided in future work. We hope that our theoretical findings can provide the basis for its use in more elaborate signal processing methods.



---

*Source: 861563-2015-06-22.xml*