12726286
Fast Multilevel Algorithm for a Minimization Problem in Impulse Noise Removal
An effective 2-phase method for removing impulse noise was recently proposed. Its phase 1 identifies noisy pixel candidates by using median-type filters. Then in phase $2$, it restores only the noisy pixel candidates by some variational methods. The resulting method can handle salt-and-pepper noise and random-valued impulse noise at a level as high as 90% and 60%, respectively. The aim of this paper is to generalize a fast multilevel method for Gaussian denoising to solving the minimization problem arising in phase $2$ of the 2-phase method. The multilevel algorithm gives better images than standard optimization methods such as the Newton method or the conjugate gradient method. Also it can handle more general regularization functionals than the smooth ones previously considered. Supporting numerical experiments on two-dimensional gray-scale images are presented.
15785287
A Nonlinear Multigrid Method for Total Variation Minimization from Image Restoration
Abstract
Image restoration has been an active research topic and variational formulations are particularly effective in high quality recovery. Although there exist many modelling and theoretical results, available iterative solvers are not yet robust in solving such modeling equations. Recent attempts on developing optimisation multigrid methods have been based on first order conditions. Different from this idea, this paper proposes to use piecewise linear function spanned subspace correction to design a multilevel method for directly solving the total variation minimisation. Our method appears to be more robust than the primal-dual method (Chan et al., SIAM J. Sci. Comput. 20(6), 1964–1977, 1999) previously found reliable. Supporting numerical results are presented.

21847139
An Analysis of Sparse Approximate Inverse Preconditioners for Boundary Integral Equations
Preconditioning techniques for dense linear systems arising from singular boundary integral equations are described and analyzed. A particular class of approximate inverse based preconditioners related to the mesh neighbor methods is known to be efficient. This paper shows that it is an operator splitting preconditioner and clusters eigenvalues for the normal equation matrix thus ensuring a fast convergence of the conjugate gradient normal method. Clustering of the eigenvalues of the preconditioned matrix and fast convergence of the generalized minimal residual method are also observed. For the type of problems considered, we demonstrate a crucial connection between two essential features of eigenvalue clustering for a sparse preconditioner---approximate inversion for a small cluster radius and operator splitting for a small cluster size. Experimental results from several boundary integral equations are presented.
3879090
On A Recursive Schur Preconditioner For Iterative Solution Of A Class Of Dense Matrix Problems
There are currently several distinct preconditioning methods for dense matrices based on applying a wavelet transform to obtain a matrix with a large number of small entries. A sparse preconditioner for this transformed matrix can be formed by setting to zero entries that are assumed to be unimportant. The effectiveness of the preconditioner depends on retaining the most important entries and on ensuring that they are positioned conveniently within the transformed matrix. In this paper we present a new, recursive preconditioning strategy that takes into account more of the significant entries without greatly increasing cost and outperforms existing methods in certain cases.
122233994
An efficient method for evaluating the integral of a class of highly oscillatory functions
Highly oscillatory integrals require special techniques for their effective evaluation. Various studies have been conducted to find computational methods for evaluating such integrals. In this paper we present an efficient numerical method to evaluate a class of generalised Fourier integrals (on a line or a square) with integrands of the form f(x)e^i^k^g^(^x^), under the assumption that in the domain of integration, both f and g are sufficiently smooth and that g does not have any stationary/critical points. Numerical analysis and results are given to illustrate the effectiveness of our method for computing generalised Fourier integrals.
25215706
On Two Variants of an Algebraic Wavelet Preconditioner
A recursive method of constructing preconditioning matrices for the nonsymmetric stiffness matrix in a wavelet basis is proposed for solving a class of integral and differential equations. It is based on a level-by-level application of the wavelet scales decoupling the different wavelet levels in a matrix form just as in the well-known nonstandard form. The result is a powerful iterative method with built-in preconditioning leading to two specific algebraic multilevel iteration algorithms: one with an exact Schur preconditioning and the other with an approximate Schur preconditioning. Numerical examples are presented to illustrate the efficiency of the new algorithms.
16063876
How to play a coloring game against a color-blind adversary
We study the problem of conflict-free (CF) coloring of a set of points in the plane, in an online fashion, with respect to halfplanes, nearly-equal axis-parallel rectangles, and congruent disks. As a warm-up exercise, the online CF coloring of points on the line with respect to intervals is also considered. We present randomized algorithms in the oblivious adversary model, where the adversary does not see the colors used. For the problems considered, the algorithms always produce valid CF colorings, and use O(logn) colors with high probability (these bounds are optimal in the worst case). Our randomized online algorithms are considerably simpler than previous algorithms for this problem and use fewer colors.We also present a deterministic algorithm for the CF coloring of points in the plane with respect to nearly-equal axis-parallel rectangles, using O(polylog(n)) colors. This is the first efficient deterministic online CF coloring algorithm for this problem.
1262783
An Immunity-Based Intrusion Detection Solution for Database Systems
Database intrusion detection has been an important research area in database security. It focuses on malicious transaction attacks, which cannot be handled by traditional database security mechanisms, such as authorization, access control, integrity control, and so on. Although there have appeared some intrusion detection systems, current researches on malicious transaction detection are limited in accuracy and efficiency. Inspired by natural immune system, we propose a novel immunity-based intrusion detection solution for database system in this paper. It provides an additional layer of defense against DBMS misuse, especially malicious transactions. The ability to learn and to adapt to the environment dynamically entitles the system to detect both known and unknown malicious transaction intrusions efficiently. Simulations show that the database intrusion detection system based on data immunity can accelerate detection of malicious transaction attacks and improve its accuracy without causing any other performance penalty.
1589839
Optimization of the Sliding Window Size for Protein Structure Prediction
Sliding window based methods are relatively often applied in prediction of various aspects related to protein structure. Despite their wide spread use, researchers did not establish a standard related to the size of the window, i.e., window sizes ranging between 7 and 17 residues were used in the past. To this end, this paper performs a computational study based on a probabilistic approach that aims at finding an optimal sliding window size. The results shows that formation of helical structure can be affected by amino acids (AAs) that are up to 9 positions away in the sequence, while the formation of coils and strands can be affected by AAs that are up to 3 and 6 positions away, respectively. Overall, our results suggest that a sliding window with 19 residues is optimal for secondary structure prediction, while for a specific prediction tasks, such as prediction of p-strands, a smaller window size is sufficient. Finally, the 20 AAs are categorized into five groups based on their influence of formation of the secondary structure. The finding related to the optimal window size was confirmed based on an independent experimental study related to the prediction of secondary protein structure
11647155
Methods of Combining Multiple Classifiers with Different Features and Their Applications to Text-Independent Speaker Identification
In practical applications of pattern recognition, there are often different features extracted from raw data which needs recognizing. Methods of combining multiple classifiers with different features are viewed as a general problem in various application areas of pattern recognition. In this paper, a systematic investigation has been made and possible solutions are classified into three frameworks, i.e. linear opinion pools, winner-take-all and evidential reasoning. For combining multiple classifiers with different features, a novel method is presented in the framework of linear opinion pools and a modified training algorithm for associative switch is also proposed in the framework of winner-take-all. In the framework of evidential reasoning, several typical methods are briefly reviewed for use. All aforementioned methods have already been applied to text-independent speaker identification. The simulations show that results yielded by the methods described in this paper are better than not only the individual classifiers' but also ones obtained by combining multiple classifiers with the same feature. It indicates that the use of combining multiple classifiers with different features is an effective way to attack the problem of text-independent speaker identification.
14878951
The orienteering problem in the plane revisited
We consider the <i>orienteering problem</i>: Given a set <i>P</i> of <i>n</i> points in the plane, a starting point <i>r</i> ∈ <i>P</i>, and a length constraint <i>B</i>, one needs to find a tour starting at <i>r</i> that visits as many points of <i>P</i> as possible and of length not exceeding <i>B</i>. We present a (1−ε)-approximation algorithm for this problem that runs in <i>n</i><sup><i>O</i>(1/ε)</sup> time, and visits at least (1−ε)<i>k</i><sub>opt</sub> points of <i>P</i>, where <i>k</i><sub>opt</sub> is the number of points visited by the optimal solution. This is the first polynomial time approximation scheme (PTAS) for this problem. The algorithm also works in higher dimensions.