Interpolation that leads to the narrowest intervals and its application to expert systems and intelligent control

In many real-life situations, we want to reconstruct the dependencyy=f(x ₁,…, x_n) from the known experimental resultsx _i ^(k) , y^(k). In other words, we want tointerpolate the functionf from its known valuesy ^(k)=f(x ₁ ^(k) ,…, x _n ^(k) ) in finitely many points $\bar x^{(k)} = (x_1^{(k)} , \ldots ,x_n^{(k)} )$ , 1≤k≤N There are many functions that go through given points. How to choose one of them? The main goal of findingf is to be able to predicty based onx _i. If we getx _i from measurements, then usually, we only getintervals that containx _i. As a result of applyingf, we get an interval y of possible values ofy. It is reasonable to choosef for which the resulting interval is the narrowest possible. In this paper, we formulate this choice problem in mathematical terms, solve the corresponding problem for several simple cases, and describe the application of these solutions to intelligent control.     

Choosing,Agreeing, and Eliminating in Communication Complexity

We consider several questions inspired by the direct-sum problem in (two-party) communication complexity. In all questions, there are k fixed Boolean functions f ₁,…,f _k and each of Alice and Bob has k inputs, x ₁,…,x _k and y ₁,…,y _k , respectively. In the eliminate problem, Alice and Bob should output a vector σ₁,…,σ _k such that f _i (x _i , y _i ) ≠ σ _i for at least one i (i.e., their goal is to eliminate one of the 2 ^k output vectors); in the choose problem, Alice and Bob should return (i, f _i (x _i , y _i )), for some i (i.e., they choose one instance to solve), and in the agree problem they should return f _i (x _i , y _i ), for some i (i.e., if all the k Boolean values agree then this must be the output). The question, in each of the three cases, is whether one can do better than solving one (say, the first) instance. We study these three problems and prove various positive and negative results. In particular, we prove that the randomized communication complexity of eliminate, of k instances of the same function f, is characterized by the randomized communication complexity of solving one instance of f.     

A note on a problem on ω-limit sets of N–dimensional skew-product maps

In 2003, Balibrea et al. stated the problem of finding a skew-product map G on 𝕀³ holding ω _G ={0}×𝕀²=ω _G (x, y, z) for any (x, y, z)∈𝕀³, x≠0. We present a method for constructing skew-product maps F on 𝕀 ⁿ⁺¹ holding ω _F ={0}×𝕀 ⁿ =ω _F (x ₁, x ₂, …, x _n+1), (x ₁, x ₂, …, x _n+1)∈𝕀 ⁿ⁺¹, x ₁≠0.     

Fast modular exponentiation of large numbers with large exponents

In many problems, modular exponentiation |x^b|_m is a basic computation, often responsible for the overall time performance, as in some cryptosystems, since its implementation requires a large number of multiplications.It is known that |x^b|_m=|x^|b|_(m)|_m for any x in [1,m−1] if m is prime; in this case the number of multiplications depends on (m) instead of depending on b. It was also stated that previous relation holds in the case m=pq, with p and q prime; this case occurs in the RSA method.In this paper it is proved that such a relation holds in general for any x in [1,m−1] when m is a product of any number n of distinct primes and that it does not hold in the other cases for the whole range [1,m−1].Moreover, a general method is given to compute |x^b|_m without any hypothesis on m, for any x in [1,m−1], with a number of modular multiplications not exceeding those required when m is a product of primes.Next, it is shown that representing x in a residue number system (RNS) with proper moduli m_i allows to compute |x^b|_m by n modular exponentiations |x_i^b|_mi in parallel and, in turn, to replace b by |b|_(mi) in the worst case, thus executing a very low number of multiplications, namely log₂m_i for each residue digit.A general architecture is also proposed and evaluated, as a possible implementation of the proposed method for the modular exponentiation.     

Optimizing a damped system – a case study

We consider a second-order damped-vibrational system described by the equation M ?+C(v) [xdot]+K x=0, where M, C(v), K are real, symmetric matrices of order n. We assume that the undamped eigenfrequencies (eigenvalues of (λ² M+K) x=0) ω₁, ω₂, …, ω _n , are multiple in the sense that ω₁=ω₂, ω₃=ω₄, …, ω _n?1=ω _n , or are given in close pairs ω₁ ≈ ω₂, ω₃ ≈ ω₄, …, ω _n?1 ≈ ω _n . We present a formula which gives the solution of the corresponding phase space Lyapunov equation, which then allows us to calculate the first and second derivatives of the trace of the solution, with no extra cost. It can serve for the efficient trace minimization.     

Synthesising cluster operators

Let Γ_i ? R^m denote pattern classes with means γ_i and covariances R_i, i = 1, …, l respectively. The set {ψ_i} ? R^k denotes signatures for the pattern classes. A function f : R^m → R^k is said to be a cluster function provided (i) f (γ_i) = ψ_i, i = 1, …, l and (ii) f minimizes a dispersion functional. This paper develops a complete theory for realization of polynomic cluster functions, including the linear case.     

Checking If There Exists a Monotonic Function That Is Consistent with the Measurements: An Efficient Algorithm

In many problems in science and engineering ranging from astrophysics to geosciences to financial analysis, we know that a physical quantity y depends on the physical quantity x, i.e., y = f(x) for some function f(x), and we want to check whether this dependence is monotonic. Specifically, finitely many measurements of x_i and y = f(x) have been made, and we want to check whether the results of these measurements are consistent with the monotonicity of f(x). An efficient parallelizable algorithm is known for solving this problem when the values x_i are known precisely, while the values y_i are known with interval uncertainty. In this paper, we extend this algorithm to a more general (and more realistic) situation when both x_i and y_i are known with interval uncertainty.     

Empirical Bayes estimation of the scale parameter in a Pareto distribution

Let f(xθ) = αθ^αx^−(α+1)I(x>θ) be the pdf of a Pareto distribution with known shape parameter α>0, and unknown scale parameter θ. Let {(X_i, θ_i)} be a sequence of independent random pairs, where X_i's are independent with pdf f(xα_i), and θ_i are iid according to an unknown distribution G in a class of distributions whose supports are included in an interval (0, m), where m is a positive finite number. Under some assumption on the class and squared error loss, at (n + 1)th stage we construct a sequence of empirical Bayes estimators of θ_n+1 based on the past n independent observations X₁,…, X_n and the present observation X_n+1. This empirical Bayes estimator is shown to be asymptotically optimal with rate of convergence O(n^−1/2). It is also exhibited that this convergence rate cannot be improved beyond n^−1/2 for the priors in class .     

RELION—time-sub-optimal variable structure control law

RELION is an abbreviation for the relay-linear control law. It as a double structure—relay and linear—and it is a modification of the constructive time-sub-optimal control law, u = sgn(p_Mx + sgn(p_M-1 + … + sgn(p₂x + sgnp_ix)…)). For determining the RELION it is necessary to calculate the n-vectors p₁,… p_m and to evaluate the factor K of the linear control law u = K_p1x. Two algorithms for calculating these parameters are presented.     

Communication Complexity of Sum-Type Functions Invariant under Translation

The communication complexity of a function f denotes the number of bits that two processors have to exchange in order to compute f(x, y), when each processor knows one of the variables x and y, respectively. In this paper the deterministic communication complexity of sum-type functions, such as the Hamming distance and the Lee distance, is examined. Here f: X × X → G, where X is a finite set and G is an Abelian group, and the sum-type function f_n:Xⁿ × Xⁿ → G is defined by f_n((x₁, ..., x_n), (y₁, ..., y_n)) = Σⁿ_i=1f(x_i, y_i) Since the functions examined are also translation-invariant, their function matrices are simultaneously diagonalizable and the corresponding eigenvalues can be calculated. This allows to apply a rank lower bound for the communication complexity. The best results are obtained for G = /2 . For prime numbers |X| in this case the communication complexity of all non-trivial sum-type functions is determined exactly. Exact results are also obtained for the parity of the Hamming distance and the parity of the Lee distance. For the Hamming distance and the Lee distance exact results are only obtained for special parameters n and |X|.     

Lower Bounds for the Determinantal Complexity of Explicit Low Degree Polynomials

The determinantal complexity of a polynomial f(x ₁,x ₂,…,x _n ) is the minimum m such that f=det  _m (L(x ₁,x ₂,…,x _n )), where L(x ₁,x ₂,…,x _n ) is a matrix whose entries are affine forms in the x _i s over some field $\mbox {$\mbox {.     

Why clustering in function approximation? Theoretical explanation

Function approximation is a very important practical problem: in many practical applications, we know the exact form of the functional dependence y=f(x₁,…,x_n) between physical quantities, but this exact dependence is complicated, so we need a lot of computer space to store it, and a lot of time to process it, i.e., to predict y from the given x_i. It is therefore necessary to find a simpler approximate expression g(x₁,…,x_n)≈f(x₁,…,x_n) for this same dependence. This problem has been analyzed in numerical mathematics for several centuries, and it is, therefore, one of the most thoroughly analyzed problems of applied mathematics. There are many results related to approximation by polynomials, trigonometric polynomials, splines of different type, etc. Since this problem has been analyzed for so long, no wonder that for many reasonable formulations of the optimality criteria, the corresponding problems of finding the optimal approximations have already been solved. Lately, however, new clustering‐related techniques have been applied to solve this problem (by Yager, Filev, Chu, and others). At first glance, since for most traditional optimality criteria, optimal approximations are already known, the clustering approach can only lead to non‐optimal approximations, i.e., approximations of inferior quality. We show, however, that there exist new reasonable criteria with respect to which clustering‐based function approximation is indeed the optimal method of function approximation. © 2000 John Wiley & Sons, Inc.     

One-way functions and circuit complexity

A finite function f is a mapping of {0, 1}ⁿ into {0, 1}^m{#}, where “#” is a symbol to be thought of as “undefined.” A family of finite functions is said to be one-way (in a circuit complexity sense) if it can be computed with polynomial-size circuits, but every family of inverses of these functions cannot. In this paper we show that, provided functions that are not one-to-one are allowed, one-way functions exist if and only if the satisfiability problem SAT does not have polynomial-size circuits. A family of functions f_i(x) can be checked if some family of polynomial-size circuits with inputs x and y can determine if f_i(x) = y. A family of functions f_i(x) can be evaluated if some family of polynomial-size circuits with input x can compute f_i(x). Can all families of total functions that can be checked also be evaluated? We show that this is true if and only if the nonuniform versions of the complexity classes P and UP co-UP are equal. A family of functions f_i is one-way for constant depth circuits if f_i can be computed with unbounded famin circuits of polynomial size and constant depth, but every family of inverses f_i⁻¹ cannot. We give two provably one-way functions (in fact permutaions) for constant-depth circuits. The second example has the stronger property that no bit of its inverse can be computed in polynomial size and constant depth.     

Methods for optimization of nonlinear problems with discrete variables: A review

The methods for discrete-integer-continuous variable nonlinear optimization are reviewed. They are classified into the following six categories: branch and bound, simulated annealing, sequential linearization, penalty functions, Lagrangian relaxation, and other methods. Basic ideas of each method are described and details of some of the algorithms are given. They are transcribed into a step-by-step format for easy implementation into a computer. Under other methods, rounding-off, heuristic, cutting-plane, pure discrete, and genetic algorithms are described. For nonlinear problems, none of the methods are guaranteed to produce the global minimizer; however, good practical solutions can be obtained.Notation BBM branch and bound method - D set of discrete values for all the discrete variables - D _i set of discrete values for thei-th variable - d _ij j-th discrete value for thei-th variable - f cost function to be minimized - f ^* upper bound for the cost function - g _i i-th constraint function - IP integer programming - ILP integer linear programming - L Lagrangian - LP linear programming - m total number of constraints - MDLP mixed-discrete linear programming - MDNLP mixed-discrete nonlinear programming - n _d number of discrete variables - NLP nonlinear programming - p number of equality constraints; acceptance probability used in simulated annealing - q _i number of discrete values for thei-th variable - SLP sequential linear programming - SQP sequential quadratic programming - x design variable vector of dimension n - x _iL smallest allowed value for thei-th variable - x _iU largest allowed value for thei-th variable - the gradient operator     

Interpolazione con splines verificanti una opportuna condizione

Summary A partition of the interval [x ₀,x _n+1] inton+1 subintervals [x _i ,x _i+1] (i=0,1,...,n) is considered. A spline functionf(x)∈C ^m , which coincides with a polynomialp _i (x)[p _i (x _i )=y _i ,p _i (x _i+1)=y _i+1] of degreem+1 in [x _i ,x _i+1 ], is introduced. Such a spline depends onm arbitrary constants. These constants are determined minimizing the integral .      

Diagonal polynomials for small dimensions

HereR andN denote respectively the real numbers and the nonnegative integers. Also 0 <n εN, ands(x) =x ₁+...+x _n when x = (x ₁,...,x _n) εR ⁿ. Adiagonal function of dimensionn is a mapf onN ⁿ (or any larger set) that takesN ⁿ bijectively ontoN and, for all x, y inN ⁿ, hasf(x) <f(y) whenevers(x) <s(y). We show that diagonalpolynomials f of dimensionn all have total degreen and have the same terms of that degree, so that the lower-degree terms characterize any suchf. We call two polynomialsequivalent if relabeling variables makes them identical. Then, up to equivalence, dimension two admits just one diagonal polynomial, and dimension three admits just two.     

An enlarged family of packing polynomials on multidimensional lattices

HereN = {0, 1, 2, ...}, while a functionf onN ^m or a larger domain is apacking function if its restrictionf|N ^m is a bijection ontoN. (Packing functions generalize Cantor's [1]pairing polynomials, and yield multidimensional-array storage schemes.) We call two functionsequivalent if permuting arguments makes them equal. Alsos(x) =x ₁ + ... +x _m when x = (x ₁,...,x _m); and such anf is adiagonal mapping iff(x) <f(y) whenever x, y εN ^m ands(x) <s(y). Lew [7] composed Skolem's [14], [15] diagonal packing polynomials (essentially one for eachm) to constructc(m) inequivalent nondiagonal packing polynomials on eachN ^m. For eachm > 1 we now construct 2^m−2 inequivalent diagonal packing polynomials. Then, extending the tree arguments of the prior work, we obtaind(m) inequivalent nondiagonal packing polynomials, whered(m)/c(m) → ∞ asm → ∞. Among these we count the polynomials of extremal degree.