Equiangular tight frames and fourth root seidel matrices

In this paper we construct complex equiangular tight frames (ETFs). In particular, we study the grammian associated with an ETF whose off-diagonal entries consist entirely of fourth roots of unity. These ETFs are classified, and we also provide some computational techniques which give rise to previously undiscovered ETFs.     

Complex Hadamard matrices and equiangular tight frames

In this paper, we give a new construction of parametric families of complex Hadamard matrices of square orders, and connect them to equiangular tight frames. The results presented here generalize some of the recent ideas of Bodmann et al. [3] and extend the list of known equiangular tight frames. In particular, a (36, 21)-frame coming from a nontrivial cube root signature matrix is obtained for the first time.     

On the construction of highly symmetric tight frames and complex polytopes

Many “highly symmetric” configurations of vectors in C^d${\mathbb{C}}^d$, such as the vertices of the platonic solids and the regular complex polytopes, are equal-norm tight frames by virtue of being the orbit of the irreducible unitary action of their symmetry group. For nonabelian groups there are uncountably many such tight frames up to unitary equivalence. The aim of this paper is to single out those orbits which are particularly nice, such as those which are the vertices of a complex polytope. This is done by defining a finite class of tight frames of n   vectors for C^d${\mathbb{C}}^d$ (n and d fixed) which we call the highly symmetric tight frames. We outline how these frames can be calculated from the representations of abstract groups using a computer algebra package. We give numerous examples, with a special emphasis on those obtained from the (Shephard–Todd) finite reflection groups. The interrelationships between these frames with complex polytopes, harmonic frames, equiangular tight frames, and Heisenberg frames (maximal sets of equiangular lines) are explored in detail.     

Equiangular tight frames

A survey on equiangular tight frames in the space is presented. Several equivalent definitions of a tight frame are given. The construction of the Mercedes–Benz frame, the well-known example of a tight frame on the plane, is generalized to the space . The existence problems for the Mercedes–Benz systems and other more general equiangular tight frames are discussed. It is shown that the Welch inequality becomes the equality only on equiangular tight frames (if they exist). Necessary and sufficient conditions for the existence of an equiangular tight (n,m)-frame are formulated in terms of the so-called signature matrices. All the main results are completely proved. Bibliography: 37 titles. Illustrations: 3 figures. Translated from Problems in Mathematical Analysis 39 February, 2009, pp. 3–25.     

Maximally Equiangular Frames and Gauss Sums

In a finite-dimensional complex Euclidean space, a maximally equiangular frame is a tight frame which has a number of elements equal to the square of the dimension of the space, and in which the inner products of distinct elements are of constant magnitude. Though the general question of their existence remains open, many examples of maximally equiangular frames have been constructed as finite Gabor systems. These constructions involve number theory, specifically Schaar’s identity, which provides a reciprocity formula for quadratic Gauss sums. To be precise, Zauner used Schaar’s identity to compute the spectrum of a chirp-Fourier operator, the eigenvectors of which he conjectured to be well-suited for the construction of maximally equiangular Gabor frames. We provide two new characterizations of such frames, both of which further confirm the relevance of the theory of Gauss sums to this area of frame theory. We also show how the unique time-frequency properties of a particular cyclic chirp function may be exploited to provide a new, short and elementary proof of Schaar’s identity.      

Complex equiangular tight frames and erasures

In this paper we demonstrate that there are distinct differences between real and complex equiangular tight frames (ETFs) with regards to erasures. For example, we prove that there exist arbitrarily large non-trivial complex equiangular tight frames which are optimal against three erasures, and that such frames come from a unique class of complex ETFs. In addition, we extend certain results in Bodmann and Paulsen (2005) [2] to complex vector spaces as well as show that other results regarding real ETFs are not valid for complex ETFs.     

A note on equiangular tight frames

We settle a conjecture of Joseph Renes about the existence and construction of certain equiangular tight frames.     

Numerically erasure-robust frames

Given a channel with additive noise and adversarial erasures, the task is to design a frame that allows for stable signal reconstruction from transmitted frame coefficients. To meet these specifications, we introduce numerically erasure-robust frames. We first consider a variety of constructions, including random frames, equiangular tight frames and group frames. Later, we show that arbitrarily large erasure rates necessarily induce numerical instability in signal reconstruction. We conclude with a few observations, including some implications for maximal equiangular tight frames and sparse frames.     

Steiner equiangular tight frames

We provide a new method for constructing equiangular tight frames (ETFs). The construction is valid in both the real and complex settings, and shows that many of the few previously-known examples of ETFs are but the first representatives of infinite families of such frames. It provides great freedom in terms of the frame’s size and redundancy. This method also explicitly constructs the frame vectors in their native domain, as opposed to implicitly defining them via their Gram matrix. Moreover, in this domain, the frame vectors are very sparse. The construction is extremely simple: a tensor-like combination of a Steiner system and a regular simplex. This simplicity permits us to resolve an open question regarding ETFs and the restricted isometry property (RIP): we show that the RIP behavior of some ETFs is unfortunately no better than their coherence indicates.     

Equiangular tight frames with centroidal symmetry

An equiangular tight frame (ETF) is a set of unit vectors whose coherence achieves the Welch bound, and so is as incoherent as possible. Though they arise in many applications, only a few methods for constructing them are known. Motivated by the connection between real ETFs and graph theory, we introduce the notion of ETFs that are symmetric about their centroid. We then discuss how well-known constructions, such as harmonic ETFs and Steiner ETFs, can have centroidal symmetry. Finally, we establish a new equivalence between centroid-symmetric real ETFs and certain types of strongly regular graphs (SRGs). Together, these results give the first proof of the existence of certain SRGs, as well as the disproofs of the existence of others.     

On the construction of equiangular frames from graphs

We give details of the 1-1 correspondence between equiangular frames of n vectors for and graphs with n vertices. This has been studied recently for tight equiangular frames because of applications to signal processing and quantum information theory. The nontight examples given here (which correspond to graphs with more than 2 eigenvalues) have the potential for similar applications, e.g., the frame corresponding to the 5-cycle graph is the unique Grassmannian frame of 5 vectors in openR³. Further, the associated canonical tight frames have a small number of angles in many cases.     

Some Birkhoff interpolation problems on the roots of unity

The object of this note is to study three row almost Hermitian incidence matrices and to give sufficient conditions when the corresponding interpolation problem is regular on the roots of unity. In particular, a three row almost Hermitian matrix with only two nonzero entries in one row is regular on the cube roots of unity. Other situations are also examined in detail.     

The symmetry group of a finite frame

We define the symmetry group of a finite frame as a group of permutations on its index set. This group is closely related to the symmetry group of Vale and Waldron (2005) [12] for tight frames: they are isomorphic when the frame is tight and has distinct vectors. The symmetry group is the same for all similar frames, in particular for a frame, its dual and canonical tight frames. It can easily be calculated from the Gramian matrix of the canonical tight frame. Further, a frame and its complementary frame have the same symmetry group. We exploit this last property to construct and classify some classes of highly symmetric tight frames.     

The Structure of Minimizers of the Frame Potential on Fusion Frames

In this paper we study the fusion frame potential that is a generalization of the Benedetto-Fickus (vectorial) frame potential to the finite-dimensional fusion frame setting. We study the structure of local and global minimizers of this potential, when restricted to suitable sets of fusion frames. These minimizers are related to tight fusion frames as in the classical vector frame case. Still, tight fusion frames are not as frequent as tight frames; indeed we show that there are choices of parameters involved in fusion frames for which no tight fusion frame can exist. We exhibit necessary and sufficient conditions for the existence of tight fusion frames with prescribed parameters, involving the so-called Horn-Klyachko’s compatibility inequalities. The second part of the work is devoted to the study of the minimization of the fusion frame potential on a fixed sequence of subspaces, with a varying sequence of weights. We related this problem to the index of the Hadamard product by positive matrices and use it to give different characterizations of these minima.     

The Road to Deterministic Matrices with the Restricted Isometry Property

The restricted isometry property (RIP) is a well-known matrix condition that provides state-of-the-art reconstruction guarantees for compressed sensing. While random matrices are known to satisfy this property with high probability, deterministic constructions have found less success. In this paper, we consider various techniques for demonstrating RIP deterministically, some popular and some novel, and we evaluate their performance. In evaluating some techniques, we apply random matrix theory and inadvertently find a simple alternative proof that certain random matrices are RIP. Later, we propose a particular class of matrices as candidates for being RIP, namely, equiangular tight frames (ETFs). Using the known correspondence between real ETFs and strongly regular graphs, we investigate certain combinatorial implications of a real ETF being RIP. Specifically, we give probabilistic intuition for a new bound on the clique number of Paley graphs of prime order, and we conjecture that the corresponding ETFs are RIP in a manner similar to random matrices.     

Tight wavelet frames via semi-definite programming

In this paper we state the “oblique extension principle” as a problem of semi-definite programming. Using this optimization technique we show that the existence of a tight frame is equivalent to the existence of a certain matrix from a cone of positive semi-definite matrices, whose entries satisfy linear constraints. We also discuss how to use the optimization techniques to reduce the number of frame generators in univariate and multivariate cases. We apply our results for constructing tight frames for several subdivision schemes.     

Recovery of signals from unordered partial frame coefficients

In this paper, we study the feasibility and stability of recovering signals in finite-dimensional spaces from unordered partial frame coefficients. We prove that with an almost self-located robust frame, any signal except from a Lebesgue measure zero subset can be recovered from its unordered partial frame coefficients. However, the recovery is not necessarily stable with almost self-located robust frames. We propose a new class of frames, namely self-located robust frames, that ensures stable recovery for any input signal with unordered partial frame coefficients. In particular, the recovery is exact whenever the received unordered partial frame coefficients are noise-free. We also present some characterizations and constructions for (almost) self-located robust frames. Based on these characterizations and construction algorithms, we prove that any randomly generated frame is almost surely self-located robust. Moreover, frames generated with cube roots of different prime numbers are also self-located robust.     

Toward the classification of biangular harmonic frames

Equiangular tight frames (ETFs) and biangular tight frames (BTFs) – sets of unit vectors with basis-like properties whose pairwise absolute inner products admit exactly one or two values, respectively – are useful for many applications. A well-understood class of ETFs are those which manifest as harmonic frames – vector sets defined in terms of the characters of finite abelian groups – because they are characterized by combinatorial objects called difference sets.This work is dedicated to the study of the underlying combinatorial structures of harmonic BTFs. We show that if a harmonic frame is generated by a divisible difference set, a partial difference set or by a special structure with certain Gauss summing properties – all three of which are generalizations of difference sets that fall under the umbrella term “bidifference set” – then it is either a BTF or an ETF. However, we also show that the relationship between harmonic BTFs and bidifference sets is not as straightforward as the correspondence between harmonic ETFs and difference sets, as there are examples of bidifference sets that do not generate harmonic BTFs. In addition, we study another class of combinatorial structures, the nested divisible difference sets, which yields an example of a harmonic BTF that is not generated by a bidifference set.