Search

This paper studies the approximation of generalized ridge functions, namely of functions which are constant along some submanifolds of R N. We introduce the notion of linear-sleeve functions, whose function values only depend on the distance to some unknown linear subspace L. We propose two effective algorithms to approximate linear-sleeve functions f (x) = g (dist (x , L) 2) , when both the linear subspace L ⊂ R N and the function g ∈ C s [ 0 , 1 ] are unknown. We will prove error bounds for both algorithms and provide an extensive numerical comparison of both. We further propose an approach of how to apply these algorithms to capture general sleeve functions, which are constant along some lower dimensional submanifolds. [ABSTRACT FROM AUTHOR]

Abstract We analyze a new random algorithm for numerical integration of d -variate functions over [ 0 , 1 ] d from a weighted Sobolev space with dominating mixed smoothness α ≥ 0 and product weights 1 ≥ γ 1 ≥ γ 2 ≥ ⋯ > 0 , where the functions are continuous and periodic when α > 1 ∕ 2. The algorithm is based on rank-1 lattice rules with a random number of points n. For the case α > 1 ∕ 2 , we prove that the algorithm achieves almost the optimal order of convergence of O (n − α − 1 ∕ 2) , where the implied constant is independent of the dimension d if the weights satisfy ∑ j = 1 ∞ γ j 1 ∕ α < ∞. The same rate of convergence holds for the more general case α > 0 by adding a random shift to the lattice rule with random n. This shows, in particular, that the exponent of strong tractability in the randomized setting equals 1 ∕ (α + 1 ∕ 2) , if the weights decay fast enough. We obtain a lower bound to indicate that our results are essentially optimal. This paper is a significant advancement over previous related works with respect to the potential for implementation and the independence of error bounds on the problem dimension. Other known algorithms which achieve the optimal error bounds, such as those based on Frolov's method, are very difficult to implement especially in high dimensions. Here we adapt a lesser-known randomization technique introduced by Bakhvalov in 1961. This algorithm is based on rank-1 lattice rules which are very easy to implement given the integer generating vectors. A simple probabilistic approach can be used to obtain suitable generating vectors. [ABSTRACT FROM AUTHOR]

Abstract: The cyclic projections algorithm is an important method for determining a point in the intersection of a finite number of closed convex sets in a Hilbert space. That is, for determining a solution to the “convex feasibility” problem. This is the third paper in a series on a study of the rate of convergence for the cyclic projections algorithm. In the first of these papers, we showed that the rate could be described in terms of the “angles” between the convex sets involved. In the second, we showed that these angles often had a more tractable formulation in terms of the “norm” of the product of the (nonlinear) metric projections onto related convex sets. In this paper, we show that the rate of convergence of the cyclic projections algorithm is also intimately related to the “linear regularity property” of Bauschke and Borwein, the “normal property” of Jameson (as well as Bakan, Deutsch, and Li’s generalization of Jameson’s normal property), the “strong conical hull intersection property” of Deutsch, Li, and Ward, and the rate of convergence of iterated parallel projections. Such properties have already been shown to be important in various other contexts as well. [Copyright &y& Elsevier]

Abstract: In a previous paper, the author introduced a class of multivariate rational interpolants, which are called optimal Padé-type approximants (OPTA). The main goal of this paper is to extend classical results on convergence both in measure and in capacity of sequences of Padé approximants to the multivariate case using OPTA. To this end, we obtain some estimations of the size of multivariate polynomial lemniscates in terms of the Hausdorff content, which we also think are of some interest. [Copyright &y& Elsevier]

In this paper we shall study vector cascade algorithms and refinable function vectors with a general isotropic dilation matrix in Sobolev spaces. By introducing the concept of a canonical mask for a given matrix mask and by investigating several properties of the initial function vectors in a vector cascade algorithm, we are able to take a relatively unified approach to study several questions such as convergence, rate of convergence and error estimate for a perturbed mask of a vector cascade algorithm in a Sobolev space Wpk(Rs) (1&les;p&les;∞, k∈N∪{0}). We shall characterize the convergence of a vector cascade algorithm in a Sobolev space in various ways. As a consequence, a simple characterization for refinable Hermite interpolants and a sharp error estimate of a vector cascade algorithm in a Sobolev space with a perturbed mask will be presented. The approach in this paper enables us to answer some unsolved questions in the literature on vector cascade algorithms and to comprehensively generalize and improve results on scalar cascade algorithms and scalar refinable functions to the vector case. [Copyright &y& Elsevier]

The Douglas-Rachford splitting algorithm is a classical optimization method that has found many applications. When specialized to two normal cone operators, it yields an algorithm for finding a point in the intersection of two convex sets. This method for solving feasibility problems has attracted a lot of attention due to its good performance even in nonconvex settings. In this paper, we consider the Douglas-Rachford algorithm for finding a point in the intersection of two subspaces. We prove that the method converges strongly to the projection of the starting point onto the intersection. Moreover, if the sum of the two subspaces is closed, then the convergence is linear with the rate being the cosine of the Friedrichs angle between the subspaces. Our results improve upon existing results in three ways: First, we identify the location of the limit and thus reveal the method as a best approximation algorithm; second, we quantify the rate of convergence, and third, we carry out our analysis in general (possibly infinite-dimensional) Hilbert space. We also provide various examples as well as a comparison with the classical method of alternating projections. [ABSTRACT FROM AUTHOR]

In this paper, we derive the uniform convergence of approximating tensor-product rational Bézier surfaces using tensor-product Bézier surfaces. Our main result is that arbitrary given order derivative vectors of approximating tensor-product Bézier surface sequence converge uniformly to those of the original tensor-product rational Bézier surface as the elevated degree tends to infinity, with inequality skills and infinitesimal analysis techniques. The approximating tensor-product Bézier surface sequence has the same degree and new control points of the degree-elevated tensor-product rational Bézier surfaces. [ABSTRACT FROM AUTHOR]

Abstract: In the present paper we study convergence of subgradient projection algorithms for solving convex feasibility problems in a Hilbert space. Our goal is to obtain an approximate solution of the problem in the presence of computational errors. We show that our subgradient projection algorithm generates a good approximate solution, if the sequence of computational errors is bounded from above by a constant. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate -average sampling numbers of a periodic Sobolev space with a Gaussian measure in the metric for and , and obtain their asymptotic orders. Moreover, we show that in the average case setting, the operators , which are the Lagrange interpolating operators, are asymptotically optimal in the metric for all . It is interesting to note that in the worst case setting, are not asymptotically optimal algorithms in the metric for or . [Copyright &y& Elsevier]

Abstract: Regularization schemes with an -regularizer often produce sparse representations for objects in approximation theory, image processing, statistics and learning theory. In this paper, we study a kernel-based learning algorithm for regression generated by regularization schemes associated with the -regularizer. We show that convergence rates of the learning algorithm can be independent of the dimension of the input space of the regression problem when the kernel is smooth enough. This confirms the effectiveness of the learning algorithm. Our error analysis is carried out by means of an approximation theory approach using a local polynomial reproduction formula and the norming set condition. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate the generalization performance of a regularized ranking algorithm in a reproducing kernel Hilbert space associated with least square ranking loss. An explicit expression for the solution via a sampling operator is derived and plays an important role in our analysis. Convergence analysis for learning a ranking function is provided, based on a novel capacity independent approach, which is stronger than for previous studies of the ranking problem. [Copyright &y& Elsevier]

Abstract: In this paper the two-dimensional -fraction with independent variables which is the generalization of the continued -fraction is considered. The correspondence between the formal double power series and the above mentioned fraction is studied. As a result the algorithm for the expansion of the formal double power series into the corresponding two-dimensional -fraction with independent variables has been constructed and the conditions for the existence of such an algorithm have been established. The expansion of some functions into the corresponding two-dimensional -fraction with independent variables is constructed and the efficiency of the obtained expansion by using approximants is shown. [Copyright &y& Elsevier]

Abstract: The aim of the paper is the construction and the analysis of nonlinear and non-separable multiscale representations for multivariate functions defined using a non-diagonal dilation matrix . We show that a function in or Besov spaces can be characterized by means of its multiscale representation. We also study the stability of these representations, a key issue to design adaptive algorithms. [Copyright &y& Elsevier]

Abstract: In this paper we apply a concentration technique to improve the convergence rates for a moving least-square learning algorithm for regression. The concentration technique allows us to obtain a sharper bound for the sample error. [Copyright &y& Elsevier]

Abstract: This paper concerns systems with small coherence parameter. Simple greedy-type algorithms perform well on these systems, which are also useful in the construction of compressed sensing matrices. We discuss the following problems for both and . How large can a dictionary be, if we prescribe the coherence parameter? How small could the resulting coherence parameter be, if we impose a size on the dictionary? How could we construct such a system? Several fundamental results from different areas of mathematics shed light on these important problems with far-reaching implications in approximation theory. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate nonlinear -term approximation with regard to orthogonal dictionaries. We consider this problem in the periodic multivariate case for generalized Besov classes under the condition where is a univariate function. We prove that the well-known dictionary which consists of trigonometric polynomials (shifts of the Dirichlet kernels) is nearly optimal among orthogonal dictionaries. Moreover, it is established that for these classes near-best -term approximation, with regard to , can be achieved by simple greedy-type algorithms. [Copyright &y& Elsevier]

Abstract: In this paper we deal with the approximation of a given function on by special bilinear forms via the so-called cross approximation. In particular we are interested in estimating the error function of the corresponding algorithm in the maximum norm. There is a large amount of publications available that successfully deal with similar matrix algorithms in applied situations, for example in connection with -matrices (see Boerm and Grasedyck (2003)  or Hackbusch (2007)  for many references). But as they do not give satisfactory error estimates, we concentrate on the theoretical issues of the problem in the language of functions. We connect it with related results from other areas of analysis in a historical survey and give a lot of references. Our main result is the connection of the error of our algorithm with the error of best approximation by arbitrary bilinear forms. This will be compared with the different approach in Bebendorf (2008) . [Copyright &y& Elsevier]

Abstract: In this paper, we present a new method for finding the optimal smoothing parameter for the abstract smoothing spline . The latter is defined as the solution of the minimization problem and, given an estimate for the noise, the standard choice for is that should satisfy the residual equation Whereas the classical algorithm for solving this equation based on Newton’s method converges quadratically, our new method can have any given order of convergence. [Copyright &y& Elsevier]

Abstract: In this paper we obtain some explicit three term recurrence relations for the determination of multivariate orthogonal polynomials. These formulas allow us to obtain evaluation algorithms of finite series of these polynomials. [Copyright &y& Elsevier]

Abstract: This paper presents a framework of iterative algorithms for the variational inequality problem over the Cartesian product of the intersections of the fixed point sets of nonexpansive mappings in real Hilbert spaces. Strong convergence theorems are established under a certain contraction assumption with respect to the weighted maximum norm. The proposed framework produces as a simplest example the hybrid steepest descent method, which has been developed for solving the monotone variational inequality problem over the intersection of the fixed point sets of nonexpansive mappings. An application to a generalized power control problem and numerical examples are demonstrated. [Copyright &y& Elsevier]

Abstract: The paper addresses the question of convergence of Chebyshevian spline subdivision algorithms. This study suggests some ideas about the general treatment of non-interpolatory irregular (non-uniform/non-stationary) subdivision schemes. [Copyright &y& Elsevier]

Abstract: This paper develops a techniques of Wall pairs for the study of periodic exposed quadratic irrationalities in the unit ball of the Hardy algebra. [Copyright &y& Elsevier]

Abstract: In this paper we consider the problem of best approximation in , . If , denotes the best -approximation of the element from a finite-dimensional affine subspace K of , , then , where is a best uniform approximation of h from K, the so-called strict uniform approximation. Our aim is to give a complete description of the rate of convergence of as by proving that there are constants and such that for p large enough. [Copyright &y& Elsevier]

Smolyak's method, also known as sparse grid method, is a powerful tool to tackle multivariate tensor product problems solely with the help of efficient algorithms for the corresponding univariate problem. In this paper we study the randomized setting, i.e., we randomize Smolyak's method. We provide upper and lower error bounds for randomized Smolyak algorithms with explicitly given dependence on the number of variables and the number of information evaluations used. The error criteria we consider are the worst case root mean square error (the typical error criterion for randomized algorithms, sometimes referred to as "randomized error",) and the root mean square worst case error (sometimes referred to as "worst-case error"). Randomized Smolyak algorithms can be used as building blocks for efficient methods such as multilevel algorithms, multivariate decomposition methods or dimension-wise quadrature methods to tackle successfully high-dimensional or even infinite-dimensional problems. As an example, we provide a very general and sharp result on the convergence rate of N th minimal errors of infinite-dimensional integration on weighted reproducing kernel Hilbert spaces. Moreover, we are able to characterize the spaces for which randomized algorithms for infinite-dimensional integration are superior to deterministic ones. We illustrate our findings for the special instance of weighted Korobov spaces. We indicate how these results can be extended, e.g., to spaces of functions whose smooth dependence on successive variables increases ("spaces of increasing smoothness") and to the problem of L 2 -approximation (function recovery). [ABSTRACT FROM AUTHOR]