Sparse Description of Linear Systems and Application in Tomography

The area of compressed sensing (CS) deals with finding sparse descriptions to some linear systems. The premise in providing such descriptions is based on the fact that many natural data sets can be represented in terms of a far fewer coefficients than their actual dimension in some basis or redundant dictionary. In particular, CS finds sparse solutions or approximations (i.e, the solutions with very few nonzero components) to the matrix equations of type y = Ax or y � Ax. The matrix A (of size m � N) and the vector y may have different meanings in different applications. For instance, if A has elements generated as sinusoidal functions, y represents the vector of Fourier coefficients of x. In applications that involve compressed data acquisition, the associated reconstruction problem boils down to dealing with an underdetermined system (i.e, m < N). While in applications such as denoising and system identification, one often encounters overdetermined systems (i.e, m > N). Both the scenarios are in sharp contrast mathematically, in the sense that the case m > N in general does not admit any solution, while the case m < N in general admits infinitely many solutions. For various applications as mentioned above, the sparse solutions or approximations to both types of systems are needed. The thesis is concerned with underdetermined (UD) as well as overdetermined (OD) systems. In the UD case, our objectives center around determining a preconditioner that improves the sparse recovery properties of the associated system matrix, generated by certain classes of frames. In particular, we provide sufficient conditions that ensure guaranteed improvement in sparse recovery properties which preconditioning brings in. In view of the potential of sparsity based methods, we address interior as well as incomplete data problems in Computed Tomography (CT). In the OD case, nevertheless, we provide a sparse approximation to y � Ax via a new matrix factorization method. A detailed comparison with popular solvers such as the OMP and LASSO is also included. Computed Tomography (CT) is one of the significant research areas in the field of medical image analysis. As X-rays used in CT are harmful to human bodies, it is necessary to reduce the dosage while maintaining good quality in reconstruction. The reduced dosage problem via the discretization of Radon transform translates into an under-determined system of linear equations. The associated sensing matrix, generated from the Radon transform, is very large in size and is not known to satisfy the sparse recovery properties. Our work attempts to establish the sparse recovery properties of Radon sensing matrix via careful choice of angular and radial parameters. This is in contrast to the existing results that remain focused on improving sparse solvers as applicable to CT. In addition to analyzing the Radon sensing matrix for its sparse recovery properties, we determine a preconditioner that is capable of being used in such large scale problems as in CT. The contributions of the thesis may be summarized as follows: � A convex optimization technique, along with analytical guarantees, for designing the vii preconditioner that yields a sensing matrix with improved sparse recovery properties1 � Analysis of sparse recovery properties of Radon sensing matrix and its application in CT. In particular, the preconditioner improving the sparse recovery properties of Radon matrix (A) is obtained from the following optimization problem: min kATX