# Tetris Tight Frames Construction via Hadamard Matrices

Authors: A. Abdollahi; M. Monfaredpour
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

We present a new method to construct unit norm tight frames by applying altered Hadamard matrices. Also we determine an elementary construction which can be used to produce a unit norm frame with prescribed spectrum of frame operator.


---

## Body

## 1. Introduction and Preliminaries

Frames were first introduced in 1952 by Duffin and Schaeffer [1] in the context of nonharmonic Fourier series. They are system of functions in Hilbert spaces that provide numerically stable methods for finding overcomplete decompositions of vectors and such are useful tools in various signal processing applications, data compression, wireless communications, and so on [2–4]. Frames in finite dimensional Hilbert spaces have become of interests for many of researches [5, 6]. One of the important subjects in this area is the way for constructing such frames. Some methods of construction finite tight frames are stated by researchers [7–9].LetN be a positive integer. A sequence of vectors {
f
i
}
i
∈
I in Hilbert space R
N is said to be aframe (see also [10]) for R
N if there exist constants A and B such that 0
<
A
≤
B
<
∞ and
(1)
A
∥
f
∥
2
≤
∑
i
∈
I
‍
|
〈
f
,
f
i
〉
|
2
≤
B
∥
f
∥
2
∀
f
∈
R
N
.
The numbers A and B are calledframe bounds and they are not unique. The frame {
f
i
}
i
∈
I is said to betight (or A-tight) if A
=
B. In this case, A is said to be theframe constant and it is aParsval frame, if A
=
B
=
1. When the index set I is a finite set, the frame will be calledfinite. Anormalized frame orunit norm frame is the one in which elements have the norm one.If only the right side of the inequalities (1) holds, then {
f
i
}
i
∈
I is called aBessel sequence and if {
f
i
}
i
∈
I is a normalized Bessel sequence in R
N, then {
f
i
}
i
∈
I is finite sequence [5]. According to this, our frame will be the form {
f
i
}
i
=
1
M whenever M is some positive integer. Also we will replace l
2
(
I
) by R
M. To each Bessel sequence {
f
i
}
i
=
1
M corresponds an operator
(2)
T
:
R
N
⟶
R
M
T
(
f
)
=
{
〈
f
,
f
i
〉
}
i
=
1
M
calledanalysis operator which is well-defined and bounded operator. Its adjoint is the operator
(3)
T
*
:
R
M
⟶
R
N
T
*
(
{
c
i
}
i
=
1
M
)
=
∑
i
=
1
M
‍
c
i
f
i
,
called thesynthesis operator. If {
f
i
}
i
=
1
M is a frame with frame bounds A and B, then the operator
(4)
T
*
T
:
R
N
⟶
R
N
,
T
*
T
(
f
)
=
∑
i
=
1
M
‍
〈
f
,
f
i
〉
f
i
is called theframe operator of the frame {
f
i
}
i
=
1
M. It is a positive, self-adjoint, bounded, and hence invertible operator with the inverse (
T
*
T
)
-
1. Benedetto and Fickus in [5] have proved that if {
f
i
}
i
=
1
M is a normalized A-tight frame for a N-dimensional Hilbert space H, then A
=
M
/
N.In this paper, we address the question of how to efficiently construct unit norm tight frame. After reviewing known results about the Spectral Tetris Construction and introducing the Spectral Hadamard-Tetris Construction in Section2, our main result in Section 3 presents a way to construct unit norm tight frames that we call Hadamard-Tetris Construction. In Section 4, we introduce another version of Hadamard-Tetris which can be used to construct unit norm frames with different eigenvalues for the frame operator. We give necessary condition for this version of Hadamard-Tetris to produce the desired frames.


## 2. Special Hadamard-Tetris Construction

In [11] by using the Schur-Horn Theorem, the authors have shown how to construct every possible frame in which frame operator has a given spectrum and in which vectors are of given prescribed norms, but their method is complex. In [12], the authors have presented another construction of unit norm frames which is called “Spectral Tetris Construction” (STC). Spectral Tetris is a flexible and elementary method to construct unit norm frames with a given frame operator, having all of its eigenvalues greater than or equal to two. But that way is limited to the case of frames with M elements for R
N in which M
≥
2
N. However, they extended the existing construction to unit norm tight frame of redundancy less than two [13], but those frames are in C
N not in R
N.In this paper, we implement an algorithm which is named Hadamard-Tetris for the construction of unit norm tight frames. Hadamard-Tetris constructs synthesis matrixN
×
M with unit norm columns in which rows are pairwise orthogonal and square sum to M
/
N. By this construction, the frame operator is (
M
/
N
)
I. The main advantage here is given an elementary and easily implementable algorithm for constructing frames.In our way, the assumption on the spectrum of the unit norm tight frame(
M
/
N
≥
2
) in STC can be dropped and construct unit norm tight frame for R
N with M elements, where M and N are positive integers and satisfy the following condition.If we can decomposeM as K
=
M
-
N
+
1 summation d
i  (
1
≤
i
≤
K
), that is, M
=
∑
i
=
1
K
d
i, which there exist Hadamard matrices of sizes d
i’s and they satisfy the condition
(5)
(
i
-
1
)
M
M
-
N
≤
∑
j
=
1
i
‍
d
j
<
i
M
M
-
N
1
≤
i
≤
K
-
1
,
then there exists a unit norm tight frame for R
N with sparsity at most ∑
j
=
1
K
d
j
2.A frame constructed via the Hadamard-Tetris construction is called Hadamard-Tetris frame.Aside from the fact that Hadamard-Tetris frames are easy to construct, their major advantage for applications is the sparsity of their synthesis matrices. This sparsity is dependent on the decomposition ofM.In our construction for any positive integersM and N  (
M
>
N
), we put K
=
M
-
N
+
1 and if we could decompose M as K summation of power of two, then we give a unit normalized tight frame for R
N with M elements. Hence K has minimum value. If N
=
∑
{
i
=
0
}
t
a
i
2
i is the binary representation of N, where a
i’s are 0 or 1, then ∑
{
i
=
0
}
t
a
i
≤
K.In special case, whenM
=
2
N
-
2, we can construct synthesis matrix T
* of size N
×
M which has f
i’s as its columns as in Algorithm 1.Algorithm 1:The HTC(I) algorithm for constructing a unit norm tight frame with (
2
N
-
2
)-elements for R
N.
HTC(I): Hadamard-Tetris construction
Parameter:
(i) DimensionN
∈
N.
Algorithm:
(1) Forj
=
1 to N
-
1
(2)x
j
=
1
-
j
N.
(3)f
2
j
-
1
=
x
j
e
j
+
1
-
x
j
e
j
+
1.
(4)f
2
j
=
x
j
e
j
-
1
-
x
j
e
j
+
1.
(5) end.
Output:
(i) unit norm tight frame{
f
j
}
j
=
1
2
N
-
2 for R
N.Theorem 1.
LetN be a positive integer number. Then the sparsest synthesis matrix of the (
2
N
-
2
)-element Hadamard-Tetris unit norm tight frame for R
N which consists of N
-
1 blocks of size 2 can be constructed by HTC(I) and its sparsity is 4
(
N
-
1
).Proof.
LetM
=
2
N
-
2. By the construction of HTC(I), in lines (3) and (4), f
i’s are normalized. We should show that the square norm of each row of synthesis matrix is M
/
N. It is clear that the square norm of the first row of the matrix is M
/
N and, in the last row, since x
N
-
1
=
1
/
N, the square norm of the last row is
(6)
2
(
1
-
1
N
)
=
2
N
-
2
N
=
M
N
.
Also, for2
≤
j
≤
N
-
1, the square norm of jth row is
(7)
2
(
1
-
x
j
-
1
)
+
2
x
j
=
2
(
j
-
1
N
)
+
2
(
1
-
j
N
)
=
2
N
-
2
N
=
M
N
.
In this construction, synthesis matrix of frame consists of N
-
1 blocks of size 2, so the sparsity of the matrix is 4
(
N
-
1
).In [14], Casazza et al. proved that the algorithm STC can be performed to generate a unit norm tight frame of M vectors in R
N if and only if λ
≔
M
/
N or λ is of the form λ
=
(
2
L
-
1
)
/
L, for some positive integer L. Whereas we exhibit an algorithm that utilizes matrices of size 2 such as
(8)
[
x
x
1
-
x
-
1
-
x
]
,
used in the construction of STC. For example, for M
=
4 and N
=
3, the matrix
(9)
[
2
3
2
3
0
0
1
3
-
1
3
1
3
1
3
0
0
2
3
-
2
3
]
is synthesis matrix of R
3.Example 2.
IfN
=
4 and M
=
6, then
(10)
[
3
4
3
4
0
0
0
0
1
4
-
1
4
1
2
1
2
0
0
0
0
1
2
-
1
2
1
4
1
4
0
0
0
0
3
4
-
3
4
]
is synthesis of 6-elements for R
4.


## 3. Hadamard-Tetris Frame

In this section we provide a new method for constructing finite normalized tight frames (FNTFs). In brief, we want to constructN
×
M synthesis matrix T
* which has(i)
columns of unit norm;
(ii)
orthogonal rows, meaning that the frame operatorT
*
T is diagonal;
(iii)
rows of constant norm, meaning thatT
*
T is a constant multiple of the identity matrix.The Hadamard-Tetris Construction (HTC) is capable of constructing unit norm tight frames, with the number of elements that decompose asd
i  (
1
≤
i
≤
M
-
N
+
1
). It constructs the synthesis matrices of such frames by successively filling of size d
i of M
-
N
+
1 blocks. In this construction, we use altered Hadamard matrices.The importance of Hadamard matrices to our construction stems from the fact that they have orthogonal rows and columns and that all entries have the same modulus. In the course of the construction, we will have to alter the row norms of the Hadamard matrices by multiplying rows with appropriate constants. While this will destroy the pairwise orthogonality of the columns, it will preserve the pairwise orthogonality of the rows, which is the crucial feature for our construction to work.Definition 3.
Given positive integersM and N, we denote a matrix by H
d or call it a H
d block, if it is derived from a Hadamard matrix of size d by multiplying the entries of the jth row of Hadamard matrix by M
/
N
d for j
=
2
,
…
,
d
-
1 and the entries of the first and the last row of Hadamard matrix by r
1 and r
d and if it has normalized columns. We call r
1 and r
d the first and the last correction factor of H
d, respectively.Note that the row norm of aH
d block equals M
/
N, except possibly for the first and the last rows. We want to present an algorithm following the lines of Example 4; that is, we want to compose the desired synthesis matrix which consists of square blocks in which first and last rows successively overlap. If we use K square matrix as building blocks of the N
×
M synthesis matrix, then, due to the overlapping, we have M
=
N
+
(
K
-
1
).It is perhaps most instructive to first look at the example of the construction that we are going to introduce in this section.Example 4.
We construct a 6-elements unit norm tight frame inR
5. We can start filling the desired 5
×
6 synthesis matrix with an altered 4
×
4 Hadamard matrix in the upper left corner. The alteration we make is to multiply the entries of the first row by 3
/
10 in size to make the first row have the desired norm 6
/
5. We multiply the second and the third rows of 4
×
4 Hadamard matrix by 3
/
10 to make the norm of those equal to 6
/
5.
To get normalized column, we multiply the forth row of the4
×
4 Hadamard matrix by 1
/
10. At this point, we have constructed the first three rows and the first four columns of the desired synthesis matrix:
(11)
[
3
10
3
10
-
3
10
3
10
0
0
-
3
10
3
10
-
3
10
-
3
10
0
0
3
10
-
3
10
-
3
10
-
3
10
0
0
1
10
1
10
1
10
-
1
10
·
·
0
0
0
0
·
·
]
.
Note that, so far, we have constructed a matrix in which first four rows are orthogonal, no matter how we keep filling the first four rows. The fourth row at this point has norm2
/
5, while we need to make it have norm 6
/
5.
We can insert altered2
×
2 Hadamard matrix in the same fashion as above. To do this, we would multiply its first row by the factor 2
/
5 in size to have the forth row of the synthesis matrix square sum to 6
/
5 and its second row by the factor 3
/
5 to get
(12)
[
3
10
3
10
-
3
10
3
10
0
0
-
3
10
3
10
-
3
10
-
3
10
0
0
3
10
-
3
10
-
3
10
-
3
10
0
0
1
10
1
10
1
10
-
1
10
2
5
-
2
5
0
0
0
0
3
5
3
5
]
.
The latter matrix is the synthesis matrix of the desired frame, since its columns are normalized and its rows are pairwise orthogonal and square sum to 6
/
5.The next theorem is the main theorem of this section.Theorem 5 (main theorem).
LetM and N  (
M
>
N
) be positive integers and K
=
M
-
N
+
1. Furthermore, assume that M can be decomposed as M
=
∑
j
=
1
K
‍
d
j such that, for each 1
≤
i
≤
K
-
1,
(13)
(
i
-
1
)
M
M
-
N
≤
∑
j
=
1
i
‍
d
j
<
i
M
M
-
N
,
and there exist Hadamard matrices of sizes d
i’s. Then HTC(II) gives a unit normalized tight frame for R
N with M elements.In special case, whenM
-
N
=
1, then the condition on d
i’s is confirmed automatically. Indeed, if d
1 is selected such that 0
<
d
1
<
M, then 0
<
d
2
=
M
-
d
1
<
M.Corollary 6.
IfM
=
d
1
+
d
2 such that there exist Hadamard matrices of sizes d
1 and d
2, then the synthesis matrix of the M elements for R
M
-
1 can be constructed via HTC(II).To prove Theorem5, we need to collect some information about the first and the last correction factors of H
d
i’s.In construction of synthesis matrix of sizeN
×
M, we use K
=
M
-
N
+
1 blocks of sizes d
i’s (
1
≤
i
≤
K
), where M
=
∑
i
=
1
K
d
i.As was mentioned, each block isH
d
i that derived from the Hadamard matrix of size d
i. If the factor that multiplies the entries of the jth row of Hadamard matrix of size d
i is shown by r
j
,
i, where 1
≤
j
≤
d
i, then, for each block of size d
i, the correction factor is
(14)
r
j
,
i
2
=
M
N
d
i
(
2
≤
j
≤
d
i
-
1
)
.The last row of a block and the first row of the following block appear in the same row of the synthesis matrix and while the last correction factor is chosen to ensure normalized columns, the following first correction factor is chosen to guarantee that the rows of the synthesis matrix have square normM
/
N.Hence, we have the following relationships forr
1
,
i and r
d
i
,
i, where 1
≤
i
≤
K.Lemma 7.
Ifr
1
,
i and r
d
i
,
i are the first and the last correction factors, respectively, then
(15)
r
d
i
,
i
2
=
1
-
r
1
,
i
2
-
M
N
+
2
M
N
d
i
,
r
1
,
i
+
1
2
=
1
d
i
+
1
(
M
N
-
d
i
r
d
i
,
i
2
)
.Proof.
The correction factors of second row to(
d
i
-
1
)th row of H
d
i are
(16)
r
j
,
i
=
M
N
d
i
(
2
≤
j
≤
d
i
-
1
)
.
Since norm of each column ofH
d
i must be one, we have
(17)
r
1
,
i
2
+
(
d
i
-
2
)
M
N
d
i
+
r
d
i
,
i
2
=
1
and so on
(18)
r
d
i
,
i
2
=
1
-
r
1
,
i
2
-
M
N
+
2
M
N
d
i
.
Also the last correction factor ofH
d
i and the first correction factor of H
d
i
+
1 must be chosen such that the square norm of that row is M
/
N. Hence
(19)
d
i
r
d
i
,
i
2
+
d
i
+
1
r
1
,
i
+
1
2
=
M
N
and so on
(20)
r
1
,
i
+
1
2
=
1
d
i
+
1
(
M
N
-
d
i
r
d
i
,
i
2
)
.By combining formulas (15) in Lemma 7, we get the following recursive relations:
(21)
r
1
,
i
+
1
2
=
d
i
d
i
+
1
(
M
N
+
r
1
,
i
2
-
1
)
-
M
N
d
i
+
1
,
r
d
i
+
1
,
i
+
1
2
=
d
i
d
i
+
1
r
d
i
,
i
2
-
M
-
N
N
+
M
N
d
i
+
1
for 1
≤
i
≤
K
-
1.Lemma 8.
Ifr
1
,
i and r
d
i
,
i are the first and the last correction factors of H
d
i, respectively, then
(22)
r
1
,
i
2
=
1
N
d
i
(
(
M
-
N
)
∑
j
=
1
i
-
1
‍
d
j
-
(
i
-
2
)
M
)
(
i
≥
2
)
,
r
d
i
,
i
2
=
1
N
d
i
(
i
M
-
(
M
-
N
)
∑
j
=
1
i
‍
d
j
)
(
i
≥
1
)
.Proof.
We prove these by induction oni. The first steps of the induction are trivially true. Assume that the identities are true for i. For the case i
+
1, the following identities hold by using formulas (21) and the induction hypothesis:
(23)
r
1
,
i
+
1
2
=
d
i
d
i
+
1
(
M
N
+
r
1
,
i
2
-
1
)
-
M
N
d
i
+
1
=
d
i
d
i
+
1
(
M
N
+
(
∑
j
=
1
i
-
1
d
j
d
i
)
(
M
-
N
N
)
00000000
-
(
i
-
2
d
i
)
(
M
N
)
-
1
(
∑
j
=
1
i
-
1
d
j
d
i
)
)
-
M
N
d
i
+
1
=
1
N
d
i
+
1
(
d
i
M
+
(
M
-
N
)
∑
j
=
1
i
-
1
‍
d
j
0000000000
-
(
i
-
2
)
M
-
N
d
i
-
M
∑
j
=
1
i
-
1
‍
)
=
1
N
d
i
+
1
(
(
M
-
N
)
∑
j
=
1
i
‍
d
j
-
(
i
-
1
)
M
)
,
(24)
r
d
i
+
1
,
i
+
1
2
=
d
i
d
i
+
1
r
d
i
,
i
2
-
M
-
N
N
+
M
N
d
i
+
1
=
d
i
d
i
+
1
(
(
i
d
i
)
(
M
N
)
-
(
∑
j
=
1
i
d
j
d
i
)
(
M
-
N
N
)
)
-
M
-
N
N
+
M
N
d
i
+
1
=
1
N
d
i
+
1
(
i
M
-
(
M
-
N
)
∑
j
=
1
i
‍
d
j
00000000000
-
d
i
+
1
(
M
-
N
)
+
M
∑
j
=
1
i
‍
)
=
1
N
d
i
+
1
(
(
i
+
1
)
M
-
(
M
-
N
)
∑
j
=
1
i
+
1
‍
d
j
)
.Now we are ready to prove the main Theorem5.Proof.
We check that synthesis matrix constructed by HTC(II) has row norm equalM
/
N and columns are normalized. First, we show that each row of synthesis matrix, which is constructed via HTC(II), has square norm M
/
N. It is enough to show that the last row of H
d
i together with the first row of H
d
i
+
1 makes square norm M
/
N. In other words,
(25)
d
i
r
d
i
,
i
2
+
d
i
+
1
r
1
,
i
+
1
2
=
M
N
.
By Lemma8, we have(26)
d
i
r
d
i
,
i
2
+
d
i
+
1
r
1
,
i
+
1
2
=
1
N
(
i
M
-
(
M
-
N
)
∑
j
=
1
i
‍
d
j
0000000
+
(
M
-
N
)
∑
j
=
1
i
‍
d
j
-
(
i
-
1
)
M
)
=
M
N
.
Now, we show each column of synthesis matrix that is constructed with HTC(II) has norm 1; that is,(27)
r
1
,
i
2
+
(
d
i
-
2
)
M
N
d
i
+
r
d
i
,
i
2
=
1
By Lemma 8, we have
(28)
r
1
,
i
2
+
r
d
i
,
i
2
=
1
N
d
i
(
(
M
-
N
)
(
∑
j
=
1
i
-
1
‍
d
j
-
∑
j
=
1
i
‍
d
j
)
00000000
+
M
(
-
i
+
2
+
i
)
(
∑
j
=
1
i
-
1
‍
d
j
-
∑
j
=
1
i
‍
d
j
)
)
=
-
(
M
-
N
N
)
+
2
M
N
d
i
=
1
-
(
d
i
-
2
)
M
N
d
i
.
We have to ensure that the last correction factor of the final block inserted into the synthesis matrix equalsM
/
N
d
K (in other words, the next first correction factor would be zero, but we have arrived at this point where the algorithm terminates).
In Algorithm2, line (9), when i
≔
K and t
≔
d
K, we have
(29)
r
d
K
,
K
=
1
N
d
K
(
K
M
-
(
M
-
N
)
∑
j
=
1
K
‍
d
j
)
=
M
N
d
K
and in line (4), for i
≔
K
+
1, we have r
1
,
d
K
+
1
=
0.Algorithm 2:The HTC(II) algorithm for constructing a unit norm tight frame with M elements for R
N.
HTC(II): Hadamard-Tetris Construction
Parameters:
(i) DimensionN
∈
N.
(ii) Number of frame elementsM
∈
N such that decompose as M
=
∑
i
=
1
K
‍
d
i, where K
=
M
-
N
+
1.
(iii) Hadamard matrices,H
d
i
=
[
a
k
j
(
d
i
)
]
1
≤
k
,
j
≤
d
i of size d
i for i
=
1
,
…
,
K.
Algorithm:
(1)s
=
0, m
=
0.
(2)  Fori
=
1 to K do
(3)      Fort
=
1 to d
i do
(4)
r
1
,
i
=
1
N
d
i
(
(
M
-
N
)
∑
j
=
1
i
-
1
d
j
-
(
i
-
2
)
M
).
(5)
r
1,1
=
M
N
d
1.
(6)For j
=
2 to d
i
-
1 do
(7)    r
j
,
i
=
M
N
d
i.
(8)end.
(9)
r
d
i
,
i
=
1
N
d
i
(
i
M
-
(
M
-
N
)
∑
j
=
1
i
d
j
).
(10)
f
t
+
m
=
∑
j
=
1
d
i
a
t
j
(
d
i
)
r
j
,
i
e
s
+
j.
(11)      end.
(12)m
=
m
+
d
i.
(13)s
=
s
+
d
i
-
1.
(14) end.
Output:
(i) unit norm tight frame{
f
j
}
j
=
1
M for R
N.Note that if we do a HTC(II) as in Example4 with K altered Hadamard matrices of sizes d
1
,
…
,
d
K, then the sparsity of the synthesis matrix is ∑
i
=
1
K
d
i
2.The next lemma states that if we construct synthesis matrix with blocks of sizesd
1
,
d
2
,
…
,
d
K, each condition on d
i must be established for d
K
-
i
+
1 and vice versa.Lemma 9.
LetM and N be positive integers with M
>
N, K
=
M
-
N
+
1, and M
=
∑
j
=
1
K
d
j such that d
j’s are satisfied in inequalities:
(30)
(
i
-
1
)
M
M
-
N
<
∑
j
=
1
i
‍
d
j
<
i
M
M
-
N
000000000000000
(
0
≤
i
≤
K
-
1
)
.
Then
(31)
(
i
-
1
)
M
M
-
N
<
∑
j
=
1
i
‍
d
K
-
j
+
1
<
i
M
M
-
N
0000000000000000000
(
0
≤
i
≤
K
-
1
)
.Proof.
Since∑
j
=
1
K
d
j
=
M, so
(32)
∑
j
=
1
i
‍
d
K
-
j
+
1
=
∑
j
=
1
K
‍
d
j
-
∑
j
=
1
K
-
i
‍
d
j
=
M
-
∑
j
=
1
K
-
i
‍
d
j
In the other hand, by replacing i with K
-
i in the inequality (30), we have
(33)
M
M
-
N
(
K
-
i
-
1
)
<
∑
j
=
1
K
-
i
‍
d
j
<
(
K
-
i
)
M
M
-
N
and so on
(34)
M
-
(
K
-
i
)
M
M
-
N
<
M
-
∑
j
=
1
K
-
i
‍
d
j
<
M
-
M
M
-
N
×
(
K
-
i
-
1
)
.
Hence, we have
(35)
M
M
-
N
(
M
-
N
+
i
-
K
)
<
∑
j
=
1
i
‍
d
K
-
j
+
1
<
M
M
-
N
×
(
M
-
N
-
K
+
i
+
1
)
,
which give inequalities (31).Following Lemma9, if T
*
=
[
a
i
j
] is a synthesis matrix of size N
×
M, then F
*
=
[
b
i
j
], where b
i
j
=
a
(
N
-
i
+
1
)
(
M
-
j
+
1
), is also having the same situation.Since Hadamard matrices of the size power of 2 exist, so we use altered Hadamard matrices of size2
s
i, where
(36)
2
s
i
=
max
⁡
⁡
{
2
s
∣
(
i
-
1
)
M
M
-
N
≤
∑
j
=
1
i
-
1
‍
2
s
j
+
2
s
<
i
M
M
-
N
}
,
for 1
≤
i
≤
K
-
1. However, it is provided that there exists a Hadamard matrix of size d
K
×
d
K, with d
K
=
M
-
∑
j
=
1
K
-
1
2
s
j. In this case, the algorithm HTC builds the synthesis matrix of the tight frame as in Example 4 by inserting H
d
i, where d
i
=
2
s
i  (
1
≤
i
≤
K
-
1
) and d
K
=
M
-
∑
j
=
1
K
-
1
2
s
j.


## 4. Spectral Hadamard Tetris Construction

Another case of HTC is the case of unit norm but not necessarily tight frames. Such frames are known to exist, provided that the eigenvalues of the frame operator sum up to the number of frame vectors [15]. In this section, we give a version of Hadamard-Tetris Construction which uses altered Hadamard matrices to construct unit norm frames with a given spectrum of frame operator. Our method cannot construct all such frames. We give necessary condition under which this construction works. To construct unit norm frame with prescribed spectrum, we are looking for a matrix with columns square summing up to 1 and rows square summing up to {
λ
n
}
n
=
1
N. In Algorithm 3, we present a modified Hadamard-Tetris algorithm HTC, allowing the construction of such frames.Algorithm 3:The SHTC algorithm for constructing a unit norm tight frame with M elements for R
N.
SHTC: Spectral Hadamard-Tetris construction
Parameters:
(i) DimensionN
∈
N.
(ii) Number of frame elementsM
∈
N such that decompose as M
=
∑
i
=
1
K
‍
d
i where K
=
M
-
N
+
1.
(iii) eigenvalues{
λ
n
}
n
=
1
N which ∑
n
=
1
N
‍
λ
n
=
M and ∑
j
=
1
t
i
-
i
‍
λ
j
≤
t
i
≤
∑
j
=
1
t
i
-
i
+
1
‍
λ
j where t
i
=
∑
j
=
1
i
‍
d
j and 1
≤
i
≤
K.
(iv) Hadamard matrices,H
d
i
=
[
a
k
j
(
d
i
)
]
1
≤
k
,
j
≤
d
i of size d
i for i
=
1
,
…
,
K.
Algorithm:
(1)s
=
0, m
=
0, t
0
=
0
(2)  Fori
=
1 to K do
(3)t
i
=
∑
j
=
1
i
d
j.
(4)      Fort
=
1 to d
i do
(5)
r
1
,
i
=
1
d
i
(
∑
j
=
1
t
i
-
1
-
(
i
-
2
)
λ
j
-
t
i
-
1
).
(6)For j
=
2 to d
i
-
1 do
(7)    r
j
,
i
=
1
d
i
λ
t
i
-
1
-
(
i
-
1
)
+
j.
(8)end.
(9)
r
i
,
i
=
1
d
i
(
t
i
-
∑
j
=
1
t
i
-
i
λ
j
).
(10)
f
t
+
m
=
∑
j
=
1
d
i
a
t
j
(
d
i
)
r
j
,
i
e
s
+
j.
(11)      end.
(12)m
=
m
+
d
i.
(13)s
=
s
+
d
i
-
1.
(14) end.
Output:
(i) unit norm frame{
f
j
}
j
=
1
M for R
N with eigenvalues {
λ
n
}
n
=
1
N.Given a fixed dimensionN and frame cardinality M, a necessary condition on the prescribed eigenvalues {
λ
n
}
n
=
1
N of the frame operator for SHTC to work is given in the following theorem.Theorem 10.
Let∑
n
=
1
N
λ
n
=
M
=
∑
i
=
1
K
d
i, where K
=
M
-
N
+
1, and there exist Hadamard matrices of sizes d
i’s. Then SHTC can be used to produce unit norm frame for R
N with eigenvalues {
λ
n
}
n
=
1
N if there are some permutations of {
λ
n
}
n
=
1
N and {
d
i
}
i
=
1
K such that, for each i
=
1
,
…
,
K, we have
(37)
∑
j
=
1
t
i
-
i
‍
λ
j
≤
t
i
≤
∑
j
=
1
t
i
-
i
+
1
‍
λ
j
,
where t
i
=
∑
j
=
1
i
d
j.Here, we present an example in which STC does not work whereas SHTC works.Example 11.
There are choices of prescribed eigenvalues which satisfy the conditions of Theorem10 that unit norm frame with given eigenvalues exists, but STC cannot be used to construct such a frame because no rearrangement of eigenvalues satisfies in their conditions. An example of this kind is {
λ
n
}
n
=
1
4
=
{
0.4,2.4,1.1,1.1
} as eigenvalues of frame with 5 elements for R
4.Sometimes, one rearrangement of eigenvalues and dimensions of Hadamard matrices is satisfied in desired condition while another is not. For example, the SHTC cannot be performed for the sequence ofλ
i’s is the given rearrangement 0.4,1.1,1.1,2.4 and d
1
=
4, d
2
=
1. However, rearranging the eigenvalues to the rearrangement 0.4,2.4,1.1,1.1 allows SHTC to construct the desired frame. In this case, its synthesis matrix will be
(38)
[
1
10
1
10
-
1
10
1
10
0
-
6
10
6
10
-
6
10
-
6
10
0
11
40
-
11
40
-
11
40
-
11
40
0
1
40
1
40
1
40
-
1
40
1
]
.So, there is no reason that SHTC works when the eigenvalues are in the monotonic rearrangement.Note that since we make no assumption about the ordering of the sequences{
λ
n
}
n
=
1
N and {
d
i
}
i
=
1
K, we may permute the elements of the sequences in order to make them ready to satisfy in the inequality (37).Given sequences of eigenvalues and{
d
i
}
i
=
1
K, where K
=
M
-
N
+
1 and there exist Hadamard matrices of sizes d
i’s, it may be time-consuming to find permutation of these sequences which satisfy in Theorem 10. Until now, we could not find simple conditions on these sequences that SHTC can be performed. It has been a mystery as to when Hadamard Tetris works and when fails.



---

*Source: 917491-2014-10-27.xml*