<p> The focus of this thesis is on the utilization of the sparsity concept in solving some challenging problems, e.g., finding a unique solution to the under-determined linear system of equations in which the number of equations is less than the number of unknowns. This concept is extended to the problem of solving the under-determined blind source separation (BSS) problem in which the number of source signals is greater than the number of sensors and both the mixing matrix and the source signals are unknowns. In this respect we study three problems: </p> <p> 1. Developing some algorithms for solving the under-determined linear system of equations for the case of a sparse solution vector. In this thesis we develop a new methodology for minimizing a class of non-convex (concave on the non-negative orthant) functions for solving the aforementioned problem. The proposed technique is based on locally replacing the original objective function by a quadratic convex function which is easily minimized. For a certain selection of the convex objective function, the existing class of algorithms called Iterative Re-weighted Least Squares (IRLS) can be derived from the proposed methodology. Thus the proposed algorithms are a generalization and unification of the previous methods. In this thesis we also propose a convex objective function that produces an algorithm that can converge to a sparse solution vector in significantly fewer iterations than the IRLS algorithms.</p> <p> 2. Solving the under-determined BSS problem by developing new clustering algorithms for estimating the mixing matrix. The under-determined BSS problem is usually solved by following a two-step approach, in which the mixing matrix is estimated in the first step, then the sources are estimated in the second step. For the case of sparse sources, the mixing matrix is usually estimated by clustering the columns of the observation matrix. In this thesis we develop three novel clustering algorithms that can efficiently estimate the mixing matrix, as well as the number of sources, which is usually unknown. Numerical simulations verify the efficiency of the proposed algorithms compared to some well known algorithms that are usually used for solving the same problem.</p> <p> 3. Extraction of a desired source signal from a linear mixture of hidden sources when prior information is available about the desired source signal. There are many situations in which one is interested in extracting a specific source signal. The a priori available information about the desired source signal could be temporal, spatial, or both. In this thesis we develop new algorithms for extracting a desired sparse source signal from a linear mixture of hidden sources. The information available about the desired source signal, as well as its sparsity, are incorporated in an optimization problem for extracting this source signal. Four different algorithms have been developed for solving this problem. Numerical simulations show that the proposed algorithms can be used successfully for removing different kind of artifacts from real electroencephalographic (EEG) data and for estimating the event related potential (ERP) signal from synthesized EEG data.</p> / Thesis / Doctor of Philosophy (PhD)

Group sparsity reveals underlying sparsity patterns and contains rich structural information in data. Hence, exploiting group sparsity will facilitate more efficient techniques for recovering large and complicated data in applications such as compressive sensing, statistics, signal and image processing, machine learning and computer vision. This thesis develops efficient algorithms for solving a class of optimization problems with group sparse solutions, where arbitrary group configurations are allowed and the mixed L21-regularization is used to promote group sparsity. Such optimization problems can be quite challenging to solve due to the mixed-norm structure and possible grouping irregularities. We derive algorithms based on a variable splitting strategy and the alternating direction methodology. Extensive numerical results are presented to demonstrate the efficiency, stability and robustness of these algorithms, in comparison with the previously known state-of-the-art algorithms. We also extend the existing global convergence theory to allow more generality.

In this overview of the recent Curvelet Reconstruction with Sparsity-promoting Inversion (CRSI) method, we present our latest 2-D and 3-D interpolation results on both synthetic and real datasets. We compare these results to interpolated data using other existing methods. Finally, we discuss the challenges related to sparsity-promoting solvers for the large-scale problems the industry faces.

No description available.

Compressed sensing (CS) theory has demonstrated that sparse signals can be reconstructed from far fewer measurements than suggested by the Nyquist sampling theory. CS has received great attention recently as an alternative to the current paradigm of sampling followed by compression. Initial CS operated under the implicit assumption that the sparsity domain coefficients are independently distributed. Recent results, however, show that exploiting statistical dependencies in sparse signals improves the recovery performance of CS. This dissertation proposes model-based CS reconstruction techniques. Statistical dependency models for several CS problems are proposed and incorporated into different CS algorithms. These models allow incorporation of a priori information into the CS reconstruction problems. Firstly, we propose the use of a Bayes least squares-Gaussian scale mixtures (BLS-GSM) model for CS recovery of natural images. The BLS-GSM model is able to exploit dependencies inherent in wavelet coefficients. This model is incorporated into several recent CS algorithms. The resulting methods significantly reduce reconstruction errors and/or the number of measurements required to obtain a desired reconstruction quality, when compared to state-of-the-art model-based CS methods in the literature. The model-based CS reconstruction techniques are then extended to video. In addition to spatial dependencies, video sequences exhibit significant temporal dependencies as well. In this dissertation, a model for jointly exploiting spatial and temporal dependencies in video CS is also proposed. The proposed method enforces structural self-similarity of image blocks within each frame as well as across neighboring frames. By sparsely representing collections of similar blocks, dominant image structures are retained while noise and incoherent undersampling artifacts are eliminated. A new video CS algorithm which incorporates this model is then proposed. The proposed algorithm iterates between enforcement of the self-similarity model and consistency with measurements. By enforcing measurement consistency in residual domain, sparsity is increased and CS reconstruction performance is enhanced. The proposed approach exhibits superior subjective image quality and significantly improves peak-signal-to-noise ratio (PSNR) and structural similarity index measure (SSIM).Finally, a model-based CS framework is proposed for super resolution (SR) reconstruction. The SR reconstruction is formulated as a CS problem and a self-similarity model is incorporated into the reconstruction. The proposed model enforces similarity of collections of blocks through shrinkage of their transform-domain coefficients. A sharpening operation is performed in transform domain to emphasize edge recovery. The proposed method is compared with state-of-the-art SR techniques and provides high-quality SR images, both quantitatively and subjectively.

This thesis consists of three parts. The first part is an introduction and referencessome recent work on 2D electromagnetic scattering problems at high frequencies. It alsopresents the basic integral equation types for impenetrable objects. A brief discussionof the standard elements of the method of moments is followed by summaries of thepapers.Paper I presents an accurate implementation of the method of moments for a perfectlyconducting cylinder. A scaling for the rapid variation of the solution improves accuracy.At high frequencies, the method of moments leads to a large dense system of equations.Sparsity in this system is obtained by modifying the integration path in the integralequation. The modified path reduces the accuracy in the deep shadow.In paper II, a hybrid method is used to handle the standing waves that are prominentin the shadow for the TE case. The shadow region is treated separately, in a hybridscheme based on a priori knowledge about the solution. An accurate method to combinesolutions in this hybrid scheme is presented.

In this thesis, we investigate the application of compressive sensing and sparse signal processing techniques to image compression and inpainting problems. Considering that many signals are sparse in certain transformation domain, a natural question to ask is: can an image be represented by as few coefficients as possible? In this thesis, we propose a new model for image compression/decompression based on sparse representation. We suggest constructing an overcomplete dictionary by combining two compression matrices, the discrete cosine transform (DCT) matrix and Hadamard-Walsh transform (HWT) matrix, instead of using only one transformation matrix that has been used by the common compression techniques such as JPEG and JPEG2000. We analyze the Structural Similarity Index (SSIM) versus the number of coefficients, measured by the Normalized Sparse Coefficient Rate (NSCR) for our approach. We observe that using the same NSCR, SSIM for images compressed using the proposed approach is between 4%-17% higher than when using JPEG. Several algorithms have been used for sparse coding. Based on experimental results, Orthogonal Matching Pursuit (OMP) is proved to be the most efficient algorithm in terms of computational time and the quality of the decompressed image. In addition, based on compressive sensing techniques, we propose an image inpainting approach, which could be used to fill missing pixels and reconstruct damaged images. In this approach, we use the Gradient Projection for Sparse Reconstruction (GPSR) algorithm and wavelet transformation with Daubechies filters to reconstruct the damaged images based on the information available in the original image. Experimental results show that our approach outperforms existing image inpainting techniques in terms of computational time with reasonably good image reconstruction performance.

In social and economic studies many of the collected variables are measured on a nominal scale, often with a large number of categories. The definition of categories can be ambiguous and different classification schemes using either a finer or a coarser grid are possible. Categorization has an impact when such a variable is included as covariate in a regression model: a too fine grid will result in imprecise estimates of the corresponding effects, whereas with a too coarse grid important effects will be missed, resulting in biased effect estimates and poor predictive performance. To achieve an automatic grouping of the levels of a categorical covariate with essentially the same effect, we adopt a Bayesian approach and specify the prior on the level effects as a location mixture of spiky Normal components. Model-based clustering of the effects during MCMC sampling allows to simultaneously detect categories which have essentially the same effect size and identify variables with no effect at all. Fusion of level effects is induced by a prior on the mixture weights which encourages empty components. The properties of this approach are investigated in simulation studies. Finally, the method is applied to analyse effects of high-dimensional categorical predictors on income in Austria.

Le titre de cette thèse de doctorat est formé de trois mots clés: parcimonie, image hyperspectrale, et détection de cibles. La parcimonie signifie généralement « petit en nombre ou quantité, souvent répartie sur une grande zone ». Une image hyperspectrale est constituée d'une série d'images de la même scène spatiale, mais prises dans plusieurs dizaines de longueurs d'onde contiguës et très étroites, qui correspondent à autant de "couleurs". Lorsque la dimension spectrale est très grande, la détection de cibles devient délicate et caractérise une des applications les plus importantes pour les images hyperspectrales. Le but principal de cette thèse de doctorat est de répondre à la question « Comment et Pourquoi la parcimonie peut-elle être exploitée pour détecter de cibles dans les images hyperspectrales ? ». La réponse à cette question nous a permis de développer des méthodes de détection de cibles prenant en compte l'hétérogénéité de l'environnement, le fait que les objets d'intérêt sont situés dans des parties relativement réduites de l'image observée et enfin que l'estimation de la matrice de covariance d'un pixel d'une image hyperspectrale peut être compliquée car cette matrice appartient à un espace de grande dimension. Les méthodes proposées sont évaluées sur des données synthétiques ainsi que réelles, dont les résultats démontrent leur efficacité pour la détection de cibles dans les images hyperspectrales. / The title of this PhD thesis is formed by three keywords: sparsity, hyperspectral image, and target detection. Sparsity is a word that is used everywhere and in everyday life. It generally means « small in number or amount, often spread over a large area ». A hyperspectral image is a three dimensional data cube consisting of a series of images of the same spatial scene in a contiguous and multiple narrow spectral wavelength (color) bands. According to the high spectral dimensionality, target detection is not surprisingly one of the most important applications in hyperspectral imagery. The main objective of this PhD thesis is to answer the question « How and Why can sparsity be exploited for hyperspectral target detection? ». Answering this question has allowed us to develop different target detection methods that mainly take into consideration the heterogeneity of the environment, the fact that the total image area of all the targets is very small relative to the whole image, and the estimation challenge of the covariance matrix (surrounding the test pixel) in large dimensions. The proposed mehods are evaluated on both synthetic and real experiments, the results of which demonstrate their effectiveness for hyperspectral target detection.

Hyperspectral imaging (HSI) produces spatial images with pixels that, instead of consisting of three colors, consist of hundreds of spectral measurements. Because there are so many measurements for each pixel, analysis of HSI is difficult. Frequently, standard techniques are used to help make analysis more tractable by representing the HSI data in a different manner. This research explores the utility of representing the HSI data in a learned dictionary basis for the express purpose of material identification and classification. Multiclass classification is performed on the transformed data using the RandomForests algorithm. Performance results are reported. In addition to classification, single material detection is considered also. Commonly used detection algorithm performance is demonstrated on both raw radiance pixels and HSI represented in dictionary-learned bases. Comparison results are shown which indicate that detection on dictionary-learned sparse representations perform as well as detection on radiance. In addition, a different method of performing detection, capitalizing on dictionary learning is established and performance comparisons are reported, showing gains over traditional detection methods.