Least-squares problem for the quaternion matrix equation AXB+CYD=E over different constrained matrices

For any A=A ₁+A ₂ j∈Q ^n×n and η∈<texlscub>i, j, k</texlscub>, denote A ^{η H} =?η A ^H η. If A ^{η H} =A, A is called an $\eta$-Hermitian matrix. If A ^{η H} =?A, A is called an η-anti-Hermitian matrix. Denote η-Hermitian matrices and η-anti-Hermitian matrices by η HQ ^n×n and η AQ ^n×n , respectively.

By using the complex representation of quaternion matrices, the Moore–Penrose generalized inverse and the Kronecker product of matrices, we derive the expressions of the least-squares solution with the least norm for the quaternion matrix equation AXB+CYD=E over X∈η HQ ^n×n and Y∈η AQ ^n×n .     

Stability of linear infinite-dimensional systems revisited

The paper is devoted to a study of stability questions for linear infinite-dimensional discrete-time and continuous-time systems. The concepts of power stability and l ^p Instability for a linear discrete-time system x _k+1 = Ax _k (where x _k ε X, X is a Banach space, A is linear and bounded) are introduced and studied. Relationships between these concepts and the inequality r(A) < 1, where r(A) denotes the spectral radius of A, are also given. The discrete-time results are used for a simple derivation of some well-known properties of exponentially stable and L^p-stable linear continuous-time systems described by [xdot](t) = Ax(t) (A generates here a strongly continuous semigroup of linear and bounded operators on X). Some remarks on norms related to stable systems are also included.     

Regular matrix transformations and rates of convergence of positive linear operators

Abstract This paper investigates the effects of matrix summability methods on the A-statistical approximation of sequences of positive linear operators defined on the space of all 2π-periodic and continuous functions on the whole real axis. The two main tools used in this paper are A-statistical convergence and the modulus of continuity. Keywords: Regular infinite matrices, A-statistical convergence, rates of A-statistical convergence, positive linear operators, the Korovkin theorem, modulus of continuity. Mathematics Subject Classification (2000): 41A25, 41A36     

Local Approximability of Max-Min and Min-Max Linear Programs

In a max-min LP, the objective is to maximise ω subject to A x≤1, C x≥ω 1, and x≥0. In a min-max LP, the objective is to minimise ρ subject to A x≤ρ 1, C x≥1, and x≥0. The matrices A and C are nonnegative and sparse: each row a _i of A has at most Δ _I positive elements, and each row c _k of C has at most Δ _K positive elements.     

Some consequences on the planar three-index transportation problem

In this study, some algebraic characterizations of the coefficient matrix A of the planar three-index transportation problem are derived and the equivalent formulation of this problem is obtained using the Kronecker product. It is shown that eigenvectors of the matrix G ⁺ G are characterized in terms of eigenvectors of the matrix A ⁺ A , where G ⁺ is the Moore–Penrose inverse of the coefficient matrix G of the equivalent problem.     

An Interval Linear Tolerance Problem

This paper is concerned with a tolerance problem for an interval linear system A x = b requiring inner estimation of the admissible solution set {x ⁿ | (A A)(Ax b)} formed by vectors x for which the product Ax remains within b for any possible A A. Methods for verifying the emptiness and nonemptiness of admissible solution sets are developed. Formulas for the dimensions of the interval solution of a tolerance problem with known center are derived.     

The kernel strategy and its use for the study of combinatory logic

Barendregt defines combinatory logic as an equational system satisfying the combinatorsS andK with ((Sx)y)z=(xz)(yz) and (Kx)y=x; the set consisting ofS andK provides abasis for all of combinatory logic. Rather than studying all of the logic, logicians often focus onfragments of the logic, subsets whose basis is obtained by replacingS orK or both by other combinators. In this article, we present a powerful new strategy, called thekernel strategy, for studying fragments in the context of questions concerned with fixed point properties. Interest in such properties rests in part with their relation to normal forms and paradoxes. We show how the kernel strategy was used to answer a number of open questions, offering abundant evidence that the availability of the kernel strategy marks a singular advance for automated reasoning. In all of our experiments with this strategy applied by an automated reasoning program, the rate of success has been impressively high and the CPU time to obtain the desired information startlingly small. For each fragment we study, we use the kernel strategy to attempt to determine whether the strong or the weak fixed point property holds. WhereA is a given fragment with basisB, the strong fixed point property holds forA if and only if there exists a combinatory such that, for all combinatorsx,yx=x(yx), wherey is expressed purely in terms of elements ofB. The weak fixed point property holds forA if and only if for all combinatorsx there exists a combinatory such thaty=xy, wherey is expressed purely in terms of the elements ofB and the combinatorx. Because the use of the kernel strategy is so effective in addressing questions focusing on either fixed point property, its formulation marks an important advance for combinatory logic. Perhaps of especial interest to logicians is an infinite class of infinite sets of tightly coupled fixed point combinators (presented here), whose unexpected discovery resulted directly from the application of the strategy by an automated reasoning program. We also offer various open questions for possible research and focus on an automated reasoning program and input files that may prove useful for such research.This work was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Optimal Finite Characterization of Linear Problems with Inexact Data

Abstract. For many linear problems, in order to check whether a certain property is true for all matrices A from an interval matrix A, it is sufficient to check this property for finitely many “vertex” matrices A ∈ A. J. Rohn has discovered that we do not need to use all 2ⁿ² vertex matrices, it is sufficient to only check these properties for 2²ⁿ⁻¹ ≪ 2ⁿ² vertex matrices of a special type A_yz. In this paper, we show that a further reduction is impossible: without checking all 2²ⁿ⁻¹ matrices A_yz, we cannot guarantee that the desired property holds for all A ϵ A. Thus, these special vertex matrices provide an optimal finite characterization of linear problems with inexact data.     

Integral-type generalizations of operators obtained from certain multivariate polynomials

Abstract In this work, we mainly focus on the Kantorovich-type (integral-type) generalizations of the positive linear operators obtained from the Chan-Chyan-Srivastava multivariable polynomials. Using the notion of A-statistical convergence, we obtain various approximation theorems including a statistical Korovkin-type result and rates of A-statistical convergence with the help of the modulus of continuity, Lipschitz class functionals and Peetre’s K-functionals. We also introduce an sth order generalization of our approximating operators. Keywords. Chan-Chyan-Srivastava multivariable polynomials, Korovkin approximation theorem, Kantorovich-type operators, A-statistical convergence, modulus of continuity, Lipschitz class functional, Peetre’s K-functional Mathematics Subject Classification (2000): Primary: 41A25; 41A36, Secondary: 33C45     

A Generalization of AT-Free Graphs and a Generic Algorithm for Solving Triangulation Problems

Abstract. A subset A of the vertices of a graph G is an asteroidal set if for each vertex a ∈ A a connected component of G-N[a] exists containing A\backslash{a} . An asteroidal set of cardinality three is called asteriodal triple and graphs without an asteriodal triple are called AT-free . The maximum cardinality of an asteroidal set of G , denoted by \an(G) , is said to be the asteriodal number of G . We present a scheme for designing algorithms for triangulation problems on graphs. As a consequence, we obtain algorithms to compute graph parameters such as treewidth, minimum fill-in and vertex ranking number. The running time of these algorithms is a polynomial (of degree asteriodal number plus a small constant) in the number of vertices and the number of minimal separators of the input graph.     

A theorem on atomicity in distributed algorithms

Reasoning about a distributed algorithm is simplified if we can ignore the time needed to send and deliver messages and can instead pretend that a process sends a collection of messages as a single atomic action, with the messages delivered instantaneously as part of the action. A theorem is derived that proves the validity of such reasoning for a large class of algorithms. It generalizes and corrects a well-known folk theorem about when an operation in a multiprocess program can be considered atomic.List of notations A The set of program actions - A The algorithm under consideration - A The reduced version of algorithmA - A The action obtained by executing the operationA as an atomic action - C The set of state components - d[i] A variable of the Distance-Finding Algorithm - L An operation ofA, as in C2 - The operation obtained by adding toL the actions that deliver messages sent byL - N _p(S) The set of possible next actions of processp from states - P The correctness property - R An operation ofA, as in C2 - S The set of states - S ₀ The set of initial states - S _c The range of values of state componentc - X An action ofA, as in C2 - Usually denotes an execution ofA - The execution ofA that corresponds to an execution ofA When snow conditions are poor,Dr. L. Lamport works at Digital Equipment Corporation's Systems Research Center. As an undergraduate, he took a course in atomic physics.     

Efficiently preconditioned inexact Newton methods for large symmetric eigenvalue problems

In this paper, we propose an efficiently preconditioned Newton method for the computation of the leftmost eigenpairs of large and sparse symmetric positive definite matrices. A sequence of preconditioners based on the BFGS update formula is proposed, for the preconditioned conjugate gradient solution of the linearized Newton system to solve Au=q(u) u, q(u) being the Rayleigh quotient. We give theoretical evidence that the sequence of preconditioned Jacobians remains close to the identity matrix if the initial preconditioned Jacobian is so. Numerical results onto matrices arising from various realistic problems with size up to one million unknowns account for the efficiency of the proposed algorithm which reveals competitive with the Jacobi–Davidson method on all the test problems.     

Synthesis of space optimal systolic arrays for band matrix-vector multiplication

In this paper, we consider the implementation of a product c=A b, where A is N ₁×N ₃ band matrix with bandwidth ω and b is a vector of size N ₃×1, on bidirectional and unidirectional linear systolic arrays (BLSA and ULSA, respectively). We distinguish the cases when the matrix bandwidth ω is 1≤ω≤N ₃ and N ₃≤ω≤N ₁+N ₃−1. A modification of the systolic array synthesis procedure based on data dependencies and space-time transformations of data dependency graph is proposed. The modification enables obtaining both BLSA and ULSA with an optimal number of processing elements (PEs) regardless of the matrix bandwidth. The execution time of the synthesized arrays has been minimized. We derive explicit formulas for the synthesis of these arrays. The performances of the designed arrays are discussed and compared to the performances of the arrays obtained by the standard design procedure.     

How Strong Is Strong Regularity?

We compare the notions of regularity and strong regularity of interval matrices. For an n × n interval matrix A we construct 2ⁿ open convex cones, all of them lying in the interior of the nonnegative orthant. It is shown that regularity of A is characterized by nonemptiness of all these cones, whereas strong regularity is characterized by nonemptiness of their intersection.     

Context-aware,self-scaling Fuzzy ArtMap for received signal strength based location systems

Location awareness is the key capability of mobile computing applications. Despite high demand, indoor location technologies have not become truly ubiquitous mainly due to their requirements of costly infrastructure and dedicated hardware components. Received signal strength (RSS) based location systems are poised to realize economical ubiquity as well as sufficient accuracy for variety of applications. Nevertheless high resolution RSS based location awareness requires tedious sensor data collection and training of classifier which lengthens location system development life cycle. We present a rapid development approach based on online and incremental learning method which significantly reduces development time while providing competitive accuracy in comparison with other methods. ConSelFAM (Context-aware, Self-scaling Fuzzy ArtMap) extends the Fuzzy ArtMap neural network system. It enables on the fly expansion and reconstruction of location systems which is not possible in previous systems.     

Learning bidirectional asymmetric similarity for collaborative filtering via matrix factorization

Memory-based collaborative filtering (CF) aims at predicting the rating of a certain item for a particular user based on the previous ratings from similar users and/or similar items. Previous studies in finding similar users and items have several drawbacks. First, they are based on user-defined similarity measurements, such as Pearson Correlation Coefficient (PCC) or Vector Space Similarity (VSS), which are, for the most part, not adaptive and optimized for specific applications and data. Second, these similarity measures are restricted to symmetric ones such that the similarity between A and B is the same as that for B and A, although symmetry may not always hold in many real world applications. Third, they typically treat the similarity functions between users and functions between items separately. However, in reality, the similarities between users and between items are inter-related. In this paper, we propose a novel unified model for users and items, known as Similarity Learning based Collaborative Filtering (SLCF) , based on a novel adaptive bidirectional asymmetric similarity measurement. Our proposed model automatically learns asymmetric similarities between users and items at the same time through matrix factorization. Theoretical analysis shows that our model is a novel generalization of singular value decomposition (SVD). We show that, once the similarity relation is learned, it can be used flexibly in many ways for rating prediction. To take full advantage of the model, we propose several strategies to make the best use of the proposed similarity function for rating prediction. The similarity can be used either to improve the memory-based approaches or directly in a model based CF approaches. In addition, we also propose an online version of the rating prediction method to incorporate new users and new items. We evaluate SLCF using three benchmark datasets, including MovieLens, EachMovie and Netflix, through which we show that our methods can outperform many state-of-the-art baselines.     

A more efficient algorithm for the min-plus multiplication

The (min, + ) product C of two n × n matrices A and B is defined as C _ij = min_1≦k≦n A _ik + B _kj . This paper presents an algorithm to compute the (min, +) product of two n × n matrices. The algorithm follows the approach described by Fredman, but is faster than Fredman's own algorithm: its time complexity is either O(n ³/√log₂ n) or even O(n ^2.5√log₂ n), if one adheres to the uniform-cost RAM model faithfully.

This result implies the existence of O(n ³/√log₂ n) algorithms for the problems that (min, +) matrix multiplication is equivalent to, such as the all-pairs shortest paths problem.

As the presented algorithm uses operations on sets, the formal analysis of its time complexity raises a few interesting questions about the applicability of the standard RAM complexity model.     

Quotient convergence and multi-splitting methods for solving singular linear equations

Abstract   In this paper, we use the group inverse to characterize the quotient convergence of an iterative method for solving consistent singular linear systems, when the matrix index equals one. Next, we show that for stationary splitting iterative methods, the convergence and the quotient convergence are equivalent, which was first proved in [7]. Lastly, we propose a (multi-)splitting iterative method A=F–G, where the splitting matrix F may be singular, endowed with group inverse, by using F ^# as a solution tool for any iteration. In this direction, sufficient conditions for the quotient convergence of these methods are given. Then, by using the equivalence between convergence and quotient convergence, the classical convergence of these methods is proved. These latter results generalize Cao’s result, which was given for nonsingular splitting matrices F. Keywords: Group inverse, singular linear equations, iterative method, P-regular splitting, Hermitian positive definite matrix, multi-splitting, quotient convergence AMS Classification: 15A09, 65F35