Consistent learning by composite proximal thresholding

We investigate the modeling and the numerical solution of machine learning problems with prediction functions which are linear combinations of elements of a possibly infinite dictionary of functions. We propose a novel flexible composite regularization model, which makes it possible to incorporate various priors on the coefficients of the prediction function, including sparsity and hard constraints. We show that the estimators obtained by minimizing the regularized empirical risk are consistent in a statistical sense, and we design an error-tolerant composite proximal thresholding algorithm for computing such estimators. New results on the asymptotic behavior of the proximal forward–backward splitting method are derived and exploited to establish the convergence properties of the proposed algorithm. In particular, our method features a o(1 / m) convergence rate in objective values.     

A note on quadratic convergence of a smoothing Newton algorithm for the LCP

The linear complementarity problem (LCP) is to find ${(x,s)\in\mathfrak{R}^n\times\mathfrak{R}^n}$ such that (x, s) ≥ 0, s = Mx + q, x ^T s = 0 with ${M\in\mathfrak{R}^{n\times n}}$ and ${q\in\mathfrak{R}^n}$ . The smoothing Newton algorithm is one of the most efficient methods for solving the LCP. To the best of our knowledge, the best local convergence results of the smoothing Newton algorithm for the LCP up to now were obtained by Huang et al. (Math Program 99:423–441, 2004). In this note, by using a revised Chen–Harker–Kanzow–Smale smoothing function, we propose a variation of Huang–Qi–Sun’s algorithm and show that the algorithm possesses better local convergence properties than those given in Huang et al. (Math Program 99:423–441, 2004).     

Log-convexity properties of Schur functions and generalized hypergeometric functions of matrix argument

We establish a positivity property for the difference of products of certain Schur functions, s _λ (x), where λ varies over a fundamental Weyl chamber in ? ⁿ and x belongs to the positive orthant in ? ⁿ . Further, we generalize that result to the difference of certain products of arbitrary numbers of Schur functions. We also derive a log-convexity property of the generalized hypergeometric functions of two Hermitian matrix arguments, and we show how that result may be extended to derive higher-order log-convexity properties.     

Polynomial behavior of special values of partial zeta functions of real quadratic fields at s = 0

We compute the special values of partial zeta functions at s = 0 for family of real quadratic fields K _n and ray class ideals ${\mathfrak{b}_n}$ such that ${\mathfrak{b}_n^{-1} = [1, \delta(n)]}$ where the continued fraction expansion of δ(n) ? 1 is purely periodic and terms are polynomials in n of degree bounded by d. With additional assumptions, we prove that the special values of the partial zeta functions at s = 0 are given by a quasi-polynomial of degree less than or equal to d as a function of n. We apply this to conclude that the special values of the Hecke’s L-functions at s = 0 for the family ${(K_n, \mathfrak{b}_n, \chi_n:= \chi \circ N_{K_n/\mathbb{Q}})}$ for any Dirichlet character χ behave like quasi-polynomial as well. We compute explicitly the coefficients of the quasi-polynomials. Two examples satisfying the condition are presented, and for these two families, the special values of the partial zeta functions at s = 0 are given.     

Characterizing W 2,p Submanifolds by p -Integrability of Global Curvatures

We give sufficient and necessary geometric conditions, guaranteeing that an immersed compact closed manifold ${\Sigma^m \subset \mathbb{R}^n}$ of class C ¹ and of arbitrary dimension and codimension (or, more generally, an Ahlfors-regular compact set Σ satisfying a mild general condition relating the size of holes in Σ to the flatness of Σ measured in terms of beta numbers) is in fact an embedded manifold of class ${C^{1,\tau} \cap W^{2,p}}$ , where p > m and τ = 1 ? m/p. The results are based on a careful analysis of Morrey estimates for integral curvature–like energies, with integrands expressed geometrically, in terms of functions that are designed to measure either (a) the shape of simplices with vertices on Σ or (b) the size of spheres tangent to Σ at one point and passing through another point of Σ. Appropriately defined maximal functions of such integrands turn out to be of class L ^p (Σ) for p > m if and only if the local graph representations of Σ have second order derivatives in L ^p and Σ is embedded. There are two ingredients behind this result. One of them is an equivalent definition of Sobolev spaces, widely used nowadays in analysis on metric spaces. The second one is a careful analysis of local Reifenberg flatness (and of the decay of functions measuring that flatness) for sets with finite curvature energies. In addition, for the geometric curvature energy involving tangent spheres we provide a nontrivial lower bound that is attained if and only if the admissible set Σ is a round sphere.     

Non-conformal Repellers and the Continuity of Pressure for Matrix Cocycles

The pressure function P(A, s) plays a fundamental role in the calculation of the dimension of “typical” self-affine sets, where A = (A ₁, …,A _k ) is the family of linear mappings in the corresponding generating iterated function system. We prove that this function depends continuously on A. As a consequence, we show that the dimension of “typical” self-affine sets is a continuous function of the defining maps. This resolves a folklore open problem in the community of fractal geometry. Furthermore we extend the continuity result to more general sub-additive pressure functions generated by the norm of matrix products or generalized singular value functions for matrix cocycles, and obtain applications on the continuity of equilibrium measures and the Lyapunov spectrum of matrix cocycles.     

Turán numbers for K s,t -free graphs: Topological obstructions and algebraic constructions

We show that every hypersurface in ? ^s × ? ^s contains a large grid, i.e., the set of the form S × T, with S, T ? ? ^s . We use this to deduce that the known constructions of extremal K _2,2-free and K _3,3-free graphs cannot be generalized to a similar construction of K _s,s -free graphs for any s ≥ 4. We also give new constructions of extremal K _s,t -free graphs for large t.     

On the limit behavior of the magnetic Zakharov system

In this paper,we prove that the solutions of magnetic Zakharov system converge to those of generalized Zakharov system in Sobolev space H s,s > 3/2,when parameter β→∞.Further,when parameter (α,β) →∞ together,we prove that the solutions of magnetic Zakharov system converge to those of Schro¨dinger equation with magnetic effect in Sobolev space H s,s > 3/2.Moreover,the convergence rate is also obtained.     

On a Generalization of Szász–Mirakjan–Kantorovich Operators

In this paper we introduce and study a sequence of positive linear operators acting on suitable spaces of measurable functions on [0,+∞[, including L ^p ([0,+∞[) spaces, 1 ≤ p < +∞, as well as continuous function spaces with polynomial weights. These operators generalize the Szász–Mirakjan–Kantorovich operators and they allow to approximate (or to reconstruct) suitable measurable functions by knowing their mean values on a sequence of subintervals of [0,+∞[ that do not constitute a subdivision of it. We also give some estimates of the rates of convergence by means of suitable moduli of smoothness.     

Supraconvergence and Supercloseness of a Scheme for Elliptic Equations on Nonuniform Grids

In this paper, we study the convergence of a finite difference scheme on nonuniform grids for the solution of second-order elliptic equations with mixed derivatives and variable coefficients in polygonal domains subjected to Dirichlet boundary conditions. We show that the scheme is equivalent to a fully discrete linear finite element approximation with quadrature. It exhibits the phenomenon of supraconvergence, more precisely, for s ∈ [1,2] order O(h ^s )-convergence of the finite difference solution, and its gradient is shown if the exact solution is in the Sobolev space H ^1+s (Ω). In the case of an equation with mixed derivatives in a domain containing oblique boundary sections, the convergence order is reduced to O(h ^3/2?ε) with ε > 0 if u ∈ H ³(Ω). The second-order accuracy of the finite difference gradient is in the finite element context nothing else than the supercloseness of the gradient. For s ∈ {1,2}, the given error estimates are strictly local.     

New models for locating a moving service facility

In this paper we analyze a new location problem which is a generalization of the well-known single facility location model. This extension consists of introducing a general objective function and replacing fixed locations by trajectories. We prove that the problem is well-stated and solvable. A Weiszfeld type algorithm is proposed to solve this generalized dynamic single facility location problem on L ^p spaces of functions, with p ∈(1,2]. We prove global convergence of our algorithm once we have assumed that the set of demand functions and the initial step function belong to a subspace of L ^p called Sobolev space. Finally, examples are included illustrating the application of the model to generalized regression analysis and the convergence of the proposed algorithm. The examples also show that the pointwise extension of the algorithm does not have to converge to an optimal solution of the considered problem while the proposed algorithm does.     

Estimation of Spectral Bounds in Gradient Algorithms

We consider the solution of linear systems of equations Ax=b, with A a symmetric positive-definite matrix in ? ^n×n , through Richardson-type iterations or, equivalently, the minimization of convex quadratic functions (1/2)(Ax,x)?(b,x) with a gradient algorithm. The use of step-sizes asymptotically distributed with the arcsine distribution on the spectrum of A then yields an asymptotic rate of convergence after k<n iterations, k→∞, that coincides with that of the conjugate-gradient algorithm in the worst case. However, the spectral bounds m and M are generally unknown and thus need to be estimated to allow the construction of simple and cost-effective gradient algorithms with fast convergence. It is the purpose of this paper to analyse the properties of estimators of m and M based on moments of probability measures ν _k defined on the spectrum of A and generated by the algorithm on its way towards the optimal solution. A precise analysis of the behavior of the rate of convergence of the algorithm is also given. Two situations are considered: (i) the sequence of step-sizes corresponds to i.i.d. random variables, (ii) they are generated through a dynamical system (fractional parts of the golden ratio) producing a low-discrepancy sequence. In the first case, properties of random walk can be used to prove the convergence of simple spectral bound estimators based on the first moment of ν _k . The second option requires a more careful choice of spectral bounds estimators but is shown to produce much less fluctuations for the rate of convergence of the algorithm.     

An Efficient Algorithm to Identify DNA Motifs

We consider the problem of identifying motifs that abstracts the task of finding short conserved sites in genomic DNA. The planted (l, d)-motif problem, PMP, is the mathematical abstraction of this problem, which consists of finding a substring of length l that occurs in each s _i in a set of input sequences S = {s ₁, s ₂, . . . ,s _t } with at most d substitutions. Our propose algorithm combines the voting algorithm and pattern matching algorithm to find exact motifs. The combined algorithm is achieved by running the voting algorithm on t′ sequences, t′ < t. After that we use the pattern matching on the output of the voting algorithm and the reminder sequences, t ? t′. Two values of t′ are calculated. The first value of t′ makes the running time of our proposed algorithm less than the running time of voting algorithm. The second value of t′ makes the running time of our proposed algorithm is minimal. We show that our proposed algorithm is faster than the voting algorithm by testing both algorithms on simulated data from (9, d ≤ 2) to (19, d ≤ 7). Finally, we test the performance of the combined algorithm on realistic biological data.     

The Conformal Arclength Functional

Oversampled functions can be evaluated using generalized sinc-series and filter functions connected with these series. A standard filter function is given by exp ((ζ² ? 1)^?1). We show that the Fourier transform of this filter posseses the convergence order 0(exp (?√x)), improving an estimation given in [10]. Moreover, we define a family of filter functions with convergence order O(x · exp (?x^σ)) with σ arbitrary close to 1.     

Estimation améliorée explicite d'un degré de confiance conditionnel

We consider the problem of estimating the confidence statement of the usual confidence set, with confidence coefficient 1?α, of the mean of a p-variate normal distribution with identity covariance matrix. For p?5, we give an explicit sufficient condition for domination over the standard estimator 1?α by an estimator correcting it, that is, by 1?α+s where s is a suitable function. That condition mainly relies on a partial differential inequality of the form kΔs+s²?0 (for a certain constant k>0). It allows us to formally establish (with no recourse to simulations) this domination result. To cite this article: D. Fourdrinier, P. Lepelletier, C. R. Acad. Sci. Paris, Ser. I 337 (2003).     

A new class of bent and hyper-bent Boolean functions in polynomial forms

Bent functions are maximally nonlinear Boolean functions and exist only for functions with even number of inputs. This paper is a contribution to the construction of bent functions over ${\mathbb{F}_{2^{n}}}$ (n = 2m) having the form ${f(x) = tr_{o(s_1)} (a x^ {s_1}) + tr_{o(s_2)} (b x^{s_2})}$ where o(s _i ) denotes the cardinality of the cyclotomic class of 2 modulo 2 ⁿ ? 1 which contains s _i and whose coefficients a and b are, respectively in ${F_{2^{o(s_1)}}}$ and ${F_{2^{o(s_2)}}}$ . Many constructions of monomial bent functions are presented in the literature but very few are known even in the binomial case. We prove that the exponents s ₁ = 2 ^m ? 1 and ${s_2={\frac {2^n-1}3}}$ , where ${a\in\mathbb{F}_{2^{n}}}$ (a ?? 0) and ${b\in\mathbb{F}_{4}}$ provide a construction of bent functions over ${\mathbb{F}_{2^{n}}}$ with optimum algebraic degree. For m odd, we give an explicit characterization of the bentness of these functions, in terms of the Kloosterman sums. We generalize the result for functions whose exponent s ₁ is of the form r(2 ^m ? 1) where r is co-prime with 2 ^m  + 1. The corresponding bent functions are also hyper-bent. For m even, we give a necessary condition of bentness in terms of these Kloosterman sums.     

Hemisystems of small flock generalized quadrangles

In this paper, we describe a complete computer classification of the hemisystems in the two known flock generalized quadrangles of order (5², 5) and give numerous further examples of hemisystems in all the known flock generalized quadrangles of order (s ², s) for s ≤ 11. By analysing the computational data, we identify two possible new infinite families of hemisystems in the classical generalized quadrangle H(3, s ²).     

Uniqueness of non-linear ground states for fractional Laplacians in {\mathbb{R}}

We prove uniqueness of ground state solutions Q = Q(|x|) ≥ 0 of the non-linear equation $$(-\Delta)^s Q+Q-Q^{\alpha+1}= 0 \quad {\rm in} \, \mathbb{R},$$ ( ? Δ ) s Q + Q ? Q α + 1 = 0 i n R , where 0 < s < 1 and 0 < α < 4s/(1?2s) for ${s<\frac{1}{2}}$ s < 1 2 and 0 < α < ∞ for ${s\geq \frac{1}{2}}$ s ≥ 1 2 . Here (?Δ) ^s denotes the fractional Laplacian in one dimension. In particular, we answer affirmatively an open question recently raised by Kenig–Martel–Robbiano and we generalize (by completely different techniques) the specific uniqueness result obtained by Amick and Toland for ${s=\frac{1}{2}}$ s = 1 2 and α = 1 in [5] for the Benjamin–Ono equation. As a technical key result in this paper, we show that the associated linearized operator L ₊ = (?Δ) ^s +1?(α+1)Q ^α is non-degenerate; i.e., its kernel satisfies ker L ₊ = span{Q′}. This result about L ₊ proves a spectral assumption, which plays a central role for the stability of solitary waves and blowup analysis for non-linear dispersive PDEs with fractional Laplacians, such as the generalized Benjamin–Ono (BO) and Benjamin–Bona–Mahony (BBM) water wave equations.     

Further study of entire radial solutions of a biharmonic equation with exponential nonlinearity

We study the structure of entire radial solutions of a biharmonic equation with exponential nonlinearity: $$\begin{array}{ll}\Delta^2 u = \lambda {\rm e}^u \;\; {\rm in}\; \mathbb{R}^N, N \geq 5 \quad\quad\quad (0.1)\end{array}$$ with λ = 8(N ? 2)(N ? 4). It is known from a recent interesting paper by Arioli et al. that (0.1) admits a singular solution U _s (r) = ln r ^?4. We show that for 5 ≤ N ≤ 12, any regular entire radial solution u with u(r) ? ln r ^?4 → 0 as r → ∞ of (0.1) intersects with U _s (r) infinitely many times. On the other hand, if N ≥ 13, then u(r) < U _s (r) for all r > 0, and the solutions are strictly ordered with respect to the initial value a = u(0). Moreover, the asymptotic expansions of the entire radial solutions near ∞ are also obtained. Our main results give a positive answer to a conjecture in Arioli et al. (J Differ Equ 230:743–770, 2006) [see lines ?11 to ?9, p. 747 of Arioli et al. (J Differ Equ 230:743–770, 2006)].     

Primal-dual bilinear programming solution of the absolute value equation

We propose a finitely terminating primal-dual bilinear programming algorithm for the solution of the NP-hard absolute value equation (AVE): Ax ? |x| = b, where A is an n × n square matrix. The algorithm, which makes no assumptions on AVE other than solvability, consists of a finite number of linear programs terminating at a solution of the AVE or at a stationary point of the bilinear program. The proposed algorithm was tested on 500 consecutively generated random instances of the AVE with n = 10, 50, 100, 500 and 1,000. The algorithm solved 88.6% of the test problems to an accuracy of 10^?6.