Smoothness of Nonlinear Median-Interpolation Subdivision

We give a refined analysis of the Hölder regularity for the limit functions arising from a nonlinear pyramid algorithm for robust removal of non-Gaussian noise proposed by Donoho and Yu [6,7,17]. The synthesis part of this algorithm can be interpreted as a nonlinear triadic subdivision scheme where new points are inserted based on local quadratic polynomial median interpolation and imputation. We introduce the analogon of the Donoho–Yu scheme for dyadic refinement, and show that its limit functions are in C for >log₄(128/31)=1.0229.... In the triadic case, we improve the lower bound of >log₂(135/121)=0.0997... previously obtained in [6] to >log₃(135/53)=0.8510.... These lower bounds are relatively close to the anticipated upper bounds of log₂(16/7)=1.1982... in the dyadic, respectivly 1 in the triadic cases, and have been obtained by deriving recursive inequalities for the norm of second rather than first order differences of the sequences arising in the subdivision process.     

On equivalence of rearrangements of the Haar system in dyadic Hardy and BMO spaces

H={h ₁,I } — , . : , I ¦(I)¦=¦I¦, ¦I¦ — I. H H ={h _(I),I} . , , . L ^p .

---

---

Dedicated to Professor B. Szökefalvi-Nagy on his 75th birthday

---

This research was supported in part by MTA-NSF Grants INT-8400708 and 8620153.     

High order approximation of implicitly defined maps

Summary Approximations for the function implicitly defined by (u)=(u, (u)) are obtained via the iterative scheme _n(u)=(u, _n–1(u)). In this paper the uniform convergence of high order derivatives of _n to the corresponding derivatives of is proved. This result yields a high order approximation theorem for the input-output map generated by a nonlinear control system, using linear combinations of iterated integrals of the control.Lavoro eseguito nell'ambito del G.N.A.F.A. del C.N.R.     

Uniform boundedness of a family of set functions

Let be a ring of sets, X a normed space, : X ( ) a bounded family of triangular functions. The following generalized Nikodym theorem is established: the family {} is uniformly bounded on if and only if it is bounded on every sequence of pairwise disjoint sets of which the union is a part of some set in . An analogous criterion is established also for semiadditive functions. In addition, it is shown that uniform boundedness of a family of triangular functions is preserved in passing from a ring to the -ring it generates.Translated from Matematicheskie Zametki, Vol. 23, No. 6, pp. 855–861, June, 1978.     

Error estimates for the finite element solution of variational inequalities

Summary We study the mixed finite element approximation of variational inequalities, taking as model problems the so called obstacle problem and unilateral problem. Optimal error bounds are obtained in both cases.Supported in part by National Science Foundation grant MCS 75-09457, and by Office of Naval Research grant N00014-76-C-0369     

Beitrag zur Reduktion des Entscheidungsproblems auf Klassen von Hornformeln mit kurzen Alternationen

Ohne Zusammenfassung Zusatz bei der Korrektur: Ein vollständiger und korrekter Beweis für die Entscheidbarkeit der eingangs angeführten Aanderaaschen Klasse ((0, ), (, , ...)) erscheint demnächst im JSL (S.O. Aanderaa/H.R.Lewis: Prefix classes of Krom formulas). Ebendort wird auch die Reduktionstypeneigenschaft für ((0, ), (0, 0, )) und ((0, )), (0, 0, )) nachgewiesen, während ((0, ), (, )) sich als entscheidbar herausgestellt hat (s. E. Börger: Eine entscheidbare Klasse von Kromformeln. ZMLG 19 (1973), 117–120.) Der Kromsche Reduktionstyp konnte mittlerweile einerseits zu ((0, ), (0, 4)) verschärft werden (s. D. Rödding, E. Börger: The undecidability of (0, 4)-formulae with binary disjunctions, vorgetragen auf dem Logic Coll. Bristol 1973, ein abstract erscheint im JSL), andererseits kündigt H.R.Lewis die Reduktionstypeneigenschaft für ((0, ), (0, 1)) an (s. H.R.Lewis: Krom formulas with one dyadic predicate letter. Notices AMS 20, 5 (1973) A-500, abstr. no. 73T-E78.)Dieser Aufsatz geht aus der Dissertation [2] hervor, die dem Fachbereich Mathematik der Mathematisch-Naturwissenschaftlichen Fakultät der Universität Münster im Sommersemester 1971 vorgelegt worden ist. Die Ergebnisse stammen aus dem Wintersemester 1970/71. Eine Ankündigung der hauptsächlichen Resultate ist in den Notices of the American Mathematical Society 19, 2 (1972) A-333 unter der abstract no. * 72T-E24 erschienen.     

Embeddings of Lorentz—Marcinkiewicz spaces with mixed norms

X(Y) f -:X(Y)={fM(×): f_{X(Y)=f(x,.)YX<} . =(0, ), M (×) — , ×, X, Y, Z— . X(Y) Z(×).     

The Spectral Theory of Amenable Actions and Invariants of Discrete Groups

Let G denote a semisimple group, a discrete subgroup, B=G/P the Poisson boundary. Regarding invariants of discrete subgroups we prove, in particular, the following:(1) For any -quasi-invariant measure on B, and any probablity measure on , the norm of the operator () on L ²(B,) is equal to (), where is the unitary representation in L ²(X,), and is the regular representation of .(2) In particular this estimate holds when is Lebesgue measure on B, a Patterson–Sullivan measure, or a -stationary measure, and implies explicit lower bounds for the displacement and Margulis number of (w.r.t. a finite generating set), the dimension of the conformal density, the -entropy of the measure, and Lyapunov exponents of .(3) In particular, when G=PSL₂() and is free, the new lower bound of the displacement is somewhat smaller than the Culler–Shalen bound (which requires an additional assumption) and is greater than the standard ball-packing bound.We also prove that ()=_G() for any amenable action of G and L ¹(G), and conversely, give a spectral criterion for amenability of an action of G under certain natural dynamical conditions. In addition, we establish a uniform lower bound for the -entropy of any measure quasi-invariant under the action of a group with property T, and use this fact to construct an interesting class of actions of such groups, related to 'virtual' maximal parabolic subgroups. Most of the results hold in fact in greater generality, and apply for instance when G is any semi-simple algebraic group, or when is any word-hyperbolic group, acting on their Poisson boundary, for example.     

Chebyshev approximation to data by geometric elements

An algorithm is presented and proved correct, for the efficient approximation of finite point sets in ² and ³ by geometric elements such as circles, spheres and cylinders. It is shown that the approximation criterion used, viz. minimising the maximum orthogonal deviation, is best modelled mathematically through the concept of aparallel body. This notion, besides being a valuable tool for form assessment in metrology, contributes to approximation theory by introducing a new kind of approximation, here called geometric or orthogonal. This approach is closely related to but different from Chebyshev approximation.The work described is part of a Commission of the European Communities project (Contract 3327/1/0/158/89/9-BCR-UK(30)).     

Regularization of Nonlinear Ill-Posed Variational Inequalities and Convergence Rates

Let H be a Hilbert space and K be a nonempty closed convex subset of H. For f H, we consider the (ill-posed) problem of finding u K for which 0 for all v K, where A : H H is a monotone (not necessarily linear) operator. We study the approximation of the solutions of the variational inequality by using the following perturbed variational inequality: for f H, f – f , find u, K for which 0 for all v K, where , , and are positive parameters, and K, a perturbation of the set K, is a nonempty closed convex set in H. We establish convergence and a rate O(1 / 3) of convergence of the solutions of the regularized variational inequalities to a solution of the original variational inequality using the Mosco approximation of closed convex sets, where A is a weakly differentiable inverse-strongly-monotone operator.     

Rudiments of an average case complexity theory for piecewise-linear path following algorithms

We examine the efficiency of PL path following algorithms in followingF _T ^-1 (0), whereF _T is the PL approximation, induced by the simplicial triangulationT, to a mapf: ^{n n-1}. In particular, we consider the problem of determining an upper bound on the expected number of pivots made per unit length off ^–1(0) that is approximated. We show that if the sizes of the simplices ofT are sufficiently small, where sufficiently small is an explicitly given quantity dependent on measurements of how nicef is, then the average directional density ofT, as introduced by Todd, really does give a good approximation to the expected number of pivots made, confirming what researchers have believed on intuitive grounds for a decade. Because what constitutes sufficiently small is a precisely given quantity, i.e., non-asymptotic, we are able to provide some rigorous justification for the claim that the expected number of pivots grows only polynomially inn, the number of variables.Several other issues are also examined.Research supported by an NSF Mathematical Sciences Postdoctoral Research Fellowship. This research was performed while the author was a member of the Mathematical Sciences Research Institute, Berkeley, California.     

Perturbation of the poles of the scattering matrix under variation of the boundary condition

The behavior of the poles z_n(), n=1,2,... of the scattering matrix of the operatorl u=–u(x), x , (u/n)+(x)u|=0 as 0 is considered. It is proved that |z_n()–z_n|=0(^(1/2)qn), where q_n is the order of the pole of the scattering matrix for the operator ₀u=–u, u/=0.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 117, pp. 183–191, 1981.     

Projection methods for non-linear programming

Several algorithms are presented for solving the non-linear programming problem, based on variable-metric projections of the gradient of the objective function into a local approximation to the constraints. The algorithms differ in the nature of this approximation. Inequality constraints are dealt with by selecting at each step a subset of active constraints to treat as equalities, this subset being the smallest necessary to ensure that the new point remains feasible. Some numerical results are given for the Colville problems.Paper presented at the 7^th Mathematical Programming Symposium, The Hague, September 1970.     

Hybrid programs: Linear and least-distance

We consider a quadratic program equivalent to the general problem of minimizing a convex quadratic function of many variables subject to linear inequality constraints.In previous work [12], one of us presented an algorithm related to such problems, and classified them under combinatorial equivalence. The classification contained linear programs at one end (where the function has zero quadratic part) and least-distance programs at the other. A least-distance program is a problem of finding a point of a convex polyhedron which is at least distance from a given point; such programs have been studied by one of us [15, 17] and were shown to correspond to that case of the general problem where the function has positive definite quadratic part.We now extend the work on least-distance programs to those programs intermediate between linear and least-distance (called essentially bisymmetric in [12]), and show that such programs are really hybrids, with traits inherited from both parent programs: linear and leastdistance.This paper was presented at the 7th Mathematical Programming Symposium 1970, The Hague, The Netherlands.This work was supported in part by Office of Naval Research Contract No. N00014-67-A-0151-0010 (Princeton University).     

Best approximation and best unilateral approximation of the kernel of a biharmonic equation and optimal renewal of the values of operators

For the classB _p , 0 < 1, 1p , of 2-periodic functions of the form f(t)=u(,t), whereu (,t) is a biharmonic function in the unit disk, we obtain the exact values of the best approximation and best unilateral approximation of the kernel K(t) of the convolution f= K *g, gl, with respect to the metric of L₁. We also consider the problem of renewal of the values of the convolution operator by using the information about the values of the boundary functions.Translated from Ukrainskii Matematicheskii Zhurnal, Vol.47, No. 11, pp. 1549–1557, November, 1995.     

Convergence of random products of compact contractions in Hilbert space

Let {T₁, ..., T_N} be a finite set of linear contraction mappings of a Hilbert space H into itself, and let r be a mapping from the natural numbers N to {1, ..., N}. One can form S_n=T_r(n)...T_r(1) which could be described as a random product of the T_i's. Roughly, the S_n converge strongly in the mean, but additional side conditions are necessary to ensure uniform, strong or weak convergence. We examine contractions with three such conditions. (W): x_n1, Tx_n1 implies (I-T)x_n0 weakly, (S): x_n1, Tx_n1 implies (I-T)x_n0 strongly, and (K): there exists a constant K>0 such that for all x, (I-T)x²K(x²–Tx²).We have three main results in the event that the T_i's are compact contractions. First, if r assumes each value infinitely often, then S_n converges uniformly to the projection Q on the subspace _i= ₁ ^N [x|T_ix=x]. Secondly we prove that for such compact contractions, the three conditions (W), (S), and (K) are equivalent. Finally if S=S(T₁, ..., T_N) denotes the algebraic semigroup generated by the T_i's, then there exists a fixed positive constant K such that each element in S satisfies (K) with that K.     

Waterman classes and spherical partial sums of double Fourier series

f(x,y) ₀BV(T²), ={1/n} _n=1 .

---

---

Dedicated to Professor Károly Tandori, the outstanding mathematician and academician on his seventieth birthday

---

This work was done under the financial support of the Russian Foundation for Fundamental Scientific Research, Grant 93-01-00240.     

Hankel operators and problems of best approximation of unbounded functions

For each function f, f VMO, there exists a unique function f₀, analytic in the circle and such that f–f₀=_f{gVMO_A}. We define the operator of best approximation (nonlinear) A, Af=f₀, fVMO, In the paper one considers the question of the preservation of a class under the action of the operator i.e. finding the classes X, X VMO, AX X. One investigates the classes X containing unbounded functions. It is proved that if P_X is the space of the symbols of the Hankel operators from a Banach space E of functions into the Hardy space H², then AX X. For E one can take almost any space.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 141, pp. 5–17, 1985.     

Infinitesimal,first order bendings of smooth,convex surfaces of revolution subject to conic,sleeve-like constraints along the boundary

We prove that on a closed, smooth, convex surface of revolution , whose poles are not flattening points, there exists only a countable set of parallels _n. Each of these parallels cuts surface into two parts so that one of the parts, , admits nontrivial, infinitesimal bendings in the process of which all the points of its boundary _n are displaced on a preassigned, conic sleeve K that is coaxial with the surface. The sequence of such parallels _n converges to parallel ^*, which has the following properties: 1) the tangent cone to surface along ^* is orthogonal to sleeve K; 2) surface , cut off from surface by parallel ^*, has rigidity of first order in the indicated class of bendings.Translated from Ukrainskii Geometricheskii Sbornik, No. 33, pp. 3–8, 1990.     

Some inequalities about the covering radius of Reed-Muller codes

Let R(r, m) be the rth order Reed-Muller code of length 2 ^m , and let (r, m) be its covering radius. We prove that if 2 k m - r - 1, then (r + k, m + k) (r, m + 2(k - 1). We also prove that if m - r 4, 2 k m - r - 1, and R(r, m) has a coset with minimal weight (r, m) which does not contain any vector of weight (r, m) + 2, then (r + k, m + k) (r, m) + 2k(. These inequalities improve repeated use of the known result (r + 1, m + 1) (r, m).This work was supported by a grant from the Research Council of Wright State University.