Search

This paper considers the problem of computing the real convex hull of a finite set of n-dimensional integer vectors. The starting point is a finite-automaton representation of the initial set of vectors. The proposed method consists in computing a sequence of automata representing approximations of the convex hull and using extrapolation techniques to compute the limit of this sequence. The convex hull can then be directly computed from this limit in the form of an automaton-based representation of the corresponding set of real vectors. The technique is quite general and has been implemented. [ABSTRACT FROM AUTHOR]

We give a constant factor approximation algorithm for the Asymmetric Traveling Salesman Problem on shortest path metrics of directed graphs with two different edge weights. For the case of unit edge weights, the first constant factor approximation was given recently by Svensson. This was accomplished by introducing an easier problem called Local-Connectivity ATSP and showing that a good solution to this problem can be used to obtain a constant factor approximation for ATSP. In this paper, we solve Local-Connectivity ATSP for two different edge weights. The solution is based on a flow decomposition theorem for solutions of the Held-Karp relaxation, which may be of independent interest. [ABSTRACT FROM AUTHOR]

In this paper we study a discrete version of the classical team decision problem. It has been shown previously that the general discrete team decision problem is NP-hard. Here we present an efficient approximation algorithm for this problem. For the maximization version of this problem with nonnegative rewards, this algorithm computes decision rules which are guaranteed to be within a fixed bound of optimal. [ABSTRACT FROM AUTHOR]

Currently, two-dimensional dyadic wavelet transform (2D-DWT) is habitually considered as the one presented by Mallat, which is defined by an approximation component, two detail components in horizontal and vertical directions. This paper is to introduce a new type of two-dimensional dyadic wavelet transform and its application so that dyadic wavelet can be studied and used widely furthermore. (1) Two-dimensional stationary dyadic wavelet transform (2D-SDWT) is proposed, it is defined by approximation coefficients, detail coefficients in horizontal, vertical and diagonal directions, which is essentially the extension of two-dimensional stationary wavelet transform for orthogonal/biorthogonal wavelet filters. (2) ε-decimated dyadic discrete wavelet transform (DDWT) is introduced and its relation with 2D-SDWT is given, where ε is a sequence of 0's and 1's. (3) Mallat decomposition algorithm based on dyadic wavelet is introduced as a special case of ε-decimated DDWT, and so a face recognition algorithm based on dyadic wavelet is proposed, and experimental results are given to show its effectiveness. [ABSTRACT FROM AUTHOR]

This paper shows how to compute O(√log n)-approximations to the Sparsest Cut and Balanced Separator problems in Õ(n²) time, thus improving upon the recent algorithm of Arora, Rao, and Vazirani [Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222-231]. Their algorithm uses semidefinite programming and requires Õ (n9.5) time. Our algorithm relies on efficiently finding expander flows in the graph and does not solve semidefinite programs. The existence of expander flows was also established by Arora, Rao, and Vazirani. [ABSTRACT FROM AUTHOR]

We revisit the comparison of mathematical programming with equilibrium constraints (MPEC) and nested fixed point (NFXP) algorithms for estimating structural dynamic models by Su and Judd (2012). Their implementation of the nested fixed point algorithm used successive approximations to solve the inner fixed point problem (NFXP-SA). We redo their comparison using the more efficient version of NFXP proposed by Rust (1987), which combines successive approximations and Newton-Kantorovich iterations to solve the fixed point problem (NFXP-NK). We show that MPEC and NFXP are similar in speed and numerical performance when the more efficient NFXP-NK variant is used. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we propose to use Chambolle’s dual methods to solve Total Variation (TV) inpainting model and (weighted) TV colorization model. The fidelity coefficients in these two models are functions which taking zero in the inpainting region and a positive constant in the other region. Then Chambolle’s dual method can not be directly used to solve these models since the fidelity coefficient will be denominator in the algorithm. In order to overcome this drawback, we propose to approximate these models by adding new variables. Then the approximated problems can be solved by alternating minimization method with Chambolle’s dual method and closed form solutions which is fast and easy to implement. Mathematical results of existence of minimizers are proved for both the original and the approximated problems. Numerical results and comparison with other closely related methods demonstrate that our algorithms are quite efficient. [Copyright &y& Elsevier]

Abstract: In this paper we introduce a new boundary condition that can be used when reconstructing an image from observed blurred and noisy data. Our approach uses information from the observed image to enforce boundary conditions that continue image features such as edges and texture across the boundary. Because of its similarity to methods used in texture synthesis, we call our approach synthetic boundary conditions. We provide an efficient algorithm for implementing the new boundary condition, and provide a linear algebraic framework for the approach that puts it in the context of more classical and well known image boundary conditions, including zero, periodic, reflective, and anti-reflective. Extensive numerical experiments show that our new synthetic boundary conditions provide a more accurate approximation of the true image scene outside the image boundary, and thus allow for better reconstructions of the unknown, true image scene. [Copyright &y& Elsevier]

Abstract: In this paper we describe how an idea centered on the concept of self-saturation allows several improvements in the computation of Gröbner bases via Buchberger’s Algorithm. In a nutshell, the idea is to extend the advantages of computing with homogeneous polynomials or vectors to the general case. When the input data are not homogeneous, we use as a main tool the procedure of a self-saturating Buchberger’s Algorithm. Another strictly related topic is treated later when a mathematical foundation is given to the sugar trick which is nowadays widely used in most of the implementations of Buchberger’s Algorithm. A special emphasis is also given to the case of a single grading, and subsequently some timings and indicators showing the practical merits of our approach. [Copyright &y& Elsevier]

Abstract: Symmetric rank-one (SR1) is one of the competitive formulas among the quasi-Newton (QN) methods. In this paper, we propose some modified SR1 updates based on the modified secant equations, which use both gradient and function information. Furthermore, to avoid the loss of positive definiteness and zero denominators of the new SR1 updates, we apply a restart procedure to this update. Three new algorithms are given to improve the Hessian approximation with modified secant equations for the SR1 method. Numerical results show that the proposed algorithms are very encouraging and the advantage of the proposed algorithms over the standard SR1 and BFGS updates is clearly observed. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, by solving the relaxed quasiconcave programming problem in outcome space, a new global optimization algorithm for convex multiplicative programming is presented. Two kinds of techniques are employed to establish the algorithm. The first one is outer approximation technique which is applied to shrink relaxation area of quasiconcave programming problem and to compute appropriate feasible points and to raise the capacity of bounding. And the other one is branch and bound technique which is used to guarantee global optimization. Some numerical results are presented to demonstrate the effectiveness and feasibility of the proposed algorithm. [Copyright &y& Elsevier]

Stochastic approximation problem is to find some root or extremum of a nonlinear function for which only noisy measurements of the function are available. The classical algorithm for stochastic approximation problem is the Robbins-Monro (RM) algorithm, which uses the noisy evaluation of the negative gradient direction as the iterative direction. In order to accelerate the RM algorithm, this paper gives a frame algorithm using adaptive iterative directions. At each iteration, the new algorithm goes towards either the noisy evaluation of the negative gradient direction or some other directions under some switch criterions. Two feasible choices of the criterions are proposed and two corresponding flame algorithms are formed. Different choices of the directions under the same given switch criterion in the flame can also form different algorithms. We also proposed the simultanous perturbation difference forms for the two flame algorithms. The almost surely convergence of the new algorithms are all established. The numerical experiments show that the new algorithms are promising. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we extend the algorithm in Xue and Cheng [L. Xue, X.L. Cheng, An algorithm for solving the obstacle problems, Comput. Math. Appl. 48 (2004) 1651–1657] for solving the double obstacle problem. We try to find the approximated region of the contact in the double obstacle problem with less computation time by iteration. Numerical example is given for the double obstacle problem for the elastic–plastic torsion problem to support the algorithm. [Copyright &y& Elsevier]

This article details a novel numerical scheme to approximate gradient flows for optimal transport (i.e., Wasserstein) metrics. These flows have proved useful to tackle theoretically and numerically nonlinear diffusion equations that model, for instance, porous media or crowd evolutions. These gradient flows define a suitable notion of weak solutions for these evolutions and they can be approximated in a stable way using discrete flows. These discrete flows are implicit Euler time stepping according to the Wasserstein metric. A bottleneck of these approaches is the high computational load induced by the resolution of each step. Indeed, this corresponds to the resolution of a convex optimization problem involving a Wasserstein distance to the previous iterate. Following several recent works on the approximation of Wasserstein distances, we consider a discrete flow induced by an entropic regularization of the transportation coupling. This entropic regularization allows one to trade the initial Wasserstein fidelity term for a Kullback-Leibler divergence, which is easier to deal with numerically. We show how Kullback-Leibler first order proximal schemes and, in particular, Dykstra's algorithm, can be used to compute each step of the regularized flow. The resulting algorithm is both fast, parallelizable, and versatile, because it only requires multiplications by the Gibbs kernel e -c/γ, where c is the ground cost and γ > 0 the regularization strength. On Euclidean domains discretized on a uniform grid, this corresponds to a linear filtering (for instance, a Gaussian filtering when c is the squared Euclidean distance) which can be computed in nearly linear time. On more general domains, such as (possibly nonconvex) shapes or on manifolds discretized by a triangular mesh, following a recently proposed numerical scheme for optimal transport, this Gibbs kernel multiplication is approximated by a short-time heat diffusion. We show numerical illustrations of this method to approximate crowd motions with congestion on complicated domains as well as extensions to take into account interactions between multiple densities. [ABSTRACT FROM AUTHOR]

An optimal control problem governed by the first bi-harmonic equation with the integral constraint for the state and its spectral approximations based on a mixed formulation are investigated. The optimality conditions of the exact and the discrete optimal control systems are derived. The a priori error estimates of high order spectral accuracy are obtained. Furthermore, a simple and efficient iterative algorithm is proposed to solve mixed discrete system. Some numerical examples are performed to verify the theoretical results. [ABSTRACT FROM AUTHOR]

We consider the approximate nearest neighbor search problem on the Hamming cube {0, 1}d. We show that a randomized cell probe algorithm that uses polynomial storage and word size dO(1) requires a worst case query time of Ω(log log d/log log log d). The approximation factor may be as loose as 2log1-ηd for any fixed η > 0. Our result fills a major gap in the study of this problem since all earlier lower bounds either did not allow randomization [A. Chakrabarti et al., A lower bound on the complexity of approximate nearest-neighbor searching on the Hamming cube, in Discrete and Computational Geometry, Springer, Berlin, 2003, pp. 313-328; D. Liu, Inform. Process. Lett., 92 (2004), pp. 23-29] or did not allow approximation [A. Borodin, R. Ostrovsky, and Y. Rabani, Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 1999, pp. 312-321; O. Barkol and Y. Rabani, Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, 2000, pp. 388-396; T. S. Jayram et al., J. Comput. System Sci., 69 (2004), pp. 435-447]. We also give a cell probe algorithm that proves that our lower bound is optimal. Our proof uses a lower bound on the round complexity of the related communication problem. We show, additionally, that considerations of bit complexity alone cannot prove any nontrivial cell probe lower bound for the problem. This shows that the "richness technique" [P. B. Miltersen et al., J. Comput. System Sci., 57 (1998), pp. 37-49] used in a lot of recent research around this problem would not have helped here. Our proof is based on information theoretic techniques for communication complexity, a theme that has been prominent in recent research [A. Chakrabarti et al., Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science, 2001, pp. 270-278; Z. Bar-Yossef et al., Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002, pp. 209-218; P. Sen, Proceedings of the 18th Annual IEEE Conference on Computational Complexity, 2003, pp. 73-83; R. Jain, J. Radhakrishnan, and P. Sen, Proceedings of the 30th International Colloquium on Automata, Languages and Programming, 2003, pp. 300-315]. [ABSTRACT FROM AUTHOR]

We study the convergence of an iterative projection/reflection algorithm originally proposed for solving what are known as phase retrieval problems in optics. There are two features that frustrate any analysis of iterative methods for solving the phase retrieval problem: nonconvexity and infeasibility. The algorithm that we developed, called relaxed averaged alternating reflections (RAAR), was designed primarily to address infeasibility, though our strategy has advantages for nonconvex problems as well. In the present work we investigate the asymptotic behavior of the RAAR algorithm for the general problem of finding points that achieve the minimum distance between two closed convex sets in a Hilbert space with empty intersection, and for the problem of finding points that achieve a local minimum distance between one closed convex set and a closed prox-regular set, also possibly nonintersecting. The nonconvex theory includes and expands prior results limited to convex sets with nonempty intersection. To place the RAAR algorithm in context, we develop parallel statements about the standard alternating projections algorithm and gradient descent. All of the various algorithms are unified as instances of iterated averaged alternating proximal reflectors applied to a sum of regularized maximal monotone mappings. [ABSTRACT FROM AUTHOR]

A family of dual-primal finite-element tearing and interconnecting methods for edge-element approximations in 3D is proposed and analysed. The key part of this work relies on the observation that for these finite-element spaces there is a strong coupling between degrees of freedom associated with subdomain edges and faces and a local change of basis is therefore necessary. The primal constraints are associated with subdomain edges. We propose three methods. They ensure a condition number that is independent of the number of substructures and possibly large jumps of one of the coefficients of the original problem, and only depends on the number of unknowns associated with a single substructure, as for the corresponding methods for continuous nodal elements. A polylogarithmic dependence is shown for two algorithms. Numerical results validating our theoretical bounds are given. [ABSTRACT FROM PUBLISHER]

Various log-likelihood-ratio-based belief-propagation (LLR-BP) decoding algorithms and their reduced-complexity derivatives for low-density parity-check (LDPC) codes are presented. Numerically accurate representations of the check-node update computation used in LLR-BP decoding are described. Furthermore, approximate representations of the decoding computations are shown to achieve a reduction in complexity by simplifying the check-node update, or symbol-node update, or both. In particular, two main approaches for simplified check-node updates are presented that are based on the so-called min-sum approximation coupled with either a normalization term or an additive offset term. Density evolution is used to analyze the performance of these decoding algorithms, to determine the optimum values of the key parameters, and to evaluate finite quantization effects. Simulation results show that these reduced-complexity decoding algorithms for LDPC codes achieve a performance very close to that of the BP algorithm. The unified treatment of decoding techniques for LDPC codes presented here provides flexibility in selecting the appropriate scheme from performance, latency, computational-complexity, and memory-requirement perspectives. [ABSTRACT FROM AUTHOR]

Reliability studies give rise to families of distribution functions F[sup (n)] defined recursively by the repeated convolution of a distribution function F with itself according to the scheme F[sup (1)](t) = F(t), F[sup (n+1)](t) = ∫[sup t, sub 0]F[sup (n)](1-x)F'(x)dx, n>1, where F' is the derivative of F, and is usually given by a p.d,f, ∫. In particular, many systems characteristics are defined in terms of integrals of the form ∫[sup 1, sub 0]P[sup (s)](t- x)Q[sup (r)]'(x)dx where P[sup (s)] and Q[sup (r)] are the sth and rth members of families generated from distribution functions P and Q, not necessarily distinct. It is seldom possible or convenient to express the F[sup (n)] in analytical form. An algorithm based on cubic spline interpolation is given here for recursively generating continuous numerical approximations to the F[sup (n)] in a form which allows them to be convoluted together to provide useful approximation to the second of the above integrals. [ABSTRACT FROM AUTHOR]