We prove that (1 - o(l)) ln n is a threshold below which set cover cannot be approximated efficiently, unless NP has slightly superpolynomial time algorithms. This closes the gap (up to low order terms) between the ra...
详细信息
This paper is concerned with improvement in optical image quality by image restoration. Image restoration is an ill-posed inverse problem which in volves the removal or minimization of degradations caused by noise and...
详细信息
This paper is concerned with improvement in optical image quality by image restoration. Image restoration is an ill-posed inverse problem which in volves the removal or minimization of degradations caused by noise and blur in an image, resulting from, in this case, imaging through a medium. Our work here concerns the use of the underlying Toeplitz structure of such problems, and as sociated techniques for accelerating the convergence of iterative image restoration computations. Denoising methods, including total variation minimization, followed by segmentation-based preconditioning methods for minimum residual conjugate gradient iterations, are investigated. Regularization is accomplished by segmenting the image into (smooth) segments and varying the preconditioners across the segments. By taking advantage of the Toeplitz structure, our algorithms can be implemented with computational complexity of only O(ln2log n), where n2 is the number of pixels in the image and l is the number of segments used. Also, parallelization is straightforward. Numerical tests are reported for atmospheric imaging problems, including the case of spatially varying blur.
We apply and extend some well-known and some recent techniques from algebraic residue theory in order to relate to each other two major subjects of algebraic and numerical computing, that is, computations with structu...
详细信息
We apply and extend some well-known and some recent techniques from algebraic residue theory in order to relate to each other two major subjects of algebraic and numerical computing, that is, computations with structured matrices and solving a system of polynomial equations. In the first part of our paper, we extend the Toeplitz and Hankel structures of matrices and some of their known properties to some new classes of structured (quasi-Hankel and quasi-Toeplitz) matrices, naturally associated to systems of-multivariate polynomial equations. In the second part of the paper, we prove some relations between these structured matrices, which extend the classical relations of the univariate case.
The method of complexity regularization is applied to one hidden-layer radial basis function networks to derive regression estimation bounds and convergence rates for classification. Bounds on the expected risk in ter...
详细信息
We consider the problem of reconstructing the shape of an object from multiple images related by translations, when only small portions of the object can be observed in each image. Lindenbaum and Bruckstein (1988) hav...
详细信息
We consider two-dimensional and axially symmetric critical-state problems in type-II superconductivity, and show that these problems are equivalent to evolutionary quasivariational inequalities. In a special case, whe...
We consider two-dimensional and axially symmetric critical-state problems in type-II superconductivity, and show that these problems are equivalent to evolutionary quasivariational inequalities. In a special case, where the inequalities become variational, the existence and uniqueness of the solution are proved.
Multiway trees, also known as m-ary search trees, are data structures generalising binary search trees. A common probability model for analysing the behaviour of these structures is the random permutation model. The p...
The oriented strip packingproblem is very important to manufacturing industries: given a strip of fixed width and a set of many (> 100) nonconvex polygons with 1, 2, 4, or 8 orientations permitted for each polygon,...
详细信息
We investigate the complexity of depth-3 threshold circuits with majority gates at the output, possibly negated AND gates at level two, and MODm gates at level one. We show that the fan-in of the AND gates can be redu...
详细信息
We investigate the complexity of depth-3 threshold circuits with majority gates at the output, possibly negated AND gates at level two, and MODm gates at level one. We show that the fan-in of the AND gates can be reduced to O(log n) in the case where m is unbounded, and to a constant in the case where m is constant. We then use these upper bounds to derive exponential lower bounds for this class of circuits. In the unbounded m case, this yields a new proof of a lower bound of Grolmusz;in the constant m case, our result sharpens his lower bound. In addition, we prove an exponential lower bound if OR gates are also permitted on level two and m is a constant prime power.
暂无评论