Search

The study of codes, classically motivated by the need to communicate information reliably in the presence of error, has found new life in fields as diverse as network communication, distributed storage of data, and even has connections to the design of linear measurements used in compressive sensing. But in all contexts, a code typically involves exploiting the algebraic or geometric structure underlying an application. In this thesis, we examine several problems in coding theory, and try to gain some insight into the algebraic structure behind them. The first is the study of the entropy region - the space of all possible vectors of joint entropies which can arise from a set of discrete random variables. Understanding this region is essentially the key to optimizing network codes for a given network. To this end, we employ a group-theoretic method of constructing random variables producing so-called "group-characterizable" entropy vectors, which are capable of approximating any point in the entropy region. We show how small groups can be used to produce entropy vectors which violate the Ingleton inequality, a fundamental bound on entropy vectors arising from the random variables involved in linear network codes. We discuss the suitability of these groups to design codes for networks which could potentially outperform linear coding. The second topic we discuss is the design of frames with low coherence, closely related to finding spherical codes in which the codewords are unit vectors spaced out around the unit sphere so as to minimize the magnitudes of their mutual inner products. We show how to build frames by selecting a cleverly chosen set of representations of a finite group to produce a "group code" as described by Slepian decades ago. We go on to reinterpret our method as selecting a subset of rows of a group Fourier matrix, allowing us to study and bound our frames' coherences using character theory. We discuss the usefulness of our frames in

We explore the problem of deterministically constructing frames and matrices with low coherence, which arises in areas such as compressive sensing, spherical codes, and MIMO communications. In particular, we present a generalization of the familiar harmonic frame by selecting a subset of rows of the generalized discrete Fourier transform matrix over finite groups. We apply our methods to the group SL_2(F_q) and show how to produce frames with remarkably low coherence, for which we provide upper bounds.

Designing low coherence matrices and low-correlation frames is a point of interest in many fields including compressed sensing, MIMO communications and quantum measurements. The challenge is that one must control the (^n_2) pairwise inner products between the frame elements. In this paper, we exploit the group code approach of David Slepian [1], which constructs frames using unitary group representations and which in general reduces the number of distinct inner products to n - 1. We demonstrate how to efficiently find optimal representations of cyclic groups, and we show how basic abelian groups can be used to construct tight frames that have the same dimensions and inner products as those arising from certain more complex nonabelian groups. We support our work with theoretical bounds and simulations.

The problem of designing low coherence matrices and lowcorrelation frames arises in a variety of fields, including compressed sensing, MIMO communications and quantum measurements. The challenge is that one must control the n/2 pairwise inner products of the columns of the matrix. In this paper, we follow the group code approach of David Slepian, which constructs frames using unitary group representations and which in general reduces the number of distinct inner products to n-1. We examine representations of cyclic groups as well as generalized dihedral groups, and we expand upon previous results which bound the coherence of the resulting frames.

The problem of designing low coherence matrices and low-correlation frames arises in a variety of fields, including compressed sensing, MIMO communications and quantum measurements. The challenge is that one must control the (^n_2) pairwise inner products of the columns of the matrix. In this paper, we follow the group code approach of David Slepian [1], which constructs frames using unitary group representations and which in general reduces the number of distinct inner products to n-1. When n is a prime p, we present a carefully chosen representation which reduces the number of distinct inner products further to ^(n-1)/_m, where m is the number of rows in the matrix. The resulting frames have superior performance to many earlier frame constructions and, in some cases, yield frames with optimally low coherence. We further expand a connection between frames and difference sets noted first in [2] to find bounds on the coherence when ^(n-1)/_m = 2 and 3.

We propose a new algorithm to recover a sparse signal from a system of linear measurements. By projecting the measured signal onto a properly chosen subspace, we can use the projection to zero in on a low-sparsity portion of our original signal, which we can recover using ℓ_1-minimization. We can then recover the remaining portion of our signal from an overdetermined system of linear equations. We prove that our scheme improves the threshold of ℓ_1-minimization, and we derive an upper bound for this new threshold. We support our theoretical results with numerical simulations which demonstrate that certain classes of signals come close to achieving this upper bound.

In principle, network codes derived from non-Abelian groups can be used to attain every point in the capacity region of wired acyclic networks. However, group codes derived from a particular group, and its subgroups, is useful only if it can model independent sources, as well as violate the Ingleton bound which restricts the capacity region obtainable by linear network codes. We study both the independent source and the Ingleton-violating requirement for subgroups of the groups PGL(2,p) and GL(2,p) with primes p ≥ 5. For both these groups we demonstrate that the requirements can be met, which suggests that PGL(2,p) and GL(2,p) are rich enough groups to construct network codes superior to linear ones. We also construct a model for independent sources using the direct product of the aforementioned groups.