Factoring wavelet transforms into lifting steps

This article is essentially tutorial in nature. We show how any discrete wavelet transform or two band subband filtering with finite filters can be decomposed into a finite sequence of simple filtering steps, which we call lifting steps but that are also known as ladder structures. This decomposition corresponds to a factorization of the polyphase matrix of the wavelet or subband filters into elementary matrices. That such a factorization is possible is well-known to algebraists (and expressed by the formulaSL(n;R[z, z⁻¹])=E(n;R[z, z⁻¹])); it is also used in linear systems theory in the electrical engineering community. We present here a self-contained derivation, building the decomposition from basic principles such as the Euclidean algorithm, with a focus on applying it to wavelet filtering. This factorization provides an alternative for the lattice factorization, with the advantage that it can also be used in the biorthogonal, i.e., non-unitary case. Like the lattice factorization, the decomposition presented here asymptotically reduces the computational complexity of the transform by a factor two. It has other applications, such as the possibility of defining a wavelet-like transform that maps integers to integers. Research Tutorial Acknowledgements and Notes. Page 264.  

非线性跟踪─微分器

非线性跟踪一微分器韩京清，王伟（中国科学院系统科学研究所，北京１０００８０）国家自然科学基金资助课题．１９９２年７月２５日收到，１９９３年２月１７日收到修改稿．一、前言在实际工程问题中，常存在由不连续或带随机噪声的量测信号合理地提取连续信号及微分信号...  

A new polynomial-time algorithm for linear programming

We present a new polynomial-time algorithm for linear programming. In the worst case, the algorithm requiresO(n ^3.5 L) arithmetic operations onO(L) bit numbers, wheren is the number of variables andL is the number of bits in the input. The running-time of this algorithm is better than the ellipsoid algorithm by a factor ofO(n ^2.5). We prove that given a polytopeP and a strictly interior point a εP, there is a projective transformation of the space that mapsP, a toP′, a′ having the following property. The ratio of the radius of the smallest sphere with center a′, containingP′ to the radius of the largest sphere with center a′ contained inP′ isO(n). The algorithm consists of repeated application of such projective transformations each followed by optimization over an inscribed sphere to create a sequence of points which converges to the optimal solution in polynomial time. This is a substantially revised version of the paper presented at the Symposium on Theory of Computing, Washington D. C., April 1984.  

MV-代数、BL-代数、R0-代数与多值逻辑

证明三种不同形式的MV－代数刻画的等价性，分析MV－代数、BL－代数与R0代数的逻辑背景，提出若干可进一步研究的课题。  

The ergodic theory of Markov chains in random environments

Summary A general formulation of the stochastic model for a Markov chain in a random environment is given, including an analysis of the dependence relations between the environmental process and the controlled Markov chain, in particular the problem of feedback. Assuming stationary environments, the ergodic theory of Markov processes is applied to give conditions for the existence of finite invariant measure (equilibrium distributions) and to obtain ergodic theorems, which provide results on convergence of products of random stochastic matrices. Coupling theory is used to obtain results on direct convergence of these products and the structure of the tail -field. State properties including classification and communication properties are discussed.  

A nonsmooth version of Newton's method

Newton's method for solving a nonlinear equation of several variables is extended to a nonsmooth case by using the generalized Jacobian instead of the derivative. This extension includes the B-derivative version of Newton's method as a special case. Convergence theorems are proved under the condition of semismoothness. It is shown that the gradient function of the augmented Lagrangian forC ²-nonlinear programming is semismooth. Thus, the extended Newton's method can be used in the augmented Lagrangian method for solving nonlinear programs.This author's work is supported in part by the Australian Research Council.This author's work is supported in part by the National Science Foundation under grant DDM-8721709.  

Anisotropic interpolation and quasi-Wilson element for narrow quadrilateral meshes

In this paper an anisotropic interpolation theorem is presentedthat can be easily used to check the anisotropy of an element.A kind of quasi-Wilson element is considered for second-orderproblems on narrow quadrilateral meshes for which the usualregularity condition _K/h_K c₀ > 0 is not satisfied, whereh_K is the diameter of the element K and _K is the radius of thelargest inscribed circle in K. Anisotropic error estimates ofthe interpolation error and the consistency error in the energynorm and the L²-norm are given. Furthermore, we give a Poincaréinequality on a trapezoid which improves a result of eniek.  

THE SINGULARLY PERTURBED PROBLEM FOR COMBUSTION REACTION DIFFUSION

1. IntroductionThe anchor discussed a class of problems for the nonlinear ordinary differential equations(of. [1-3]) and the reaction dimsion equations (of. [4-7]).Now we consider a model of the combustion reaction decision problem as follows:where y is a density of combustion flame, s denotes the rate of diffusion effect for reactionspeed, whiCh is a small positive parameter, t is a position of combustion, functions y - t andy t are the positions of the matter for fuel and chide respectivel…  

The search for chromatically unique graphs

The number of vertex-colourings of a simple graphG in not more than colours is a polynomial in. This polynomial, denoted byP(G, ), is called the chromatic polynomial ofG. A graphG is said to be chromatically unique, in short-unique, ifH G for any graphH withP(H, ) = P(G, ). Since the appearance of the first paper on-unique graphs by Chao and Whitehead in 1978, various families of and several results on such graphs have been obtained successively, especially during the last five years. It is the aim of this expository paper to give a survey on most of the works done on-unique graphs. A number of related problems and conjectures are also included.1980 Mathematical Subject Classification. Primary 05C15This work was done while the author was visiting the Department of Mathematics, National University of Singapore.