Error-free computer solution of certain systems of linear equations

In this article we propose a procedure which generates the exact solution for the system Ax = b, where A is an integral nonsingular matrix and b is an integral vector, by improving the initial floating-point approximation to the solution. This procedure, based on an easily programmed method proposed by Aberth [1], first computes the approximate floating-point solution x^* by using an available linear equation solving algorithm. Then it extracts the exact solution x from x^* if the error in the approximation x^* is sufficiently small. An a posteriori upper bound for the error of x^* is derived when Gaussian Elimination with partial pivoting is used. Also, a computable upper bound for |det(A)|, which is an alternative to using Hadamard's inequality, is obtained as a byproduct of the Gaussian Elimination process.     

Asymptotic distributions of functions of the eigenvalues of sample covariance matrix and canonical correlation matrix in multivariate time series

Let S = (1/n) Σ_t=1ⁿ X(t) X(t)′, where X(1), …, X(n) are p × 1 random vectors with mean zero. When X(t) (t = 1, …, n) are independently and identically distributed (i.i.d.) as multivariate normal with mean vector 0 and covariance matrix Σ, many authors have investigated the asymptotic expansions for the distributions of various functions of the eigenvalues of S. In this paper, we will extend the above results to the case when {X(t)} is a Gaussian stationary process. Also we shall derive the asymptotic expansions for certain functions of the sample canonical correlations in multivariate time series. Applications of some of the results in signal processing are also discussed.     

On the structure of the Wishart distribution

In this paper it is shown that every nonnegative definite symmetric random matrix with independent diagonal elements and at least one nondegenerate nondiagonal element has a noninfinitely divisible distribution. Using this result it is established that every Wishart distribution W_p(k, Σ, M) with both p and rank (Σ) ≥ 2 is noninfinitely divisible. The paper also establishes that any Wishart matrix having distribution W_p(k, Σ, 0) has the joint distribution of its elements in the rth row and rth column to be infinitely divisible for every r = 1,2,…,p.     

A characterization of the multivariate normal distribution

Let X_j (j = 1,…,n) be i.i.d. random variables, and let Y′ = (Y₁,…,Y_m) and X′ = (X₁,…,X_n) be independently distributed, and A = (a_jk) be an n × n random coefficient matrix with a_jk = a_jk(Y) for j, k = 1,…,n. Consider the equation U = AX, Kingman and Graybill [Ann. Math. Statist.41 (1970)] have shown U ～ N(O,I) if and only if X ～ N(O,I). provided that certain conditions defined in terms of the a_jk are satisfied. The task of this paper is to delete the identical assumption on X₁,…,X_n and then generalize the results to the vector case. Furthermore, the condition of independence on the random components within each vector is relaxed, and also the question raised by the above authors is answered.     

Antichains in the set of subsets of a multiset

A set F of distinct subsets x of a finite multiset M (that is, a set with several different kinds of elements) is a c-antichain if for no c + 1 elements x₀, x₁, …, x_c of F does x₀ ? x₁ ? ··· ? x_c hold. The weight of F, wF, is the total number of elements of M in the various elements x of F. For given integers f and c, we find min wF, where the minimum is taken over all f-element c-antichains F. Daykin [9, 10] has solved this problem for ordinary sets and Clements [3] has solved it for multisets, but only for c = 1.     

L-fuzzy normal spaces and Tietze extension theorem

In this paper we prove a characterization theorem for normal L-fuzzy topological spaces (L is an infinitely distributive lattice with an order-reversing involution). In the particular case L = {0, 1} this theorem reduces to a known result of Katětov (Fund. Math. 38 (1951), 85–91) and Tong (Duke Math. J. 19 (1952), 289–292). As an important application we obtain a fuzzy version of Tietze extension theorem. This yields an affirmative answer to a question raised in a series of papers by Rodabaugh (Fuzzy Sets and Systems 11 (1983), 163–183).     

A duality principle for lattices and categories of modules

Let R be a ring with 1, R^op the opposite ring, and R-Mod the category of left unitary R-modules and R-linear maps. A characterization of well-powered abelian categories $\text{A}$ such that there exists an exact embedding functor $\text{A}$→R-Mod is given. Using this characterization and abelian category duality, the following duality principles can be established.Theorem. There exists an exact embedding functor $\text{A}$→R-Mod if and only if there exists an exact embedding functor $\text{A}$^op→R^op-Mod.Corollary. If R-Mod has a specified diagram-chasing property, then R^op-Mod has the dual property.A lattice L is representable by R-modules if it is embeddable in the lattice of submodules of some unitary left R-module; $\text{L}$(R) denotes the quasivariety of all lattices representable by R-modules.Theorem. A lattice L is representable by R-modules if and only if its order dual L¹ is representable by R^op-modules. That is, $\text{L}\text{(}\text{R}{}^{\mathrm{op}}\text{)={L}{}^1\text{:L?}\text{L}\text{(}\text{R}\text{)}}$.If $\text{R}$ is a commutative ring with 1 and a specified diagram-chasing result is satisfied in R-Mod, then the dual result is also satisfied in R-Mod. Furthermore, $\text{L}\text{(}\text{R}\text{)}$ is self-dual: $\text{L}\text{(}\text{R}\text{)= {L}{}^1\text{:L?}\text{L}\text{(}\text{R}\text{)}.}$     

On the uniqueness of overcomplete dictionaries, and a practical way to retrieve them

A full-rank under-determined linear system of equations Ax = b has in general infinitely many possible solutions. In recent years there is a growing interest in the sparsest solution of this equation—the one with the fewest non-zero entries, measured by ∥x∥₀. Such solutions find applications in signal and image processing, where the topic is typically referred to as “sparse representation”. Considering the columns of A as atoms of a dictionary, it is assumed that a given signal b is a linear composition of few such atoms. Recent work established that if the desired solution x is sparse enough, uniqueness of such a result is guaranteed. Also, pursuit algorithms, approximation solvers for the above problem, are guaranteed to succeed in finding this solution.Armed with these recent results, the problem can be reversed, and formed as an implied matrix factorization problem: Given a set of vectors {b_i}, known to emerge from such sparse constructions, Ax_i = b_i, with sufficiently sparse representations x_i, we seek the matrix A. In this paper we present both theoretical and algorithmic studies of this problem. We establish the uniqueness of the dictionary A, depending on the quantity and nature of the set {b_i}, and the sparsity of {x_i}. We also describe a recently developed algorithm, the K-SVD, that practically find the matrix A, in a manner similar to the K-Means algorithm. Finally, we demonstrate this algorithm on several stylized applications in image processing.     

Some inverse problems involving conditional expectations

Let (Ω, F, P) be a probability space, let H be a sub-σ-algebra of F, and let Y be positive and H-measurable with E[Y] = 1. We discuss the structure of the convex set CE(Y; H) = {X ∈ pF: Y = E[X|H]} of random variables whose conditional expectation given H is the prescribed Y. Several characterizations of extreme points of CE(Y; H) are obtained. A necessary and sufficient condition is given in order that CE(Y; H) be the closed, convex hull of its extreme points. For the case of finite F we explicitly calculate the extreme points of CE(Y; H), identify pairs of adjacent extreme points, and characterize extreme points of CE(Y; H) ? CE(Z; G), where G is a second sub-σ-algebra of F and Z ∈ pG. When H = σ(Y) and appropriate topological hypotheses hold, extreme points of CE(Y; H) are shown to be in explicit one-to-one correspondence with certain left inverses of Y. Finally, it is shown how the same approach can be applied to the problem of extremal random measures on $\text{R}$₊ with a prescribed compensator, to deduce that the number of extreme points is zero or one.     

An analysis of (h,k, 1)-Shellsort

One classical sorting algorithm, whose performance in many cases remains unanalyzed, is Shellsort. Let h be a t-component vector of positive integers. An h-Shellsort will sort any given n elements in t passes, by means of comparisons and exchanges of elements. Let S>_j(h; n) denote the average number of element exchanges in the jth pass, assuming that all the n! initial orderings are equally likely. In this paper we derive asymptotic formulas of S_j(h; n) for any fixed h = (h, k, l), making use of a new combinatorial interpretation of S₃. For the special case h = (3, 2, 1), the analysis is further sharpened to yield exact expressions.     

Sums of finitely based lattice varieties

This paper is concerned with the question whether the lattice sum (join) V + V′ of two finitely based lattice varieties V and V′ is finitely based. An example is constructed showing that this is not always the case. On the other hand, it is proved that if V ? M and (V′)³ = (N)³, then V + V′ is finitely based. Here M and N are, respectively, the variety of all modular lattices and the variety generated by the pentagon (the five-element nonmodular lattice), and (V)ⁿ is the variety defined by all those identities with n variables or less that hold in V. In particular, M + N, the unique lattice variety that covers M, is finitely based.     

Bilattices for deductions in multi-valued logic

In this exploratory paper we propose a framework for the deduction apparatus of multi-valued logics based on the idea that a deduction apparatus has to be a tool to manage information on truth values and not directly truth values of the formulas. This is obtained by embedding the algebraic structure V defined by the set of truth values into a bilattice B. The intended interpretation is that the elements of B are pieces of information on the elements of V. The resulting formalisms are particularized in the framework of fuzzy logic programming. Since we see fuzzy control as a chapter of multi-valued logic programming, this suggests a new and powerful approach to fuzzy control based on positive and negative conditions.     

Operator norms,multiplicativity factors,and C-numerical radii

Let V be a normed vector space over C, let $\text{B}$(V) denote the algebra of linear bounded operators on V, and let N be an arbitrary seminorm or norm on $\text{B}$(V). In this paper we discuss multiplicativity factors for N, i.e., constants μ>0 for which N_μ≡μN is submultiplicative. We find that, while in the finite dimensional case nontrivial indefinite seminorms have no multiplicativity factors and norms do have multiplicativity factors, in the infinite dimensional case N may or may not have such factors. Our results are then applied in order to compute multiplicativity factors for certain generalizations of the classical numerical radius, called C-numerical radii. This is done with the help of a combinatorial inequality which seems to be of independent interest.     

On the existence of free topological groups

Given a Tychonoff space X and classes U and V of topological groups, we say that a topological group G = G(X, U, V) is a free (U,V)-group over X if (a) X is a subspace of G, (b) G ϵ U, and (c) every continuous f: X → H with H ϵ V extends uniquely to a continuous homomorphism f̄: G→H. For certain classes U and V, we consider the question of the existence of free (U,V)- groups. Our principal results are the following. Let PA and CA denote, respectively, the class ofpseudocompact Abelian groups and the class of compact Abelian groups. Then

• 1.(a) there is a free (PA,PA)-group over X iff; X=Ø and
• 2.(b) there is for each X a free (PA,CA)-group over X in which X is closed.

     

A computational method for the indefinite quadratic programming problem

We present an algorithm for the quadratic programming problem of determining a local minimum of ?(x)=$\text{1}\text{2}$x^TQx+c^Tx such that A^Tx?b where Q ymmetric matrix which may not be positive definite. Our method combines the active constraint strategy of Murray with the Bunch-Kaufman algorithm for the stable decomposition of a symmetric matrix. Under the active constraint strategy one solves a sequence of equality constrained problems, the equality constraints being chosen from the inequality constraints defining the original problem. The sequence is chosen so that ?(x) continues to decrease and x remains feasible. Each equality constrained subproblem requires the solution of a linear system with the projected Hessian matrix, which is symmetric but not necessarily positive definite. The Bunch-Kaufman algorithm computes a decomposition which facilitates the stable determination of the solution to the linear system. The heart of this paper is a set of algorithms for updating the decomposition as the method progresses through the sequence of equality constrained problems. The algorithm has been implemented in a FORTRAN program, and a numerical example is given.     

Invariant scale matrix hypothesis tests under elliptical symmetry

The usual assumption in multivariate hypothesis testing is that the sample consists of n independent, identically distributed Gaussian m-vectors. In this paper this assumption is weakened by considering a class of distributions for which the vector observations are not necessarily either Gaussian or independent. This class contains the elliptically symmetric laws with densities of the form f(X(n × m)) = ψ[tr(X ? M)′ (X ? M)Σ^?1]. For testing the equality of k scale matrices and for the sphericity hypothesis it is shown, by using the structure of the underlying distribution rather than any specific form of the density, that the usual invariant normal-theory tests are exactly robust, for both the null and non-null cases, under this wider class.     

Factorizing multivariate time series operators

Motivated by problems occurring in the empirical identification and modelling of a n-dimensional ARMA time series X(t) we study the possibility of obtaining a factorization (I + a₁B + … + a_pB^p) X(t) = [Π_i=1^p (I ? α_iB)] X(t), where B is the backward shift operator. Using a result in [3] we conclude that as in the univariate case such a factorization always exists, but unlike the univariate case in general the factorization is not unique for given a₁, a₂,…, a_p. In fact the number of possibilities is limited upwards by $\text{(np)!}\text{(n!)}{}^{\mathrm{p}}$, there being cases, however, where this maximum is not reached. Implications for the existence and possible use of transformations which removes nonstationarity (or almost nonstationarity) of X(t) are mentioned.     

Simple components of group algebras Q[G] central over real quadratic fields

Let k be a real quadratic field, and $\text{U}$ a central division quaternion algebra over k. In this paper sufficient conditions are given to insure that $\text{U}$ appears in a simple component of the group algebra Q[G] of some finite group G over the rational field Q. In particular, when k is assumed to be Q(√2) or Q(√5), the necessary and sufficient conditions for $\text{U}$ to appear in some Q[G] are given.     

Matroids with given restrictions and contractions

If M is a matroid on a set S and if X is a subset of S, then there are two matroids on X induced by M: namely, the restriction and the contraction of M onto X. Necessary and sufficient conditions are obtained for two matroids on the same set to be of this form and an analogous result is obtained when (X₁,…, X_t) is a partition of S. The corresponding results when all the matroids are binary are also obtained.     

Construction d’entrelacs hyperpoliques et arithmétiques

In this Note, we continue the study started in [4] about arithmetic hyperbolic links L such that S³\L is homeomorphic to H³/Γ, where Γ is not conjugate to a subgroup of any Bianchi group. One describes the steps of the construction, different from the construction in [4], which permits us to determine the first known examples in M₂(Q (i√39)) and M₂(Q (i√6 respectively.