Markov bases for two-way subtable sum problems

It is well known that for two-way contingency tables with fixed row sums and column sums the set of square-free moves of degree two forms a Markov basis. However when we impose an additional constraint that the sum of cell counts in a subtable is also fixed, then these moves do not necessarily form a Markov basis. Thus, in this paper, we show a necessary and sufficient condition on a subtable so that the set of square-free moves of degree two forms a Markov basis.     

Model selection for Gaussian latent block clustering with the integrated classification likelihood

Block clustering aims to reveal homogeneous block structures in a data table. Among the different approaches of block clustering, we consider here a model-based method: the Gaussian latent block model for continuous data which is an extension of the Gaussian mixture model for one-way clustering. For a given data table, several candidate models are usually examined, which differ for example in the number of clusters. Model selection then becomes a critical issue. To this end, we develop a criterion based on an approximation of the integrated classification likelihood for the Gaussian latent block model, and propose a Bayesian information criterion-like variant following the same pattern. We also propose a non-asymptotic exact criterion, thus circumventing the controversial definition of the asymptotic regime arising from the dual nature of the rows and columns in co-clustering. The experimental results show steady performances of these criteria for medium to large data tables.     

Group methodology in production management: A solution based on a hierarchical classification method

We consider the problem submitted by Garcia and Proth and we propose for it a solution obtained by simply applying our very general method of hierarchical classification based on the likelihood of the links, in the case of an incidence table of data. This application is done on each of the two sides of the incidence data table. In our approach, the common number p of classes has not to be fixed arbitrarily, but is an observed possible result—provided by the notions of ‘significant’ levels and nodes of the classification tree—for the ‘natural’ association between two partitions. We compare our solution with the previous one.     

Random Databases with Approximate Record Matching

In many database applications in telecommunication, environmental and health sciences, bioinformatics, physics, and econometrics, real-world data are uncertain and subjected to errors. These data are processed, transmitted and stored in large databases. We consider stochastic modelling for databases with uncertain data and for some basic database operations (for example, join, selection) with exact and approximate matching. Approximate join is used for merging or data deduplication in large databases. Distribution and mean of the join sizes are studied for random databases. A random database is treated as a table with independent random records with a common distribution (or a set of random tables). These results can be used for integration of information from different databases, multiple join optimization, and various probabilistic algorithms for structured random data.     

Discontinuous Solutions to Unbounded Differential Inclusions under State Constraints. Applications to Optimal Control Problems

We consider a nonconvex and unbounded differential inclusion derived from a control system whose control sets are time and space-dependent. We extend the inclusion in order to allow discontinuous trajectories. We prove that the set of solutions of the original inclusion is dense in the set of solutions of the extended inclusion and, moreover, these last solutions are stable with respect to the initial data. Both of these results are also proven in the presence of state and integral constraints (assuming suitable conditions at the boundary of the constraining set). As an application, the value function of a Mayer problem is shown to be continuous and the unique viscosity solution of a Hamilton–Jacobi equation with suitable boundary conditions.     

Fifth Through Eighth Grade Students’ Difficulties in Constructing Bar Graphs: Data Organization,Data Aggregation,and Integration of a Second Variable

Studies that consider the displays that students create to organize data are not common in the literature. This article compares fifth through eighth graders’ difficulties with the creation of bar graphs using either raw data (Study 1, n = 155) or a provided table (Study 2, n = 152). Data in Study 1 showed statistical differences for the type of data organization but not for grade level. Students’ primary problem was choosing a format that integrated a second variable and aggregating data. In contrast, in Study 2, we observed that seventh and eighth graders outperformed fifth and sixth graders. We interpret these results in terms of older students’ better data interpretation competence. We conclude that students’ difficulties in bar graphing can be traced to their tabulation processes. Data organization is essential for understanding and representing data, and educators should devote to it the attention it deserves.     

Damping in rigid block dynamics contained between side-walls

We consider the dynamics of a thin rigid block mounted on a horizontally oscillating rigid table and impacting both the table and nearby containing walls. We carry out a detailed analysis of certain symmetric block responses and present specific examples of other types of solutions, found through numerical experimentation. In addition a conjecture by the present author is verified.     

General Results on the Convergence of Multipoint Hermite-Pade Approximants of Nikishin Systems

We consider simultaneous approximation of Nikishin systems of functions by means of rational vector functions which are constructed interpolating along a prescribed table of points. We give general conditions for the uniform convergence of such approximants with a geometric rate under very weak assumptions.     

Generalized table algebras

A table algebra was defined in [1] in order to consider in a uniform way the common properties of conjugacy classes and irreducible characters. Non-commutative table algebras were introduced in [5]. They generalize properties of such well-known objects as coherent and Hecke algebras. Here we extend the main definition of a non-commutative table algebra by letting the ground field be an integral domain. We call these algebrasgeneralized table algebras (GT-algebras, in brief). It is worth mentioning that this class of algebras includes generic Hecke-Iwahori algebras of finite Coxeter groups. We develop the general theory for this type of algebras which includes their representation theory and theory of closed subsets. We also study the properties of primitive integral table algebras. This research was done at the Gelbart and Minerva Foundations through the Emmy Noether Research Institute for Mathematical Science at Bar-Ilan University. The authors wish to thank these institutions for their support. This author was partially supported by the Israeli Ministry of Absorption.     

Hash table reorganization

We consider the operation of permuting in place the records of an open address hash table in order to correspond to a different hashing function. Our emphasis is primarily on minimizing the amount of work space used. Lower and upper bounds are derived on the unrestricted problem, that is, without making any assumptions about the probing discipline used. For the special case of linear probing, we give an algorithm which, in practice, requires no work space outside the table and which runs in linear time with respect to the table size.     

On Some Techniques for Streaming Data: A Case Study of Internet Packet Headers

We consider the implications of streaming data for data analysis and data mining. Streaming data are becoming widely available from a variety of sources. In our case we consider the implications arising from Internet traffic data. By implication, streaming data are unlikely to be time homogeneous so that standard statistical and data mining procedures do not necessarily apply. Because it is essentially impossible to store streaming data, we consider recursive algorithms, algorithms which are adaptive and discount the past and also algorithms that create finite pseudo-samples. We also suggest some evolutionary graphics procedures that are suitable for streaming data. We begin our discussion with a discussion of Internet traffic in order to give the reader some sense of the time and data scale and visual resolution needed for such problems.     

一种构造连生状态生命表的简单易行方法:方法和理论(英文)

在多生命模型中,几乎所有精算学教科书都假设被保险人的剩余寿命之间相互独立.本文中我们研究两生命模型.我们认为剩余寿命是正相依的,并用正象限相依描述相依性,给出了一种简单方法构造联合生命表.     

Bounds on codes over an alphabet of five elements

We consider the problem of finding bounds and exact values of A₅(n,d) — the maximum size of a code of length n and minimum distance d over an alphabet of 5 elements. Using a wide variety of constructions and methods, a table of bounds on A₅(n,d) for n11 is obtained.     

Characters of Association Schemes and Normal Closed Subsets

We consider characters of association schemes. We define a kernel like subset for a character. It is a generalization of the kernel of a group character, but it need not be normal. We give a necessary and sufficient condition for it to be normal. Using this condition, we can read all normal closed subsets from the character table. Acknowledgments.The author would like to thank Dr. Mitsugu Hirasaka for valuable conversations about character theory of association schemes.     

A Sparse Singular Value Decomposition Method for High-Dimensional Data

We present a new computational approach to approximating a large, noisy data table by a low-rank matrix with sparse singular vectors. The approximation is obtained from thresholded subspace iterations that produce the singular vectors simultaneously, rather than successively as in competing proposals. We introduce novel ways to estimate thresholding parameters, which obviate the need for computationally expensive cross-validation. We also introduce a way to sparsely initialize the algorithm for computational savings that allow our algorithm to outperform the vanilla singular value decomposition (SVD) on the full data table when the signal is sparse. A comparison with two existing sparse SVD methods suggests that our algorithm is computationally always faster and statistically always at least comparable to the better of the two competing algorithms. Supplementary materials for the article are available in an online appendix. An R package ssvd implementing the algorithms introduced in this article is available on CRAN.     

Nonlinear inversion of a band-limited Fourier transform

We consider the problem of reconstructing a compactly supported function with singularities either from values of its Fourier transform available only in a bounded interval or from a limited number of its Fourier coefficients. Our results are based on several observations and algorithms in [G. Beylkin, L. Monzón, On approximation of functions by exponential sums, Appl. Comput. Harmon. Anal. 19 (1) (2005) 17–48]. We avoid both the Gibbs phenomenon and the use of windows or filtering by constructing approximations to the available Fourier data via a short sum of decaying exponentials. Using these exponentials, we extrapolate the Fourier data to the whole real line and, on taking the inverse Fourier transform, obtain an efficient rational representation in the spatial domain. An important feature of this rational representation is that the positions of its poles indicate location of singularities of the function. We consider these representations in the absence of noise and discuss the impact of adding white noise to the Fourier data. We also compare our results with those obtained by other techniques. As an example of application, we consider our approach in the context of the kernel polynomial method for estimating density of states (eigenvalues) of Hermitian operators. We briefly consider the related problem of approximation by rational functions and provide numerical examples using our approach.     

An integer programming approach to the time slot assignment problem in SS/TDMA systems with intersatellite links

We consider the time slot assignment problem (TSAP) in a cluster of satellite-switched time-division multiple-access (SS/TDMA) satellite system with intersatellite links (ISL). The problem is known to be NP-complete. In this paper, we consider TSAP as a graph coloring problem on a bipartite multigraph which is constructed from the traffic requirements. We give an integer programming (IP) model for TSAP and propose an algorithm based on the column generation technique. Computational results using randomly generated data are reported.     

On a Differential Model for Growing Sandpiles with Non-Regular Sources

We consider a variational model that describes the growth of a sandpile on a bounded table under the action of a vertical source. The possible equilibria of such a model solves a boundary value problem for a system of nonlinear partial differential equations that we analyze when the source term is merely integrable. In addition, we study the asymptotic behavior of the dynamical problem showing that the solution converges asymptotically to an equilibrium that we characterize explicitly.     

Mixed-integer programming approaches for index tracking and enhanced indexation

We consider the problem of reproducing the performance of a stock market index, but without purchasing all of the stocks that make up the index, index tracking. We also consider the problem of out-performing the index, enhanced indexation. We present mixed-integer linear programming formulations of these problems. Our formulations include transaction costs, a constraint limiting the number of stocks that can be purchased and a limit on the total transaction cost that can be incurred. As our formulations of these problems are mixed-integer linear programs we can use a standard solver (Cplex). Numeric results are presented for eight data sets drawn from major markets. The largest of these data sets involves over 2000 stocks.     

On the upper embedding of symmetric configurations with block size 3

We consider the problem of embedding a symmetric configuration with block size 3 in an orientable surface in such a way that the blocks of the configuration form triangular faces and there is only one extra large face. We develop a sufficient condition for such an embedding to exist given any orientation of the configuration, and show that this condition is satisfied for all configurations on up to 19 points. We also show that there exists a configuration on 21 points which is not embeddable in any orientation. As a by-product, we give a revised table of numbers of configurations, correcting the published figure for 19 points. We give a number of open questions about embeddability of configurations on larger numbers of points.