Limiting optimal discounted-cost control of a class of time-varying stochastic systems

We consider a class of time-varying -valued control models, and with possibly unbounded costs. The processes evolve according to the system equation x_n+1=G_n(x_n,a_n)+ξ_n ( ), where {ξ_n} are i.i.d. random vectors and {G_n} a sequence of known functions converging to some function G_∞. Under suitable hypotheses, we show the existence of an α-discount optimal policy for the limiting system x_n+1=G_∞(x_n,a_n)+ξ_n.     

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.     

A class of hybrid collocation methods for third-order ordinary differential equations

A class of numerical methods is proposed for solving general third-order ordinary differential equations directly by collocation at the grid points x = x _n+j , i = 0(1)k and at an off grid point x = x _n+u , where k is the step number of the method and u is an arbitrary rational number in (x _n , x _n+k ). A predictor of order 2k ? 1 is also proposed to cater for y _n+k in the main method. Taylor series expansion is employed for the calculation of y _n+1, y _n+2, y _n+u and their higher derivatives. Evaluation of the resulting method at x = x _n+k for any value of u in the specified open interval yields a particular discrete scheme as a special case of the method. The efficiency of the method is tested on some general initial value problems of third-order ordinary differential equations.     

Automating Pólya Theory: The Computational Complexity of the Cycle Index Polynomial

In this paper we investigate the computational difficulty of evaluating and approximately evaluating Pólya′s cycle index polynomial. We start by investigating the difficulty of determining a particular coefficient of the cycle index polynomial. In particular, we consider the following problem, in which i is taken to be a fixed positive integer: Given a set of generators for a permutation group G whose degree, n, is a multiple of i, determine the coefficient of x^n/i_i in the cycle index polynomial of G. We show that this problem is #P-hard for every fixed i >1. Next, we consider the evaluation problem. Let y₁, y₂, ... stand for an arbitrary fixed sequence of non-negative real numbers. The cycle index evaluation problem that is associated with this sequence is the following: Given a set of generators for a degree n permutation group G, evaluate the cycle index polynomial of G at the point (y₁, ..., y_n). We show that if there exists an i such that y_i ≠ yⁱ₁ and y_i ≠ 0 then the evaluation problem associated with y₁, y₂, ..., is #P-hard. We observe that the evaluation problem is solvable in polynomial time if y_j = y^j₁ for every positive integer j and that it is solvable in polynomial time if y_j = 0 for every integer j >1. Finally, we consider the approximate evaluation problem. We show that it is NP-hard to approximately solve the evaluation problem if there exists an i such that y_i > yⁱ₁. Furthermore, we show that it is NP-hard to approximately solve the evaluation problem if y₁ = y₂ = ··· = y for some positive non-integer y. We derive some corollaries of our results which deal with the computational difficulty of counting equivalence classes of combinatorial structures.     

Most Sequences Are Stochastic

The central problem in machine learning (and statistics) is the problem of predicting future events x_n+1 based on past observations x₁x₂…x_n, where n=1, 2…. The main goal is to find a method of prediction that minimizes the total loss suffered on a sequence x₁x₂…x_n+1 for n=1, 2…. We say that a data sequence is stochastic if there exists a simply described prediction algorithm whose performance is close to the best possible one. This optimal performance is defined in terms of Vovk's predictive complexity, which is a generalization of the notion of Kolmogorov complexity. Predictive complexity gives a limit on the predictive performance of simply described prediction algorithms. In this paper we argue that data sequences normally occurring in the real world are stochastic; more formally, we prove that Levin's a priori semimeasure of nonstochastic sequences is small.     

Langford strings are square-free

Given a set V _n ={v1, …v _n } of n symbols, a sequence x = x1x2…x _m is called a weak Langford string if x, ? Vn for 1≦i≦m, and any two consecutive occurrences of V _j in x are separated by precisely j characters of x, 1≦ j≦n. Proving subsequent conjectures of P[acaron] un [5] and Marcus and P[acaron] un [4], we show that every weak Langford string is square-free. As a consequence, all Langford languages are finite. Some related questions are raised.     

Finite-dimensional filters with nonlinear drift,VI: Linear structure of Ω

Ever since the concept of estimation algebra was first introduced by Brockett and Mitter independently, it has been playing a crucial role in the investigation of finite-dimensional nonlinear filters. Researchers have classified all finite-dimensional estimation algebras of maximal rank with state space less than or equal to three. In this paper we study the structure of quadratic forms in a finite-dimensional estimation algebra. In particular, we prove that if the estimation algebra is finite dimensional and of maximal rank, then the Ω=(∂f _j /∂x _i −∂f _i /∂x _j )matrix, wheref denotes the drift term, is a linear matrix in the sense that all the entries in Ω are degree one polynomials. This theorem plays a fundamental role in the classification of finite-dimensional estimation algebra of maximal rank. This research was supported by Army Research Office Grants DAAH 04-93-0006 and DAAH 04-1-0530.     

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 .     

Binding number and Hamiltonian (g,f)-factors in graphs II

A (g, f)-factor F of a graph G is called a Hamiltonian (g, f)-factor if F contains a Hamiltonian cycle. For a subset X of V(G), let N _G (X)= gcup _x∈X N _G (x). The binding number of G is defined by bind(G)=min{| N _G (X) |/| X|| ?≠X?V(G), N _G (X)≠V(G)}. Let G be a connected graph of order n, 3≤a≤b be integers, and b≥4. Let g, f be positive integer-valued functions defined on V(G), such that a≤g(x)≤f(x)≤b for every x∈V(G). Suppose n≥(a+b?4)²/(a?2) and f(V(G)) is even, we shall prove that if bind(G)>((a+b?4)(n?1))/((a?2)n?(5/2)(a+b?4)) and for any independent set X?V(G), N _G (X)≥((b?3)n+(2a+2b?9)| X|)/(a+b?5), then G has a Hamiltonian (g, f)-factor.     

Decomposition of Polynomials with Respect to the Cyclic Group of Orderm

Given a polynomial solution of a differential equation, its m -ary decomposition, i.e. its decomposition as a sum of m polynomials P^{[ j ]}(x)  = ∑_kα_j,kx^{λ_{j, k}}containing only exponentsλ_{j, k} with λ_{j,k  + 1} − λ_j,k = m, is considered. A general algorithm is proposed in order to build holonomic equations for the m -ary parts P^{[ j ]}(x) starting from the initial one, which, in addition, provides a factorized form of them. Moreover, these differential equations are used to compute expansions of the m -ary parts of a given polynomial in terms of classical orthogonal polynomials. As illustration, binary and ternary decomposition of these classical families are worked out in detail.     

On the rate of convergence of 2-term recursions in ℝ d

LetG be a compact set in ℝ ^d d≥1,M=G×G andϕ:M →G a map inC ₃(M). Suppose thatϕ has a fixed pointξ, i.e.ϕ(ξ, ξ)=ξ. We investigate the rate of convergence of the iterationx ⁿ⁺²=φ(x ⁿ⁺¹,x ⁿ) withx ⁰,x ¹∈G andx ⁿ→ξ. Iff _n=Q‖x ⁿ−ξ‖ with a suitable norm and a constantQ depending onξ, an exact representation forf _n is derived. The error terms satisfyf _2m+1≍(ƒ_2m)^γ,f _2m+2≍(ƒ_2m+1)^2γ,m≥0, with 1<gg<2, andγ=γ(x ¹,x ⁰). According to our main result we have lim_n→∞{‖x ⁿ⁺²‖/(‖x ⁿ‖)²}=Q, 0<Q<∞. This paper constitutes an extension of a part of the author’s doctoral thesis realized under the direction of Prof. E. Wirsing and Prof. A. Peyerimhoff, University of Ulm (Germany).     

Numerical solution for the one-phase Stefan problem by Piecewise constant approximation of the interface

The classical one-phase one-dimensional Stefan problem is numerically solved on rectangles,R _j , of increasing size controlled by the Stefan condition. This approach is based on a scheme introduced by E. Di Benedetto and R. Spigler in 1983. The practical implementation rests on the representation viathermal potentials of the solutionu ^j (x, t) to the heat equation inR _j . The quantityu _x ^j (x _j ,jΔt) which determines the (j+1)-th rectangle is evaluatedanalytically by solving explicitly an integral equation. The solution inR _j+1 is then obtained bynumerically evaluating a further integral expression. The algorithm is tested by solving two problems whose solution is explicitly known. Convergence, stability and convergence rate as Δx→0, Δt→0 have been tested and plots are shown.     

Rational Interpolation from Stochastic Data: A New Froissart's Phenomenon

The analytic structure of Rational Interpolants (R.I.) f (z) built from randomly perturbed data is explored; the interpolation nodes x _j , j = 1,...,M, are real points where the function f reaches these prescribed data . It is assumed that the data are randomly perturbed values of a rational function _(n) ^(m) (m / n is the degree of the numerator/denominator). Much attention is paid to the R.I. familyf _(n+1) ^(m–1), in the small stochasticity régime. The main result is that the additional zero and pole are located nearby the root of the same random polynomial, called the Froissart Polynomial (F.P.). With gaussian hypothesis on the noise, the random real root of F.P. is distributed according to a Cauchy-Lorentz law, with parameters such that the integrated probability over the interpolation interval x ₁, x _M is always larger than 1/2; in two cases studied in detail, it reaches 2/3 in one case and almost 3/4 in the other. For the families f _(n+k) ^(m+k), numerical explorations point to similar phenomena; inspection shows that, in the mean, the localization occurs in the complex and/or real vicinity of the interpolation interval.     

Espaces métriques rationnellement présentés et complexité, le cas de l'espace des fonctions réelles uniformément continues sur un intervalle compact

We define the notion of rational presentation of a complete metric space, in order to study metric spaces from the algorithmic complexity point of view. In this setting, we study some representations of the space C[0,1] of uniformly continuous real functions over [0,1] with the usual norm: ||f||_∞ = Sup{|f(x)|; 0x1}. This allows us to have a comparison of global kind between complexity notions attached to these presentations. In particular, we get a generalization of Hoover's results concerning the Weierstrass approximation theorem in polynomial time. We get also a generalization of previous results on analytic functions which are computable in polynomial time.     

Variational Image Restoration and Decomposition with Curvelet Shrinkage

The curvelet is more suitable for image processing than the wavelet and able to represent smooth and edge parts of image with sparsity. Based on this, we present a new model for image restoration and decomposition via curvelet shrinkage. The new model can be seen as a modification of Daubechies-Teschke’s model. By replacing the B _p,q ^β term by a G _p,q ^β term, and writing the problem in a curvelet framework, we obtain elegant curvelet shrinkage schemes. Furthermore, the model allows us to incorporate general bounded linear blur operators into the problem. Various numerical results on denoising, deblurring and decomposition of images are presented and they show that the model is valid.

Construction of superoptimal approximants

LetG be a matrix function of type m×n and suppose thatG is expressible as the sum of anH ^∞ function and a continuous function on the unit circle. Then it is known that there is a unique superoptimal approximant toG inH ^∞: that is, there is a unique analytic matrix functionQ in the open unit disc which minimizess ^∞(G?Q) or, in other words, which minimizes the sequence $$(s_0^\infty (G - Q),s_1^\infty (G - Q),s_2^\infty (G - Q), \ldots )$$ with respect to the lexicographic ordering, wheres _j ^∞ (F)=sup _x∈ s _j (F(z)) ands _j (·) denotes thejth singular value of a matrix. We give a function-theoretic (frequency domain) algorithm for the construction of this approximant. We calculate an example to illustrate the algorithm. The construction works for rationalG, but is also valid for non-rational functions. It is based on the authors' uniqueness proof in [PY1], but contains extra ingredients required to render it practicable, notably one which obviates the need for the preliminary solution of a Nehari problem. We also establish a formula forQ in terms of the maximizing vectors of a sequence of Hankel-type operators.     

A constrained optimization approach for an adaptive generalized subspace tracking algorithm

In this paper, we present an orthonormal version of the generalized signal subspace tracking. It is based on an interpretation of the generalized signal subspace as the solution of a constrained minimization task. This algorithm, referred to as the CGST algorithm, guarantees the C_x-orthonormality of the estimated generalized signal subspace basis at each iteration which C_x denotes the correlation matrix of the sequence x(t). An efficient implementation of the proposed algorithm enhances applicability of it in real time applications.     

Learning criteria for training neural network classifiers

This paper presents a study of two learning criteria and two approaches to using them for training neural network classifiers, specifically a Multi-Layer Perceptron (MLP) and Radial Basis Function (RBF) networks. The first approach, which is a traditional one, relies on the use of two popular learning criteria, i.e. learning via minimising a Mean Squared Error (MSE) function or a Cross Entropy (CE) function. It is shown that the two criteria have different charcteristics in learning speed and outlier effects, and that this approach does not necessarily result in a minimal classification error. To be suitable for classification tasks, in our second approach an empirical classification criterion is introduced for the testing process while using the MSE or CE function for the training. Experimental results on several benchmarks indicate that the second approach, compared with the first, leads to an improved generalisation performance, and that the use of the CE function, compared with the MSE function, gives a faster training speed and improved or equal generalisation performance.Nomenclature x random input vector withd real number components [x ₁ ...x _d ] - t random target vector withc binary components [t ₁ ...t _c ] - y(·) neural network function or output vector - parameters of a neural model - learning rate - momentum - decay factor - O objective function - E mean sum-of-squares error function - L cross entropy function - n nth training pattern - N number of training patterns - (·) transfer function in a neural unit - z _j output of hidden unit-j - a _i activation of unit-j - W _ij weight from hidden unit-j to output unit-i - W _jl ⁰ weight from input unit-l to hidden unit-j - _j centre vector [ _{j 1} ... _jd ] of RBF unit-j - _j width vector [ _{j 1}, ... _jd ] of RBF unit-j - p( ·¦·) conditional probability function