Signal Reconstruction from Frame and Sampling Erasures

This dissertation is concerned with the efficient reconstruction of signals from frame coefficient erasures at known locations. Three methods of perfect reconstruction from frame coefficient erasures will be discussed. These reconstructions are more efficient than older methods in the literature because they only require an L × L matrix inversion, where L denotes the cardinality of the erased set of indices. This is a significant improvement over older methods which require an n × n matrix inversion, where n denotes the dimension of the underlying Hilbert space. The first of these methods, called Nilpotent Bridging, uses a small subset of the non-erased coefficients to reconstruct the erased coefficients. This subset is called the bridge set. To perform the reconstruction an equation, known as the bridge equation, must be solved. A proof is given that under a very mild assumption there exists a bridge set of size L for which the bridge equation has a solution. A stronger result is also proven that shows that for a very large class of frames, no bridge set search is required. We call this set of frames the set of full skew-spark frames. Using the Baire Category Theorem and tools from Matrix Theory, the set of full skew-spark frames is shown to be an open, dense subset of the set of all frames in finite dimensions. The second method of reconstruction is called Reduced Direct Inversion because it provides a basis-free, closed-form formula for inverting a particular n × n matrix, which only requires the inversion of an L × L matrix. By inverting this matrix we obtain another efficient reconstruction formula. The final method considered is a continuation of work by Han and Sun. The method utilizes an Erasure Recovery Matrix, which is a matrix that annihilates the range of the analysis operator for a frame. Because of this, the erased coefficients can be reconstructed using a simple pseudo-inverse technique. For each method, a discussion of the stability of our algorithms is presented. In particular, we present numerical experiments to investigate the effects of normally distributed additive channel noise on our reconstruction. For Reduced Direct Inversion and Erasure Recovery Matrices, using the Restricted Isometry Property, we construct classes of frames which are numerically robust to sparse channel noise. For these frames, we provide error bounds for sparse channel noise