#### Termes les plus recherchés

# [PDF](+33👁️) Télécharger DTIC ADA568541: Parametrizing Finite Frames and Optimal Frame Completions pdf

#### Frames are used in many signal processing applications. We consider the problem of constructing every frame whose frame operator has a given spectrum and whose vectors have prescribed lengths. For a given spectrum and set of lengths, we know when such a frame exists by the Schur-Horn Theorem; it exists if and only if its spectrum majorizes its squared lengths. We provide a more constructive proof of Horn's original result. This proof is based on a new method for constructing any and all frames whose frame operator has a prescribed spectrum and whose vectors have prescribed lengths. Constructing all such frames requires one choose eigensteps--a sequence of interlacing spectra--which transform the trivial spectrum into the desired one. We give a complete characterization of the convex set of all eigensteps. Taken together, these results permit us, for the first time, to explicitly parametrize the set of all frames whose frame operator has a given spectrum and whose elements have a givenTélécharger gratuit DTIC ADA568541: Parametrizing Finite Frames and Optimal Frame Completions pdf

PARAMETRIZING FINITE FRAMES AND OPTIMAL FRAME COMPLETIONS

DISSERTATION

Miriam J. Poteet, Civilian

AFIT-ENC-DAM-12-02

DEPARTMENT OF THE AIR FORCE

AIR UNIVERSITY

AIR FORCE INSTITUTE OF TECHNOLOGY

Wright-Patterson Air Force Base, Ohio

DISTRIBUTION STATEMENT A:

APPROVED FOR PUBLIC RELEASE; DISTRIBUTION UNLIMITED

The views expressed in this dissertation are those of the author and do not reflect the official

policy or position of the United States Air Force, the Department of Defense, or the United

States Government.

This material is declared a work of the U.S. Government and is not subject to copyright

protection in the United States.

AFIT-ENC-DAM-12-02

PARAMETRIZING FINITE FRAMES AND OPTIMAL FRAME COMPLETIONS

DISSERTATION

Presented to the Faculty

Graduate School of Engineering and Management

Air Force Institute of Technology

Air University

Air Education and Training Command

in Partial Fulfillment of the Requirements for the

Degree of Doctor of Philosophy

Miriam J. Poteet, B.S., M.S.

Civilian

December 2012

DISTRIBUTION STATEMENT A:

APPROVED FOR PUBLIC RELEASE; DISTRIBUTION UNLIMITED

AFIT-ENC-DAM-12-02

PARAMETRIZING FINITE FRAMES AND OPTIMAL FRAME COMPLETIONS

Miriam J. Poteet, B.S., M.S.

Civilian

Approved:

_ //signed//

Matthew Fickus, PhD (Chairman)

_ //signed//

Mark E. Oxley, PhD (Member)

_ //signed//

Richard K. Martin, PhD (Member)

Accepted:

16 November 2012

Date

16 November 2012

Date

16 November 2012

Date

//signed//

27 November 2012

M. U. Thomas

Dean, Graduate School of Engineering and Management

Date

AFIT-ENC-DAM-12-02

Abstract

Frames are used in many signal processing applications. We consider the problem of

constructing every frame whose frame operator has a given spectrum and whose vectors

have prescribed lengths. For a given spectrum and set of lengths, we know when such a

frame exists by the Schur-Hom Theorem; it exists if and only if its spectrum majorizes

its squared lengths. We provide a more constructive proof of Horn’s original result. This

proof is based on a new method for constructing any and all frames whose frame operator

has a prescribed spectrum and whose vectors have prescribed lengths. Constructing all

such frames requires one choose eigensteps—a sequence of interlacing spectra—which

transform the trivial spectrum into the desired one. We give a complete characterization of

the convex set of all eigensteps. Taken together, these results permit us, for the first time,

to explicitly parametrize the set of all frames whose frame operator has a given spectrum

and whose elements have a given set of lengths. Moreover, we generalize this theory to

the problem of constructing optimal frame completions. That is, given a preexisting set

of measurements, we add new measurements so that the final frame operator has a given

spectrum and whose added vectors have prescribed lengths. We introduce a new matrix

notation for representing the final spectrum with respect to the initial spectrum and prove

that existence of such a frame relies upon a majorization constraint involving the final

spectrum and the frame’s matrix representation. In a special case, we provide a formula

for constructing the optimal frame completion with respect to fusion metrics such as the

mean square error (MSE) and frame potential (FP). Such fusion metrics provide a means

of evaluating the efficacy of reconstructing signals which have been distorted by noise.

IV

Table of Contents

Page

Abstract. iv

Table of Contents. v

I. Introduction. 1

1.1 Major contributions. 3

1.2 Outline. 6

II. Literature Review. 8

2.1 Frames. 9

2.2 Majorization and interlacing . 12

III. Constructing frames of a given spectrum and set of lengths . 15

3.1 The necessity and sufficiency of eigensteps. 17

3.2 Constructing frame elements from eigensteps . 27

IV. Top Kill algorithm and the characterization of the set of all eigensteps. 55

4.1 Preliminaries. 56

4.2 Top Kill and the existence of eigensteps . 64

4.3 Parametrizing eigensteps. 71

V. Completing finite frames . 87

5.1 Preliminaries. 90

5.2 (a,/i)-constructible sequences and Chop Kill. 94

5.3 Parametrizing continued eigensteps.103

VI. Optimal frame completions.124

6.1 Frame metrics.125

6.2 Construction of the optimal (a, yu)-constructible sequence.128

VII. Conclusions and Future Work.137

v

Page

Appendix: MATLAB code.143

Bibliography .148

vi

PARAMETRIZING FINITE FRAMES AND OPTIMAL FRAME COMPLETIONS

I. Introduction

Frames, or redundant sets of vectors in a Hilbert space, have been used in many signal

processing applications and are the subject of the research discussed herein. We begin with

a few important definitions regarding frames. A sequence of vectors F = {f n } N =1 is a frame

in an M-dimensional (real or complex) Hilbert space M m if there exist 0 < A < B < oo

such that

N

A\\f\\ 2 <J]\(f,f n )\ 2 <B\\f\\ 2

72=1

for all / in M m . It is straightforward to show that F is a frame if and only if the F spans

H m , which necessitates M < N. Letting K be either the real or complex field, the synthesis

operator of a sequence of vectors {/„|^ =1 is F : K N —» i M , Fg := Xn=\ g( n )fn- The

corresponding frame operator FF* : W M —> EI M is given by:

N

FF*f = J](f,f n )f n , (1.1)

72=1

where * denotes the Hermitian transpose of F. Viewing as K M , F is the M x N matrix

whose columns are given by the /„’s. The constants A and B are called the lower and upper

frame bounds for F, respectively. Since is finite-dimensional, then the frame bounds

of F are the least and greatest eigenvalues of the frame operator. That is, | is the condition

number of FF* and F is a frame if and only if FF* is invertible.

For a given frame F, the canonical ducdframe F = {f„}^ =v f„ := ( FF*)~ l f, , provides

a means of expressing any / e IHI M as a linear combination of frame vectors, that is:

N

f = FF*f = Y J (fJn)f n . ( 1 . 2 )

72=1

1

The canonical dual frame of F satisfies FF* = I. Unlike bases, frames provide a means

of representing any / e in terms of overcomplete sets of vectors. The fact that frames

may be redundant make them useful in many signal processing applications where data loss

and degradation are concerns [35, 36].

In particular, frames have found a natural application to source coding and robust

transmission. Frames have been shown to provide numerically stable reconstruction and

resilience to additive noise [27]. While not always fully realistic, additive noise can be used

to model channel noise and/or quantization errors which are introduced in analog-to-digital

conversion. In addition to noise, erasures of frame coefficients can also be problematic

when transmitting a signal [13, 26, 31]. The redundancy of frames allows signals in

which data has been lost to be reconstructed in a feasible manner. Such applications have

motived current research efforts to find ways of constructing frames with certain desirable

properties.

The focus of our research is on constructing finite frames for a given spectrum and set

of lengths. This is a generalization of a problem that the field has long been interested in:

constructing unit norm tight frames (UNTFs). A tight frame is one for which A = B. and

a UNTF is a tight frame with the additional condition that ||/„|| = 1 for all n = l,... ,N.

In this dissertation, we show how to explicitly construct all UNTFs and moreover, how to

construct any frame for a given arbitrary spectrum and set of lengths. This theory has also

been generalized to the problem of constructing frame completions', given a preexisting set

of measurements, we add new measurements so that the final frame operator has a given

spectrum and whose added vectors have prescribed lengths. More formally, given an initial

sequence of vectors F N = {f n }^ =l in W M whose frame operator has spectrum [ar m }£f =1 , we

wish to complete the frame by adding P additional measurements in order to construct

F = {fn\^f\ such that \\f N+p \\ 2 = p N+p for all p = 1,... ,P, and such that the new frame

operator of F = {f n )"f p has spectrum \f „\" =v

2

Furthermore, we provide some results on optimal frame completions. For real world

applications, we often want to choose a frame that is optimal with respect to certain criteria.

For example, in cases where part of a signal being transmitted is distorted by noise or lost

due to network errors, an optimal frame would be one that minimizes the reconstruction

error. Goyal, Kovacevic, and Kelner [26] used the mean square error (MSE) as a means of

evaluating the quality of reconstruction in the former case. The MSE is given by:

m .

MSE = cr 2 Tr[(FF*) -1 ] = cr 2 Y — (1.3)

Am

where ] A m }^ = , are the eigenvalues of FF* and cr 2 is the variance of the zero-mean,

independent, identically distributed added noise e = [ei e 2 ... ey] 1 . Since calculating the

MSE involves inverting the frame operator, which can be difficult, the frame potential may

also be used as an alternative notion of the quality of a frame. The frame potential (FP) of

a sequence {/„}^ =| in K N is given by:

M

FP({/„}" i) = Tr[(EF*) 2 ] = d 2 (1.4)

m-\

where again, {A m }^ =1 are the eigenvalues of FF*. It has already been shown that a unit norm

frame minimizes the MSE and FP if and only if it is tight [5, 26]. However, constructing a

UNTF for a given application may not always be achievable if, given an initial frame, one is

restricted to adding only a finite number of new measurements. In such cases, determining

optimality of a frame is not as straightforward. We provide an algorithm for constructing

the optimal frame completion with respect to fusion metrics such as the MSE and FP.

1.1 Major contributions

In this section, we briefly summarize the major contributions that have arisen from

our doctoral studies [8, 24, 25]. Our first major contribution (Section 3.1) is Theorem 2

which characterizes and proves the existence of sequences of vectors that generate a given

sequence of outer eigensteps. In particular, for any {A m j^ =l and {p n }„ =l , every sequence of

3

vectors {/„}^ =1 in H M whose frame operator FF* has spectrum {A m }^ =] and which satisfies

||/„|| 2 = ji n for all n can be constructed by the two-step process given in Theorem 2, and

conversely, any F constructed by this process has {/l,„|ff =l as the spectrum of FF* and

\\fn \\ 2 = Hn for nil n. However, Theorem 2 alone is not an easily implementable algorithm:

Step A requires one to choose a sequence of interlacing spectra which transform the trivial

spectrum into the desired one; Step B requires one to compute orthonormal eigenbases for

each F n . These steps are addressed in Chapters 4 and 3, respectively.

Our second major contribution (Section 3.2) is to provide a more explicit algorithm

for Step B of Theorem 2. Theorem 7 provides a more explicit iterative algorithm for

constructing every sequence of vectors F = {f n }% =l in whose frame operator FF* has

spectrum {A m }^ =1 and which satisfies \\f ,\\ 2 = p n for all n. The proof of Theorem 7 involves

Lagrange interpolating polynomials and a few additional polynomial identities which set it

apart from prior theory. Of particular interest is the construction of UNTFs. While there are

a few algorithms which can construct UNTFs, little up to this point was known about the

manifold of all UNTFs. Two common ways of constructing UNTFs are by (i) truncating

a discrete Fourier transform basis [26] and (ii) using an iterative method called Spectral

Tetris [12]. Our results go far beyond the existing theory in that they not only show how

to construct all UNTFs, but they also show how to explicitly construct every frame whose

frame operator has a given arbitrary spectrum and whose vectors are of given arbitrary

lengths.

The third major contribution (Section 4.2) has been to provide an explicit algorithm,

called Top Kill , for constructing a sequence of inner eigensteps {{/l„ ;m }^ =1 }^ = 0 which satisfy

Definition 12. Given in Theorem 16, this algorithm refines Step A of Theorem 2 by giving

an explicit construction of a feasible set of inner eigensteps whenever {d„}^ =1 majorizes

{p n \tr The Schur-Horn Theorem gives that this set is nonempty if and only if {A n }^ =l

majorizes {p n \ N n=v Horn and Johnson [33] already proved that such a sequence exists,

4

however, their proof is not constructive. The Top Kill algorithm presented not only provides

an alternative proof of Horn and Johnson’s result, but it provides a method to explicitly

construct a sequence of eigensteps as required by Step A of Theorem 2.

Our fourth contribution (Section 4.3) as stated in Theorem 17 gives a complete

characterization of the set of all eigensteps for a given {d„}^ =1 and {p n }^ =v Unlike Top

Kill which gives one strategy for constructing one sequence of eigensteps, Theorem 17

provides an algorithm for constructing all such sequences. We further show in Chapter 4

that the set of all such sequences is convex. Taken together, these results permit us, for the

first time, to explicitly parametrize the set of all frames whose frame operator has a given

spectrum and whose elements have a given set of lengths.

The next two major contributions are results of the frame completion problem; that

is, given a sequence of vectors F N = {f„\* =v we wish to complete the frame by adding

P additional vectors {/n+ p } p p={ such that ||/,' V+/J || 2 = i_i N+p for all p = 1 and such

that the new frame operator of F = {/„}^2j p has spectrum \ A m }^ = ,. In Chapter 5, we

determine what it means for a sequence {A m }^ =l to be (cr,/r)-constructible (Theorem 39)

and show that constructibility relies upon a majorization constraint involving {A m }ff I=i and

the frame’s spectral partition matrix. The second major contribution in Chapter 5 is a

new algorithm called Chop Kill (Theorem 40) which is a generalization of the Top Kill

algorithm in Chapter 4. This algorithm enables us to explicitly construct a valid sequence of

continued outer eigensteps whenever {DS(A)y}4f =1 majorizes {p-N+ P }p =l , be., for any ( a,p )-

constructible sequence. Having a valid sequence of eigensteps, we then return to Step B

of the two-step process and use the algorithm given in Theorem 7 in order to explicitly

construct the added frame vectors {/v+ P } P =1 -

Finally, our last major contribution (Section 6.2) as stated in Theorem 48, is a closed-

form solution for the optimal (a,yu)-constructible sequence in the special case that \p N+f) } l ’ i=l

are all of equal lengths. To prove this result, we measure optimality with respect to

5

majorization, and show that the optimal (o\p)-constructiblc sequence is the the one which

is majorized by all other sequences which can be built from {a m }^ =1 and {p N+p \ F p=v i.e., all

other (a ,//)-constructible sequences.

The following is a list of current publications that have arisen from my PhD studies:

Journal Articles

1. Cahill, Jameson, Matthew Fickus, Dustin G. Mixon, Miriam J. Poteet and Nate

Strawn. “Constructing finite frames of a given spectrum and set of lengths,” to appear

in Applied and Computational Harmonic Analysis, 22 pages (2012).

2. Fickus, Matthew, Dustin G. Mixon, Miriam J. Poteet and Nate Strawn. “Constructing

all self-adjoint matrices with prescribed spectrum and diagonal,” submitted to:

Advances in Computational Mathematics, 20 pages.

Book Chapters

1. Fickus, Matthew, Dustin G. Mixon and Miriam J. Poteet. “Constructing all finite

frames with a given spectrum,” in Finite Frames: Theory and Applications, P. G.

Casazza and G. Kutyniok eds., Birkhauser, pp. 55-107 (2012).

Conference Proceedings

1. Fickus, Matthew, Dustin G. Mixon and Miriam J. Poteet. “Frame completions for

optimally robust reconstruction,” Proceedings ofSPIE, 8138: 81380Q/1-8 (2011).

1.2 Outline

In Chapter 2, we review the relevant background literature of frames, majorization,

and interlacing. In Chapter 3, we present one of our main result (Theorem 2) which

characterizes and proves the existence of sequences of vectors that generate a given

sequence of outer eigensteps. We then present a second major result (Theorem 7)

which provides a more explicit iterative algorithm for constructing every sequence of

6

vectors F = {/„}^ =1 in H, v/ whose frame operator FF has spectrum {/t,„}^ =1 and which

satisfies ||/„|| 2 = n„ for all n. Chapter 4 contains the Top Kill algorithm and a result

(Theorem 17) which gives a complete characterization of the set of all eigensteps, as

needed by Step A of Theorem 2. Finally, we discuss frame completions in Chapters 5

and 6. Specifically, Chapter 5 contains the Chop Kill algorithm and a result (Theorem 39)

which determines when a sequence is (cr, ) u)-constructible. Chapter 6 contains our final

major result (Theorem 48) which is an explicit formula for the optimal (cr,yu)-constructible

sequence in the special case that {jJL N+p } p p=x are all of equal lengths.

7

II. Literature Review

In this chapter, we review the literature that is relevant to our research. In Section 2.1,

we discuss the relevant frame theory literature. Simply stated, frames are redundant sets of

vectors in a Hilbert space. In contrast to unique representation of vectors with respect to a

given basis, frames provide a means of representing any / in W M in terms of overcomplete

sets of vectors. Frames have many useful applications including, but not limited to, their

resiliency to additive noise and quantization [27], and erasures [26].

In Section 2.2, we discuss literature relevant to majorization. Namely, given two

nonnegative nonincreasing sequences [d„}^ =1 and {Hn)„ =v we say that {d„}^ =1 majorizes

U/«C = r denoted {d„}^ =1 > \/J n }^ =r if

n n

V/7 = 1,

n '=1 n '=1

N N

y ^ = y ^ fi n '.

n '=1 «'=1

Hardy et al. discussed many of the main ideas of majorization in their 1934 book

Inequalities [29]. From that point forward, the concepts of majorization have been applied

to a broad spectrum of fields from statistical mechanics to graph theory [2].

Also in Section 2.2, we discuss the background literature of interlacing. We say a

nonnegative nonincreasing sequence [y m [^ =| interlaces on another such sequence {p,„}^ =v

denoted [yS m (" =l E {y,„(^ =l , provided

Pm < 7m ^ Pm -i ^ 7m -i < ■ • • < Pi<7i< P\ < 7\-

Under the convention y M+ i := 0, we have that \p m };jf = , E [y m } ; ^ =l if and only if y m+i < p m <

7 , n for all m = 1, ..., M. In the context of our research, interlacing is applied to the spectra

of partial sums of the frame operator, and is also useful in that it provides an alternative

way of viewing majorization [33].

8

2.1 Frames

Frame theory was first introduced by DufRn and Schaeffer in 1952 in their paper

on nonharmonic Fourier series [20]. The fact that frames may be redundant makes

them useful in many signal processing applications where data loss and degradation are

a concern [35, 36]. In particular, quantization error is introduced in analog-to-digital

conversion, that is, when a signal that is varying continuously is restricted to a set of discrete

values. There, round-off and truncation errors may distort the signal. While not always

realistic, additive noise can be used to model channel noise and/or quantization errors.

Goyal et al. found that consistent reconstruction methods yielded smaller reconstruction

errors than that of classical methods and that UNTFs are optimally robust with respect to

additive noise [26, 27].

Another application of frames is that of data transmission. For example, when data

is transmitted over a communications network such as the internet, it is possible that the

information being transmitted can be distorted or lost due to network errors. When modeled

in terms of frames, this corresponds to erasures , namely having some of the transform

coefficients are lost during the transmission. Erasures of frame coefficients have been

well studied [13, 26, 31]. In particular, it has been shown that UNTFs are useful for data

transmission which is robust against erasures [13]. One useful class of UNTFs in this

setting are harmonic tight frames (HTFs) which are constructed from a discrete Fourier

transform basis [13].

In light of these applications, we often want to choose a frame that is optimal with

respect to certain criteria. The authors of [5, 26, 27] have already explored metrics such

as the MSE (1.3) and FP (1.4) as a means of quantifying reconstruction errors in the

applications mentioned above, and have shown that unit norm frames minimize these

quantities if and only if they are tight [5, 26]. In particular, for an M x N UNTF the

minimum value of the FP is precisely jj- [5]. In regards to channel noise and quantization

9

errors, consistent reconstruction methods were shown to be optimal, with the MSE of the

reconstruction being equal to where cr 2 is the variance of the added noise [27]. UNTFs

are also known as Welch-Bound-Equality sequences since they give equality to the Welch

bound , that is Tr[(FF*) 2 ] = ^ [47, 48]. These sequences are shown to be the optimal

signature sequences in CDMA systems [46].

When considering frames for applications such as those mentioned above, we often

wish to retain control over the spectrum of FF* and the lengths of the frame vectors [24].

Of particular interest is the construction of UNTFs. It is known that the manifold of all real

MxN UNTFs, modulo rotations, has dimension (N—M—l)(M—l) when N > M [22]. When

M = N + 1, it is shown in [26], that such tight frames are essentially unique. Additionally,

it is shown in [43] that explicit local parameterizations of this manifold can be constructed.

Since the columns of F must have unit norm and the rows must be orthogonal, constructing

a UNTF is not an easy task as it involves solving a large system of quadratic equations. In

fact, only a few algorithms exist which can construct examples of such frames, and even

then, they only construct a finite subset of this continuous manifold. Two common ways of

constructing UNTFs are HTFs [26] and iteratively by a method called Spectral Tetris [12].

Tight frames can also be constructed via a method based on alternating projections as

discussed in [45] and by using Householder transformations [23].

Algorithms constructing UNTFs have also been proposed to address the Paulsen

problem : How close is a frame which is almost tight and almost unit norm to some UNTF?

This question arises in applications when given an initial frame, it may be more desirable

to transform the given frame into a UNTF which, as described above, is optimal for a

variety of reasons. It is shown in [11] that for a given unit norm frame, a nearby UNTF can

iteratively be found by a method of gradient descent of the frame potential. Additionally,

Bodmann and Casazza [6] have shown that equal-norm Parseval frames (frames for which

10

A = B = 1) can be constructed via a method based on a system of ordinary differential

equations.

Tight frames can also be constructed from an existing set of vectors. That is, given an

initial sequence of vectors, additional vectors with prescribed norms are added in order to

construct a tight frame. The necessary and sufficient conditions for the existence of such

frames can be found in [39]. In [23], the problem of tight frame completions is considered

as well as finding a lower bound for the number of vectors to add in order to construct a

tight frame. However, as the authors of [23] point out, when the added vectors are required

to be unit norm, the lower bound they propose is not a true lower bound. Massey and

Ruiz [39] considered this problem as well, and calculate the minimum number of vectors

to add regardless of whether they are unit norm or not. Additionally, they provide an

algorithm for constructing a tight frame completion from an initial sequence of vectors.

For real world applications, it may be desirable to complete the frame in such a way

that it is optimal with respect to certain criteria. For example, in cases where part of a

signal being transmitted is distorted by noise or lost due to network errors, an optimal

frame would be one that minimizes the reconstruction error. Constructing a UNTF for a

given application may not always be achievable if one is restricted to adding only a finite

number of new vectors in order to complete the frame. Moreover, in this setting, it is not

straightforward to optimally complete the frame. Massey, Ruiz, and Stojanoff show in [40]

and [41] that determining optimality of a frame completion does not have to be limited to

the MSE and the FP, but rather can be measured with respect to majorization. In short, they

show that optimal frame completions are minimizers of a family of convex functionals,

that includes, but is not limited to the MSE and FP. Algorithms for solving for the optimal

frame completion can be found in [40] and [41]; however, as the authors note in [41], the

algorithm’s performance in cases when a larger number of vectors is added or when the

11

dimension of the space is large is contingent upon a conjecture which they have yet to

prove.

As we will show in the chapters that follow, for the first time, we have been able to go

beyond the existing theory of constructing UNTFs by showing how to explicitly construct

every frame belonging to the manifold of all real UNTFs. Moreover, we provide a partial

solution to the frame completion problem we posed in [24] and present an algorithm for

finding the optimal frame completion in a special case which can be implemented in a finite

number of iterations. Being able to explicitly construct every frame whose frame operator

has a given arbitrary spectrum and whose vectors are of given arbitrary lengths requires

existing theory of majorization and the Schur-Hom Theorem which are discussed in the

following section. Relevant interlacing literature is also discussed.

2.2 Majorization and interlacing

Majorization arises in a variety of contexts including combinatorial analysis, matrix

theory, numerical analysis, and statistics just to name a few [2, 29]. Here, we are interested

in how the majorization inequalities apply to matrix theory. Specifically, the concept of

majorization was used by Schur in [42] where he showed that the spectrum of a self-

adjoint positive semidefinite matrix necessarily majorizes its diagonal entries. Some

time later, Horn [32] proved the converse: if { A n then there exists a self-

adjoint matrix that has [T„}^ =1 as its spectrum and {ju„}^ =l as its diagonal [32]. Combining

these two results gives the Schur-Hom Theorem which states that there exists a positive

semidefinite self-adjoint matrix with spectrum | A n }^ = t and diagonal entries {jj„} n =1 if an d

only if > {^n)n=v Alternative proofs of this theorem are given in [37].

Existence of frames with predefined lengths have been studied in [10, 21]. In regards

to tight frames, Casazza et al. gave necessary conditions upon a set of lengths , to

prove existence of tight frames for which ||/J,|| = /j n for all n. Moreover, it is shown that

for any set of lengths {n„}„ =l which satisfy the fundamental inequality , max„ =1 jv(/u) <

12

there exists a tight frame for which |[/„j = //„ for all n. Viswanath and

Anantharam [46] independently discovered the fundamental inequality when constructing

optimal signature sequences for CDMA systems. The connection between constructing

optimal CDMA signature sequences and the Schur-Horn Theorem is discussed in [44], and

finite-step algorithms for constructing such sequences are given.

In context of our research, by applying the Schur-Horn Theorem to the Gram matrix

F*F, whose diagonal entries are given by {||/„|| 2 }^ =1 and whose spectrum is ]d„}^ =1 , we are

able to determine when a frame with prescribed spectrum and lengths exists. Here it is

important to note that the spectrum of the Gram matrix F*F is a zero-padded version of the

spectrum {T m }^ =1 of the frame operator FF*. In [1], Antezana el al. make the connection

between the Schur-Horn Theorem and majorization explicit, extending the Schur-Horn

Theorem to give conditions on the existence of frames with prescribed norms and frame

operator FF*. This connection is also made clear in [45]. Majorization also plays a role in

the frame completion problem and is used to determine which frames can be built from a

preexisting set of vectors.

Also of interest is the problem of explicitly constructing frames which satisfy the

Schur-Horn Theorem. Algorithms relying on Givens rotations [14, 15, 18, 19] have been

used to produce self-adjoint matrices with a given majorized diagonal. Dhillon el al ., in

particular, improve upon the Chan-Li [15] and Bendel-Mickey [4] algorithms and present

more generalized versions of these algorithms which have the ability of constructing a

much larger subset of the corresponding manifold of desired matrices. Chu [16] also

considered constructing such matrices via a lift-and-projection method and a projected

gradient method. Each of these methods provides a more constructive proof of Horn’s

original result [32]. In the remainder of this section, we discuss interlacing and its relevance

to majorization.

13

Interlacing inequalities arise when considering the relationship among eigenvalues

of principle submatrices [34, 49] and have also been applied to matrices associated with

graphs [28]. Interlacing is also useful in that it provides an alternative way of viewing

majorization [33]. Here we consider the inverse eigenvalue problem which involves

reconstructing a matrix from prescribed spectral data. Inverse eigenvalue problems not

only pose spectral constraints, but also structural constraints upon a solution matrix. A

survey of how interlacing applies to these types of problems can be found in [7], and more

recently in [17].

For our research, interlacing comes into play by considering partial sums of the frame

operator (3.4). First let {A„ ;m )^ =l and {A n+Um }^ =1 denote the spectrum of F n F* and F n+l F* +v

respectively. Here, F n denotes the Mxn submatrix of the MxN matrix F obtained by taking

its first n columns. By applying a classical result in [33] to F n+] F* +] = F n F* + f n+l f* +v

where f n+l f* +l is a rank-one positive operator, it can be shown that {A n+ interlaces

with {/l„ ;m }^ =| . Another result of Horn and Johnson, which will be revisited in Chapters 3

and 4, states that given sequences { A „}^ = , and , such that [d„}^ =1 > !/./„}') ,, there

exists a sequence {X n }^=l such that {d«}^ =1 interlaces with {A n }^ and {d,,}^ 1 majorizes

{P3].

14

III. Constructing frames of a given spectrum and set of lengths

In this chapter, we provide an algorithm for how to explicitly construct every frame

whose frame operator has a given arbitrary spectrum and whose vectors are of given

arbitrary lengths. The major results are Theorem 2, which gives a two-step algorithm for

constructing all such frames, and Theorem 7, which makes Step B of Theorem 2 much

more explicit and implementable.

In order to construct all such frames, we make use of the existing theory of

majorization and the Schur-Horn Theorem. Namely, given two nonnegative nonincreasing

sequences {A n }^ = 1 and {p„}^ =l , recall that {A„}% =1 majorizes {//„}",, denoted {A n }^ =l >

, if

n n

n'>Yj^n' Vft = 1, . . . ,iV - 1, (3.1)

n'—\ n'= 1

N N

X An ' = ( 3 -2)

n '=1 n '=1

One of Schur’s results stated that the spectrum of a self-adjoint positive semidefinite matrix

necessarily majorizes its diagonal entries [42]. Some time later, Horn showed that if

{/t„}^ =| > {p n }^ =l , then there exists a self-adjoint matrix that has {d„}^ =1 as its spectrum and

{yu„}^ =1 as its diagonal [32]. Combining these two results gives the Schur-Horn Theorem:

Schur-Horn Theorem. There exists a positive semidefinite self-adjoint matrix with

spectrum { A n , and diagonal entries {p n }^ ={ if and only if{A n }^ =l > {p„}^ =] .

By applying this theorem to the Gram matrix F*F, whose diagonal entries are given

by {||/„|| 2 }" j and whose spectrum is [T„}^ =1 , we are able to determine when a frame with

prescribed spectrum and lengths exists. Here it is important to note that the spectrum of the

Gram matrix is a zero-padded version of the spectrum {A m \ M =] of the frame operator FF*.

The only difference between the eigenvalues of the Gram matrix and the frame operator is

zero eigenvalues; that is, A„ = 0 for M < n < N.

15

For the current research, we consider an alternative approach to majorization which

involves the repeated application of eigenvalue interlacing [33]. Recall that we say a

nonnegative nonincreasing sequence {y,„)^ =| interlaces on another such sequence {/3„,}^ =l ,

denoted {/3 m (" =l E {y,„};Jf =l , provided

Pm < jm ^ Pm- 1 ^ yw-i < ■ ■ ■ < Pi < yi < P\ < yi • (3.3)

Interlacing arises in frame theory in the following context: given any sequence of vectors

F = {/„}^ =1 in W M , then for every n = 1,..., N, we consider the partial sequence of vectors

F n := {/„,}" =1 . Note that F N = F and the frame operator of F n is

n

= (3.4)

n'= 1

Let {/l„ ;m }“ =1 denote the spectrum of (3.4). For any n = l,... ,N - l, (3.4) gives that

F )+1 F* +1 = F n F* + f n+l f* +l . By a result in [33] involving the addition of rank-one positive

operators we know that {A n;m }^ =1 E {A„ +1;m }m=i- That is, the spectrum of the (n + l)st partial

sum interlaces on the spectrum of the nth partial sum. Moreover, if || /„|| 2 = /./„ for all

n = 1 ,... ,N, then for any such n,

M n n

Y = Tr (F„F*„) = Tr(F*F„) = Y \\fA 1 = Y^' (3 ' 5)

m— 1 n '=1 rc'=l

Thus, for any given frame, the sequence of the spectra of its partial frame operators satisfies

a set of interlacing and trace conditions. As such, in order to construct a frame F with

prescribed spectrum and lengths, we give a name to sequences of interlacing spectra that

satisfy (3.5):

Definition 1. Given nonnegative nonincreasing sequences {A m }^ =1 and a sequence

of outer eigensteps is a doubly-indexed sequence of sequences {{A n;m }^ =l )n=o f° r which:

(i) The initial sequence is trivial: Ao ;m = 0, Vm = 1 ,... ,M.

(ii) The final sequence is {A m }^ =1 : A N:m = A m , Vm = 1,..., M.

16

(iii) The sequences interlace: U„_i ;m )" =l E {A n;m }% =1 , Vn=

M n

(iv) The trace condition is satisfied: Fn', Vn = l,...,N.

m -1 n '=1

We refer to the values {{A n - m \^ =] }^ =0 as outer eigensteps since they arise from sums

of outer products of the fjs (frame operators). Every sequence of vectors whose frame

operator has the spectrum {A m }^ =l and whose vectors have squared lengths {p n }„ =i generates

a sequence of outer eigensteps. In the remainder of this chapter, we show that the converse

is also true. To be precise, one of our main results, Theorem 2, provides an algorithm for

explicitly constructing every possible finite frame of a given spectrum and set of lengths,

in terms of such eigensteps.

3.1 The necessity and sufficiency of eigensteps

In this section, our goal is to prove the following theorem:

Theorem 2. For any nonnegative nonincreasing sequences {A m }^ =1 and {p„}„ =l , every

sequence of vectors F = {/„}^ =1 in whose frame operator FF* has spectrum {A m }^ =1

and which satisfies \\f n \\ 2 = Pnfor all n can be constructed by the following process:

A. Pick outer eigensteps {{/l„ ;m [^ =I }^ =() as in Definition 1.

B. For each n = 1 ,,N, consider the polynomial:

M

Pn(x)'-=\\(x- A n - m ). (3.6)

m- 1

Take any f\ 6 such that ||/i|| 2 = p\. For each n = 1 ,...,N - 1, choose any f n+ 1

such that

II PnJr,

n +11

,. . n Pn + \(X )

-hm(x-d)——

Pn(x)

(3.7)

for all A e {A n;m }^ =l , where P n;A denotes the orthogonal projection operator onto the

eigenspace N(TI - F n F*) of the frame operator F n F* of F n = {f n f n n , =1 . The limit

in (3.7) exists and is nonpositive.

17

Conversely, any F constructed by this process has {A m }^ =l as the spectrum of FF* and

||/„|| 2 = Pnfor all n. Moreover, for any F constructed in this manner, the spectrum of F n F*

is U«;mC = , for all n = 1,..., N.

Theorem 2 is not an easily-implementable algorithm nor does it address the existence

of such an F for a given {A m }^ =l and {p n }^ =v Later in this chapter, we will address Step B

and how to compute orthonormal eigenbases for each F n . In the following chapter, we

discuss Step A which requires one choose a valid sequence of eigensteps. In order to prove

Theorem 2, we first prove the following lemma:

Lemma 3. Let {A m }^ =l and {p n }^ =l be nonnegative and nonincreasing, and let {{d„ ;m }^ =1 }^ =0

be any corresponding sequence of outer eigensteps as in Definition 1. If a sequence of

vectors F = {/„}^ =1 has the property that the spectrum of the frame operator F n F* of

F n = {f n 'Yf = i is for all n = 1 then the spectrum of FF* is {A m }^ =l and

WfnW 2 = Pnfor all n = 1

Proof Definition l.(ii) immediately gives that the spectrum of FF* = F N F* N is indeed

! A„i}^ = | = {/l/v; m (^ =l , as claimed. Moreover, for any n = 1,..., N, Definition l.(iv) gives

n M n

Y Ill'll 2 = Tr (W = Tr (F n F* n ) = Y^m = Y^'- W

n '=1 m -1 n '=1

Letting n = 1 in (3.8) gives ||/i|| 2 = p\, while for n = 2,..., N, considering (3.8) at both n

and 77-1 gives

n n -1 n n —1

WfnW 2 = Y Hrf - Y = TjV"' - Y^’ = u

n '=1 n '=1 n '=1 n '=1

The next result gives conditions that a vector must satisfy in order for it to perturb the

spectrum of a given frame operator in a desired way, and was inspired by the proof of the

Matrix Determinant Lemma and its application in [3].

Theorem 4. Let F n = \f,') n n ,=\ an arbitrary sequence of vectors in and let {A n;m }^ =1

denote the eigenvalues of the corresponding frame operator F n F* n . For any choice of f n+ \

18

in M. m , let F, I+1 = {//I'/Jp Then for any A e {A n;m }^ =l , the norm of the projection of f n+i

onto the eigenspace N(/1I - F n F* n ) is given by

l|F M /„ + il| 2 = -lim(x-T)^^,

pfx)

where p n (x) and p n+ \(x) denote the characteristic polynomials of F n F* and F n+l F* +v

respectively.

Proof. For the sake of notational simplicity, we let F := F n , f := f n+ \ and so F n+] F* +| =

FF* + //*. Suppose * is not an eigenvalue of F n+] F* +] . Then:

Pn + i(x) = det(jcl - FF * - ././*)

= det(*I - FF*)det(I - (jcI - FF*)~ X ff*)

= p n (x) det(I - (x\ - FF*) -1 //*). (3.9)

We can simplify the determinant of I - (jcI - FF*) -1 //* by multiplying by certain matrices

with unit determinant:

det(I-(xl-FF*) -1 //*)

= det

= det

= det

VL

I - (x\ - FF*) -1 //*

0

I 0

r i_

I 0 I

r ij[-r

I -(xl - FF*) -1 /

0 1 - f (xl - FF*) -1 /

1 - f*{x\ - FF*) -1 /.

-(xl - FF*) -1 /

1

I 0

-/* 1

v

-(xl -FF*) -1 /

1

jy

v

(3.10)

M

We now use (3.9) and (3.10) with the spectral decomposition FF* = ^ A„ ; „

m= 1

Pn+ l(x) = Pn(x)( 1 - f*(x I - FF*) l f ) = p n (x)[ 1 - V L

A—i r —

I (f,U m )Y

m= 1

A' - /L

(3.11)

19

Rearranging (3.11) and grouping the eigenvalues A = {A n;m }^ =1 according to multiplicity

then gives

Pn+l(x) _

Pn(x)

As such, for any A e A,

M

m -1

X ^n:.m

‘-E

/I'sA

ll^;,r/H 2

x - A'

Vjc i A.

lim(.r - /t) ^" +1 ^ = lim(.r - /l)(l - 'V

x-** p„(x) ^

/I'eA

Il/Wll 2

jc - /!'

= lim

*—>/l

(X -A)- \\P n -J\\ 2 - Yj W P nwf\f

A'? A

x - A

x - A'

= -|l^;4/lP

yielding our claim.

□

While the following two lemmas depend only on basic algebra and calculus, their

results will be used in the proof of Theorem 2.

Lemma 5. If {J3 m }% =1 and {y m )^ =l are real and nonincreasing, then {J3 m }% =l E |y m };|f =l if

and only if

lim (x - < 0 Vm = 1,..., M,

x-^Pm p(x)

M M

where p(x) = r> - f5 m ) and q(x) = IT 1 Tm)*

m=l m=l

Proof (=>) Let {y m }^f =1 interlace on {J3 m }^ =] , and let T = /?,„ for some m = 1,..., M. Letting

L p denote the multiplicity of A as a root of pix), the fact that {[3 m )™ =] E {y m }^f =1 implies that

the multiplicity L q of A as a root of q(x) is at least L p — 1. Moreover, if L q > L p — 1 then

our claim holds at A since

lim(jc - d)-^—- = 0 < 0.

x->a p(x)

Meanwhile, if L q = L p - 1, then choosing m p = min {m : f3 m = d} gives

Pm

> A,

1 <

m

<

m p - 1,

Pm

= A,

VI

a.

s

m

<

nip + Lp 1,

Pm

<A,

TYlp + Lp ^

m

<

M.

20

(3.12)

We now determine a similar set of relations between A and all choices of y m . For 1 < m <

m p - 1, interlacing and (3.12) imply y m > (3 m > A. If instead m p + 1 < m < m p + L p - 1, then

interlacing and (3.12) imply A = fi„, < y m < J3 m -i = A and so y m = A. Another possibility is

to have m p + L p + 1 < m < M, in which case interlacing and (3.12) imply y m < (3 m _\ < A.

Taken together, we have

ym

>4,

1

<

m

<

nip

ym

= 4,

m p + 1

<

m

<

m p

ym

<4,

nip + L p + 1

<

m

<

M.

(3.13)

Note that (3.13) is unlike (3.12) in that in (3.13), the relationship between y m and A is still

undecided for m - m p and m = m p + L p . Indeed, in general we only know y mp > fi m = A,

and so either y„ lp = A or y nip > A. Similarly, we only know y m „+L p < Pm p +L p - i = T, so either

7 hip+l ( , = A or y,„ p+ L p < A. Of these four possibilities, three lead to either having L q = L p + 1

or L q = L p , only the case where y IHp > A and y mp +L p < T leads to our current assumption

that L q = L p — 1. As such, under this assumption (3.13) becomes

(3.14)

ym

>4,

1 <

m

<

nip

ym

= 4,

nip + 1 <

m

<

nip

ym

<4,

m p + Lp <

m

<

M.

We now prove our claim using (3.12) and (3.14):

m p

(x - A) Lp P](.v - y m ) ]~~[ (x - y m )

M

lim(x - A)^-j—- = lim

x->A p(x) x->A

m= 1

M

(x - A) Lp ]~[ (x - 13 m ) Y\ ( X - P>n)

m= 1 m=m p +L p

m p M

I(4 - 7m) f”[ (4 - y m )

m- 1

M

n (4 -js«) n (/{ -^

m— 1

< o.

21

(<=) We prove by induction on M. For M - 1, we have p(x) = x - (3[ and q(x) - x - y i,

and so if

0 > lim (x ~ = lim(oc-jSi)^—^ = lim(jc-yi) = /?i -yi,

x— P\X) x ^Pi \X —Pi) x ~‘

then /?) < yi, and so {y 1 } interlaces on {/?i}, as claimed. Now assume this direction of the

proof holds for M' = 1,..., M - 1, and let {/3 m }^ =l and {y m }ff =1 be real, nonincreasing and

have the property that

lim (x — Pm)~~ 7 ~~ < 0 Vm = 1,. .., M, (3.15)

X~>Pm p{X)

where p{x) and q(x) are defined as in the statement of the result. We will show that {y m }“ =]

interlaces on {/3 m )" =| .

To do this, we consider two cases. The first case is when {/?,„}„=! and {y m (^ =l have

no common members, that is, (3 m ± y m > for all in, in' = 1,..., M. In this case, note

that if J3 m - fi m > for some m ± in' then the corresponding limit in (3.15) would diverge,

contradicting our implicit assumption that these limits exist and are nonpositive. As such,

in this case the values of {/S m }^ =l are necessarily distinct, at which point (3.15) for a given

m becomes:

0>

M

lim (x-/?,„) fl

m— 1

(•^ Pm ')

M

| | (Pm Tm')

m '=1

M

j - [ (J3,n ~P,n’)

m '=1

m'tm

M

| | (Pm Tm')

m '=1

m-1 M

H _ Pm ’) J - [ iPm - Pm ’)

m'=l m'=m+l

(3.16)

Moreover, since /?,„ ± y m , for all in, in', then the limit in (3.16) is nonzero. As the sign of

the denominator on the right-hand side of (3.16) is (-l) m 1 , the sign of the corresponding

22

numerator rs

M

(-1)" 1 = sgn^ (fim - 7m')j = sgn(q(fi m )) Vm = 1

m '=1

Thus, for any m = 2 q(x) changes sign over i], implying by the

Intermediate Value Theorem that at least one of the roots {y m }“ =l of ry(.v) lies in (fi n „fi m _x).

Moreover, since q(x ) is monic, we have lim*-^ q(x) = oo; coupled with the fact that

q(j3 1 ) < 0, this implies that at least one root of q(x) lies in (fi i,oo). Thus, each of the

M disjoint subintervals of (fix, oo) u [u^ =9 (/?„„ fi, n -i)\ contains at least one of the M roots of

q{x). This is only possible if each of these subintervals contains exactly one of these roots.

Moreover, since {y m }^ =1 is nonincreasing, this implies fix < y\ and fi m < y m < fi,„_x for all

m = 2 meaning that {y m }^f =1 indeed interlaces on {fi, n \^ =] .

We are thus left to consider the remaining case where {fi m }^ =1 and {y,„}^ =| share at least

one common member. Fix A such that fi m = A = y IH > for at least one pair m, in' = 1 ,,M.

Let nip = min {m : fi m = 2} and m q = min{»r : y,„ = d}. Let Fix) and Q(x) be (M - 1)-

degree polynomials such that p(x) = (x - A)P(x) and q(x) - (x - A)Q(x). Here, our

assumption (3.15) implies

0 > lim {x -fim)

X

q(x)

p{x)

lim ( x-fi m )

X

(x-A)Q(x)

(x - A)P(x)

lim ( x-fi ,„)

X

Q(x)

P(x)

(3.17)

for all m = 1 Since P(x) and Q(x) satisfy (3.17) and have degree M — 1, our

inductive hypothesis gives that the roots {y m } m ± mq of Q(x) interlace on the roots {fi m } m ± mp of

P(x).

We claim that m q is necessarily either m p or m p + 1, that is, m p < m q < m p + 1. We

first show that m p < m q , a fact which trivially holds for m p = 1. For m p > 1, the fact that

{fim)mtm„ E {y m \m+m q implies that the value of the (m p - l)th member of {y m } m ±m q is at least

that of the (m p - l)th member of {fi m } m ± mp . That is, the (m p - l)th member of {y m } m ± mq is at

least fi mp -\ > A, meaning m p - 1 < m q - 1 and so m p < m q , as claimed. We similarly prove

that m q < m p + 1, a fact which trivially holds for m p = M. For m p < M, interlacing implies

23

that the m p th member of {p m \ m ± m is at least the (m p + l)th member of {y„ t } m ±m q - That is,

the {m p + l)th member of \y m \m±m q is at most p mp+ \ < A and so m p + 1 > m q , as claimed.

Now, in the case that m q = m p , the fact that {J3 m } m * mp E {y m \m±m q implies that

Pm < 7m ^ ^ Pm„+\ ^ 7m p +l ^ Pm p -1 ^ 7m p -1 < ' ' ' < Pi < 7l- (3.18)

Since in this case y ,„ p+ 1 = y m?+ i < d < /? mp _i, the terms = d and y,„ p = y,„ 9 = d can be

inserted into (3.18):

Pm < 7m < • • • < An p +1 ^ 7m p +l < d < d < Pm p -\ < 7m p -l < • • • < /?1 < 7l,

and so {P, n }^ =l E {y m }m=i- In the remaining case where m q = + 1, having E

{7m}m^m ? means that

Pm — 7m — ' ' ' — Pm p + 2 — y ntp+2 — Pm p + 1 — 7m p — Pm p - 1 — 7m p -1 — ' ' ' — I — 7l • (3.19)

Since in this case y3 mp+ , < d < y m? _i = y mp , the terms y mp +i = y m<? = d and p mp = d can be

inserted into (3.19):

Pm — yM — " " " — 7m„+ 2 — Pm„+ 1 — d < d < 7m., — Pin,,- 1 — ' ' ' — /h — 7l

and so {/3 m }“ =1 E {y„,}“ =1 in this case as well.

Lemma 6. Jf{p m \m=\’ {7mlm=i’ an ^ rea ^ an ^ nonincreasing and

□

lim (x - /3 m ) —— = lim (x - /?,„) —-

x^>/3 m p(X) x >/3 m p(x)

dm = 1 ,...,M,

M

M

M

where p{x) = J J(x - p m ), q(x) = J J(x - y m ) and r(x) = [(x - 8 m ), then q(x) = r(x).

m =1 m=l m=l

Proof. Fix any m = l,... ,M, and let L be the multiplicity of p m as a root of p(x). Since

(3.20)

r / a x^W r , 0 /W

lim (x - p m ) —— = lim (x - p m ) —— ,

*->An p(x) x p(x)

where each of these two limits is assumed to exist, then the multiplicities of p m as a roots

of q(x) and r(x) are both at least L - 1. As such, evaluating /th derivatives at p m gives

24

q (l> (j3 m ) = 0 = r il) (J3 m ) for all / = 0,... ,L - 2. Meanwhile, for l = L - 1, l’Hopital’s Rule

gives

lim (x-j3 m )

X >f3m

q(x)

p(x)

q(x ) (x-/3 w ) l

lim -—-

(x - Pm) L p(x)

q {L ~ Y) (J3 m ) L\

(L-l)! pV>(J3 m )

Lg (L - Y) ifi m )

P (L) (fim)

(3.21)

Deriving a similar expression for r(x) and substituting both it and (3.21) into (3.20) yields

q (L ~ l> (fi m ) = r (L ~ l> (fi m ). As such, q (l) (J3 m ) = r a> (J3 m ) for all / = 0,..., L - 1. As this argument

holds at every distinct we see that q(x) - r(x) has M roots, counting multiplicity. But

since q(x) and r(x) are both monic, q(x)-r(x) has degree at most M -1 and so q(x)-r(x) = 0,

as claimed. □

With Theorem 4 and Lemmas 3, 5 and 6 in hand, we are ready to prove the main result

of this section.

Proof of Theorem!. (=>) Let {/t,„}^ =1 and {p n }„ =i be arbitrary nonnegative nonincreasing

sequences, and let F = {f,}^ =i be any s

Lire la suite

- 1.02 MB
- 15

##### Vous recherchez le terme ""

33

63