FRAMES AS CODES FOR STRUCTURED ERASURES

This dissertation studies the role of frames as codes. Frames are families of vectors that give rise to embeddings of Hilbert spaces. These embeddings can be interpreted as codes, because possible linear dependencies among frame vectors can be used to recover missing components in the embedded data, so-called erasures. This dissertation is dedicated to structured erasures. One type of structured erasure occurs when consecutive frame coefficients are lost due to the occurrence of random burst errors. Assuming that the distribution of bursts is invariant under cyclic shifts and that the burst-length statistics are known, we wish to find frames of a given size, which minimize the mean-square reconstruction error for the encoding of vectors in a complex finite-dimensional Hilbert space. We derive statistical error bounds for a given Parseval frame and relate them to its generalized frame potential. In the case of cyclic Parseval frames, we find a family of frames which minimizes the upper bound. Under certain conditions, these minimizers are identical to complex Bose- Chaudhuri-Hocquenghem(BCH) codes discussed in the literature. The accuracy of our upper bounds for the mean-square error is substantiated by complementary lower bounds. Another part of the dissertation concerns the transmission of digital media, typically following a protocol that splits data into a number of packets having a fixed size. When such packets are sent over a network such as the Internet, there is in principle no guarantee of reliability, that is, the contents of each packet may become corrupted in the course of transmission or entire packets may be lost due to buffer overflows. We assume that during the transmission, only a few of these packets are corrupted or lost. In this part of the dissertation we adapt ideas by Candes and Tao in order to construct frames as codes for such erasures. The frames are associated with consistency checks for the data that are obtained from random matrices whose entries are independent realizations of a Gaussian random variable. In addition to the random Gaussian matrices, we use random projections to achieve recovery based on a low dimensional check-sum measurement. We use a generalized technique of l_1 minimization to reconstruct the error vector from these measurements.Mathematics, Department o