Document [original]

JOURNAL NAME, VOLUME, NO., DATE 1

Measures of Scalability

Xuemei Chen, Gitta Kutyniok, Kasso A. Okoudjou, Friedrich Philipp, and Rongrong Wang

Abstract—Scalable frames are frames with the property that

the frame vectors can be rescaled resulting in tight frames.

However, if a frame is not scalable, one has to aim for an

approximate procedure. For this, in this paper we introduce

three novel quantitative measures of the closeness to scalability

for frames in finite dimensional real Euclidean spaces. Besides

the natural measure of scalability given by the distance of a

frame to the set of scalable frames, another measure is obtained

by optimizing a quadratic functional, while the third is given

by the volume of the ellipsoid of minimal volume containing

the symmetrized frame. After proving that these measures

are equivalent in a certain sense, we establish bounds on the

probability of a randomly selected frame to be scalable. In the

process, we also derive new necessary and sufficient conditions

for a frame to be scalable.

Index Terms—Convex Geometry, Quality Measures, Parseval

frame, Scalable frame.

I. INTRODUCTION

DURING the last years, frames have had a tremendous

impact on applications due to their unique ability to

deliver redundant, yet stable expansions. The redundancy of

a frame is typically utilized by applications which either

require robustness of the frame coefficients to noise, erasures,

quantization, etc. or require sparse expansions in the frame.

More precisely, letting Φ = {ϕi}M

i=1 ⊂RNbe a frame,

either decompositions into a sequence of frame coefficients

of a signal x∈RN, which is the image of xunder the

analysis operator T:RN→RM,x7→ (hx, ϕii)M

i=1, are

exploited by applications such as telecommunications and

imaging sciences, or expansions in terms of the frame, i.e.,

x=PM

i=1 ciϕiwith suitable choice of coefficients (ci)M

i=1,

are required by applications such as efficient PDE solvers.

Intriguingly, the novel area of compressed sensing is based on

the fact that typically signals exhibit a sparse expansion in a

frame, which is nowadays considered the standard paradigm

in data processing. Some compressed sensing applications also

‘hope’ that the sequence of frame coefficients itself is sparse;

a connection deeply studied in a series of papers on cosparsity

(cf. [18]).

The discussed applications certainly require stability, nu-

merically as well as theoretically. For instance, notice that

most results in compressed sensing are stated for tight frames,

Xuemei Chen and Kasso A. Okoudjou are with the Department of Math-

ematics, University of Maryland, College Park, MD, 20742 USA, email

addresses: [email protected], [email protected]

Gitta Kutyniok and Friedrich Philipp are with the Institut f¨

ur Mathe-

matik, Technische Universit¨

at Berlin, Straße des 17. Juni 136, 10623 Berlin,

Germany, email addresses: [email protected], [email protected]

berlin.de

Rongrong Wang is with the Department of Mathematics, University of

British Columbia, Vancouver, BC, V6T1Z2 Canada, email address: rong-

[email protected]

Manuscript received Month XX, 2014; revised Month XX, 2014.

i.e., for optimal stability. It is known that such frames – in

the case of normalized vectors – can be characterized by

the frame potential (see, e.g., [2], [6], [11]) and construc-

tion methods have been derived (cf. [5] and [21] for an

algebro-geometric point of view). However, a crucial question

remains: Given a frame with desirable properties, can we

turn it into a tight frame? The immediate answer is yes,

since it can easily be shown that applying S−1/2to each

frame element, S:RN→RNdenoting the frame operator

Sx =PM

i=1hx, ϕiiϕi, produces a Parseval frame. Thinking

further one however realizes a serious problem with this

seemingly elegant approach; it typically completely destroys

any properties of the frame for which it was carefully designed

before. Thus, unless we are merely interested in theoretical

considerations, this approach is unacceptable.

Trying to be as careful as possible, the most noninvasive

approach seems to merely scale each frame vector, i.e., multi-

ply it by a scalar. And, indeed, almost all frame properties one

can think of such as erasure resilience or sparse expansions

are left untouched by this modification. In fact, this approach

is currently extensively studied under the theme of scalable

frames.

A. Scalability of Frames

The notion of a scalable frame was first introduced in [17]

as a frame whose frame vectors can be rescaled to yield a

tight frame. Recall that a sequence Φ = {ϕi}M

i=1 ⊂RNforms

aframe provided that

Akxk2≤

i=1 |hx, ϕii|2≤Bkxk2

for all x∈RN, where Aand Bare called the frame bounds.

One often also writes Φfor the N×Mmatrix whose ith

column is the vector ϕi. When A=B, the frame is called

atight frame. Furthermore, A=B= 1 produces a Parseval

frame. In the sequel, the set of frames with Mvectors in

RNwill be denoted by F(M, N). We refer to [9] for an

introduction to frame theory and to [7] for an overview of

the current research in the field.

A frame Φ = {ϕi}M

i=1 for RNis called (strictly)scal-

able if there exist nonnegative (positive, respectively) scalars

{si}M

i=1 such that {siϕi}M

i=1 is a tight frame for RN. The

set of (strictly) scalable frames is denoted by SC(M, N)

(SC+(M, N), respectively). This definition obviously allows

one to restrict the study to the class of unit norm frames

Fu(M, N) := {ϕi}M

i=1 ∈ F(M, N) : kϕik2= 1 ∀i,

and further to substitute tight frame by Parseval frame in the

above definition. Therefore a frame Φ = {ϕi}M

i=1 is scalable if

JOURNAL NAME, VOLUME, NO., DATE 2

and only if there exist non-negative scalars {ci}M

i=1 such that

ΦCΦT=

i=1

ciϕ1ϕT

i=I, where C=diag(ci).(I.1)

In [17], characterizations of SC(M, N)and SC+(M, N),

both of functional analytic and geometric type were derived in

the infinite as well as finite dimensional setting. As a sequel,

using topological considerations, it was proved in [16] that

the set of scalable frames, SC(M, N), is a ‘small’ subset

of F(M, N)when Mis relatively small and a yet differ-

ent characterization using a particular mapping was derived.

This last mapping is closely related to the so-called diagram

vectors/mapping in [10]. In [4], arbitrary scalars in Cwere

allowed, and it was shown that in this case most frames

are either not scalable or scalable in a unique way and, if

uniqueness is not given, the set of all possible sequences of

scalars is studied.

B. How Scalable is a Frame?

However, in the applied world, scalability seems too ideal-

istic, in particular, if our frame at hand is not scalable. This

calls for a measure of ‘closeness to being scalable’. It is though

not obvious how to define such a measure, and one can easily

justify different points of view of what ‘closeness’ shall mean.

Let us discuss the following three viewpoints:

•Distance to SC(M, N).Maybe the most straightforward

approach is to measure the distance of a frame Φ∈

Fu(M, N)to the set of scalable frames:

dΦ:= inf

Ψ∈SC(M,N)kΦ−ΨkF.

This notion seems natural if we anticipate efficient al-

gorithmic approaches for computing the closest scalable

frame by projections onto SC(M, N).

•Conical Viewpoint. Inspired by (I.1), we observe that Φ

is scalable if and only if the identity operator Ilies in

the cone generated by the vectors ϕiϕT

i,i= 1, . . . , M,

which is {PM

i=1 ciϕiϕT

i:ci≥0}. Thus the distance of

Ito this cone seems to be another suitable measure for

scalability of Φ∈ Fu(M, N), and we define

DΦ:= min

C≥0diagonal 

ΦCΦT−I

F,

where k·kFdenotes the Frobenius norm. Note that

the minimum is attained because this polyhedral cone is

closed. This conical viewpoint leads to a computationally

efficient algorithm, since we can recast the problem as a

quadratic program (see Section III-B).

•Ellipsoidal Viewpoint. Finally, one can consider the ellip-

soid of minimal volume (also known as the L¨

owner ellip-

soid) circumscribing the convex hull of the symmetrized

frame of Φ∈ Fu(M, N):

ΦSym := {ϕi}M

i=1 ∪{−ϕi}M

i=1,

which in the sequel we denote by EΦand refer to as

the minimal ellipsoid of Φ. Its ‘normalized’ volume is

defined by

VΦ:= Vol(EΦ)

ωN

where ωNis the volume of the unit ball in RN. By defini-

tion, we have VΦ≤1, and we will later show (Theorem

II.11) that VΦ= 1 holds if and only if the frame Φis

scalable. Hence, yet another conceivably useful measure

for scalability is the closeness of VΦto 1. This ellipsoidal

viewpoint establishes a novel link to convex geometry.

Moreover, it will turn out that this measure is of particular

use when estimating the probability of a random frame

being scalable.

Each notion seems justified from a different perspective, and

hence there is no ‘general truth’ for what the best measure is.

C. Our Contributions

Our contributions are three-fold: First, we introduce the

scalability measures dΦ,DΦ, and VΦ, derive estimates for

their values, and study their relations in Theorems III.3 and

III.4. Second, with Theorems II.11 and IV.1 we provide new

necessary and sufficient conditions for scalability based on the

ellipsoidal viewpoint. And, third, we estimate the probability

of a frame being scalable when each frame vector is drawn in-

dependently and uniformly from the unit sphere (see Theorem

IV.9).

D. Expected Impact

We anticipate our results to have the following impacts:

•Constructions of Scalable Frames: One construction pro-

cedure which is a byproduct of our analysis is to consider

random frames with the probability of scalability being

explicitly given. However, certainly, there is the need for

more sophisticated efficient algorithmic approaches. But

with the measures provided in our work, the groundwork

is laid for analyzing their accuracy.

•Extensions of Scalability: One might also imagine other

methodological approaches to modify a frame to become

tight. If sparse approximation properties is what one

seeks, another possibility is to be allowed to take linear

combinations of ‘few’ frame vectors in the spirit of the

‘double sparsity’ approach in [20]. The introduced three

quality measures provide an understanding of scalability

which we hope might allow an attack on analyzing those

approaches as well.

•-Scalability: One key question even more important to

applications than scalability is that of what is typically

loosely coined -scalability, meaning a frame which is

scalable ‘up to an ’, but which was not precisely de-

fined before. The scalability measures now immediately

provide even three definitions of -scalability in a very

natural way, opening three doors to approaching this

problem.

•Convex Geometry: The ellipsoidal viewpoint of scala-

bility provides a very interesting link between frame

theory and convex geometry. Theorem IV.1 and Theorem

IV.9 are results about frames using convex geometry

tools; Theorem II.13 is a result about minimal ellipsoids

exploiting frame theory. We strongly expect the link

established in this paper to bear further fruits in frame

JOURNAL NAME, VOLUME, NO., DATE 3

theory, in particular the approach of regarding frames

from a convex geometric viewpoint by analyzing the

convex hull of a (symmetrized) frame.

E. Outline

This paper is organized as follows. In Section, II, the three

measures of closeness of a given frame to be scalable are

introduced in three respective subsections and some basic

properties are studied. This is followed by a comparison of

the measures both theoretically and numerically (Section III).

Finally, in Section IV we exploit those results to analyze

the probability of a frame to be scalable. Interestingly, along

the way we derive necessary and sufficient (deterministic)

conditions for a frame to be scalable (see Subsection IV-A).

II. PROPERTIES OF THE MEASURES OF SCALABILITY

In this section, we explore some basic properties of the three

measures of scalibility which we introduced in the previous

section. As mentioned before, we consider only unit norm

frames.

A. Distance to the Set of Scalable Frames

Recall that the measure dΦis defined as the distance of Φ

to the set of scalable frames:

dΦ= inf

Ψ∈SC(M,N)kΦ−ΨkF.(II.1)

Since the set SC(M, N)is not closed (choose Φ∈ SC(M, N),

then (1

nΦ)n∈Nis a sequence in SC(M, N)which converges to

the zero matrix), it is not clear whether the infimum in (II.1) is

attained. The following proposition, however, shows that this

is the case if dΦ<1.

Proposition II.1. If Φ∈ Fu(M, N)such that dΦ<1then

there exists ˆ

Φ∈ SC(M, N)such that kΦ−ˆ

ΦkF=dΦ.

Proof. Let ε=1−dΦ

2, and {Φn}n∈N⊂ SC(M, N)be a

sequence of scalable frames such that kΦ−ΦnkF≤dΦ+ε/n.

The sequence {Φn}n∈Nis bounded as

kΦnkF≤ kΦkF+kΦ−ΦnkF≤√M+dΦ+1−dΦ

so without loss of generality, we assume that {Φn}n∈Ncon-

verges to some ˆ

Φ∈RN×M. It remains to prove that ˆ

Φis

scalable. For this, denote by ϕi,n the i-th column of Φn. Then

kϕi,nk2≥ kϕik2−kϕi−ϕi,nk2≥1−dΦ−ε=ε

for all n≥0and all i∈ {1, . . . , M}. Let Cn=

diag(c1,n, . . . , cM,n)be a non-negative diagonal matrix such

that ΦnCnΦT

n=I. Now, for each j∈ {1, . . . , M}and each

n≥0we have

N=Tr M

i=1

ci,nϕi,nϕT

i,n!=

i=1

ci,nkϕi,nk2≥ε2cj,n.

Therefore, each sequence (ci,n)n∈Nis bounded. Thus, we find

an index sequence (nk)k∈Nsuch that

ci:= lim

k→∞ ci,nk

exists for each i∈ {1, . . . , M}. Now, it is easy to see that

ΦnkCnkΦT

nkconverges to ˆ

ΦCˆ

ΦTas k→ ∞, where C:=

diag(c1, . . . , cm). Hence, ˆ

ΦCˆ

ΦT=I, and ˆ

Φis a scalable

frame.

Remark II.2.The proof of Proposition II.1 also yields that

the frame vectors of any minimizer of (II.1) are non-zero if

dΦ<1.

Lemma II.3. Assume that dΦ<1, and let ˆ

Φ = {ˆϕi}M

i=1 be

a minimizer of (II.1). Then for every i= 1, . . . , M,

(i) hϕi,ˆϕii=kˆϕik2

(ii) kˆϕik2≤1, and equality holds if and only if ˆϕi=ϕi.

(iii) kˆ

Φk2

F=M−d2

Φ.

Proof. (i). Fix j∈ {1, . . . , M}and α∈R\{0}be arbitrary.

Define the frame Ψ = {ψi}M

i=1 as

ψi=(ˆϕiif i6=j

αˆϕjif i=j,

which is scalable. Hence, we have

kΦ−ˆ

Φk2

F≤ kΦ−Ψk2

i6=jkϕi−ˆϕik2

2+kϕj−αˆϕjk2

i=1 kϕi−ˆϕik2

2+kϕj−αˆϕjk2

2−kϕj−ˆϕjk2

2

=kΦ−ˆ

Φk2

F+kϕj−αˆϕjk2

2−kϕj−ˆϕjk2

2.

This implies

kϕj−αˆϕjk2

2≥ kϕj−ˆϕjk2

or, equivalently,

−2αhϕj,ˆϕji+α2kˆϕjk2

2≥ −2hϕj,ˆϕji+kˆϕjk2

2(II.2)

for all α∈R\ {0}and all j∈ {1, . . . , M}. Putting α=

hϕj,ˆϕji

kˆϕjk2

in (II.2) gives

−hϕj,ˆϕji2

kˆϕjk2

2≥ −2hϕj,ˆϕji+kˆϕjk2

which is equivalent to

0≥hϕj,ˆϕji

kˆϕjk2−kˆϕjk22

which leads to the conclusion.

(ii). By (i) we have

kˆϕjk2

2=hϕj,ˆϕji ≤ kϕjk2kˆϕjk2=kˆϕjk2

This proves kˆϕjk2≤1and that kˆϕjk2= 1 holds if and only

if ˆϕj=λϕjfor some λ∈R. In the latter case, as both vectors

are normalized, we have λ=±1. But ˆϕj=−ϕjis impossible

due to (i). Thus, ϕj= ˆϕjfollows.

(iii). By (i),

M−d2

Φ=M−kΦ−ˆ

Φk2

F=M−

i=1 kϕi−ˆϕik2

=M−

i=1 1−2hϕi,ˆϕii+kˆϕik2

2=

i=1 kˆϕik2

JOURNAL NAME, VOLUME, NO., DATE 4

which proves the claim.

Since we do not yet have a complete understanding of the

set SC(M, N), we do not have an algorithm for calculating

the infimum dΦin (II.1). For this reason, we introduce two

other measures of scalability in the remainder of this section

which are more accessible in practice. We will relate these

measures to each other and to dΦin Section III.

B. Distance of the Identity to a Cone

As mentioned in the introduction, the measure DΦfor the

scalability of Φ∈ Fu(M, N)is the distance of the identity

operator to the cone generated by {ϕiϕT

i}. Let us recall its

definition:

DΦ:= min

ci≥0



i=1

ciϕiϕT

i−I



F

.(II.3)

For the following, it is convenient to represent the function to

be minimized in (II.3) in another form:



i=1

ciϕiϕT

i−I



=Tr 



i,j=1

cicjϕiϕT

iϕjϕT

j−2

i=1

ciϕiϕT

i+I



i,j=1

cicj|hϕi, ϕji|2−2

i=1

ci+N.

(II.4)

If we now put 1:= (1,...,1)T∈RM,fij := |hϕi, ϕji|2,

i, j = 1, . . . , M,F:= (fij)M

i,j=1, and c:= (c1, . . . , cm)T, we

obtain

g(c) := 



i=1

ciϕiϕT

i−I



=cTFc −2·1Tc+N. (II.5)

First of all, we can associate DΦwith the frame potential (see,

e.g., [2]):

FP(Φ) :=

i,j=1 |hϕi, ϕji|2.

By plugging in α1into gwith α > 0:

g(α1) = α2FP(Φ) −2Mα +N.

Φ≤min

α≥0g(α1) = N−M2

FP(Φ).

We summarize the above discussion in a proposition.

Proposition II.4. For Φ∈ Fu(M, N)we have

Φ≤N−M2

FP(Φ).(II.6)

Remark II.5.Since FP(Φ) < M2, the inequality (II.6) implies

that DΦ<√N−1. It is worth noting that this upper bound

is sharp in the sense that for each ε > 0there exists Φ∈

Fu(M, N)such that DΦ>√N−1−ε. This can be done

by essentially choosing the frame vectors of Φvery close to

each other.

The following proposition can be thought of as an analog

to Lemma II.3 (iii).

Proposition II.6. Let the non-negative diagonal matrix ˆ

diag(ˆc1,...,ˆcM)∈RM×Mbe a minimizer of (II.3). Then

Tr(Φ ˆ

CΦT) =

i=1

ˆci=N−D2

Φ.(II.7)

Proof. The first equality in (II.7) is due to the fact that the

ϕi’s are normalized. Define

f(α) := g(αˆc) = α2ˆcTFˆc−2α1Tˆc+N.

for α > 0. The function f(α)has a local minimum at α= 1,

therefore

dαα=1 = 0 =⇒ˆcTFˆc=1Tc.

So,

Φ=f(1) = ˆcTFˆc−2·1Tˆc+N=N−1Tˆc=N−

i=1

ˆci,

which proves the proposition.

C. Volume of the Smallest Ellipsoid Enclosing the Sym-

metrized Frame

In the following, we shall examine the properties of the

measure VΦ. We will have to recall a few facts from convex

geometry, especially results dealing with the ellipsoid of a

convex polytope first. An N-dimensional ellipsoid centered at

cis defined as

E(X, c) := c+X−1/2(B) = {v:hX(v−c),(v−c)i ≤ 1},

where Xis an N×Npositive definite matrix, and Bis the

unit ball in RN. It is easy to see that

Vol(E(X, c)) = det(X−1/2)ωN.(II.8)

Here, as already mentioned in the introduction, ωNdenotes

the volume of the unit ball in RN.

Aconvex body in RNis a nonempty compact convex subset

of RN. It is well-known that for any convex body Kin RN

with nonempty interior there is a unique ellipsoid of minimal

volume containing Kand a unique ellipsoid of maximal

volume contained in K; see, e.g., [22, Chapter 3]. We refer to

[1], [12], [22] for more on these extremal ellipsoids.

In what follows, we only consider the ellipsoid of minimal

volume that encloses a given convex body, and this ellipsoid

will be called the minimal ellipsoid of that convex body.

The following theorem is a generalization of John’s ellipsoid

theorem [13], which will be referred as John’s theorem in this

paper.

Theorem II.7. [12, Theorem 12.9] Let K⊂RNbe a convex

body and let Xbe an N×Npositive definite matrix. Then

the following are equivalent:

(i) E(X, c)is the minimal ellipsoid of K.

JOURNAL NAME, VOLUME, NO., DATE 5

(ii) K⊂E(X, c), and there exist positive multipliers

{λi}k

i=1, and contact points {ui}k

i=1 in Ksuch that

X−1=

i=1

λi(ui−c)(ui−c)T,(II.9)

0 =

i=1

λi(ui−c),(II.10)

ui∈∂K ∩∂E(X, c), i = 1, . . . , k. (II.11)

Given a frame Φ = {ϕi}M

i=1 ∈ Fu(M, N), we will apply

John’s theorem to the convex hull of the symmetrized frame

ΦSym ={ϕi}M

i=1 ∪ {−ϕi}M

i=1. By EΦwe will denote the

minimal ellipsoid of the convex hull of ΦSym. We shall also

call this ellipsoid the minimal ellipsoid of Φ. This is not in

conflict with the notion of the minimal ellipsoid of a convex

body since the finite set Φis not a convex body. The next

lemma says that the center of EΦis always 0.

Lemma II.8. Let Kbe a convex body which is symmetric

about the origin. Then the center of the minimal ellipsoid of

Kis 0.

Proof. Let E(X, c)denote the minimal ellipsoid of K. By

definition, if u∈Kwe also have −u∈K, which implies

hX(u−c), u −ci ≤ 1and hX(−u−c),−u−ci ≤ 1.

Adding those inequalities, we obtain

2hXu, ui+ 2hXc, ci ≤ 2.

Since X∈RN×Nis positive definite, the above equation

implies hXu, ui ≤ 1or, equivalently, u∈E(X, 0). This

proves K⊂E(X, 0). And as E(X, 0) has the same volume as

E(X, c), it follows from the uniqueness of minimal ellipsoids

that c= 0.

In the following, we write E(X)instead of E(X, 0). For

completeness, we now state a version of Theorem II.7 that is

specifically taylored to our situation.

Corollary II.9. Let Φ = {ϕi}M

i=1 ∈ Fu(M, N), and let X

be an N×Npositive definite matrix. Then the following are

equivalent:

(i) E(X)is the minimal ellipsoid of Φ.

(ii) There exist nonnegative scalars {ρi}M

i=1 such that

X−1=

i=1

ρiϕiϕT

i,(II.12)

hXϕi, ϕii ≤ 1for all i= 1,2, . . . , M, (II.13)

hXϕi, ϕii= 1 if ρi>0.(II.14)

Proof. (i)⇒(ii). By John’s theorem, the contact points must be

points in the set ΦSym. Since ϕiϕT

i= (−ϕi)(−ϕi)T, equation

(II.9) with the center c= 0 implies that there exists I⊂

{1, . . . , M}such that

X−1=X

i∈I

λiϕiϕT

Setting ρi=λifor i∈Iand ρi= 0 for i /∈I, we get (II.12).

Equation (II.13) follows from the fact that ϕi∈E(X)for

each i= 1, . . . , M, and equation (II.14) is implied by (II.11).

(ii)⇒(i). Let I={i:ρi>0}. Then the assumptions

imply conditions (II.9) and (II.11) with {ui}i∈I={ϕi}i∈I,

and {λi}i∈I={ρi}i∈I. We just need to slightly modify

{ui},{λi}to make it satisfy (II.10) as well. Indeed, we replace

uiby the pair ±uieach with half the weight of the original

λi. Finally, (II.13) implies that the convex hull of ΦSym is

contained in E(X). Now, (i) follows from the application of

John’s theorem.

Remark II.10.It is convenient to view (II.12) as saying that

{X1/2ϕi}M

i=1 is scalable with scalars {√ρi}M

i=1. Therefore

by [16, Remark 3.12] (see also [4, Corollary 3.4], since the

dimension of span{ϕiϕi}M

i=1 is at most N(N+1)

2), we can

always pick a set of ρi’s as in (ii) above such that the number

of non-zero (i.e., positive) ρi’s does not exceed N(N+1)

Recall that in the introduction we defined a third measure

of scalability as follows:

VΦ=Vol(EΦ)

ωN

= det X−1/2.(II.15)

The second equality is due to (II.8).

Let us now see how VΦrelates to scalability of Φ. If Φ∈

Fu(M, N)is scalable then (II.12)–(II.14) hold with X=I.

Therefore, EΦ=E(I)is the unit ball which implies VΦ= 1.

Conversely, if VΦ= 1 then EΦmust be the unit ball since the

ellipsoid of minimal volume is unique. Hence, EΦ=E(I),

and (II.12) implies that Φis scalable. This quickly provides

another characterization of scalability.

Theorem II.11. A frame Φ∈ Fu(M, N)is scalable if and

only if its minimal ellipsoid is the N-dimensional unit ball, in

which case VΦ= 1.

We can now prove an important property of the minimal

ellipsoid EΦof a unit norm frame Φ.

Lemma II.12. Given Φ∈ Fu(M, N), let E(X)be the

minimal ellipsoid of Φwhere X−1=PM

i=1 ρiϕiϕT

i, and let

{λi}N

i=1 be the eigenvalues of X−1. Then

VΦ=

i=1

λ1/2

i,(II.16)

Tr X−1=

i=1

ρi=

i=1

λi=N. (II.17)

Proof. The relation (II.16) immediately follows from (II.15).

To prove (II.17), we set ui=X1/2ϕi. Then

I=X1/2 M

i=1

ρiϕiϕT

i!X1/2=

i=1

ρiuiuT

i.(II.18)

In addition, we know that whenever ρi>0, we have

hϕi, Xϕii= 1, or equivalently kuik2= 1. Using this fact

as well as (II.18), we deduce

i=1

ρi=X

ρi>0

ρiTr(uiuT

i) = Tr M

i=1

ρiuiuT

i!=Tr(I) = N.

JOURNAL NAME, VOLUME, NO., DATE 6

The lemma is proved.

Given a frame Φwith minimal ellipsoid EΦ=E(X), we

have shown in (II.17) that the trace of X−1is always fixed.

This naturally raises the question whether any ellipsoid E(X)

with Tr(X−1) = Nis necessarily the minimal ellipsoid of

some frame. The next theorem answers this question in the

affirmative.

Theorem II.13. Every ellipsoid E(X)with Tr(X−1) = Nis

the minimal ellipsoid of some frame Φ∈ Fu(M, N).

Proof. Given any invertible positive definite matrix X−1

whose trace is N, there exists Φ0={ϕi}N

i=1 ∈ Fu(N, N)

such that

X−1=

i=1

ϕiϕT

i.(II.19)

This is a direct result of Corollary 3.1 in [8].

Next, we show that hXϕi, ϕii= 1 for all i= 1, . . . , N.

For this, fix j∈ {1, . . . , N}and choose x∈ {ϕi:i6=j}⊥

with hx, ϕji= 1. Then

1 = *N

i=1

XϕiϕT

ix, ϕj+=hXϕjϕT

jx, ϕji=hXϕj, ϕji.

Now, it follows from Corollary II.9 that E(X)is the minimal

ellipsoid of Φ0. Construct Φ∈ Fu(M, N)by adding M−N

unit norm vectors inside E(X)to Φ0. Then E(X)is also the

minimal ellipsoid of Φsince (II.19) still holds with Nreplaced

by Mand ρi= 0 for i=N+ 1, . . . , M.

Remark II.14.It is possible using the geometric characteriza-

tion of scalable frames by VΦto define an equivalence relation

on Fu(M, N). Indeed, Φ,Ψ∈ Fu(M, N)can be defined to

be equivalent if VΦ=VΨ. We denote each equivalence class

by the unique volume for all its members. Specifically, for any

0< a ≤1, the class P[M, N, a]consists of all Φ∈ Fu(M, N)

with VΦ=a. Then, SC(M, N) = P[M, N, 1]. This also

allows a parametrization of Fu(M, N):

Fu(M, N) = [

a∈(0,1]

P[M, N, a].

III. COMPARISON OF THE MEASURES

In this section, we relate the three measures dΦ,DΦ, and

VΦof scalability to each other. Hereby, we will frequently

make use of the standard inequalities in the following lemma,

in particular the arithmetic geometric means inequality.

Lemma III.1. Given ai>0,i= 1, . . . , N, we have

i=1 a−1

i≤

i=1

i≤PN

i=1 ai

N,(III.1)

i<j

aiaj≥N(N−1)

i=1

i.(III.2)

The inequality (III.2) is a special case of the right hand side

inequality of (III.1).

A. Comparison of DΦand VΦ

Given a frame Φ∈ Fu(M, N), by definition VΦ≤1.

Moreover, by Theorem II.11, we have VΦ= 1 if and only

if the frame is scalable. Intuitively, when a frame is scalable,

the frame vectors spread out in the space, which makes its

minimal ellipsoid to be the unit ball. But when a frame gets

more and more non-scalable, the frame vectors tend to bundle

in one place, and thus produce a very “flat” ellipsoid with

small volume. In this section, we formalize this intuition, and

establish that VΦis just as suitable as DΦin quantifying how

scalable a frame is.

We first consider the 2-dimensional case, where there is a

straightforward characterization of scalability: Φ = {ϕi}M

i=1

is a scalable frame of R2if and only if the smallest double

cone (with apex at origin) containing all the frame vectors of

ΦSym has an apex angle greater than or equal to π/2. This

is essentially proved in [17, Corollary 3.8]; See also Remark

IV.2 (b).

Example III.2. Given Φ∈ Fu(M, 2), suppose ϕ1, ϕ2∈

ΦSym generate the smallest cone containing ΦSym. With-

out loss of generality, we assume ϕ1= (cos θ, sin θ)and

ϕ2= (cos θ, −sin θ), where 2θis the apex angle. We have

EΦ=E{ϕ1,ϕ2}, and this ellipsoid is determined by the

solution of the following problem:

min

a,b ab s.t. cos2θ

a2+sin2θ

b2= 1.

The solution is a=√2 cos θ,b=√2 sin θ. So in this case,

X−1=2 cos2θ0

0 2 sin2θ=ϕ1ϕT

1+ϕ2ϕT

and VΦ= det(X−1/2) = sin 2θ.

Now let us calculate DΦ. Since all vectors of ΦSym are

contained in the cone {±(aϕ1+bϕ2), a, b ≥0}, any ϕi

can be represented as ϕi=cϕ1+dϕ2with cd ≥0. Thus

ϕiϕT

i=c2ϕ1ϕT

1+d2ϕ2ϕT

2+cd(ϕ1ϕT

2+ϕ2ϕT

1). Therefore,

the Frobenius norm minimization problem becomes

min

a,b,c≥0

aϕ1ϕT

1+bϕ2ϕT

2+c(ϕ1ϕT

2+ϕ2ϕT

1)−I

F.

The solution of this problem is a=b=2

3+cos 4θ,c= 0, and

thus

Φ= 2 −2a= 2 −2

2−V2

So, as VΦis approaching 1, DΦis approaching 0, and vice

versa.

In Example III.2 it is shown that in the 2-dimensional case,

VΦis a function of DΦ. However, in general VΦis no longer

uniquely determined by DΦbut falls into a range defined by

DΦas the following theorem indicates. But the key point

here is that it still remains true that DΦapproaches zero is

equivalent to the volume ratio tending to one.

Theorem III.3. Let Φ = {ϕi}M

i=1 ∈ Fu(M, N), then

N(1 −D2

Φ)

N−D2

Φ≤V4/N

Φ≤N(N−1−D2

Φ)

(N−1)(N−D2

Φ)≤1,(III.3)

JOURNAL NAME, VOLUME, NO., DATE 7

where the leftmost inequality requires DΦ<1. Consequently,

VΦ→1is equivalent to DΦ→0.

Proof. The rightmost inequality is clear. Let us prove the

upper bound on V4/N

Φin (III.3). For this, let EΦ=E(X)be

the minimal ellipsoid of Φ, and let {λi}N

i=1 be the eigenvalues

of X−1=PM

i=1 ρiϕiϕT

i. For any α > 0, we have

Φ≤



i=1

αρiϕiϕT

i−I



=kαX−1−Ik2

i=1

(αλi−1)2=α2

i=1

λ2

i−2α

i=1

λi+N.

Therefore, by (II.17),

Φ≤min

α>0 α2

i=1

λ2

i−2α

i=1

λi+N!=N−N2

i=1 λ2

(III.4)

We use (II.16) and (III.2) to estimate PN

i=1 λ2

i=1

λ2

i= N

i=1

λi!2

−2X

i<j

λiλj=N2−2X

i<j

λiλj

≤N2−N(N−1)

i=1

λ2/N

i=N2−N(N−1)V4/N

Φ.

(III.5)

Plugging (III.5) in (III.4) and solving it for V4/N

Φyields the

upper bound in (III.3).

For the lower bound, let ˆ

C=diag{ci}M

i=1 be a minimizer

of (II.3). Then DΦ=kΦˆ

CΦT−IkF. Moreover,

Tr(Φ ˆ

CΦTX) =

i=1

ciϕT

iXϕi≤

i=1

ci.

The last inequality holds due to (II.13). Therefore,

Tr(X)−N(III.6)

=Tr(Φ ˆ

CΦTX)−Tr((Φ ˆ

CΦT−I)X)−N

=Tr(Φ ˆ

CΦTX)−Tr(Φ ˆ

CΦT−I)

−Tr((Φ ˆ

CΦT−I)(X−I)) −N

≤

i=1

ci− M

i=1

ci−N!−Tr((Φ ˆ

CΦT−I)(X−I)) −N

≤ kΦˆ

CΦT−IkFkX−IkF=DΦv

i=1 λ−1

i−12

=DΦv

t N

i=1

λ−1

i!2

−2X

i<j

λ−1

iλ−1

j−2

i=1

λ−1

i+N

≤DΦqTr2(X)−N(N−1)V−4/N

Φ−2Tr(X) + N,

where the last inequality is due to (III.2) with ai=λ−1

i, and

(II.16). By (III.1),

Tr(X) =

i=1

λ−1

i≥N

i=1

λ1/N

=NV −2/N

Φ≥N. (III.7)

Now, we square both sides of (III.6) and note that the new

inequality is equivalent to

Tr(X)−N−D2

1−D2

Φ2

≤D2

Φ(N−1)

(1 −D2

Φ)2ω,

where

ω:= N−D2

Φ−(1 −D2

Φ)NV −4/N

Φ.

Hence, ω≥0, which is equivalent to the leftmost inequality

in (III.3).

B. Algorithms and Numerical Experiments

The computation in (II.4) shows that DΦcan be computed

via Quadratic Programming (QP). As is well known, this

problem can be solved by many well developed methods, e.g.,

Active-Set, Conjugate Gradient, Interior point.

The minimal ellipsoid problem has been studied for half

a century. For a given convex body Kand a small quantity

η > 0, a fast algorithm to compute an ellipsoid E⊇Kwith

Vol(E)≤(1 + η) Vol(Minimal ellipsoid(K))

is the Khachiyan’s barycentric coordinate descent algorithm

[14], which needs a total of O(M3.5ln(Mη−1)) operations.

For the case NM, Kumar and Yildirim [15] improved

this algorithm using core sets and reduce the complexity to

O(MN3η−1).

For all numerical simulations in this paper, we use Khachi-

yan’s method to compute minimal ellipsoids and the active

set method to solve the quadratic programming in (II.3). As

expected, we have observed a much faster computational speed

of the later, especially when the problem grows large in size.

Figure 1 shows the values of DΦand VΦfor randomly

generated frames in F(M, 4) with M= 6,11,15,and 20. In

each plot, we generated 1000 frames, where each column of

the frame is chosen uniformly at random from the unit sphere,

and calculated both VΦand DΦ.

As expected, for a fixed DΦ, we see a range of VΦ. For

a direct comparison, we plotted the two bounds from (III.3).

The lower bound from (III.3) is quite optimal based on the

figure.

On the other hand, as Mincreases, we observe a change of

concentration of the points from scattering around to being

heavily distributed around DΦ= 0: “the scalable region”.

Indeed, as shown by Theorem IV.9 in Section IV, the threshold

for having positive probability of scalable frames in dimension

N= 4 is N(N+1)/2 = 10. Therefore, we have considerably

many points achieving DΦ= 0 for M= 11,15,20. In fact,

about 60% of these 1000 frames in F(4,20) are scalable (up

to a machine error).

This suggests that the two measures of scalability, the

distance between DΦand 0and the distance between VΦand

1, though closely related, are indeed different in the sense

that there is no one-to-one correspondence between them. An

advantage of using DΦto measure scalability lies in the fact

it is more naturally related to the notion of m−scalability

(defined in [16]) and is more efficient to compute. By contrast,

VΦis a more intuitive measure of scalability from a geometric

point of view.

JOURNAL NAME, VOLUME, NO., DATE 8

0 0.5 1 1.5

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1Frames of size 4× 6

DΦ

VΦ

0 0.5 1 1.5

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1Frames of size 4× 11

DΦ

VΦ

0 0.5 1 1.5

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1Frames of size 4× 15

DΦ

VΦ

0 0.5 1 1.5

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1Frames of size 4× 20

DΦ

VΦ

Fig. 1. Relation between VΦand DΦfor Φ∈ Fu(M, 4) with M=

6,11,15,20. The solid line indicates the upper bound in (III.3), while

the dash line indicates the lower bound.

C. Comparison of the Measures DΦand VΦwith dΦ

The distance of a frame Φ∈ Fu(M, N)to the set of

scalable frames is the most intuitive and natural measure of

scalability. The next theorem shows that the practically more

accessible measures DΦand VΦare equivalent to dΦin the

sense that dΦtends to zero if and only if the same holds for

DΦor 1−VΦ.

Theorem III.4. Let Φ∈ Fu(M, N)and assume that dΦ<1.

Then with K:= min{M, N(N+1)

2}and ω:= DΦ+√Kwe

have

DΦ

ω+pω2−D2

Φ≤dΦ≤rKN 1−V2/N

Φ.(III.8)

Consequently, with the help of Theorem III.3, we can bound

dΦbelow and above by expressions of DΦor expressions of

VΦ.

Proof. Following the same notation as in the proof of The-

orem III.3, let λ1, . . . , λNbe the eigenvalues of X−1=

i=1 ρiϕiϕT

i. Furthermore, let J={i:ρi>0}. By Remark

II.10, |J| ≤ K. Define a frame e

Φ = {˜ϕi}M

i=1 by

˜ϕi:= (V1/N

ΦX1/2ϕiif i∈J

ϕiif i /∈J. (III.9)

Note that e

Φis scalable, and, moreover, kX1/2ϕik2= 1 for

i∈Jby (II.14). So,

kΦ−e

Φk2

F=X

i∈Jkϕi−V1/N

ΦX1/2ϕik2

i∈Jk(X−1/2−V1/N

ΦI)X1/2ϕik2

2(III.10)

≤ kX−1/2−V1/N

ΦIk2

i∈JkX1/2ϕik2

≤K

j=1 λ1/2

j−V1/N

Φ2

(III.11)

=K

N+V2/N

ΦN−2V1/N

j=1

λ1/2

j



=KN 

1 + V2/N

Φ−2V1/N

j=1

λ1/2

j



≤KN 1 + V2/N

Φ−2V2/N

Φ(III.12)

=KN 1−V2/N

Φ2.(III.13)

As dΦ≤ kΦ−e

ΦkF, this proves the right-hand side of (III.8).

Let ˆ

Φbe a minimizer of (II.1) (which exists due to Propo-

sition II.1 and has non-zero columns by Remark II.2). Since

Φis scalable, there exists a non-negative diagonal matrix

S=diag(si)M

i=1 such that ˆ

ΦSˆ

ΦT=I. Again by Remark

II.10, we may assume that at most Kof the siare non-zero.

We then have

ΦSΦT−I= ΦSΦT−ˆ

ΦSˆ

ΦT

i=1

siϕi(ϕT

i−ˆϕT

i)+(ϕi−ˆϕi) ˆϕT

i,

and therefore, as kˆϕik2≤1(see Lemma II.3 (ii)),

DΦ≤ kΦSΦT−IkF

≤

i=1

sikϕi−ˆϕik2+kϕi−ˆϕik2kˆϕik2

≤2

i=1

sikϕi−ˆϕik2

≤2 M

i=1

i!1/2 M

i=1 kϕi−ˆϕik2

2!1/2

≤2Kmax

is2

i1/2kΦ−ˆ

ΦkF= 2√Kmax

isidΦ.

Now, for each i∈ {1, . . . , M}we have

si=ˆϕiTsiˆϕiˆϕiTˆϕi

kˆϕik4

2≤

k=1

ˆϕT

iskˆϕkˆϕT

kˆϕi

kˆϕik4

=ˆϕT

iˆ

ΦSˆ

ΦTˆϕi

kˆϕik4

kˆϕik2

2≤1

(1 −dΦ)2,

where the last inequality follows from the triangle inequality.

This gives

DΦ≤2√KdΦ

(1 −dΦ)2.(III.14)

Solving for dΦin the last inequality leads to the left hand side

of (III.8).

We conclude this section by a theorem on approximating

unit norm frames by scalable frames.

Theorem III.5 (Approximation by scalable frames).Let

Φ∈ Fu(M, N)and assume that dΦ≤1

2(1 + √K)−1,

K= min{M, N(N+ 1)/2}. Let ˆ

Φbe a minimizer of (II.1),

and let EΦ=E(X)be the minimal ellipsoid of Φ, where

X−1=PM

i=1 ρiϕiϕT

i. Then the scalable frame e

Φ = {˜ϕi}M

i=1

JOURNAL NAME, VOLUME, NO., DATE 9

defined in (III.9) is a good approximation to Φin the following

sense:

Φ−Φk2

F≤KN 1−sN(1 −dΦ)4−4Kd2

N(1 −dΦ)4−4Kd2

Φ!.

(III.15)

Proof. We extend the estimate (III.12) with the help of the

leftmost inequality of (III.3):

kΦ−e

Φk2

F≤KN 1−sN1−D2

N−D2

Φ!.(III.16)

Since the right-hand side of (III.16) is an increasing function

of DΦon [0,1], we substitute (III.14) into (III.16) and obtain

the left hand side of (III.15), where we need the requirement

on dΦso that DΦ<1.

IV. PROBABILITY OF HAVING SCALABLE FRAMES

This section aims to estimate the probability PM,N of unit

norm frames to be scalable when the frame vectors are drawn

independently and uniformly from the unit sphere SN−1⊂

RN. This is in a sense equivalent to estimating the “size” of

SC(M, N)in Fu(M, N).

The basic idea is to use the characterization of scalability in

terms of the minimum volume ellipsoids through John’s the-

orem, see Theorem II.11. From this geometric point of view,

we derive new and relatively simple conditions for scalability

and non-scalability (Theorem IV.1). These conditions are the

key tools we use to estimate the probability PM,N .

A. Necessary and Sufficient Conditions for Scalability

The following theorem plays a crucial role in the proof of

our main theorem on the probability of having scalable frames

in Subsection IV-B. However, it is also of independent interest.

Theorem IV.1. Let Φ∈ Fu(M, N). Then the following hold:

(a) (A necessary condition for scalability )If Φis scalable,

then

min

kdk2=1 max

i|hd, ϕii| ≥ 1

√N.(IV.1)

(b) (A sufficient condition for scalability )If

min

kdk2=1 max

i|hd, ϕii| ≥ rN−1

N,(IV.2)

then Φis scalable.

Proof. (a). We will use the following fact: if EKis the

minimal ellipsoid of a convex body K⊂RNwhich is

symmetric about the origin, then 1

√NEK⊂K, see [12,

Theorem 12.11]. If Φis scalable, then the unit ball is the

minimal ellipsoid of the convex hull co(ΦSym)of ΦSym.

Therefore, 1

√NB⊂co(ΦSym). And as a continuous convex

function on a compact convex set attains its maximum at an

extreme point of this set (see, e.g., [19, Theorem 3.4.7]), we

conclude that for each d∈SN−1we have

√N= max

x∈1

√NB|hd, xi| ≤ max

x∈co(ΦSym)|hd, xi| ≤ max

i|hd, ϕii|.

(b). Let EΦ=E(X)be the minimal ellipsoid of Φ. With a

unitary transformation, we can assume X−1/2=diag(ai)N

i=1.

Towards a contradiction, suppose that (IV.2) holds, but that Φ

is not scalable. Then, by Theorem II.11, a1≤a2≤. . . ≤aN

with a1< aN. Take any frame vector ϕ= (x1, x2, . . . , xN)T

from Φ. It satisfies PN

i=1

=hXϕ, ϕi ≤ 1and PN

i=1 x2

1, which implies

N−1

i=1

i1

i−1

N≤1−1

Hence, setting ρ= (1−1

)/(1

1−1

), we have x2

1≤ρ. We

claim that

ρ < N−1

N.(IV.3)

Then we choose d= (1,0,...,0)Tand find that |hd, ϕi| =

|x1|<qN−1

Nfor each ϕ∈Φwhich contradicts the

assumption.

Proving (IV.3) is equivalent to proving 1

+N−1

1> N,

which is true because

+N−1

1≥

i=1

>N2

i=1 a2

=N,

where we have used (II.17) and (III.1) (in which equality holds

if and only if a1=. . . =aN).

Remark IV.2.(a) Another necessary condition for scalability

was proved in [10, Theorem 3.1]. We wish to point out that

this necessary condition is unrelated to the one given in part

(a) of the previous theorem in the sense that neither of these

conditions implies the other.

(b) When the dimension N= 2, Theorem IV.1 gives a

necessary and sufficient condition for a frame to be scalable.

This condition can be easily interpreted in terms of cones

as already mentioned before: {ϕi}M

i=1 is a scalable frame for

R2if and only if every double cone with apex at origin and

containing ΦSym has an apex angle greater than or equal to

π/2.

large. However, this gap cannot be improved. Theorem IV.1(a)

is tight in the sense that we cannot replace 1/√Nby a bigger

constant. This is because an orthonormal basis reaches this

constant. The sufficient condition is also optimal in the sense

that p(N−1)/N cannot be replaced by a smaller number.

This requires some more analysis as shown below.

Proposition IV.3. For any small ε > 0and any N∈N, there

exists a unit norm frame Φfor RN, such that

min

kdk2=1 max

i|hd, ϕii| ≥ rN−1

N−2ε,

but Φis not scalable.

Proof. Pick an ellipsoid E(X)with X−1=diag(a2

i)N

i=1,

where a2

1=a2

2=. . . =a2

N−1=N−1−ε

N−1, and a2

N= 1 + ε.

By Theorem II.13, there exists a (non-scalable) frame Φ∈

Fu(M, N)whose minimal ellipsoid is E(X).

JOURNAL NAME, VOLUME, NO., DATE 10

Then for any x∈E(X)∩SN−1, we have

1≥

N−1

i=1

+x2

=(N−1)(1 −x2

N−1−ε+x2

1 + ε,

which implies that

N≥1 + ε

Now for any d= (d1, d2, . . . , dN)∈SN−1, if d2

N<1+ε

then let

x0=r1−1 + ε

k˜

dk+sign(dN) 0,0, ..., 0,r1 + ε

N!,

where ˜

d= (d1, d2, ...., dN−1,0). It is easy to verify that x0∈

E(X)∩SN−1and that hx0, di ≥ qN−1−ε

N. If d2

N≥1+ε

then let x0=d. It is again easy to check x0∈E(X)∩SN−1

and hx0, di= 1. In summary, for any d∈SN−1, there exists

an x0∈E(X)∩SN−1, such that hx0, di ≥ qN−1−ε

We add vectors from the set E(X)∩SN−1to Φsuch that the

frame vectors are dense enough to form an ε-ball of E(X)∩

SN−1, i.e., for any x∈E(X)∩SN−1, there exists a ϕi∈

E(X)∩SN−1, such that kϕi−xk2≤ε. Notice this new

frame has the same minimal ellipsoid. With this construction,

for any d∈SN−1, we can find a frame vector ϕisuch that

hϕi, di=hx, di+hϕi−x, di ≥ qN−1−ε

N−ε≥qN−1

N−2ε

provided that εis small enough.

In Remark IV.2(b), we mentioned that (IV.1) is necessary

and sufficient for scalability if N= 2. In the following, we

shall show that the same holds if M=N:

Theorem IV.4. For Φ∈ Fu(N, N), the following statements

are equivalent.

(i) Φis scalable.

(ii) Φis unitary.

(iii) minkdk2=1 maxi|hd, ϕii| ≥ 1

√N.

In order to prove Theorem IV.4, we need the following

lemma.

Lemma IV.5. Let Φ∈RN×Nbe a non-unitary invertible

matrix with unit norm columns. Then there exists a vector d∈

RNwith kdk2>1and a vector a∈RNwith |ai|= 1/√N

for all i= 1, . . . , N, such that ΦTd=a.

Proof. Let {bi}N

i=1 be a sequence with each entry being

a Bernoulli random variable, Ψ = diag(bi)N

i=1, and g=

√N(1, ...., 1)T. Suppose dΨis the solution to

ΦTdΨ= Ψg. (IV.4)

Let ΦT=UΣVTbe the singular value decomposition of ΦT,

where Σ = diag(σi). Observe that

√N=kΦkF=kΣkF=v

i=1

σ2

Hence, from (III.1) we obtain

i=1

σ−2

i≥N2

i=1 σ2

=N.

On the other hand, from (IV.4) we have

VTdΨ= Σ−1UTΨg.

Next, we calculate the expectation EkdΨk2. If it is greater than

1, then there must exist one instance of dΨwith norm greater

than 1, which makes the lemma hold. As E(bibj) = δij, we

obtain

EkdΨk2=EkVTdΨk2=EkΣ−1UTΨgk2

NE



X

σ−2

i

X

ujibj



2





σ−2

iE

X

ji +X

k,k6=j

ujiukibjbk



σ−2

ji =1

σ−2

i≥1,

while for the last inequality, equality holds only when all σiare

equal, i.e., Φis unitary, which is ruled out by our assumption.

Therefore the last inequality is strict.

Proof of Theorem IV.4.The equivalence (i)⇔(ii) is easy to

see and follows from, e.g., [17, Corollary 2.8]. Moreover,

(i)⇒(iii) is a direct consequence of Theorem IV.1(a). It

remains to prove that (iii) implies (i). For this, we prove

the contraposition. Suppose that Φis not scalable. Then Φ

is not unitary, and Lemma IV.5 implies the existence of

d0∈RN,kd0k2>1, such that |hd0, ϕii| = 1/√Nfor

all i= 1, . . . , N. Hence, with d=d0/kd0k2we have

|hd, ϕii| = (kd0k2√N)−1<1/√Nfor all i= 1, . . . , N.

That is, (iii) does not hold, and the theorem is proved.

B. Estimation of the probability

With the help of Theorem IV.1, we now estimate the

probability for a frame to be scalable when its vectors are

drawn independently and uniformly from SN−1. First of all, it

is easy to see the probability strictly increases as Mincreases.

Secondly, ϕiϕT

i∈SymN, where

SymN:= A∈RN×N:A=AT,

which is a vector space of dimension N(N+1)

2. By (I.1), being

scalable requires Ito be in the positive cone generated by

{ϕiϕT

i}M

i=1. If M < N(N+1)

2, then this set cannot be a

basis of SymN, so the chance for any symmetric matrix to

be in the span of {ϕiϕT

i}M

i=1 is minimal, which makes it

even more difficult for Ito be in positive cone generated by

this set. Therefore we expect the probability to be 0 when

M < N(N+1)

2. Finally, as M→ ∞, we expect the probability

of frames to be scalable to approach 1.

Let us first consider the case N= 2 for which the

probability P2,M can be explicitly computed.

Example IV.6. If vectors ϕ1, . . . , ϕMare drawn indepen-

dently and uniformly from S1, then the probability of {ϕi}M

i=1

to be a scalable frame in Fu(M, 2) is given by

PM,2= 1 −M

2M−1, M ≥2.

JOURNAL NAME, VOLUME, NO., DATE 11

Proof. First of all, define the angle of a vector vas the angle

between vand positive x-axis, counterclockwise. Among all

the double cones that cover all the vectors in ΦSym, let PΦ

be the one with the smallest apex angle α. It is known that

Φis scalable if and only if α≥π/2. Let ϕΦbe the “right

boundary” of PΦ. To be rigorous, Let ϕΦbe the vector with

angle β0∈[0, π)such that for βin some neighborhood of β0

we have (cos β, sin β)T∈PΦif β > β0and (cos β, sin β)T/∈

PΦif β < β0. For fixed i∈ {1, . . . , M}we then have

Pr(Φ not scalable and ϕΦ=±ϕi)

2πZ2π

Pr (Φ not scalable and ϕΦ=±ϕi|∠ϕi=β)dβ

2πZ2π

2M−1dβ =1

2M−1.

Now, it follows that Pr(Φ is not scalable) =

PiPr(Φ not scalable and ϕΦ=±ϕi) = M/2M−1.

We can see in R2, as the number of frame vectors increases,

the probability PM,2increases as well, starting from zero

and eventually approaching 1. The critical point where the

probability turns from zero to positive is M= 3 = N(N+1)

which meets our expectation. We will show that this is true

for arbitrary dimension, and provide an estimate for the

probability of frames being scalable. The following lemma

completes the series of preparatory statements for the proof

of our main theorem.

Lemma IV.7. If Φ = {ϕi}M

i=1 is a strictly scalable frame for

RNand {ϕiϕT

i}M

i=1 is a frame for SymN, then there exists

ε > 0such that any frame Ψsatisfying kΨ−ΦkF< ε is

strictly scalable.

Proof. Let Abe the lower frame bound of {ϕiϕT

i}M

i=1, where

SymNis endowed with the Frobenius norm. Moreover, by F:

DiagM→SymNdenote the synthesis operator of {ϕiϕT

i}M

i=1,

where DiagMdenotes the space of all diagonal matrices in

SymM. Then FD = ΦDΦT,D∈DiagM. Since Φis strictly

scalable, there exists a positive definite D∈DiagMsuch that

FD =I.

Let δ > 0be so small that whenever ∆∈DiagMwith

k∆kF≤δ, we have that D+ ∆ remains positive definite.

Moreover, let ε > 0be so small that

τ:= (ε+2kΦkF)ε≤max (√A

2,δA

2(√A+ 2kFkop)kDkF).

Now, let Ψ = {ψi}M

i=1 ⊂RNbe such that kΦ−ΨkF< ε.

By G: DiagM→SymNdenote the synthesis operator of

{ψiψT

i}M

i=1. We can see that kF−Gkop ≤τ, since for any

diagonal matrix C,

kFC −GCkF=kΦCΦT−ΨCΨTkF

≤ kΦC(ΦT−ΨT)kF+k(Φ −Ψ)CΨTkF

≤(kΦkF+kΨ||F)kCkF

≤(+ 2kΦkF)kC||F.

Hence, for X∈SymNwe have

kG∗XkF≥ kF∗XkF−k(F−G)∗XkF≥(√A−τ)kXkF

≥(√A/2)kXkF.

In particular, this implies that {ψiψT

i}M

i=1 is a frame for

SymN, and hGG∗X, XiF=kG∗Xk2

F≥(A/4)kXk2

Fyields

k(GG∗)−1kop ≤4/A. Now, we define

∆ := G∗(GG∗)−1(F−G)D∈DiagM.

Then G(D+ ∆) = GD + (F−G)D=FD =I. Moreover,

k∆kF≤ kGkopk(GG∗)−1kopkF−GkopkDkF

≤((√A/2) + kFkop)(4/A)τkDkF≤δ,

so that D+ ∆ is positive definite. Consequently, Ψis strictly

scalable.

Remark IV.8.We mention that Lemma IV.7 implies that the

set {Φ∈SC+(M, N) : {ϕiϕT

i}M

i=1 is a frame}is open.

The statement and proof of the main theorem use the notion

of spherical caps. We define RN

a(C)to be the spherical cap

in SNwith angular radius a, centered at C, i.e.

a(C) = x∈SN:hx, Ci ≥ cos(a).

By AN

awe denote the relative area of RN

a(C)(ratio of area

of RN

a(C)and area of SN).

Theorem IV.9. Given Φ = {ϕi}M

i=1 ⊂RN, where each vector

ϕiis drawn independently and uniformly from SN−1, let PM,N

denote the probability that Φis scalable. Then the following

holds:

(i) When M < N(N+1)

2,PM,N = 0

(ii) When M≥N(N+1)

2,PM,N >0and

CN1−AN−1

αM≥1−PM,N ≥1−AN−1

aM−N,

where

α=1

2arccos rN−1

N, a = arccos 1

√N,

and where CNis the number of caps with angu-

lar radius αneeded to cover SN−1. Consequently,

limM→∞ PM,N = 1.

Proof. By µuwe denote the uniform measure on SN−1and by

µGthe Gaussian measure on RN. Furthermore, on (SN−1)M

and (RN)Mdefine the product measures

µk

u:=

j=1

µuand µk

G:=

j=1

µG,

JOURNAL NAME, VOLUME, NO., DATE 12

respectively. For a set B⊂(SN−1)k,k∈N, we define

B0:= (x1, . . . , xk)∈(RN\{0})k:

x1

kx1k2

,..., xk

kxkk2∈B.

Since µu(A) = µG(A0)for any A⊂SN−1, we have

µk

u(B) = µk

G(B0)for any B⊂(SN−1)k.(IV.5)

(i). Set K=N(N+ 1)/2. It suffices to show PM,N = 0

only for M=K−1. For this, let

B:= (ϕ1, . . . , ϕM)∈(SN−1)M:

{ϕ1ϕT

1, . . . , ϕMϕT

M, I}is linearly dependent.

Then

B0=(ϕ1, . . . , ϕM)∈(RN\{0})M:

{ϕ1ϕT

1, . . . , ϕMϕT

M, I}is linearly dependent.

This set, seen as a subset of RNM , is contained in the zero

locus of a polynomial in the entries of the ϕi’s. Therefore,

the Lebesgue measure of B0is zero. But this shows that

µM

G(B0)=0since µM

Gis absolutely continuous with respect

to the Lebesgue measure. Consequently, we obtain

PM,N =µM

u({Φ∈ Fu(M, N):Φscalable})

≤µM

u(B) = µM

G(B0)=0.

(ii). With Lemma IV.7, we only need to prove the existence

of a strictly scalable unit norm frame Φsuch that {ϕiϕT

i}M

i=1

spans SymN. For this, we note that by [4, Theorem 2.1], there

exists a frame V={vi}M

i=1 such that {vivT

i}M

i=1 spans SymN.

Let Sbe its frame operator, and ϕi=S−1/2vi. Therefore

Φ = {ϕi}is a tight frame, thus strictly scalable. It is also easy

to check that the linear map T: SymN→SymN, defined

by T(A) := S−1/2AS−1/2,A∈SymN, is invertible and

maps vivT

ito ϕiϕT

i. Therefore, {ϕiϕT

i}M

i=1 also spans SymN.

Finally, we normalize Φto attain the desired frame.

For the estimate on 1−PM,N , we first prove the right hand

side inequality. For this, we put Ψ := {ϕi}N

i=1 and Υ :=

{ϕi}M

i=N+1. If Ψis not unitary, by Theorem IV.4 there exists

dΨ∈SN−1such that |hdΨ, ϕii| <1/√Nand hence ϕi/∈

RN−1

a(dΨ)for i= 1, . . . , N. Therefore, if Ψis not unitary

and ϕN+1, . . . , ϕM/∈RN−1

a(dΨ)then Φis not scalable by

Theorem IV.1(a). This yields

1−PM,N

≥µM

uΦ:Ψ/∈ SC(N, N),∀ϕ∈Υ : ϕ /∈RN−1

a(dΨ)

=ZSC(N,N)c

µM−N

uΥ∈(SN−1)M−N:

∀ϕ∈Υ : ϕ /∈RN−1

a(dΨ)dµN

u(Ψ)

=ZSC(N,N)c

µM−N

uRN−1

a(dΨ)cM−NdµN

u(Ψ)

=1−AN−1

aM−NZ

SC(N,N)c

dµN

u(Ψ)

=1−AN−1

aM−N1−µN

u(SC(N, N)).

But µN

u(SC(N, N)) = 0 by (i), and hence the inequality

follows.

For the left hand side inequality, let {Rj}C

j=1 be a cover

of SN−1with spherical caps of angular radius α. Define the

event E:= {∀j∈ {1,2,··· , C}∃isuch that ϕi∈Rj}. If

event Eholds, whenever d∈SN−1, there exists jsuch that

d∈Rj. Thus, there also exists isuch that dand ϕiare in the

same spherical cap, which means hd, ϕii ≥ qN−1

N. Therefore,

Theorem IV.1(b) yields that Φis scalable. So, we have

PM,N ≥Pr(E)=1−Pr ∃j∀i:ϕi∈Rc

j

= 1 −Pr 

[

j{∀i:ϕi∈Rc

j}



≥1−X

Pr {∀i:ϕi∈Rc

j}

= 1 −X

j1−AN−1

αM= 1 −C1−AN−1

αM.

This finishes the proof of the theorem.

Remark IV.10.An estimate for CNcan be found in [3,

Theorem 1.2] as

CN≤3N+ 2 + √N(N+ 1) cos(a)(AN−1

a)−21

2AN−1

aN

ACKNOWLEDGMENT

G. Kutyniok acknowledges support by the Einstein Foun-

dation Berlin, by the Einstein Center for Mathematics Berlin

(ECMath), by Deutsche Forschungsgemeinschaft (DFG) Grant

KU 1446/14, by the DFG Collaborative Research Center

SFB/TRR 109 ”Discretization in Geometry and Dynamics”,

and by the DFG Research Center MATHEON ”Mathematics

for key technologies” in Berlin. Also F. Philipp thanks the

MATHEON for their support. K. A. Okoudjou was supported

by the Alexander von Humboldt foundation. He would also

like to express his gratitude to the Institute of Mathematics

at the Technische Universit¨

at Berlin for its hospitality while

part of this work was completed. R. Wang was supported by

CRD Grant DNOISE 334810-05 and by the industrial sponsors

of the Seismic Laboratory for Imaging and Modelling: BG

Group, BGP, BP, Chevron, ConocoPhilips, Petrobras, PGS,

Total SA, and WesternGeco. Furthermore, the authors thank

Anton Kolleck (TU Berlin) for valuable discussions.

REFERENCES

[1] K. Ball, An elementary introduction to modern convex geometry, Flavors

of geometry, 1–58, Math. Sci. Res. Inst. Publ., 31, Cambridge Univ.

Press, Cambridge, 1997.

[2] J. J. Benedetto and M. Fickus, Finite Normalized Tight Frames, Adv.

Comput. Math., 18 (2003), 357–385.

[3] P. B¨

urgisser, F. Cucker, and M. Lotz, Coverage processes on spheres and

condition numbers for linear programming, The Annals of Probability,

38.2 (2010): 570–604.

[4] J. Cahill and X. Chen, A note on scalable frames, Proceedings of the

10th International Conference on Sampling Theory and Applications,

pp. 93–96.

[5] J. Cahill, M. Fickus, D. G. Mixon, M. J. Poteet, and N. Strawn,

Constructing finite frames of a given spectrum and set of lengths, Appl.

Comput. Harmon. Anal., 35 (2013), no. 1, 52–73.

JOURNAL NAME, VOLUME, NO., DATE 13

[6] P. G. Casazza, M. Fickus, and D. G. Mixon, Auto-tuning unit norm

frames, Appl. Comput. Harmon. Anal., 32 (2012), no. 1, 1-15.

[7] P. G. Casazza and G. Kutyniok, Finite Frame Theory, Eds., Birkh¨

auser,

Boston (2012).

[8] P. G. Casazza and M. Leon. Existence and construction of finite frames

with a given frame operator. Int. J. Pure Appl. Math, 63 (2010), 149–

158.

[9] O. Christensen, An introduction to frames and Riesz bases, Applied and

Numerical Harmonic Analysis. Birkh¨

auser Boston, Inc., Boston, MA,

2003.

[10] M. S. Copenhaver, Y. H. Kim, C. Logan, K. Mayfield, S. K. Narayan, and

J. Sheperd, Diagram vectors and tight frame scaling in finite dimensions,

Operators and Matrices, 8, no.1 (2014), 73 – 88.

[11] M. Fickus, B. D. Johnson, K. Kornelson, and K. A. Okoudjou, Convo-

lutional frames and the frame potential, Appl. Comput. Harmon. Anal.,

19 (2005), 77–91.

[12] O. G¨

uler, Foundations of Optimization, Graduate Texts in Mathematics,

258 Springer, New York, 2010.

[13] F. John, Extremum problems with inequalities as subsidiary conditions,

Studies and Essays Presented to R. Courant on his 60th Birthday,

January 8, 1948, 187–204. Interscience Publishers, Inc., New York, N.

Y., 1948.

[14] L. G. Khachiyan, Rounding of polytopes in the real number model of

computation, Math. Oper. Res., 21, 1996, 307–320.

[15] P. Kumar, E. A. Yildirim, Minimum volume enclosing ellipsoids and

core sets, J. Optim. Theory Appl., 126 (2005), 1–21.

[16] G. Kutyniok, K. A. Okoudjou, and F. Philipp, Scalable frames and

convex geometry, Spectra of Wavelets, Tilings, and Frames (Boulder,

CO, 2012), Contemp. Math. 345, Amer. Math. Soc., Providence, RI

(2013), to appear.

[17] G. Kutyniok, K. A. Okoudjou, F. Philipp, and E. K. Tuley, Scalable

frames, Linear Algebra and its Applications 438 (2013), 2225–2238.

[18] S. Nam, M. E. Davies, M. Elad, and R. Gribonval, The Cosparse

Analysis Model and Algorithms, Appl. Comput. Harmon. Anal., 34

(2013), 30–56.

[19] C P. Niculescu and L.-E. Persson, Convex Functions and Their Appli-

cations – A Contemporary Approach, Canadian Mathematical Society,

Springer, New York, 2006.

[20] R. Rubinstein, M. Zibulevsky, and M. Elad, Double Sparsity: Learning

Sparse Dictionaries for Sparse Signal Approximation, IEEE Trans.

Signal Process., 58 (2010), 1553–1564.

[21] N. Strawn, Optimization over finite frame varieties and structured

dictionary design, Appl. Comput. Harmon. Anal., 32 (2012), 413–434.

[22] N. Tomczak-Jaegermann, Banach-Mazur Distances and Finite-Dimen-

sional Operator Ideals, Pitman Monographs and Surveys in Pure and

Applied Mathematics, 38 Longman Scientific &Technical, Harlow;

copublished in the United States with John Wiley &Sons, Inc., New

York, 1989.