Low rank approximation is the problem of finding two low rank factors W and H such that the rank(WH) << rank(A) and A ≈ WH. These low rank factors W and H can be constrained for meaningful physical interpretation and referred as Constrained Low Rank Approximation (CLRA). Like most of the constrained optimization problem, performing CLRA can be computationally expensive than its unconstrained counterpart. A widely used CLRA is the Non-negative Matrix Factorization (NMF) which enforces non-negativity constraints in each of its low rank factors W and H. In this thesis, I focus on scalable/distributed CLRA algorithms for constraints such as boundedness and non-negativity for large real world matrices that includes text, High Definition (HD) video, social networks and recommender systems. First, I begin with the Bounded Matrix Low Rank Approximation (BMA) which imposes a lower and an upper bound on every element of the lower rank matrix. BMA is more challenging than NMF as it imposes bounds on the product WH rather than on each of the low rank factors W and H. For very large input matrices, we extend our BMA algorithm to Block BMA that can scale to a large number of processors. In applications, such as HD video, where the input matrix to be factored is extremely large, distributed computation is inevitable and the network communication becomes a major performance bottleneck. Towards this end, we propose a novel distributed Communication Avoiding NMF (CANMF) algorithm that communicates only the right low rank factor to its neighboring machine. Finally, a general distributed HPC- NMF framework that uses HPC techniques in communication intensive NMF operations and suitable for broader class of NMF algorithms.

International Telemetering Conference Proceedings / October 25-28, 1999 / Riviera Hotel and Convention Center, Las Vegas, Nevada / Experimentation with various routines that create floating point values in MIL-STD-1750A 32 and 48 bit formats has uncovered several flaws that result in loss of precision in approximation and/or incorrect results. This paper will discuss approximation and key computational conditions in the creation of values in these formats, and will describe algorithms that create values correctly and to the closest possible approximation. Test cases for determining behavior of routines of this type will also be supplied.

People rely on the ability to transmit information over channels of communication that aresubject to noise and interference. This makes the ability to detect and recover from errorsextremely important. Coding theory addresses this need for reliability. A fundamentalquestion of coding theory is whether and how we can correct the errors in a message thathas been subjected to interference. One answer comes from structures known as errorcorrecting codes.A well studied parameter associated with a code is its covering radius. The coveringradius of a code is the smallest radius such that every vector in the Hamming space of thecode is contained in a ball of that radius centered around some codeword. Covering radiusrelates to an important decoding strategy known as nearest neighbor decoding.The multicovering radius is a generalization of the covering radius that was proposed byKlapper [11] in the course of studying stream ciphers. In this work we develop techniques forfinding the multicovering radius of specific codes. In particular, we study the even weightcode, the 2-error correcting BCH code, and linear codes with covering radius one.We also study questions involving the complexity of finding the multicovering radius ofcodes. We show: Lower bounding the m-covering radius of an arbitrary binary code is NPcompletewhen m is polynomial in the length of the code. Lower bounding the m-coveringradius of a linear code is Σp2-complete when m is polynomial in the length of the code. IfP is not equal to NP, then the m-covering radius of an arbitrary binary code cannot beapproximated within a constant factor or within a factor nϵ, where n is the length of thecode and ϵ andlt; 1, in polynomial time. Note that the case when m = 1 was also previouslyunknown. If NP is not equal to Σp2, then the m-covering radius of a linear code cannot beapproximated within a constant factor or within a factor nϵ, where n is the length of thecode and ϵ andlt; 1, in polynomial time.

L'adaptation de maillage pour l'approximation des fonctions par éléments finis permet d'adapter localement la résolution en la raffinant dans les lieux de variations rapides de la fonction. Cette méthode intervient dans de nombreux domaines du calcul scientifique. L'utilisation de triangles anisotropes permet d'améliorer l'efficacité du maillage en introduisant des triangles longs et fins épousant notamment les directions des courbes de discontinuité. Etant donnée une norme d'intérêt et une fonction f à approcher, nous formulons le problème de l'adaptation optimale de maillage, comme la minimisation de l'erreur d'approximation par éléments finis de degré k donné parmi toutes les triangulations (potentiellement anisotropes) de cardinalité donnée N du domaine de définition de f. Nous étudions ce problème sous l'angle des quatre questions ci dessous: I. Comment l'erreur d'approximation se comporte-t-elle dans le régime asymptotique où le nombre N de triangles tend vers l'infini, lorsque f est une fonction suffisamment régulière? II. Quelles classes de fonctions gouvernent la vitesse de décroissance de l'erreur d'approximation lorsque N augmente, et sont en ce sens naturellement liées au problème d'adaptation optimale de maillage? III. Ce problème d'optimisation, qui porte sur les triangulations de cardinalité donnée N, peut-il être remplacé par un problème équivalent portant sur un objet continu? IV. Est-il possible de construire une suite quasi-optimale de triangulations en utilisant une procédure hiérarchique de raffinement?

Data-mining has become a hot topic in recent years. It consists of extracting relevant information or structures from data such as: pictures, textual material, networks, etc. Such information or structures are usually not trivial to obtain and many techniques have been proposed to address this problem, including Independent Component Analysis, Latent Sematic Analysis, etc. Nonnegative Matrix Factorization is yet another technique that relies on the nonnegativity of the data and the nonnegativity assumption of the underlying model. The main advantage of this technique is that nonnegative objects are modeled by a combination of some basic nonnegative parts, which provides a physical interpretation of the construction of the objects. This is an exclusive feature that is known to be useful in many areas such as Computer Vision, Information Retrieval, etc. In this thesis, we look at several aspects of Nonnegative Matrix Factorization, focusing on numerical algorithms and their applications to different kinds of data and constraints. This includes Tensor Nonnegative Factorization, Weighted Nonnegative Matrix Factorization, Symmetric Nonnegative Matrix Factorization, Stochastic Matrix Approximation, etc. The recently proposed Rank-one Residue Iteration (RRI) is the common thread in all of these factorizations. It is shown to be a fast method with good convergence properties which adapts well to many situations.

.

.

.

.

No description available.