Anisotropic smoothness spaces via level sets

It has been understood for sometime that the classical smoothness spaces, such as the Sobolev and Besov classes, are not satisfactory for certain problems in image processing and nonlinear PDEs. Their deficiency lies in their isotropy. Functions in these smoothness spaces must be simultaneously smooth in all directions. The anisotropic generalizations of these spaces also have the deficiency that they are biased in coordinate directions. While they allow different smoothness in certain directions, these directions must be aligned to the coordinate axes. In the application areas mentioned above, it would be desirable to measure smoothness in new ways that would allow one to have more local control over the smoothness directions. We introduce one possible approach to this problem based on defining smoothness via level sets. We present this approach in the case of functions defined on ?^d. Our smoothness spaces depend on two smoothness indices (s₁, s₂). The first reflects the smoothness of the level sets of the function, while the second index reflects how smoothly the level sets themselves are changing. As a motivation, we start with d = 2 and investigate Besov smooth domains. © 2007 Wiley Periodicals, Inc.     

Edge-Directions of Standard Polyhedra with Applications to Network Flows

Recent results show that edge-directions of polyhedra play an important role in (combinatorial) optimization; in particular, a d-dimensional polyhedron with |D| distinct edge-directions has at most O(|D|^d-1) vertices. Here, we obtain a characterization of the directions of edges that are adjacent to a given vertex of a standard polyhedron of the form P = {x : Ax = b, l⩽ x⩽ u, tightening a standard necessary condition which asserts that such directions must be minimal support solutions of the homogenous equation Ax = 0 which are feasible at the given vertex. We specialize the characterization for polyhedra that correspond to network flows, obtaining a graph characterization of circuits which correspond to edge-directions. Applications to partitioning polyhedra are discussed. Research of these authors was supported by a grant from ISF – the Israel Science Foundation, by a VPR grant at the Technion, and by the Fund for the Promotion of Research at the Technion.     

Directional maximal operators with smooth densities

We study directional maximal operators on ?ⁿ with smooth densities. We prove that if the classical directional maximal operator in a given set of directions is weak type (1, 1), then the corresponding smooth‐density maximal operator in that set of directions will be bounded on L^q for q suitably large, depending on the order of the stationary points of the density function. In contrast to the classical case, if q is too small, the smooth density operator need not be bounded on L^q. Improving upon previously known results, we also establish that if the density function has only finitely many extreme points, each of finite order, then any maximal operator in a finite sum of diadic directions is bounded on all L^q for q > 1 (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Regularity of limits of noncollapsing sequences of manifolds

We prove that iterated spaces of directions of a limit of a noncollapsing sequence of manifolds with lower curvature bound are topologically spheres. As an application we show that for any finite dimensional Alexandrov space X ⁿ with there exists an Alexandrov space Y homeomorphic to X which cannot be obtained as such a limit. Submitted: December 2000, Revised: March 2001.     

Some remarks on the Fefferman-Stein inequality

We investigate the Fefferman-Stein inequality related to a function f and the sharp maximal function f ^# on a Banach function space X. It is proved that this inequality is equivalent to a certain boundedness property of the Hardy-Littlewood maximal operator M. The latter property is shown to be self-improving. We apply our results in several directions. First, we show the existence of nontrivial spaces X for which the lower operator norm of M is equal to 1. Second, in the case when X is the weighted Lebesgue space L ^p (w), we obtain a new approach to the results of Sawyer and Yabuta concerning the C _p condition.     

A New Second-Order Infeasible Primal-Dual Path-Following Algorithm for Symmetric Optimization

In this article, we propose a new second-order infeasible primal-dual path-following algorithm for symmetric cone optimization. The algorithm further improves the complexity bound of a wide infeasible primal-dual path-following algorithm. The theory of Euclidean Jordan algebras is used to carry out our analysis. The convergence is shown for a commutative class of search directions. In particular, the complexity bound is 𝒪(r^5/4log ?^?1) for the Nesterov-Todd direction, and 𝒪(r^7/4log ?^?1) for the xs and sx directions, where r is the rank of the associated Euclidean Jordan algebra and ? is the required precision. If the starting point is strictly feasible, then the corresponding bounds can be reduced by a factor of r^3/4. Some preliminary numerical results are provided as well.     

Generating and counting valid patterns in routes between two points

Given two points on a plane, any rectilinear route between them can be specified by directions and lengths of constituent line segments. A word (pattern) over the alphabetN, E, S, andW is defined to represent a sequence of directions. The length of each line segment is ignored. In this paper we characterize and count all valid words, that is, those words representing non-selfcrossing routes.Notation V _n The set of all valid words of lengthn. - P ⁿ The set of all words of lengthn.     

Graded Modules Over the q-Analog Virasoro-Like Algebra

In this paper, we deal with the classification of the irreducible Z-graded and Z ²-graded modules with finite dimensional homogeneous subspaces for the q analog Virasoro-like algebra L. We first prove that a Z-graded L-module must be a uniformly bounded module or a generalized highest weight module. Then we show that an irreducible generalized highest weight Z-graded module with finite dimensional homogeneous subspaces must be a highest (or lowest) weight module and give a necessary and sufficient condition for such a module with finite dimensional homogeneous subspaces. We use the Z-graded modules to construct a class of Z ²-graded irreducible generalized highest weight modules with finite dimensional homogeneous subspaces. Finally, we classify the Z ²-graded L-modules. We first prove that a Z ²-graded module must be either a uniformly bounded module or a generalized highest weight module. Then we prove that an irreducible nontrivial Z ²-graded module with finite dimensional homogeneous subspaces must be isomorphic to a module constructed as above. As a consequence, we also classify the irreducible Z-graded modules and the irreducible Z ²-graded modules with finite dimensional homogeneous subspaces and center acting nontrivial. Supported by the National Science Foundation of China (No 10671160), the China Postdoctoral Science Foundation (No. 20060390693), the Specialized Research fund for the Doctoral Program of Higher Education (No.20060384002), and the New Century Talents Supported Program from the Education Department of Fujian Province.     

The compactness of adaptive routing tables

The compactness of a routing table is a complexity measure of the memory space needed to store the routing table on a network whose nodes have been labelled by a consecutive range of integers. It is defined as the smallest integer k such that, in every node u, every set of labels of destinations having the same output in the table of u can be represented as the union of k intervals of consecutive labels. While many works studied the compactness of deterministic routing tables, few of them tackled the adaptive case when the output of the table, for each entry, must contain a fixed number α of routing directions. We prove that every n-node network supports shortest path routing tables of compactness at most n/α for an adaptiveness parameter α, whereas we show a lower bound of n/α^O(1).     

Embeddings through discrete sets of balls

We investigate whether a Stein manifold M which allows proper holomorphic embedding into ℂ ⁿ can be embedded in such a way that the image contains a given discrete set of points and in addition follow arbitrarily close to prescribed tangent directions in a neighbourhood of the discrete set. The infinitesimal version was proven by Forstnerič to be always possible. We give a general positive answer if the dimension of M is smaller than n/2 and construct counterexamples for all other dimensional relations. The obstruction we use in these examples is a certain hyperbolicity condition.     

Geometric Tomography of Convex Cones

The parallel X-ray of a convex set K⊂ℝ ⁿ in a direction u is the function that associates to each line l, parallel to u, the length of K∩l. The problem of finding a set of directions such that the corresponding X-rays distinguish any two convex bodies has been widely studied in geometric tomography. In this paper we are interested in the restriction of this problem to convex cones, and we are motivated by some applications of this case to the covariogram problem. We prove that the determination of a cone by parallel X-rays is equivalent to the determination of its sections from a different type of tomographic data (namely, point X-rays of a suitable order). We prove some new results for the corresponding problem which imply, for instance, that convex polyhedral cones in ℝ³ are determined by parallel X-rays in certain sets of two or three directions. The obtained results are optimal.     

On linear vertex-arboricity of complementary graphs

The linear vertex-arboricity ρ(G) of a graph G is defined to be the minimum number of subsets into which the vertex set of G can be partitioned such that each subset induces a linear forest. In this paper, we give the sharp upper and lower bounds for the sum and product of linear vertex-arboricities of a graph and its complement. Specifically, we prove that for any graph G of order p. and for any graph G of order p = (2n + 1)², where n ? Z⁺, 2n + 2 ≦ ρ(G) + ρ(G ).     

Correctors for some asymptotic problems

In the theory of anisotropic singular perturbation boundary value problems, the solution u _ɛ does not converge, in the H ¹-norm on the whole domain, towards some u ₀. In this paper we construct correctors to have good approximations of u _ɛ in the H ¹-norm on the whole domain. Since the anisotropic singular perturbation problems can be connected to the study of the asymptotic behaviour of problems defined in cylindrical domains becoming unbounded in some directions, we transpose our results for such problems.     

Zero-sum problems with subgroup weights

In this note, we generalize some theorems on zero-sums with weights from [1], [4] and [5] in two directions. In particular, we consider ℤ _p ^d for a general d and subgroups of Z* _p as weights.     

A Subcritical Spatially Homogeneous Branching Process May Have an Equilibrium

We characterize those Banach spaces X for which K(X ⊕_p X) is an M-ideal in L(X ⊕_p X) by means of a variant of the compact metric approximation property. As a consequence we obtain that such a space X must be hereditarily l^p-rich.     

Maps preserving square-zero matrices on the algebra consisting of all upper triangular matrices

Let F be a field, T _n (F) (respectively, N _n (F)) the matrix algebra consisting of all n × n upper triangular matrices (respectively, strictly upper triangular matrices) over F. A ∈ T _n (F) is said to be square zero if A ² = 0. In this article, we firstly characterize non-singular linear maps on N _n (F) preserving square-zero matrices in both directions, then by using it we determine non-singular linear maps on T _n (F) preserving square-zero matrices in both directions.     

Explicit Geometric Integration of Polynomial Vector Fields

We present a unified framework in which to study splitting methods for polynomial vector fields in R ⁿ . The vector field is to be represented as a sum of shears, each of which can be integrated exactly, and each of which is a function of k<n variables. Each shear must also inherit the structure of the original vector field: we consider Hamiltonian, Poisson, and volume-preserving cases. Each case then leads to the problem of finding an optimal distribution of points on an appropriate homogeneous space, generally the Grassmannians of k-planes or (in the Hamiltonian case) isotropic k-planes in R ⁿ . These optimization problems have the same structure as those of constructing optimal experimental designs in statistics.     

Rigidity of Quasicrystallic and <Emphasis Type="Italic">Z</Emphasis><Superscript><Emphasis Type="Italic">γ</Emphasis></Superscript>-Circle Patterns

The uniqueness of the orthogonal Z ^γ -circle patterns as studied by Bobenko and Agafonov is shown, given the combinatorics and some boundary conditions. Furthermore we study (infinite) rhombic embeddings in the plane which are quasicrystallic, that is, they have only finitely many different edge directions. Bicoloring the vertices of the rhombi and adding circles with centers at vertices of one of the colors and radius equal to the edge length leads to isoradial quasicrystallic circle patterns. We prove for a large class of such circle patterns which cover the whole plane that they are uniquely determined up to affine transformations by the combinatorics and the intersection angles. Combining these two results, we obtain the rigidity of large classes of quasicrystallic Z ^γ -circle patterns.     

Reduced bodies in normed planes

We say that a convex body R of a d-dimensional real normed linear space M ^d is reduced, if Δ(P) < Δ(R) for every convex body P ⊂ R different from R. The symbol Δ(C) stands here for the thickness (in the sense of the norm) of a convex body C ⊂ M ^d . We establish a number of properties of reduced bodies in M ². They are consequences of our basic Theorem which describes the situation when the width (in the sense of the norm) of a reduced body R ⊂ M ² is larger than Δ(R) for all directions strictly between two fixed directions and equals Δ(R) for these two directions.