abstract: Advances in data collection technologies have made it cost-effective to obtain heterogeneous data from multiple data sources. Very often, the data are of very high dimension and feature selection is preferred in order to reduce noise, save computational cost and learn interpretable models. Due to the multi-modality nature of heterogeneous data, it is interesting to design efficient machine learning models that are capable of performing variable selection and feature group (data source) selection simultaneously (a.k.a bi-level selection). In this thesis, I carry out research along this direction with a particular focus on designing efficient optimization algorithms. I start with a unified bi-level learning model that contains several existing feature selection models as special cases. Then the proposed model is further extended to tackle the block-wise missing data, one of the major challenges in the diagnosis of Alzheimer's Disease (AD). Moreover, I propose a novel interpretable sparse group feature selection model that greatly facilitates the procedure of parameter tuning and model selection. Last but not least, I show that by solving the sparse group hard thresholding problem directly, the sparse group feature selection model can be further improved in terms of both algorithmic complexity and efficiency. Promising results are demonstrated in the extensive evaluation on multiple real-world data sets. / Dissertation/Thesis / Doctoral Dissertation Computer Science 2014

No description available.

[pt] A estimação de direção de chegada (DoA) é uma importante área de processamento de arranjos de sensores que é encontrada em uma ampla gama de aplicações de engenharia. Este fato, juntamente com o desenvolvimento da área de Compressed Sensing (CS) nos últimos anos, são a principal motivação desta dissertação. Nesta dissertação, é apresentada uma formulação do problema de estimação de direção de chegada como um problema de representação esparsa da sinal e vários algoritmos de recuperação esparsa são derivados e investigados para resolver o problema atual. Os algoritmos propostos são baseados na incorporação da informação prévia sobre o sinal esparso no processo de estimativa. Na primeira parte, nos concentramos no desenvolvimento de dois algoritmos Bayesianos , que se baseiam principalmente no algoritmo iterative hard thresholding (IHT). Devido ao desempenho inferior dos algoritmos convencionais de estimação de chegada em cenários com fontes correlacionadas, nós prestamos atenção especial ao desempenho dos algoritmos propostos nesta condição. Na segunda parte, o problema de otimização baseados na minimização da norma l1 é apresentado e um algoritmo bayesiano é proposto para resolver o problema chamado basis pursuit denoising (BPDN). Os resultados da simulação mostram que os estimadores Bayesianos superam os estimadores não Bayesianos e que a incorporação do conhecimento prévio da distribuição do sinal melhorou substancialmente o desempenho dos algoritmos. / [en] Direction of arrival (DoA) estimation is a key area of sensor array processing which is encountered in a broad range of important engineering applications. This fact together with the development of the Compressed Sensing (CS) area in the last years are the principal motivation of this thesis. In this dissertation, a formulation of the source localization problem as a sparse signal representation problem is presented and several sparse recovery algorithms are derived and investigated for solving the current problem. The proposed algorithms are based on the incorporation of the prior information about the sparse signal in the estimation process. In the first part, we focus on the development of two Bayesian greedy algorithms which are principally based on the iterative hard thresholding (IHT) algorithm. Due to the inferior performance of the conventional DoA estimation algorithm in scenarios with correlated sources, we pay special attention to the performance of the proposed algorithms under this condition. In the second part, the optimization problem using a l1 penalty is introduced and a Bayesian algorithm for solving the basis pursuit denoising problem is presented. Simulation results shows that Bayesian estimators which take into account the prior knowledge of the signal distribution outperform and improve substantially the performance of the non-Bayesian estimators.

Compressed sensing and matrix completion are two new data acquisition techniques whose efficiency is achieved by exploring low dimensional structures in high dimensional data. Despite the combinatorial nature of compressed sensing and matrix completion, there has been significant development of computationally efficient algorithms which can produce accurate desired solutions to these problems. In this thesis, we are concerned with the development of low per iteration computational complexity algorithms for compressed sensing and matrix completion. First, we derive a locally optimal stepsize selection rule for the simplest iterative hard thresholding algorithm for matrix completion, and obtain a simple yet efficient algorithm. It is observed to have average case performance superior in some aspects to other matrix completion algorithms. To balance the fast convergence rates of more sophisticated recovery algorithms with the low per iteration computational cost of simple line-search algorithms, we introduce a family of conjugate gradient iterative hard thresholding algorithms for both compressed sensing and matrix completion. The theoretical results establish recovery guarantees for the restarted and projected variants of the algorithms, while the empirical performance comparisons establish significant computational advantages of the proposed methods over other hard thresholding algorithms. Finally, we introduce an alternating steepest descent method and a scaled variant especially designed for the matrix completion problem based on a simple factorization model of the low rank matrix. The computational efficacy of this method is achieved by reducing the high per iteration computational cost of the second order method and fully exploring the numerical linear algebra structure in the algorithm. Empirical evaluations establish the effectiveness of the proposed algorithms, compared with other state-of-the-art algorithms.

In this dissertation, two classes of distributed algorithms are developed for sparse signal recovery in large sensor networks. All the proposed approaches consist of local computation (LC) and global computation (GC) steps carried out by a group of distributed local sensors, and do not require the local sensors to know the global sensing matrix. These algorithms are based on the original approximate message passing (AMP) and iterative hard thresholding (IHT) algorithms in the area of compressed sensing (CS), also known as sparse signal recovery. For distributed AMP (DiAMP), we develop a communication-efficient algorithm GCAMP. Numerical results demonstrate that it outperforms the modified thresholding algorithm (MTA), another popular GC algorithm for Top-K query from distributed large databases. For distributed IHT (DIHT), there is a step size $\mu$ which depends on the $\ell_2$ norm of the global sensing matrix A. The exact computation of $\|A\|_2$ is non-separable. We propose a new method, based on the random matrix theory (RMT), to give a very tight statistical upper bound of $\|A\|_2$, and the calculation of that upper bound is separable without any communication cost. In the GC step of DIHT, we develop another algorithm named GC.K, which is also communication-efficient and outperforms MTA. Then, by adjusting the metric of communication cost, which enables transmission of quantized data, and taking advantage of the correlation of data in adjacent iterations, we develop quantized adaptive GCAMP (Q-A-GCAMP) and quantized adaptive GC.K (Q-A-GC.K) algorithms, leading to a significant improvement on communication savings. Furthermore, we prove that state evolution (SE), a fundamental property of AMP that in high dimensionality limit, the output data are asymptotically Gaussian regardless of the distribution of input data, also holds for DiAMP. In addition, compared with the most recent theoretical results that SE holds for sensing matrices with independent subgaussian entries, we prove that the universality of SE can be extended to far more general sensing matrices. These two theoretical results provide strong guarantee of AMP's performance, and greatly broaden its potential applications.

This thesis focuses on image processing using wavelet transform. The usage of wavelet transform is analysed especially for image compression and image noise reduction purposes. The analysis describes in detail aspects and application of the following wavelet transform methods: CWT, DWT, DTWT, 2D DWT. The thesis further explains the meaning of the mother wavelet and studies certain specific kinds of wavelets, kinds of thresholding and its purposes and also touches on the JPEG2000 standard. Mathematica and Sage software packages were used to design algorithms for image compression and image noise reduction, utilising relevant wavelet transform findings. The concluding part of the thesis compares the two software packages and results obtained using different algorithms.

This thesis focuses on image processing using wavelet transform. The usage of wavelet transform is analysed especially for image compression and image noise reduction purposes. The analysis describes in detail aspects and application of the following wavelet transform methods: CWT, DWT, DTWT, 2D DWT. The thesis further explains the meaning of the mother wavelet and studies certain specific kinds of wavelets, kinds of thresholding and its purposes and also touches on the JPEG2000 standard. Mathematica and Sage software packages were used to design algorithms for image compression and image noise reduction, utilising relevant wavelet transform findings. The concluding part of the thesis compares the two software packages and results obtained using different algorithms.

Dans la première partie de cette thèse, on formule deux méthodes pour le calcul d'une décomposition polyadique canonique avec facteurs matriciels linéairement structurés (tels que des facteurs de Toeplitz ou en bande): un algorithme de moindres carrés alternés contraint (CALS) et une solution algébrique dans le cas où tous les facteurs sont circulants. Des versions exacte et approchée de la première méthode sont étudiées. La deuxième méthode fait appel à la transformée de Fourier multidimensionnelle du tenseur considéré, ce qui conduit à la résolution d'un système d'équations monomiales homogènes. Nos simulations montrent que la combinaison de ces approches fournit un estimateur statistiquement efficace, ce qui reste vrai pour d'autres combinaisons de CALS dans des scénarios impliquant des facteurs non-circulants. La seconde partie de la thèse porte sur la récupération de tenseurs de rang faible et, en particulier, sur le problème de reconstruction tensorielle (TC). On propose un algorithme efficace, noté SeMPIHT, qui emploie des projections séquentiellement optimales par mode comme opérateur de seuillage dur. Une borne de performance est dérivée sous des conditions d'isométrie restreinte habituelles, ce qui fournit des bornes d'échantillonnage sous-optimales. Cependant, nos simulations suggèrent que SeMPIHT obéit à des bornes optimales pour des mesures Gaussiennes. Des heuristiques de sélection du pas et d'augmentation graduelle du rang sont aussi élaborées dans le but d'améliorer sa performance. On propose aussi un schéma d'imputation pour TC basé sur un seuillage doux du coeur du modèle de Tucker et son utilité est illustrée avec des données réelles de trafic routier / In the first part of this thesis, we formulate two methods for computing a canonical polyadic decomposition having linearly structured matrix factors (such as, e.g., Toeplitz or banded factors): a general constrained alternating least squares (CALS) algorithm and an algebraic solution for the case where all factors are circulant. Exact and approximate versions of the former method are studied. The latter method relies on a multidimensional discrete-time Fourier transform of the target tensor, which leads to a system of homogeneous monomial equations whose resolution provides the desired circulant factors. Our simulations show that combining these approaches yields a statistically efficient estimator, which is also true for other combinations of CALS in scenarios involving non-circulant factors. The second part of the thesis concerns low-rank tensor recovery (LRTR) and, in particular, the tensor completion (TC) problem. We propose an efficient algorithm, called SeMPIHT, employing sequentially optimal modal projections as its hard thresholding operator. Then, a performance bound is derived under usual restricted isometry conditions, which however yield suboptimal sampling bounds. Yet, our simulations suggest SeMPIHT obeys optimal sampling bounds for Gaussian measurements. Step size selection and gradual rank increase heuristics are also elaborated in order to improve performance. We also devise an imputation scheme for TC based on soft thresholding of a Tucker model core and illustrate its utility in completing real-world road traffic data acquired by an intelligent transportation