Three problems in compressive sensing, namely, recovery of sparse signals from noise-free measurements, recovery of sparse signals from noisy measurements, and recovery of so called block-sparse signals from noisy measurements, are investigated. In Chapter 2, the reconstruction of sparse signals from noise-free measurements is investigated and three algorithms are developed. The first and second algorithms minimize the approximate L0 and Lp pseudonorms, respectively, in the null space of the measurement matrix using a sequential quasi-Newton algorithm. An efficient line search based on Banach's fixed-point theorem is developed and applied in the second algorithm. The third algorithm minimizes the approximate Lp pseudonorm in the null space by using a sequential conjugate-gradient (CG) algorithm. Simulation results are presented which demonstrate that the proposed algorithms yield improved signal reconstruction performance relative to that of the iterative reweighted (IR), smoothed L0 (SL0), and L1-minimization based algorithms. They also require a reduced amount of computations relative to the IR and L1-minimization based algorithms. The Lp-minimization based algorithms require less computation than the SL0 algorithm. In Chapter 3, the reconstruction of sparse signals and images from noisy measurements is investigated. First, two algorithms for the reconstruction of signals are developed by minimizing an Lp-pseudonorm regularized squared error as the objective function using the sequential optimization procedure developed in Chapter 2. The first algorithm minimizes the objective function by taking steps along descent directions that are computed in the null space of the measurement matrix and its complement space. The second algorithm minimizes the objective function in the time domain by using a CG algorithm. Second, the well known total variation (TV) norm has been extended to a nonconvex version called the TVp pseudonorm and an algorithm for the reconstruction of images is developed that involves minimizing a TVp-pseudonorm regularized squared error using a sequential Fletcher-Reeves' CG algorithm. Simulation results are presented which demonstrate that the first two algorithms yield improved signal reconstruction performance relative to the IR, SL0, and L1-minimization based algorithms and require a reduced amount of computation relative to the IR and L1-minimization based algorithms. The TVp-minimization based algorithm yields improved image reconstruction performance and a reduced amount of computation relative to Romberg's algorithm. In Chapter 4, the reconstruction of so-called block-sparse signals is investigated. The L2/1 norm is extended to a nonconvex version, called the L2/p pseudonorm, and an algorithm based on the minimization of an L2/p-pseudonorm regularized squared error is developed. The minimization is carried out using a sequential Fletcher-Reeves' CG algorithm and the line search described in Chapter 2. A reweighting technique for the reduction of amount of computation and a method to use prior information about the locations of nonzero blocks for the improvement in signal reconstruction performance are also proposed. Simulation results are presented which demonstrate that the proposed algorithm yields improved reconstruction performance and requires a reduced amount of computation relative to the L2/1-minimization based, block orthogonal matching pursuit, IR, and L1-minimization based algorithms. / Graduate

Consider the following system model y = Ax + e, where x is n-dimensional sparse signal, y is the measurement vector in a much lower dimension m, A is the measurement matrix and e is the error in our measurements. The Dantzig selector estimates x by solving the following optimization problem minimize || x ||₁ subject to || A'(Ax - y) ||∞ ≤ ε, (DS). This is a convex program and can be recast into a linear program and solved using any modern optimization method e.g., interior point methods. We propose a fast and efficient scheme for solving the Dantzig Selector (DS), which we call "Primal-Dual pursuit". This algorithm can be thought of as a "primal-dual homotopy" approach to solve the Dantzig selector (DS). It computes the solution to (DS) for a range of successively relaxed problems, by starting with a large artificial ε and moving towards the desired value. Our algorithm iteratively updates the primal and dual supports as ε reduces to the desired value, which gives final solution. The homotopy path solution of (DS) takes with varying ε is piecewise linear. At some critical values of ε in this path, either some new elements enter the support of the signal or some existing elements leave the support. We derive the optimality and feasibility conditions which are used to update the solutions at these critical points. We also present a detailed analysis of primal-dual pursuit for sparse signals in noiseless case. We show that if our signal is S-sparse, then we can find all its S elements in exactly S steps using about "S² log n" random measurements, with very high probability.

Fusion frames and block sparse recovery are of interest in signal processing and communication applications. In these applications it is required that the fusion frame have some desirable properties. One such requirement is that the fusion frame be tight and its subspaces form an optimal packing in a Grassmannian manifold. Such fusion frames are called Grassmannian fusion frames. Grassmannian frames are known to be optimal dictionaries for sparse recovery as they have minimum coherence. By analogy Grassmannian fusion frames are potential candidates as optimal dictionaries in block sparse processing. The present work intends to study fusion frames in finite dimensional vector spaces assuming a specific structure useful in block sparse signal processing. The main focus of our work is the design of Grassmannian fusion frames and their implication in block sparse recovery. We will consider burst error correction as an application of block sparsity and fusion frame concepts. We propose two new algebraic methods for designing Grassmannian fusion frames. The first method involves use of Fourier matrix and difference sets to obtain a partial Fourier matrix which forms a Grassmannian fusion frame. This fusion frame has a specific structure and the parameters of the fusion frame are determined by the type of difference set used. The second method involves constructing Grassmannian fusion frames from Grassmannian frames which meet the Welch bound. This method uses existing constructions of optimal Grassmannian frames. The method, while fairly general, requires that the dimension of the vector space be divisible by the dimension of the subspaces. A lower bound which is an analog of the Welch bound is derived for the block coherence of dictionaries along with conditions to be satisfied to meet the bound. From these results we conclude that the matrices constructed by us are optimal for block sparse recovery from block coherence viewpoint. There is a strong relation between sparse signal processing and error control coding. It is known that burst errors are block sparse in nature. So, here we attempt to solve the burst error correction problem using block sparse signal recovery methods. The use of Grassmannian fusion frames which we constructed as optimal dictionary allows correction of maximum possible number of errors, when used in conjunction with reconstruction algorithms which exploit block sparsity. We also suggest a modification to improve the applicability of the technique and point out relationship with a method which appeared previously in literature. As an application example, we consider the use of the burst error correction technique for impulse noise cancelation in OFDM system. Impulse noise is bursty in nature and severely degrades OFDM performance. The Grassmannian fusion frames constructed with Fourier matrix and difference sets is ideal for use in this application as it can be easily incorporated into the OFDM system.