21 |
Dimensionality Reduction of Hyperspectral Imagery Using Random ProjectionsMenon, Vineetha 09 December 2016 (has links)
Hyperspectral imagery is often associated with high storage and transmission costs. Dimensionality reduction aims to reduce the time and space complexity of hyperspectral imagery by projecting data into a low-dimensional space such that all the important information in the data is preserved. Dimensionality-reduction methods based on transforms are widely used and give a data-dependent representation that is unfortunately costly to compute. Recently, there has been a growing interest in data-independent representations for dimensionality reduction; of particular prominence are random projections which are attractive due to their computational efficiency and simplicity of implementation. This dissertation concentrates on exploring the realm of computationally fast and efficient random projections by considering projections based on a random Hadamard matrix. These Hadamard-based projections are offered as an alternative to more widely used random projections based on dense Gaussian matrices. Such Hadamard matrices are then coupled with a fast singular value decomposition in order to implement a two-stage dimensionality reduction that marries the computational benefits of the data-independent random projection to the structure-capturing capability of the data-dependent singular value transform. Finally, random projections are applied in conjunction with nonnegative least squares to provide a computationally lightweight methodology for the well-known spectral-unmixing problem. Overall, it is seen that random projections offer a computationally efficient framework for dimensionality reduction that permits hyperspectral-analysis tasks such as unmixing and classification to be conducted in a lower-dimensional space without sacrificing analysis performance while reducing computational costs significantly.
|
22 |
Essays on Time Series Analysis : With Applications to Financial EconometricsPreve, Daniel January 2008 (has links)
<p>This doctoral thesis is comprised of four papers that all relate to the subject of Time Series Analysis.</p><p>The first paper of the thesis considers point estimation in a nonnegative, hence non-Gaussian, AR(1) model. The parameter estimation is carried out using a type of extreme value estimators (EVEs). A novel estimation method based on the EVEs is presented. The theoretical analysis is complemented with Monte Carlo simulation results and the paper is concluded by an empirical example.</p><p>The second paper extends the model of the first paper of the thesis and considers semiparametric, robust point estimation in a nonlinear nonnegative autoregression. The nonnegative AR(1) model of the first paper is extended in three important ways: First, we allow the errors to be serially correlated. Second, we allow for heteroskedasticity of unknown form. Third, we allow for a multi-variable mapping of previous observations. Once more, the EVEs used for parameter estimation are shown to be strongly consistent under very general conditions. The theoretical analysis is complemented with extensive Monte Carlo simulation studies that illustrate the asymptotic theory and indicate reasonable small sample properties of the proposed estimators.</p><p>In the third paper we construct a simple nonnegative time series model for realized volatility, use the results of the second paper to estimate the proposed model on S&P 500 monthly realized volatilities, and then use the estimated model to make one-month-ahead forecasts. The out-of-sample performance of the proposed model is evaluated against a number of standard models. Various tests and accuracy measures are utilized to evaluate the forecast performances. It is found that forecasts from the nonnegative model perform exceptionally well under the mean absolute error and the mean absolute percentage error forecast accuracy measures.</p><p>In the fourth and last paper of the thesis we construct a multivariate extension of the popular Diebold-Mariano test. Under the null hypothesis of equal predictive accuracy of three or more forecasting models, the proposed test statistic has an asymptotic Chi-squared distribution. To explore whether the behavior of the test in moderate-sized samples can be improved, we also provide a finite-sample correction. A small-scale Monte Carlo study indicates that the proposed test has reasonable size properties in large samples and that it benefits noticeably from the finite-sample correction, even in quite large samples. The paper is concluded by an empirical example that illustrates the practical use of the two tests.</p>
|
23 |
Nonnegative feedback systems in population ecologyBill, Adam January 2016 (has links)
We develop and adapt absolute stability results for nonnegative Lur'e systems, that is, systems made up of linear part and a nonlinear feedback in which the state remains nonnegative for all time. This is done in both continuous and discrete time with an aim of applying these results to population modeling. Further to this, we consider forced nonnegative Lur'e systems, that is, Lur'e systems with an additional disturbance, and provide results on input-to-state stability (ISS), again in both continuous and discrete time. We provide necessary and sufficient conditions for a forced Lur'e system to have the converging-input converging-state (CICS) property in a general setting before specializing these results to nonnegative, single-input, single-output systems. Finally we apply integral control to nonnegative systems in order to control the output of the system with the key focus being on applications to population management.
|
24 |
Essays on Time Series Analysis : With Applications to Financial EconometricsPreve, Daniel January 2008 (has links)
This doctoral thesis is comprised of four papers that all relate to the subject of Time Series Analysis. The first paper of the thesis considers point estimation in a nonnegative, hence non-Gaussian, AR(1) model. The parameter estimation is carried out using a type of extreme value estimators (EVEs). A novel estimation method based on the EVEs is presented. The theoretical analysis is complemented with Monte Carlo simulation results and the paper is concluded by an empirical example. The second paper extends the model of the first paper of the thesis and considers semiparametric, robust point estimation in a nonlinear nonnegative autoregression. The nonnegative AR(1) model of the first paper is extended in three important ways: First, we allow the errors to be serially correlated. Second, we allow for heteroskedasticity of unknown form. Third, we allow for a multi-variable mapping of previous observations. Once more, the EVEs used for parameter estimation are shown to be strongly consistent under very general conditions. The theoretical analysis is complemented with extensive Monte Carlo simulation studies that illustrate the asymptotic theory and indicate reasonable small sample properties of the proposed estimators. In the third paper we construct a simple nonnegative time series model for realized volatility, use the results of the second paper to estimate the proposed model on S&P 500 monthly realized volatilities, and then use the estimated model to make one-month-ahead forecasts. The out-of-sample performance of the proposed model is evaluated against a number of standard models. Various tests and accuracy measures are utilized to evaluate the forecast performances. It is found that forecasts from the nonnegative model perform exceptionally well under the mean absolute error and the mean absolute percentage error forecast accuracy measures. In the fourth and last paper of the thesis we construct a multivariate extension of the popular Diebold-Mariano test. Under the null hypothesis of equal predictive accuracy of three or more forecasting models, the proposed test statistic has an asymptotic Chi-squared distribution. To explore whether the behavior of the test in moderate-sized samples can be improved, we also provide a finite-sample correction. A small-scale Monte Carlo study indicates that the proposed test has reasonable size properties in large samples and that it benefits noticeably from the finite-sample correction, even in quite large samples. The paper is concluded by an empirical example that illustrates the practical use of the two tests.
|
25 |
Block Coordinate Descent for Regularized Multi-convex OptimizationXu, Yangyang 16 September 2013 (has links)
This thesis considers regularized block multi-convex optimization, where the feasible set and objective function are generally non-convex but convex in each block of variables.
I review some of its interesting examples and propose a generalized block coordinate descent (BCD) method. The generalized BCD uses three different block-update schemes.
Based on the property of one block subproblem, one can freely choose one of the three schemes to update the corresponding block of variables. Appropriate choices of block-update schemes can often speed up the algorithm and greatly save computing time.
Under certain conditions, I show that any limit point satisfies the Nash equilibrium conditions. Furthermore, I establish its global convergence and estimate its asymptotic convergence rate by assuming a property based on the Kurdyka-{\L}ojasiewicz inequality. As a consequence, this thesis gives a global linear convergence result of cyclic block coordinate descent for strongly convex optimization. The proposed algorithms are adapted for factorizing nonnegative matrices and tensors, as well as completing them from their incomplete observations. The algorithms were tested on synthetic data, hyperspectral data, as well as image sets from the CBCL, ORL and Swimmer databases. Compared to the existing state-of-the-art algorithms, the proposed algorithms demonstrate superior performance in both speed and solution quality.
|
26 |
On the nonnegative least squaresSantiago, Claudio Prata 19 August 2009 (has links)
In this document, we study the nonnegative least squares primal-dual method
for solving linear programming problems. In particular, we investigate connections
between this primal-dual method and the classical Hungarian method for the assignment problem.
Firstly, we devise a fast procedure for computing the unrestricted least
squares solution of a bipartite matching problem by exploiting the special
structure of the incidence matrix of a bipartite graph. Moreover, we explain
how to extract a solution for the cardinality matching problem from the
nonnegative least squares solution. We also give an efficient procedure
for solving the cardinality matching problem on general graphs using the
nonnegative least squares approach.
Next we look into some theoretical results concerning the minimization of p-norms,
and separable differentiable convex functions, subject to linear constraints
described by node-arc incidence matrices for graphs.
Our main result is the reduction of the assignment problem to a single
nonnegative least squares problem. This means that the primal-dual
approach can be made to converge in one step for the assignment problem.
This method does not reduce the primal-dual approach to one step for
general linear programming problems, but it appears to give a good
starting dual feasible point for the general problem.
|
27 |
Dictionary learning methods for single-channel source separationLefèvre, Augustin 03 October 2012 (has links) (PDF)
In this thesis we provide three main contributions to blind source separation methods based on NMF. Our first contribution is a group-sparsity inducing penalty specifically tailored for Itakura-Saito NMF. In many music tracks, there are whole intervals where only one source is active at the same time. The group-sparsity penalty we propose allows to blindly indentify these intervals and learn source specific dictionaries. As a consequence, those learned dictionaries can be used to do source separation in other parts of the track were several sources are active. These two tasks of identification and separation are performed simultaneously in one run of group-sparsity Itakura-Saito NMF. Our second contribution is an online algorithm for Itakura-Saito NMF that allows to learn dictionaries on very large audio tracks. Indeed, the memory complexity of a batch implementation NMF grows linearly with the length of the recordings and becomes prohibitive for signals longer than an hour. In contrast, our online algorithm is able to learn NMF on arbitrarily long signals with limited memory usage. Our third contribution deals user informed NMF. In short mixed signals, blind learning becomes very hard and sparsity do not retrieve interpretable dictionaries. Our contribution is very similar in spirit to inpainting. It relies on the empirical fact that, when observing the spectrogram of a mixture signal, an overwhelming proportion of it consists in regions where only one source is active. We describe an extension of NMF to take into account time-frequency localized information on the absence/presence of each source. We also investigate inferring this information with tools from machine learning.
|
28 |
Applications of Linear Algebra to Information RetrievalVasireddy, Jhansi Lakshmi 28 May 2009 (has links)
Some of the theory of nonnegative matrices is first presented. The Perron-Frobenius theorem is highlighted. Some of the important linear algebraic methods of information retrieval are surveyed. Latent Semantic Indexing (LSI), which uses the singular value de-composition is discussed. The Hyper-Text Induced Topic Search (HITS) algorithm is next considered; here the power method for finding dominant eigenvectors is employed. Through the use of a theorem by Sinkohrn and Knopp, a modified HITS method is developed. Lastly, the PageRank algorithm is discussed. Numerical examples and MATLAB programs are also provided.
|
29 |
Blind inverse imaging with positivity constraints / Inversion aveugle d'images avec contraintes de positivitéLecharlier, Loïc 09 September 2014 (has links)
Dans les problèmes inverses en imagerie, on suppose généralement connu l’opérateur ou matrice décrivant le système de formation de l’image. De façon équivalente pour un système linéaire, on suppose connue sa réponse impulsionnelle. Toutefois, ceci n’est pas une hypothèse réaliste pour de nombreuses applications pratiques pour lesquelles cet opérateur n’est en fait pas connu (ou n’est connu qu’approximativement). On a alors affaire à un problème d’inversion dite “aveugle”. Dans le cas de systèmes invariants par translation, on parle de “déconvolution aveugle” car à la fois l’image ou objet de départ et la réponse impulsionnelle doivent être estimées à partir de la seule image observée qui résulte d’une convolution et est affectée d’erreurs de mesure. Ce problème est notoirement difficile et pour pallier les ambiguïtés et les instabilités numériques inhérentes à ce type d’inversions, il faut recourir à des informations ou contraintes supplémentaires, telles que la positivité qui s’est avérée un levier de stabilisation puissant dans les problèmes d’imagerie non aveugle. La thèse propose de nouveaux algorithmes d’inversion aveugle dans un cadre discret ou discrétisé, en supposant que l’image inconnue, la matrice à inverser et les données sont positives. Le problème est formulé comme un problème d’optimisation (non convexe) où le terme d’attache aux données à minimiser, modélisant soit le cas de données de type Poisson (divergence de Kullback-Leibler) ou affectées de bruit gaussien (moindres carrés), est augmenté par des termes de pénalité sur les inconnues du problème. La stratégie d’optimisation consiste en des ajustements alternés de l’image à reconstruire et de la matrice à inverser qui sont de type multiplicatif et résultent de la minimisation de fonctions coût “surrogées” valables dans le cas positif. Le cadre assez général permet d’utiliser plusieurs types de pénalités, y compris sur la variation totale (lissée) de l’image. Une normalisation éventuelle de la réponse impulsionnelle ou de la matrice est également prévue à chaque itération. Des résultats de convergence pour ces algorithmes sont établis dans la thèse, tant en ce qui concerne la décroissance des fonctions coût que la convergence de la suite des itérés vers un point stationnaire. La méthodologie proposée est validée avec succès par des simulations numériques relatives à différentes applications telle que la déconvolution aveugle d'images en astronomie, la factorisation en matrices positives pour l’imagerie hyperspectrale et la déconvolution de densités en statistique. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished
|
30 |
Optimization over nonnegative matrix polynomialsCederberg, Daniel January 2023 (has links)
This thesis is concerned with convex optimization problems over matrix polynomials that are constrained to be positive semidefinite on the unit circle. Problems of this form appear in signal processing and can often be solved as semidefinite programs (SDPs). Interior-point solvers for these SDPs scale poorly, and this thesis aims to design first-order methods that are more efficient. We propose methods based on a generalized proximal operator defined in terms of a Bregman divergence. Empirical results on three applications in signal processing demonstrate that the proposed methods scale much better than interior-point solvers. As an example, for sparse estimation of spectral density matrices, Douglas--Rachford splitting with the generalized proximal operator is about 1000 times faster and scales to much larger problems. The ability to solve larger problems allows us to perform functional connectivity analysis of the brain by constructing a sparse estimate of the inverse spectral density matrix.
|
Page generated in 0.1147 seconds