The efficiency of linear algebra operations for sparse matrices on modern high performance computing system is often constrained by the available memory bandwidth. We are interested in sparse matrices whose sparsity pattern is unknown. In this thesis, we study the efficiency of major storage schemes of sparse matrices during multiplication with dense vector. A proper reordering of columns or rows usually results in reduced memory traffic due to the improved data reuse. This thesis also proposes an efficient column ordering algorithm based on binary reflected gray code. Computational experiments show that this ordering results in increased performance in computing the product of a sparse matrix with a dense vector. / xi, 76 leaves : ill. ; 29 cm.

In computed tomography (CT) there are many situations where reconstruction may need to be performed with sparse-view data. In sparse-view CT imaging, strong streak artifacts may appear in conventionally reconstructed images due to the limited sampling rate, compromising image quality. Compressed sensing (CS) algorithm has shown potential to accurately recover images from highly undersampled data. In the past few years, total variation (TV)-base compressed sensing algorithms have been proposed to suppress the streak artifact in CT image reconstruction. In this paper, we formulate the problem of CT imaging under transform sparsity and sparse-view constraints, and propose a novel compressed sensing-based algorithm for CT image reconstruction from few-view data, in which we simultaneously minimize the ℓ1 norm, total variation and a least square measure. The main feature of our algorithm is the use of two sparsity transforms: discrete wavelet transform and discrete gradient transform, both of which are proven to be powerful sparsity transforms. Experiments with simulated and real projections were performed to evaluate and validate the proposed algorithm. The reconstructions using the proposed approach have less streak artifacts and reconstruction errors than other conventional methods.

A novel framework based on cluster co-occurrence and graph theory for structure discovery is applied to audio to find new types of audio objects which enable the compression of an input signal. These new objects differ from those found in current object coding schemes as their shape is not restricted by any a priori psychoacoustic knowledge. The framework is novel from an application perspective, as it marks the first time that graph theory is applied to audio, and with regards to theoretical developments, as it involves new extensions to the areas of unsupervised learning algorithms and frequent subgraph mining methods. Tests are performed using a corpus of audio files spanning a wide range of sounds. Results show that the framework discovers new types of audio objects which yield average respective overall and relative compression gains of 15.90% and 23.53% while maintaining a very good average audio quality with imperceptible changes.

In recent years several depth cameras have emerged on the consumer market, creating many interesting possibilities forboth professional and recreational usage. One example of such a camera is the Microsoft Kinect sensor originally usedwith the Microsoft Xbox 360 game console. In this master thesis a system is presented that utilizes this device in order to create an as accurate as possible 3D reconstruction of an indoor environment. The major novelty of the presented system is the data structure based on signed distance fields and voxel octrees used to represent the observed environment. / Under de senaste åren har flera olika avståndskameror lanserats på konsumentmarkanden. Detta har skapat många intressanta applikationer både i professionella system samt för underhållningssyfte. Ett exempel på en sådan kamera är Microsoft Kinect som utvecklades för Microsofts spelkonsol Xbox 360. I detta examensarbete presenteras ett system som använder Kinect för att skapa en så exakt rekonstruktion i 3D av en innomhusmiljö som möjligt. Den främsta innovationen i systemet är en datastruktur baserad på signed distance fields (SDF) och octrees, vilket används för att representera den rekonstruerade miljön.

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

This thesis develops a methodology for the segmentation of anatomical structures within "sparse" MR images. Sparse images were acquired in large numbers prior to the emergence of high-resolution MRI and they form the basis of many long term imaging studies. The term sparse refers to the fact that the volumetric image has very poor spatial resolution in the direction perpendicular to the slice plane. This leads to a significant degradation in image quality and effectively destroys the spatial continuity of the imaged object. Consequently, generic segmentation schemes --- particularly those based on voxel classification --- will yield poor results unless they have been augmented in some manner. Our Segmentation approach is based on a deformable simplex mesh surface, which iteratively interpolates extracted boundary point data. Prior information is mobilised at two levels. Boundary points are found using a matching algorithm based on a database of pre-specified piecewise constant models. These models represent possible idealised intensity profiles for the object boundary. In addition to the boundary model, there is a shape template. The template is generated from a training set of pre-segmented structures, which means that only shapes similar to those in the training set will be recovered. The segmentation proceeds in two phases. The first recovers the normal shape component, determined by the training set, whilst the second deforms smoothly from this constrained solution to produce a more veridical boundary representation. The segmentation scheme is applied to a number of sparse brain images. Qualitative validation --- accomplished by registering the surface extracted from the sparse data to a high resolution scan acquired at the same time-point --- indicates that a good approximation to the underlying boundary is obtainable from such images.

Thesis (M.Sc.)--Memorial University of Newfoundland, 1999. / Bibliography: leaves 64-68.

Thesis (M.S.)--University of Florida, 2005. / Title from title page of source document. Document formatted into pages; contains 79 pages. Includes vita. Includes bibliographical references.

Thesis (M.S.)--Oregon Graduate Center, 1987.

Thesis (M.S. in Modeling, Virtual Environment, and Simulation (MOVES))--Naval Postgraduate School, March 2007. / Thesis Advisor(s): Christian Darken. "March 2007." Includes bibliographical references (p. 115). Also available in print.