Parameter estimation under ambiguity and contamination with the spurious model

Recently, we proposed variants as a statistical model for treating ambiguity. If data are extracted from an object with a machine then it might not be able to give a unique safe answer due to ambiguity about the correct interpretation of the object. On the other hand, the machine is often able to produce a finite number of alternative feature sets (of the same object) that contain the desired one. We call these feature sets variants of the object. Data sets that contain variants may be analyzed by means of statistical methods and all chapters of multivariate analysis can be seen in the light of variants. In this communication, we focus on point estimation in the presence of variants and outliers. Besides robust parameter estimation, this task requires also selecting the regular objects and their valid feature sets (regular variants). We determine the mixed MAP-ML estimator for a model with spurious variants and outliers as well as estimators based on the integrated likelihood. We also prove asymptotic results which show that the estimators are nearly consistent.The problem of variant selection turns out to be computationally hard; therefore, we also design algorithms for efficient approximation. We finally demonstrate their efficacy with a simulated data set and a real data set from genetics.     

Polynomial identity rings as rings of functions

We generalize the usual relationship between irreducible Zariski closed subsets of the affine space, their defining ideals, coordinate rings, and function fields, to a non-commutative setting, where “varieties” carry a PGL_n-action, regular and rational “functions” on them are matrix-valued, “coordinate rings” are prime polynomial identity algebras, and “function fields” are central simple algebras of degree n. In particular, a prime polynomial identity algebra of degree n is finitely generated if and only if it arises as the “coordinate ring” of a “variety” in this setting. For n=1 our definitions and results reduce to those of classical affine algebraic geometry.     

Subregular Spreads of (2n+1,q)

In this paper, we develop some of the theory of spreads of projective spaces with an eye towards generalizing the results of R. H. Bruck (1969,in“Combinatorial Mathematics and Its Applications,” Chap. 27, pp. 426–514, Univ. of North Carolina Press, Chapel Hill). In particular, we wish to generalize the notion of asubregularspread to the higher dimensional case. Most of the theory here was anticipated by Bruck in later papers; however, he never provided a detailed formulation. We fill this gap here by developing the connections between a regular spread of (2n+1)-dimensional projective space and ann-dimensional circle geometry, which is the appropriate generalization of the Miquelian inversive plane. After developing this theory, we provide a fairly general method for constructing subregular spreads of (5,q). Finally, we explore a special case of this construction, which yields several examples of three-dimensional subregular translation planes which are not André planes.     

Negation of binomial coefficients

We extend the concept of a binomial coefficient to all integer values of its parameters. Our approach is purely algebraic, but we show that it is equivalent to the evaluation of binomial coefficients by means of the Γ-function. In particular, we prove that the traditional rule of “negation” is wrong and should be substituted by a slightly more complex rule. We also show that the “cross product” rule remains valid for the extended definition.     

Borel extractions of converging sequences in compact sets of Borel functions

It is well known by a classical result of Bourgain–Fremlin–Talagrand that if K is a pointwise compact set of Borel functions on a Polish space then given any cluster point f of a sequence (f_n)_nω in K one can extract a subsequence (f_nk)_kω converging to f. In the present work we prove that this extraction can be achieved in a “Borel way.” This will prove in particular that the notion of analytic subspace of a separable Rosenthal compacta is absolute and does not depend on the particular choice of a dense sequence.     

Existence of nonstationary bubbles in higher dimensions

We are interested in the existence of travelling-waves for the nonlinear Schrödinger equation in R^N with “ψ³−ψ⁵”-type nonlinearity. First, we prove an abstract result in critical point theory (a local variant of the classical saddle-point theorem). Using this result, we get the existence of travelling-waves moving with sufficiently small velocity in space dimension N4.     

Middle diamond

Under certain cardinal arithmetic assumptions, we prove that for every large enough regular λ cardinal, for many regular κ < λ, many stationary subsets of λ concentrating on cofinality κ has the “middle diamond”. In particular, we have the middle diamond on {δ < λ: cf(δ) = κ}. This is a strong negation of uniformization.I would like to thank Alice Leonhardt for the beautiful typing. This research was partially supported by the Israel Science Foundation. Publication 775.     

Solution of the Ulam Stability Problem for Euler–Lagrange Quadratic Mappings

In 1940 S. M. Ulam proposed at the University of Wisconsin theproblem: “Give conditions in order for a linear mapping near an approximately linear mapping to exist.” In 1968 S. U. Ulam proposed the moregeneral problem: “When is it true that by changing a little the hypotheses of a theorem one can still assert that the thesis of the theorem remains true or approximately true?” In 1978 P. M. Gruber proposed theUlam type problem: “Suppose a mathematical object satisfies a certain property approximately. Is it then possible to approximate this object by objects, satisfying the property exactly?” According to P. M. Gruber this kind of stability problems is of particular interest in probability theory and in the case of functional equations of different types. In 1982–1996 we solved the above Ulam problem, or equivalently the Ulam type problem for linear mappings and established analogous stability problems. In this paper we first introduce newquadratic weighted meansandfundamental functional equationsand then solve theUlam stability problemfornon-linear Euler–Lagrange quadratic mappingsQ:X → Y, satisfying a mean equation and functional equation[formula]for all 2-dimensional vectors (x₁, x₂) X², withXa normed linear space (Y a real complete normed linear space), and any fixed pair (a₁, a₂) of realsa_iand any fixed pair (m₁, m₂) of positive realsm_i(i = 1, 2), [formula]     

Best Interpolatory Approximation in Normed Linear Spaces

A theory of best approximation with interpolatory contraints from a finite-dimensional subspaceMof a normed linear spaceXis developed. In particular, to eachxX, best approximations are sought from a subsetM(x) ofMwhichdependson the elementxbeing approximated. It is shown that this “parametric approximation” problem can be essentially reduced to the “usual” one involving a certainfixedsubspaceM₀ofM. More detailed results can be obtained when (1) Xis a Hilbert space, or (2) Mis an “interpolating subspace” ofX(in the sense of [1]).     

Reverse mathematics and well-ordering principles: A pilot study

The larger project broached here is to look at the generally sentence “if X is well-ordered then f(X) is well-ordered”, where f is a standard proof-theoretic function from ordinals to ordinals. It has turned out that a statement of this form is often equivalent to the existence of countable coded ω-models for a particular theory T_f whose consistency can be proved by means of a cut elimination theorem in infinitary logic which crucially involves the function f. To illustrate this theme, we prove in this paper that the statement “if X is well-ordered then ε_X is well-ordered” is equivalent to . This was first proved by Marcone and Montalban [Alberto Marcone, Antonio Montalbán, The epsilon function for computability theorists, draft, 2007] using recursion-theoretic and combinatorial methods. The proof given here is principally proof-theoretic, the main techniques being Schütte’s method of proof search (deduction chains) [Kurt Schütte, Proof Theory, Springer-Verlag, Berlin, Heidelberg, 1977] and cut elimination for a (small) fragment of .     

On the Spectra of Certain Graphs Arising from Finite Fields

Cayley graphs on a subgroup ofGL(3,p),p>3 a prime, are defined and their properties, particularly their spectra, studied. It is shown that these graphs are connected, vertex-transitive, nonbipartite, and regular, and their degrees are computed. The eigenvalues of the corresponding adjacency matrices depend on the representations of the group of vertices. The “1-dimensional” eigenvalues can be completely described, while a portion of the “higher dimensional” eigenfunctions are discrete analogs of Bessel functions. A particular subset of these graphs is conjectured to be Ramanujan and this is verified for over 2000 graphs. These graphs follow a construction used by Terras on a subgroup ofGL(2,p). This method can be extended further to construct graphs using a subgroup ofGL(n, p) forn≥4. The 1-dimensional eigenvalues in this case can be expressed in terms of the 1-dimensional eigenvalues of graphs fromGL(2,p) andGL(3,p); this part of the spectra alone is sufficient to show that forn≥4, the graphs fromGL(n, p) are not in general Ramanujan.     

Fuzzy Relation Equations for Compression/Decompression Processes of Colour Images in the RGB and YUV Colour Spaces

We use particular fuzzy relation equations for compression/decompression of colour images in the RGB and YUV spaces, by comparing the results of the reconstructed images obtained in both cases. Our tests are made over well known images of 256×256 pixels (8 bits per pixel in each band) extracted from Corel Gallery. After the decomposition of each image in the three bands of the RGB and YUV colour spaces, the compression is performed using fuzzy relation equations of “min - →_t” type, where “t” is the Lukasiewicz t-norm and “→_t” is its residuum. Any image is subdivided in blocks and each block is compressed by optimizing a parameter inserted in the Gaussian membership functions of the fuzzy sets, used as coders in the fuzzy equations. The decompression process is realized via a fuzzy relation equation of max-t type. In both RGB and YUV spaces we evaluate and compare the root means square error (RMSE) and the consequentpeak signal to noise ratio (PSNR) on the decompressed images with respect to the original image under several compression rates.     

Maximizing Queueing Network Utility Subject to Stability: Greedy Primal-Dual Algorithm

We study a model of controlled queueing network, which operates and makes control decisions in discrete time. An underlying random network mode determines the set of available controls in each time slot. Each control decision “produces” a certain vector of “commodities”; it also has associated “traditional” queueing control effect, i.e., it determines traffic (customer) arrival rates, service rates at the nodes, and random routing of processed customers among the nodes. The problem is to find a dynamic control strategy which maximizes a concave utility function H(X), where X is the average value of commodity vector, subject to the constraint that network queues remain stable.We introduce a dynamic control algorithm, which we call Greedy Primal-Dual (GPD) algorithm, and prove its asymptotic optimality. We show that our network model and GPD algorithm accommodate a wide range of applications. As one example, we consider the problem of congestion control of networks where both traffic sources and network processing nodes may be randomly time-varying and interdependent. We also discuss a variety of resource allocation problems in wireless networks, which in particular involve average power consumption constraints and/or optimization, as well as traffic rate constraints.     

Wave atoms and sparsity of oscillatory patterns

We introduce “wave atoms” as a variant of 2D wavelet packets obeying the parabolic scaling wavelength(diameter)². We prove that warped oscillatory functions, a toy model for texture, have a significantly sparser expansion in wave atoms than in other fixed standard representations like wavelets, Gabor atoms, or curvelets. We propose a novel algorithm for a tight frame of wave atoms with redundancy two, directly in the frequency plane, by the “wrapping” technique. We also propose variants of the basic transform for applications in image processing, including an orthonormal basis, and a shift-invariant tight frame with redundancy four. Sparsity and denoising experiments on both seismic and fingerprint images demonstrate the potential of the tool introduced.     

A unifying look at the Apostolico–Giancarlo string-matching algorithm

String matching is the problem of finding all the occurrences of a pattern in a text. We present a new method to compute the combinatorial shift function (“matching shift”) of the well-known Boyer–Moore string matching algorithm. This method implies the computation of the length of the longest suffixes of the pattern ending at each position in this pattern. These values constituted an extra-preprocessing for a variant of the Boyer–Moore algorithm designed by Apostolico and Giancarlo. We give here a new presentation of this algorithm that avoids extra preprocessing together with a tight bound of 1.5n character comparisons (where n is the length of the text).     

A general framework of compactly supported splines and wavelets

Let {V_k} be a nested sequence of closed subspaces that constitute a multiresolution analysis of L²( ). We characterize the family Φ = {φ} where each φ generates this multiresolution analysis such that the two-scale relation of φ is governed by a finite sequence. In particular, we identify the ε Φ that has minimum support. We also characterize the collection Ψ of functions η such that each η generates the orthogonal complementary subspaces W_k of V_k, . In particular, the minimally supported ψ ε Ψ is determined. Hence, the “B-spline” and “B-wavelet” pair (, ψ) provides the most economical and computational efficient “spline” representations and “wavelet” decompositions of L² functions from the “spline” spaces V_k and “wavelet” spaces W_k, k . A very general duality principle, which yields the dual bases of both {(·−j):j and {η(·−j):j } for any η ε Ψ by essentially interchanging the pair of two-scale sequences with the pair of decomposition sequences, is also established. For many filtering applications, it is very important to select a multiresolution for which both and ψ have linear phases. Hence, “non-symmetric” and ψ, such as the compactly supported orthogonal ones introduced by Daubechies, are sometimes undesirable for these applications. Conditions on linear-phase φ and ψ are established in this paper. In particular, even-order polynomial B-splines and B-wavelets φ_m and ψ_m have linear phases, but the odd-order B-wavelet only has generalized linear phases.     

Diagnosability of regular systems

A novel approach aimed at evaluating the diagnosability of regular systems under the PMC model is introduced. The diagnosability is defined as the ability to provide a correct diagnosis, although possibly incomplete. This concept is somehow intermediate between one-step diagnosability and sequential diagnosability. A lower bound to diagnosability is determined by lower bounding the minimum of a “syndrome-dependent” bound t_σ over the set of all the admissible syndromes. In turn, t_σ is determined by evaluating the cardinality of the smallest consistent fault set containing an aggregate of maximum cardinality. The new approach, which applies to any regular system, relies on the “edge-isoperimetric inequalities” of connected components of units declaring each other non-faulty. This approach has been used to derive tight lower bounds to the diagnosability of toroidal grids and hypercubes, which improve the existing bounds for the same structures.     

Polynomial growth rates

We consider linear equations v^′=A(t)v with a polynomial asymptotic behavior, that can be stable, unstable and central. We show that this behavior is exhibited by a large class of differential equations, by giving necessary and sufficient conditions in terms of generalized “polynomial” Lyapunov exponents for the existence of polynomial behavior. In particular, any linear equation in block form in a finite-dimensional space, with three blocks having “polynomial” Lyapunov exponents respectively negative, positive, and zero, has a nonuniform version of polynomial trichotomy, which corresponds to the usual notion of trichotomy but now with polynomial growth rates. We also obtain sharp bounds for the constants in the notion of polynomial trichotomy. In addition, we establish the persistence under sufficiently small nonlinear perturbations of the stability of a nonuniform polynomial contraction.     

Pseudorandom numbers and entropy conditions

We investigate measures of pseudorandomness of finite sequences (x_n) of real numbers. Mauduit and Sárközy introduced the “well-distribution measure”, depending on the behavior of the sequence (x_n) along arithmetic subsequences (x_ak+b). We extend this definition by replacing the class of arithmetic progressions by an arbitrary class of sequences of positive integers and show that the so obtained measure is closely related to the metric entropy of the class . Using standard probabilistic techniques, this fact enables us to give precise bounds for the pseudorandomness measure of classical constructions. In particular, we will be interested in “truly” random sequences and sequences of the form {n_kω}, where {·} denotes fractional part, (n_k) is a given sequence of integers and ω[0,1).