Este trabalho apresenta uma solução geral para a detecção de alinhamentos de dados em conjuntos multidimensionais não ordenados e ruidosos. Nesta abordagem, o tipo requerido de alinhamento de dados pode ser uma forma geométrica (e.g., linha reta, plano, círculo, esfera, seção cônica, entre outras) ou qualquer estrutura, com dimensionalidade arbitrária, que possa ser caracterizada por um subespaço linear. A detecção é realizada por meio de um procedimento composto por três etapas. Na etapa de inicialização, um espaço de parâmetros com p (n − p) dimensões é definido de modo que cada ponto neste espaço represente uma instância do alinhamento requerido, descrito por um subespaço p-dimensional em um domínio n-dimensional. Em seguida, uma grade de acumuladores é criada como sendo a representação discreta do espaço de parâmetros. Na segunda etapa do procedimento, cada elemento no conjunto de dados de entrada (também um subespaço no domínio n-dimensional) é mapeado para o espaço de parâmetros como os pontos (no espaço de parâmetros) representando os subespaços requeridos que contém ou que estão contidos no elemento de entrada. À medida que os elementos de entrada são mapeados, as células do acumulador relacionadas com o mapeamento são incrementadas pelo valor de importância do elemento mapeado. A etapa final do procedimento recupera os subespaços p-dimensionais que melhor se ajustam aos dados de entrada como sendo os máximos locais na grade de acumuladores. A parametrização proposta é independente das propriedades geométricas dos alinhamentos a serem detectados. Além disso, o procedimento de mapeamento é independente do tipo de dado de entrada e é capaz de se adaptar a elementos com dimensionalidades arbitrárias. Essas características permitem a utilização da técnica (sem a necessidade de modificações) como uma ferramenta para a detecção de padrões em uma grande quantidade de aplicações. Por conta de sua natureza geral, otimizações desenvolvidas para a abordagem proposta beneficiam, de forma imediata, todos os casos de detecção. Neste trabalho eu demonstro uma implementação em software da técnica proposta e mostro que ela pode ser aplicada tanto em casos simples de detecção, quanto na detecção concorrente de tipos diferentes de alinhamentos, com diferentes interpretações geométricas e em conjuntos de dados compostos por vários tipos de elementos. Esta dissertação também apresenta uma extensão do esquema de detecção para dados de entrada com distribuição Gaussiana de incerteza. A extensão proposta produz distribuições de valores mais suaves na grade de acumuladores e faz com que a técnica fique mais robusta à detecção de subespaços espúrios. / This dissertation presents a generalized closed-form framework for detecting data alignments in large unordered noisy multidimensional datasets. In this approach, the intended type of data alignment may be a geometric shape (e.g., straight line, plane, circle, sphere, conic section, among others) or any other structure, with arbitrary dimensionality that can be characterized by a linear subspace. The detection is performed using a three-step process. In the initialization, a p (n − p)-dimensional parameter space is defined in such a way that each point in this space represents an instance of the intended alignment described by a p-dimensional subspace in some n-dimensional domain. In turn, an accumulator array is created as the discrete representation of the parameter space. In the second step each input entry (also a subspace in the n-dimensional domain) is mapped to the parameter space as the set of points representing the intended p-dimensional subspaces that contain or are contained by the entry. As the input entries are mapped, the bins of the accumulator related to such a mapping are incremented by the importance value of the entry. The subsequent and final step retrieves the p-dimensional subspaces that best fit input data as the local maxima in the accumulator array. The proposed parameterization is independent of the geometric properties of the alignments to be detected. Also, the mapping procedure is independent of the type of input data and automatically adapts to entries of arbitrary dimensionality. This allows application of the proposed approach (without changes) in a broad range of applications as a pattern detection tool. Given its general nature, optimizations developed for the proposed framework immediately benefit all the detection cases. I demonstrate a software implementation of the proposed technique and show that it can be applied in simple detection cases as well as in concurrent detection of multiple kinds of alignments with different geometric interpretations, in datasets containing multiple types of data. This dissertation also presents an extension of the general detection scheme to data with Gaussian-distributed uncertainty. The proposed extension produces smoother distributions of values in the accumulator array and makes the framework more robust to the detection of spurious subspaces.

Symmetric generalized eigenvalue problems arise in many physical applications and frequently only a few of the eigenpairs are of interest. Typically, the problems are large and sparse, and therefore traditional methods such as the QZ algorithm may not be considered. Moreover, it may be impractical to apply shift-and-invert Lanczos, a favored method for problems of this type, due to difficulties in applying the inverse of the shifted matrix. With these difficulties in mind, Golub and Ye developed an inverse free Krylov subspace algorithm for the symmetric generalized eigenvalue problem. This method does not rely on shift-and-invert transformations for convergence acceleration, but rather a preconditioner is used. The algorithm suffers, however, in the presence of multiple or clustered eigenvalues. Also, it is only applicable to the location of extreme eigenvalues. In this work, we extend the method of Golub and Ye by developing a block generalization of their algorithm which enjoys considerably faster convergence than the usual method in the presence of multiplicities and clusters. Preconditioning techniques for the problems are discussed at length, and some insight is given into how these preconditioners accelerate the method. Finally we discuss a transformation which can be applied so that the algorithm extracts interior eigenvalues. A preconditioner based on a QR factorization with respect to the B-1 inner product is developed and applied in locating interior eigenvalues.

By considering Krylov subspace methods in nonstandard inner products, we develop in this thesis new methods for solving large sparse linear systems and examine the effectiveness of existing preconditioners. We focus on saddle point systems and systems with a nonsymmetric, diagonalizable coefficient matrix. For symmetric saddle point systems, we present a preconditioner that renders the preconditioned saddle point matrix nonsymmetric but self-adjoint with respect to an inner product and for which scaling is not required to apply a short-term recurrence method. The robustness and effectiveness of this preconditioner, when applied to a number of test problems, is demonstrated. We additionally utilize combination preconditioning (Stoll and Wathen. SIAM J. Matrix Anal. Appl. 2008; 30:582-608) to develop three new combination preconditioners. One of these is formed from two preconditioners for which only a MINRES-type method can be applied, and yet a conjugate-gradient type method can be applied to the combination preconditioned system. Numerical experiments show that application of these preconditioners can result in faster convergence. When the coefficient matrix is diagonalizable, but potentially nonsymmetric, we present conditions under which the pseudospectra of a preconditioner and coefficient matrix are identical and characterize the pseudospectra when this condition is not exactly fulfilled. We show that when the preconditioner and coefficient matrix are self-adjoint with respect to nearby symmetric bilinear forms the convergence of a particular minimum residual method is bounded by a term that depends on the spectrum of the preconditioned coefficient matrix and a constant that is small when the symmetric bilinear forms are close. An iteration-dependent bound for GMRES in the Euclidean inner product is presented that shows precisely why a standard bound can be pessimistic. We observe that for certain problems known, effective preconditioners are either self-adjoint with respect to the same symmetric bilinear form as the coefficient matrix or one that is nearby.

Title: Analysis of Krylov subspace methods Author: Tomáš Gergelits Department: Department of Numerical Mathematics Supervisor: prof. Ing. Zdeněk Strakoš, DrSc. Abstract: After the derivation of the Conjugate Gradient method (CG) and the short review of its relationship with other fields of mathematics, this thesis is focused on its convergence behaviour both in exact and finite precision arith- metic. Fundamental difference between the CG and the Chebyshev semi-iterative method is described in detail. Then we investigate the use of the widespread lin- ear convergence bound based on Chebyshev polynomials. Through the example of the composite polynomial convergence bounds it is showed that the effects of rounding errors must be included in any consideration concerning the CG rate of convergence relevant to practical computations. Furthermore, the close corre- spondence between the trajectories of the CG approximations generated in finite precision and exact arithmetic is studied. The thesis is concluded with the discus- sion concerning the sensitivity of the closely related Gauss-Christoffel quadrature. The last two topics may motivate our further research. Keywords: Conjugate Gradient Method, Chebyshev semi-iterative method, fi- nite precision computations, delay of convergence, composite polynomial conver-...

In this paper, we discuss the need for quantum error correction. We also describe some basic techniques used in quantum error correction which includes decoherence-free subspaces and subsystems. These subspaces and subsystems are described in detail. We also introduce a numerical algorithm that was used previously to search for these decoherence-free subspaces and subsystems under collective error. It is useful to search for them as they can be used to store quantum information. We use this algorithm in some specific examples involving qubits and qutrits. The results of these algorithm are then compared with the error algebra obtained using Young tableaux. We use these results to describe how the specific numerical algorithm can be used for the search of approximate decoherence-free subspaces and subsystems and minimal noise subsystems.

Les simulations à grande dimension jouent un rôle crucial dans l'étude d'une grande variété de phénomènes physiques complexes, entraînant souvent des demandes écrasantes sur les ressources informatiques. La gestion de ces demandes constitue la principale motivation pour la réduction du modèle : produire des modèles de commande réduite plus simples, qui permettent une simulation plus rapide et moins coûteuse tout en se rapprochant avec précision du comportement du modèle d'origine. La présence des systèmes avec multiples entrées et multiples sorties (MIMO) rend le processus de réduction encore plus difficile. Dans cette thèse, nous nous intéressons aux méthodes de réduction de modèles à grande dimension en utilisant la projection sur des sous-espaces de Krylov tangentielles. Nous nous penchons sur le développement de techniques qui utilisent l'interpolation tangentielle. Celles-ci présentent une alternative efficace et intéressante à la troncature équilibrée qui est considérée comme référence dans le domaine et tout particulièrement la réduction pour les systèmes linéaire à temps invariants. Enfin, une attention particulière sera portée sur l'élaboration de nouveaux algorithmes efficaces et sur l'application à des problèmes pratiques. / Large-scale simulations play a crucial role in the study of a great variety of complex physical phenomena, leading often to overwhelming demands on computational resources. Managing these demands constitutes the main motivation for model reduction : produce simpler reduced-order models, which allow for faster and cheaper simulation while accurately approximating the behaviour of the original model. The presence of multiple inputs and outputs (MIMO) systems, makes the reduction process even more challenging. In this thesis we are interested in methods of reducing large-scale models, using projection on tangential Krylov subspaces. We are looking at the development of techniques using tangential interpolation. These present an effective and interesting alternative to the balanced truncation which is considered as a reference in the field and especially for the reduction of linear time invariant systems. Finally, special attention will be focused on the development of new efficient algorithms and application to practical problems.

Recent advances in robust subspace estimation have made dimensionality reduction and noise and outlier suppression an area of interest for research, along with continuous improvements in computer vision applications. Due to the nature of image and video signals that need a high dimensional representation, often storage, processing, transmission, and analysis of such signals is a difficult task. It is therefore desirable to obtain a low-dimensional representation for such signals, and at the same time correct for corruptions, errors, and outliers, so that the signals could be readily used for later processing. Major recent advances in low-rank modelling in this context were initiated by the work of Cand`es et al. [17] where the authors provided a solution for the long-standing problem of decomposing a matrix into low-rank and sparse components in a Robust Principal Component Analysis (RPCA) framework. However, for computer vision applications RPCA is often too complex, and/or may not yield desirable results. The low-rank component obtained by the RPCA has usually an unnecessarily high rank, while in certain tasks lower dimensional representations are required. The RPCA has the ability to robustly estimate noise and outliers and separate them from the low-rank component, by a sparse part. But, it has no mechanism of providing an insight into the structure of the sparse solution, nor a way to further decompose the sparse part into a random noise and a structured sparse component that would be advantageous in many computer vision tasks. As videos signals are usually captured by a camera that is moving, obtaining a low-rank component by RPCA becomes impossible. In this thesis, novel Approximated RPCA algorithms are presented, targeting different shortcomings of the RPCA. The Approximated RPCA was analysed to identify the most time consuming RPCA solutions, and replace them with simpler yet tractable alternative solutions. The proposed method is able to obtain the exact desired rank for the low-rank component while estimating a global transformation to describe camera-induced motion. Furthermore, it is able to decompose the sparse part into a foreground sparse component, and a random noise part that contains no useful information for computer vision processing. The foreground sparse component is obtained by several novel structured sparsity-inducing norms, that better encapsulate the needed pixel structure in visual signals. Moreover, algorithms for reducing complexity of low-rank estimation have been proposed that achieve significant complexity reduction without sacrificing the visual representation of video and image information. The proposed algorithms are applied to several fundamental computer vision tasks, namely, high efficiency video coding, batch image alignment, inpainting, and recovery, video stabilisation, background modelling and foreground segmentation, robust subspace clustering and motion estimation, face recognition, and ultra high definition image and video super-resolution. The algorithms proposed in this thesis including batch image alignment and recovery, background modelling and foreground segmentation, robust subspace clustering and motion segmentation, and ultra high definition image and video super-resolution achieve either state-of-the-art or comparable results to existing methods.

The fundamental task in human motion analysis is the extraction or capture of human motion and the established industrial technique is marker-based human motion capture. However, marker-based systems, apart from being expensive, are obtrusive and require a complex, time-consuming experimental setup, resulting in increased user discomfort. As an alternative solution, research on markerless human motion analysis has increased in prominence. In this thesis, we present three human motion analysis algorithms performing markerless tracking and classification from multiple-view studio-based video sequences using particle swarm optimisation and charting, a subspace learning technique.In our first framework, we formulate, and perform, human motion tracking as a multi-dimensional non-linear optimisation problem, solved using particle swarm optimisation (PSO), a swarm-intelligence algorithm. PSO initialises automatically, does not need a sequence-specific motion model, functioning as a blackbox system, and recovers from tracking divergence through the use of a hierarchical search algorithm (HPSO). We compare experimentally HPSO with particle filter, annealed particle filter and partitioned sampling annealed particle filter, and report similar or better tracking performance. Additionally we report an extensive experimental study of HPSO over ranges of values of its parameters and propose an automatic-adaptive extension of HPSO called as adaptive particle swarm optimisation. Next, in line with recent interest in subspace tracking, where low-dimensional subspaces are learnt from motion models of actions, we perform tracking in a low-dimensional subspace obtained by learning motion models of common actions using charting, a nonlinear dimensionality reduction tool. Tracking takes place in the subspace using an efficient modified version of particle swarm optimisation. Moreover, we perform a fast and efficient pose evaluation by representing the observed image data, multi-view silhouettes, using vector-quantized shape contexts and learning the mapping from the action subspace to shape space using multi-variate relevance vector machines. Tracking results with various action sequences demonstrate the good accuracy and performance of our approach.Finally, we propose a human motion classification algorithm, using charting-based low-dimensional subspaces, to classify human action sub-sequences of varying lengths, or snippets of poses. Each query action is mapped to a single subspace space, learnt from multiple actions. Furthermore we present a system in which, instead of mapping multiple actions to a single subspace, each action is mapped separately to its action-specific subspace. We adopt a multi-layered subspace classification scheme with layered pruning and search. One of the search layers involves comparing the input snippet with a sequence of key-poses extracted from the subspace. Finally, we identify the minimum length of action snippet, of skeletal features, required for classification, using competing classification systems as the baseline. We test our classification component on HumanEva and CMU mocap datasets, achieving similar or better classification accuracy than various comparable systems. human motion and the established industrial technique is marker-based human motion capture. However, marker-based systems, apart from being expensive, are obtrusive and require a complex, time-consuming experimental setup, resulting in increased user discomfort. As an alternative solution, research on markerless human motion analysis has increased in prominence. In this thesis, we present three human motion analysis algorithms performing markerless tracking and clas- si?cation from multiple-view studio-based video sequences using particle swarm optimisation and charting, a subspace learning technique. In our ?rst framework, we formulate, and perform, human motion tracking as a multi-dimensional non-linear optimisation problem, solved using particle swarm optimisation (PSO), a swarm-intelligence algorithm. PSO initialises automat- ically, does not need a sequence-speci?c motion model, functioning as a black- box system, and recovers from temporary tracking divergence through the use of a powerful hierarchical search algorithm (HPSO). We compare experiment- ally HPSO with particle ?lter, annealed particle ?lter and partitioned sampling annealed particle ?lter, and report similar or better tracking performance. Addi- tionally we report an extensive experimental study of HPSO over ranges of values of its parameters and propose an automatic-adaptive extension of HPSO called as adaptive particle swarm optimisation. Next, in line with recent interest in subspace tracking, where low-dimensional subspaces are learnt from motion models of actions, we perform tracking in a low-dimensional subspace obtained by learning motion models of common actions using charting, a nonlinear dimensionality reduction tool. Tracking takes place in the subspace using an e?cient modi?ed version of particle swarm optimisa- tion. Moreover, we perform a fast and e?cient pose evaluation by representing the observed image data, multi-view silhouettes, using vector-quantized shape contexts and learning the mapping from the action subspace to shape space us- ing multi-variate relevance vector machines. Tracking results with various action sequences demonstrate the good accuracy and performance of our approach. Finally, we propose a human motion classi?cation algorithm, using charting-based low-dimensional subspaces, to classify human action sub-sequences of varying lengths, or snippets of poses. Each query action is mapped to a single subspace space, learnt from multiple actions. Furthermore we present a system in which, instead of mapping multiple actions to a single subspace, each action is mapped separately to its action-speci?c subspace. We adopt a multi-layered subspace classi?cation scheme with layered pruning and search. One of the search lay- ers involves comparing the input snippet with a sequence of key-poses extracted from the subspace. Finally, we identify the minimum length of action snippet, of skeletal features, required for accurate classi?cation, using competing classi?ca- tion systems as the baseline. We test our classi?cation component on HumanEva and CMU mocap datasets, achieving similar or better classi?cation accuracy than

This thesis describes a blind beamforming technique for GPS receivers. It improves the performance of a GPS receiver by mitigating interference and enhancing GPS signals separately and has a three-stage structure. The technique is based on a linear antenna array and integrates the eigendecomposition based subspace and multiple independent beamforming techniques. A signal model is carefully constructed. Particular emphasis is placed upon the projection matrix derived from the subspace technique. The effect of interference and phase error on this technique is discussed. This technique is tested and compared to null steering and MMSE technique using simulated data for a number of interference environments. Furthermore, the proposed technique is applied to real data and shows several advantages over simple null steering. / Thesis (M.Eng.Sc.) - University of Adelaide, School of Electrical and Electronic Engineering, 2008

No description available.