Linear Algebra, Matrix Theory, and Frame Theory

Linear algebra and matrix theory are an important tool in communication and signal processing. With collaborators and students I have studied a specific area of matrix theory and signal processing known as frame theory. Essentially frames are overcomplete basis expansions. They allow redundant representations of information for the purpose of correcting erasures, improving reliability, etc. One long-standing problem in frame theory has been creating the notion of a uniform frame. The idea of a uniform frame is to come up with a basic expansion such that each component of the basis carries equal “weight” on average. This requires a very uniform kind of structure. A particular area I have looked at with collaborators is equiangular frames. Essentially we have proposed a very elegant generalization of an orthogonal basis, known as Grassmannian frames or equiangular frames, which has connections to line packing and graph theory. We have also developed practical algorithms for constructing these frames. This work has provided tools for solving important problems in wireless communication and limited feedback.

Selected Publications

J. A. Tropp, I. Dhillon, R. W. Heath, Jr., and T. Strohmer “Constructing Packings in Grassmannian Manifolds via Alternating Projections,” Experimental Mathematics, vol. 17:1, pp. 9-35, 2008.

Packings on the Grassmann manifold have been used in several engineering applications, notably in the design of codebooks for limited feedback wireless systems. Previous work on designing Grassmannian packings was limited to either algebraic techniques (few) or the results of rather complex software. This paper presents an alternating minimization algorithm that can be used to construct packings on the Grassmann manifold. Compared with prior work, the algorithm is relatively simple to implement.

B. Mondal, R. Samanta, and R. W. Heath, Jr., “Congruent Voronoi Tessellations from an Equiangular Frame,” Applied and Computational Harmonic Analysis vol. 23, pp. 254-258, Sept. 2007.

It is proven that the Voronoi tessellations of the real projective space generated by an equiangular frame are congruent. Of particular interest, this means that an equiangular frame forms the best N-point representation of an isotropically distributed one-dimensional subspace in terms of mutual information and a subspace quantizer defined by an equiangular frame provides equal partial distortion.

M. A. Sustik, J. A. Tropp, I. Dhillon, and R. W. Heath, Jr., “On the Existence of Equiangular Tight Frames,”Linear Algebra and its Applications, vol. 426, no. 2-3, pp. 619-635, Oct. 2007.

This paper develops conditions for the existence of equiangular tight frames using a one-to-one correspondence between equivalence classes of real equiangular tight frames and strongly regular graphs of a certain type. Real equiangular tight frames generalize Grassmannian frames; they require that all the vectors are equiangular but permit the inner product to be larger than the Rankin bound.The arguments also extend to deliver novel necessary conditions for the existence of equiangular tight frames whose Gram matrices have entries drawn from a discrete set of complex numbers, leveraging a combination of field theory and graph theory.

I. Dhillon, R. W. Heath, Jr., M. Sustik, and J. A. Tropp “Generalized Finite Algorithms for Constructing Hermitian Matrices With Prescribed Diagonal And Spectrum”, SIAM Journal on Matrix Analysis and Applications, vol. 27, no. 1, pages 61-71, June 2005.

In this paper, we present new algorithms that can replace the diagonal entries of a Hermitian matrix by any set of diagonal entries that majorize the original set without altering the eigenvalues of the matrix. This has applications to signature design in CDMA systems for example. We present new finite-step algorithms that permit us to construct a class of Hermitian matrices satisfying spectral and diagonal constraints that is richer than the collection provided by prior results.

J. A. Tropp, I. Dhillon, R. W. Heath, Jr., T. Strohmer“Designing Structured Tight Frames Via An Alternating Projection Method,” *IEEE Trans. on Info. Theory*, vol. 51, no. 1, pp. 188-209, January 2005.

This paper proposes an alternating projection method that is versatile enough to solve a class of inverse eigenvalue problems, which includes the frame design problem. To apply this method, one only needs to solve a matrix nearness problem that arises naturally from the design specifications. Alternating between solutions provides a flexible solution for frame design that convergences under reasonable assumptions. The alternating minimization concept can be used for a variety of problems including structured frame design, finding CDMA signature sequences, and for limited feedback codebook design.

T. Strohmer and R. W. Heath, Jr. “Grassmannian Frames with Applications to Coding and Communications,” in Applied and Computational Harmonic Analysis Vol. 14, Issue 3, pp. 257-275, May 2003.

Grassmannian frames are uniform tight frames that the minimize the maximum correlation over the class of uniform frames of fixed redundancy. The name “Grassmannian” comes from the natural relationship to packing lines in the Grassmann manifold. We have investigated both finite-dimensional and infinite-dimensional Grassmannian frames. Our results extend recent findings on uniform tight frames and have nice applications to wireless communication and multiple description coding.