Thesis (M.S.)--Rochester Institute of Technology, 2007. / Typescript. Includes bibliographical references (leaf 39).

This dissertation reviews the theory of fast matrix multiplication from a multilinear-algebraic point of view, as well as recent fast matrix multiplication algorithms based on discrete Fourier transforms over nite groups. To this end, the algebraic approach is described in terms of group algebras over groups satisfying the triple product Property, and the construction of such groups via uniquely solvable puzzles. The higher order singular value decomposition is an important decomposition of tensors that retains some of the properties of the singular value decomposition of matrices. However, we have proven a novel negative result which demonstrates that the higher order singular value decomposition yields a matrix multiplication algorithm that is no better than the standard algorithm. / Mathematical Sciences / M. Sc. (Applied Mathematics)

This dissertation reviews the theory of fast matrix multiplication from a multilinear-algebraic point of view, as well as recent fast matrix multiplication algorithms based on discrete Fourier transforms over nite groups. To this end, the algebraic approach is described in terms of group algebras over groups satisfying the triple product Property, and the construction of such groups via uniquely solvable puzzles. The higher order singular value decomposition is an important decomposition of tensors that retains some of the properties of the singular value decomposition of matrices. However, we have proven a novel negative result which demonstrates that the higher order singular value decomposition yields a matrix multiplication algorithm that is no better than the standard algorithm. / Mathematical Sciences / M. Sc. (Applied Mathematics)

Channel order estimation is an important problem in many fields including signal processing, communications, acoustics, and more. In this thesis, blind channel order estimation problem is considered for single-input, multi-output (SIMO) FIR systems. The problem is to estimate the effective channel order for the SIMO system given only the output samples corrupted by noise. Two new methods for channel order estimation are presented. These methods have several useful features compared to the currently known techniques. They are guaranteed to find the true channel order for noise free case and they perform significantly better for noisy observations. These algorithms show a consistent performance when the number of observations, channels and channel order are changed. The proposed algorithms are integrated with the least squares smoothing (LSS) algorithm for blind identification of the channel coefficients. LSS algorithm is selected since it is a deterministic algorithm and has some additional features suitable for order estimation. The proposed algorithms are compared with a variety of dierent algorithms including linear prediction (LP) based methods. LP approaches are known to be robust to channel order overestimation. In this thesis, it is shown that significant gain can be obtained compared to LP based approaches when the proposed techniques are used. The proposed algorithms are also compared with the oversampled single-input, single-output (SISO) system with a generic decision feedback equalizer, and better mean-square error performance is observed for the blind setting. Channel order estimation problem is also investigated for semi-blind systems where a pilot signal is used which is known at the receiver. In this case, two new methods are proposed which exploit the pilot signal in dierent ways. When both unknown and pilot symbols are used, a better estimation performance can be achieved compared to the proposed blind methods. The semi-blind approach is especially effective in terms of bit error rate (BER) evaluation thanks to the use of pilot symbols in better estimation of channel coecients. This approach is also more robust to ill-conditioned channels. The constraints for these approaches, such as synchronization, and the decrease in throughput still make the blind approaches a good alternative for channel order estimation. True and effective channel order estimation topics are discussed in detail and several simulations are done in order to show the significant performance gain achieved by the proposed methods.

A stiffened DKT shell element is formulated for the linear static analysis of stiffened plates and shells. Three-noded triangular shell elements and two-noded beam elements with 18 and 12 degrees of freedom are used respectively in the formulation. The stiffeners follow the nodal lines of the shell element. Eccentricity of the stiffener is taken into account. The dynamic and stability characteristic of the element is also investigated. With the developed computer program, the results obtained by the proposed element agrees fairly well with the existing literature.

We investigate categorical models of the unit-free multiplicative and multiplicative-additive fragments of linear logic by representing derivations as particular structures known as dinatural transformations. Suitable categories are considered to satisfy a property known as full completeness if all such entities are the interpretation of a correct derivation. It is demonstrated that certain Hyland-Schalk double glueings [HS03] are capable of transforming large numbers of degenerate models into more accurate ones. Compact closed categories with finite biproducts possess enough structure that their morphisms can be described as forms of linear arrays. We introduce the notion of an extended tensor (or ‘extensor’) over arbitrary semirings, and show that they uniquely describe arrows between objects generated freely from the tensor unit in such categories. It is made evident that the concept may be extended yet further to provide meaningful decompositions of more general arrows. We demonstrate how the calculus of extensors makes it possible to examine the combinatorics of certain double glueing constructions. From this we show that the Hyland-Tan version [Tan97], when applied to compact closed categories satisfying a far weaker version of full completeness, produces genuine fully complete models of unit-free multiplicative linear logic. Research towards the development of a full completeness result for the multiplicative-additive fragment is detailed. The proofs work for categories of finite arrays over certain semirings under both the Hyland-Tan and Schalk [Sch04] constructions. We offer a possible route to finishing this proof. An interpretation of these results with respect to linear logic proof theory is provided, and possible further research paths and generalisations are discussed.

Denoising signals is an important task of digital signal processing. Many linear and non-linear methods for signal denoising have been developed. Wavelet based denoising is the most famous nonlinear denoising method lately. In the linear case, Kalman filter is famous for its easy implementation and real-time nature. Wavelet- Kalman filter developed lately is an important improvement over Kalman filter, in which the Kalman filter operates in the wavelet domain, filtering the wavelet coeffi- cients, and resulting in the filtered wavelet transform of the signal in real-time. The real-time filtering and multiresolution representation is a powerful feature for many real world applications. This study explains in detail the derivation and implementation of Real-Time Wavelet-Kalman Filter method to remove noise from signals in real-time. The filter is enhanced to use different wavelet types than the Haar wavelet, and also it is improved to operate on higer block sizes than two. Wavelet shrinkage is integrated to the filter and it is shown that by utilizing this integration more noise suppression is obtainable. A user friendly application is developed to import, filter and export signals in Java programming language. And finally, the applicability of the proposed method to suppress noise from seismic waves coming from eartquakes and to enhance spontaneous potentials measured from groundwater wells is also shown.

In this work, we study some generalized multipartite access structures and linear secret sharing schemes for their realizations. Given a multipartite set of participants with m compartments (or levels) and m conditions to be satisfied by an authorized set, we firstly examine the intermediary access structures arousing from the natural case concerning that any c out of m of these conditions suffice, instead of requiring anyone or all of the m conditions simultaneously, yielding to generalizations for both the compartmented and hierarchical cases. These are realized essentially by employing a series of Lagrange interpolations and a simple frequently-used connective tool called access structure product, as well as some known constructions for existing ideal schemes. The resulting schemes are non-ideal but perfect. We also consider nested multipartite access structures, where we let a compartment to be defined within another, so that the access structure is composed of some multipartite substructures. We extend formerly employed bivariate interpolation techniques to multivariate interpolation, in order to realize such access structures. The generic scheme we consider is perfect with a high probability such as 1-O(1/q) on a finite field F_q. In particular, we propose a non-nested generalization for the conventional compartmented access structures, which depicts a stronger way of controlling the additional participants.

CoordenaÃÃo de AperfeiÃoamento de NÃvel Superior / In this dissertation, the face recognition problem is investigated from the standpoint of multilinear algebra, more specifically the tensor decomposition, and by making use of Gabor wavelets. The feature extraction occurs in two stages: first the Gabor wavelets are applied holistically in feature selection; Secondly facial images are modeled as a higher-order tensor according to the multimodal factors present. Then, the HOSVD is applied to separate the multimodal factors of the images. The proposed facial recognition approach exhibits higher average success rate and stability when there is variation in the various multimodal factors such as facial position, lighting condition and facial expression. We also propose a systematic way to perform cross-validation on tensor models to estimate the error rate in face recognition systems that explore the nature of the multimodal ensemble. Through the random partitioning of data organized as a tensor, the mode-n cross-validation provides folds as subtensors extracted of the desired mode, featuring a stratified method and susceptible to repetition of cross-validation with different partitioning. / Nesta dissertaÃÃo o problema de reconhecimento facial à investigado do ponto de vista da Ãlgebra multilinear, mais especificamente por meio de decomposiÃÃes tensoriais fazendo uso das wavelets de Gabor. A extraÃÃo de caracterÃsticas ocorre em dois estÃgios: primeiramente as wavelets de Gabor sÃo aplicadas de maneira holÃstica na seleÃÃo de caracterÃsticas; em segundo as imagens faciais sÃo modeladas como um tensor de ordem superior de acordo com o fatores multimodais presentes. Com isso aplicamos a decomposiÃÃo tensorial Higher Order Singular Value Decomposition (HOSVD) para separar os fatores que influenciam na formaÃÃo das imagens. O mÃtodo de reconhecimento facial proposto possui uma alta taxa de acerto e estabilidade quando hà variaÃÃo nos diversos fatores multimodais, tais como, posiÃÃo facial, condiÃÃo de iluminaÃÃo e expressÃo facial. Propomos ainda uma maneira sistemÃtica para realizaÃÃo da validaÃÃo cruzada em modelos tensoriais para estimaÃÃo da taxa de erro em sistemas de reconhecimento facial que exploram a natureza multilinear do conjunto de imagens. AtravÃs do particionamento aleatÃrio dos dados organizado como um tensor, a validaÃÃo cruzada modo-n proporciona a criaÃÃo de folds extraindo subtensores no modo desejado, caracterizando um mÃtodo estratificado e susceptÃvel a repetiÃÃes da validaÃÃo cruzada com diferentes particionamentos.

Dans le cadre du traitement statistique du signal, la plupart des algorithmes couramment utilisés reposent sur l'utilisation de la matrice de covariance des signaux étudiés. En pratique, ce sont les versions adaptatives de ces traitements, obtenues en estimant la matrice de covariance à l'aide d'échantillons du signal, qui sont utilisés. Ces algorithmes présentent un inconvénient : ils peuvent nécessiter un nombre d'échantillons important pour obtenir de bons résultats. Lorsque la matrice de covariance possède une structure rang faible, le signal peut alors être décomposé en deux sous-espaces orthogonaux. Les projecteurs orthogonaux sur chacun de ces sous espaces peuvent alors être construits, permettant de développer des méthodes dites rang faible. Les versions adaptatives de ces méthodes atteignent des performances équivalentes à celles des traitements classiques tout en réduisant significativement le nombre d'échantillons nécessaire. Par ailleurs, l'accroissement de la taille des données ne fait que renforcer l'intérêt de ce type de méthode. Cependant, cet accroissement s'accompagne souvent d'un accroissement du nombre de dimensions du système. Deux types d'approches peuvent être envisagées pour traiter ces données : les méthodes vectorielles et les méthodes tensorielles. Les méthodes vectorielles consistent à mettre les données sous forme de vecteurs pour ensuite appliquer les traitements classiques. Cependant, lors de la mise sous forme de vecteur, la structure des données est perdue ce qui peut entraîner une dégradation des performances et/ou un manque de robustesse. Les méthodes tensorielles permettent d'éviter cet écueil. Dans ce cas, la structure est préservée en mettant les données sous forme de tenseurs, qui peuvent ensuite être traités à l'aide de l'algèbre multilinéaire. Ces méthodes sont plus complexes à utiliser puisqu'elles nécessitent d'adapter les algorithmes classiques à ce nouveau contexte. En particulier, l'extension des méthodes rang faible au cas tensoriel nécessite l'utilisation d'une décomposition tensorielle orthogonale. Le but de cette thèse est de proposer et d'étudier des algorithmes rang faible pour des modèles tensoriels. Les contributions de cette thèse se concentrent autour de trois axes. Un premier aspect concerne le calcul des performances théoriques d'un algorithme MUSIC tensoriel basé sur la Higher Order Singular Value Decomposition (HOSVD) et appliqué à un modèle de sources polarisées. La deuxième partie concerne le développement de filtres rang faible et de détecteurs rang faible dans un contexte tensoriel. Ce travail s'appuie sur une nouvelle définition de tenseur rang faible et sur une nouvelle décomposition tensorielle associée : l'Alternative Unfolding HOSVD (AU-HOSVD). La dernière partie de ce travail illustre l'intérêt de l'approche tensorielle basée sur l'AU-HOSVD, en appliquant ces algorithmes à configuration radar particulière: le Traitement Spatio-Temporel Adaptatif ou Space-Time Adaptive Process (STAP). / Most of statistical signal processing algorithms, are based on the use of signal covariance matrix. In practical cases this matrix is unknown and is estimated from samples. The adaptive versions of the algorithms can then be applied, replacing the actual covariance matrix by its estimate. These algorithms present a major drawback: they require a large number of samples in order to obtain good results. If the covariance matrix is low-rank structured, its eigenbasis may be separated in two orthogonal subspaces. Thanks to the LR approximation, orthogonal projectors onto theses subspaces may be used instead of the noise CM in processes, leading to low-rank algorithms. The adaptive versions of these algorithms achieve similar performance to classic classic ones with less samples. Furthermore, the current increase in the size of the data strengthens the relevance of this type of method. However, this increase may often be associated with an increase of the dimension of the system, leading to multidimensional samples. Such multidimensional data may be processed by two approaches: the vectorial one and the tensorial one. The vectorial approach consists in unfolding the data into vectors and applying the traditional algorithms. These operations are not lossless since they involve a loss of structure. Several issues may arise from this loss: decrease of performance and/or lack of robustness. The tensorial approach relies on multilinear algebra, which provides a good framework to exploit these data and preserve their structure information. In this context, data are represented as multidimensional arrays called tensor. Nevertheless, generalizing vectorial-based algorithms to the multilinear algebra framework is not a trivial task. In particular, the extension of low-rank algorithm to tensor context implies to choose a tensor decomposition in order to estimate the signal and noise subspaces. The purpose of this thesis is to derive and study tensor low-rank algorithms. This work is divided into three parts. The first part deals with the derivation of theoretical performance of a tensor MUSIC algorithm based on Higher Order Singular Value Decomposition (HOSVD) and its application to a polarized source model. The second part concerns the derivation of tensor low-rank filters and detectors in a general low-rank tensor context. This work is based on a new definition of tensor rank and a new orthogonal tensor decomposition : the Alternative Unfolding HOSVD (AU-HOSVD). In the last part, these algorithms are applied to a particular radar configuration : the Space-Time Adaptive Process (STAP). This application illustrates the interest of tensor approach and algorithms based on AU-HOSVD.