Finite normalized tight frames

A few years ago, I read the following paper, and I have since considered it to be the source of my interest in finite frame theory:

Finite normalized tight frames

John J. Benedetto, Matthew Fickus

It’s all about unit norm tight frames (UNTFs), which are short, fat matrices with additional properties. Back in the day, these were called “normalized tight frames,” but the finite frame community has since agreed to call them UNTFs. To study UNTFs, this paper introduces an objective function called the frame potential. Taking inspiration from physics, the authors consider an alternate universe in which unit-norm vectors repel each other much like electrons, except instead of seeking distance, the vectors seek orthogonality. After redefining the forces of nature, potential energy is derived: An M\times N matrix F=[f_1\cdots f_N] with unit-norm columns has frame potential

\displaystyle\mathrm{FP}(F):=\sum_{n=1}^N\sum_{n'=1}^N|\langle f_n,f_{n'}\rangle|^2=\|F^*F\|_{\mathrm{HS}}^2.

It is well known that the frame potential of any short, fat matrix with unit-norm columns satisfies \|F^*F\|_{\mathrm{HS}}^2\geq N^2/M, and interestingly, equality is achieved if and only if F is a UNTF. With this context in mind, the following is the main result of the paper:

Theorem (Benedetto, Fickus). Every local minimizer of the frame potential is a unit norm tight frame.

The proof of this result uses the contrapositive: Given any short, fat matrix with unit-norm columns that isn’t tight, the authors find a family of arbitrarily close matrices, each having a strictly smaller frame potential. This result has a few important consequences. First, since the frame potential is a continuous function on a compact set, it’s guaranteed to have a global minimum, which will certainly be a local minimum. Thus, M\times N UNTFs exist whenever N\geq M. Also, since UNTFs are the matrices which achieve equality in the lower bound \mathrm{FP}(F)\geq N^2/M, we deduce that every local minimum of the frame potential is a global minimum. Lastly, this result indicates that finding UNTFs reduces to performing gradient descent on the frame potential, and the convergence of such a method was later established to solve an important problem regarding the approximation of UNTFs.

Beyond its results, this paper does a fantastic job of building intuition for UNTFs and their construction. I highly recommend giving it a look.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s