Minimally Supported Frequency Composite Dilation Wavelets

A composite dilation wavelet is a collection of functions generating an orthonormal basis for L ²(ℝ ⁿ ) under the actions of translations from a full rank lattice and dilations by products of elements of non-commuting groups A and B. A minimally supported frequency composite dilation wavelet has generating functions whose Fourier transforms are characteristic functions of a lattice tiling set. In this paper, we study the case where A is the group of integer powers of some expanding matrix while B is a finite subgroup of the invertible n×n matrices. This paper establishes that with any finite group B together with almost any full rank lattice, one can generate a minimally supported frequency composite dilation wavelet system. The paper proceeds by demonstrating the ability to find such minimally supported frequency composite dilation wavelets with a single generator.     

Orthogonality criteria for compactly supported refinable functions and refinable function vectors

A refinable function φ(x):ℝⁿ→ℝ or, more generally, a refinable function vector Φ(x)=[φ₁(x),...,φ_r(x)]^T is an L¹ solution of a system of (vector-valued) refinement equations involving expansion by a dilation matrix A, which is an expanding integer matrix. A refinable function vector is called orthogonal if {φ_j(x−α):α∈ℤⁿ, 1≤j≤r form an orthogonal set of functions in L²(ℝⁿ). Compactly supported orthogonal refinable functions and function vectors can be used to construct orthonormal wavelet and multiwavelet bases of L²(ℝⁿ). In this paper we give a comprehensive set of necessary and sufficient conditions for the orthogonality of compactly supported refinable functions and refinable function vectors.     

Local Regularity of L∞ ∞-Refinable Function Vectors

This article discusses the local regularity of refinable function vectors associated with a dilation matrix M. Suppose that D is a complete set of representatives of Z^s/MZ^s. Under the assumptions that the self-affine tile T (M,D), associated with dilation matrix M and digit set D, has measure 1 and that the corresponding refinable function vector φ ∈ L_∞, we prove that there is a set H ? R^s of full measure such that the restriction φ|_H of φ on H has a positive Hölder exponent α(x) at every x ∈ H. Similar result holds for the derivatives of refinable function vectors provided that the dilation matrix is diagonalizable.     

Combinatorial Integer Labeling Theorems on Finite Sets with Applications

Tucker’s well-known combinatorial lemma states that, for any given symmetric triangulation of the n-dimensional unit cube and for any integer labeling that assigns to each vertex of the triangulation a label from the set {±1,±2,…,±n} with the property that antipodal vertices on the boundary of the cube are assigned opposite labels, the triangulation admits a 1-dimensional simplex whose two vertices have opposite labels. In this paper, we are concerned with an arbitrary finite set D of integral vectors in the n-dimensional Euclidean space and an integer labeling that assigns to each element of D a label from the set {±1,±2,…,±n}. Using a constructive approach, we prove two combinatorial theorems of Tucker type. The theorems state that, under some mild conditions, there exists two integral vectors in D having opposite labels and being cell-connected in the sense that both belong to the set {0,1} ⁿ +q for some integral vector q. These theorems are used to show in a constructive way the existence of an integral solution to a system of nonlinear equations under certain natural conditions. An economic application is provided.     

Dyadic Bivariate Fourier Multipliers for Multi-Wavelets in L2(R2)

The single 2 dilation orthogonal wavelet multipliers in one dimensional case and single A-dilation(where A is any expansive matrix with integer entries and|det A|=2) wavelet multipliers in high dimensional case were completely characterized by the Wutam Consortium(1998) and Z. Y. Li, et al.(2010). But there exist no more results on orthogonal multivariate wavelet matrix multipliers corresponding integer expansive dilation matrix with the absolute value of determinant not 2 in L~2(R~2). In this paper, we choose 2I2=(_0~2 _2~0)as the dilation matrix and consider the 2 I2-dilation orthogonal multivariate waveletΨ = {ψ_1, ψ_2, ψ_3},(which is called a dyadic bivariate wavelet) multipliers. We call the3 × 3 matrix-valued function A(s) = [ f_(i, j)(s)]_(3×3), where fi, jare measurable functions, a dyadic bivariate matrix Fourier wavelet multiplier if the inverse Fourier transform of A(s)( ψ_1(s), ψ_2(s), ψ_3(s)) ~T=( g_1(s), g_2(s), g_3(s))~ T is a dyadic bivariate wavelet whenever(ψ_1, ψ_2, ψ_3) is any dyadic bivariate wavelet. We give some conditions for dyadic matrix bivariate wavelet multipliers. The results extended that of Z. Y. Li and X. L.Shi(2011). As an application, we construct some useful dyadic bivariate wavelets by using dyadic Fourier matrix wavelet multipliers and use them to image denoising.     

Vector and matrix apportionment problems and separable convex integer optimization

The problems of (bi-)proportional rounding of a nonnegative vector or matrix, resp., are written as particular separable convex integer minimization problems. Allowing any convex (separable) objective function we use the notions of vector and matrix apportionment problems. As a broader class of problems we consider separable convex integer minimization under linear equality restrictions Ax = b with any totally unimodular coefficient matrix A. By the total unimodularity Fenchel duality applies, despite the integer restrictions of the variables. The biproportional algorithm of Balinski and Demange (Math Program 45:193–210, 1989) is generalized and derives from the dual optimization problem. Also, a primal augmentation algorithm is stated. Finally, for the smaller class of matrix apportionment problems we discuss the alternating scaling algorithm, which is a discrete variant of the well-known Iterative Proportional Fitting procedure.     

A Law of the Iterated Logarithm for Randomly Stopped Sums of Heavy Tailed Random Vectors

 Let be an i.i.d. sequence of -valued random vectors belonging to the generalized domain of semistable attraction of some nonnormal law. Assume further that is a sequence of positive integer valued random variables such that for some for some discrete positive random variable D, where we do not assume that and are independent. Let . Then various laws of the iterated logarithm for the norm of as well as the radial projection onto a unit vector θ are presented.     

Frames for vector spaces and affine spaces

A finite frame for a finite dimensional Hilbert space is simply a spanning sequence. We show that the linear functionals given by the dual frame vectors do not depend on the inner product, and thus it is possible to extend the frame expansion (and other elements of frame theory) to any finite spanning sequence for a vector space. The corresponding coordinate functionals generalise the dual basis (the case when the vectors are linearly independent), and are characterised by the fact that the associated Gramian matrix is an orthogonal projection. Existing generalisations of the frame expansion to Banach spaces involve an analogue of the frame bounds and frame operator.The potential applications of our results are considerable. Whenever there is a natural spanning set for a vector space, computations can be done directly with it, in an efficient and stable way. We illustrate this with a diverse range of examples, including multivariate spline spaces, generalised barycentric coordinates, and vector spaces over the rationals, such as the cyclotomic fields.     

A Law of the Iterated Logarithm for Randomly Stopped Sums of Heavy Tailed Random Vectors

 Let be an i.i.d. sequence of -valued random vectors belonging to the generalized domain of semistable attraction of some nonnormal law. Assume further that is a sequence of positive integer valued random variables such that for some for some discrete positive random variable D, where we do not assume that and are independent. Let . Then various laws of the iterated logarithm for the norm of as well as the radial projection onto a unit vector θ are presented. (Received 31 January 2000; in revised form 5 April 2000)     

On the integrality of an extreme solution to pluperfect graph and balanced systems

Let A be a nonnegative integer matrix, and let e denote the vector all of whose components are equal to 1. The pluperfect graph theorem states that if for all integer vectors b the optimal objective value of the linear program minse′xvbAx ? b, x ? 0 s is integer, then those linear programs possess optimal integer solutions. We strengthen this theorem and show that any lexicomaximal optimal solution to the above linear program (under any arbitrary ordering of the variables) is integral and an extreme point of sxvbAx ? b, x ? 0 s. We note that this extremality property of integer solutions is also shared by covering as well as packing problems defined by a balanced matrix A.     

Dissipative q-Dirac operator with general boundary conditions

In this paper, we consider the symmetric q-Dirac operator. We describe dissipative, accumulative, self-adjoint and the other extensions of such operators with general boundary conditions. We construct a self-adjoint dilation of dissipative operator. Hence, we determine the scattering matrix of dilation. Later, we construct a functional model of this operator and define its characteristic function. Finally, we prove that all root vectors of this operator are complete.     

On the dimension of the algebra generated by a boolean matrix

We investigate the subspace of the space of all n × n Boolean (0,1)-matrices, spanned by the powers of an arbitrary matrix. We estimate the maximum dimension of such spaces as a function of n and show that their bases consists of consecutive integer powers of the matrix, starting at I. We also determine the maximum dimension of the space spanned by the powers of as symmetric matrix and characterise the matrices achieving that maximum.     

Small Grid Embeddings of 3-Polytopes

We introduce an algorithm that embeds a given 3-connected planar graph as a convex 3-polytope with integer coordinates. The size of the coordinates is bounded by O(2^7.55n )=O(188 ⁿ ). If the graph contains a triangle we can bound the integer coordinates by O(2^4.82n ). If the graph contains a quadrilateral we can bound the integer coordinates by O(2^5.46n ). The crucial part of the algorithm is to find a convex plane embedding whose edges can be weighted such that the sum of the weighted edges, seen as vectors, cancel at every point. It is well known that this can be guaranteed for the interior vertices by applying a technique of Tutte. We show how to extend Tutte’s ideas to construct a plane embedding where the weighted vector sums cancel also on the vertices of the boundary face.     

Approximating disjoint-path problems using packing integer programs

In a packing integer program, we are given a matrix $A$ and column vectors $b,c$ with nonnegative entries. We seek a vector $x$ of nonnegative integers, which maximizes $c^{T}x,$ subject to $Ax \leq b.$ The edge and vertex-disjoint path problems together with their unsplittable flow generalization are NP-hard problems with a multitude of applications in areas such as routing, scheduling and bin packing. These two categories of problems are known to be conceptually related, but this connection has largely been ignored in terms of approximation algorithms. We explore the topic of approximating disjoint-path problems using polynomial-size packing integer programs. Motivated by the disjoint paths applications, we introduce the study of a class of packing integer programs, called column-restricted. We develop improved approximation algorithms for column-restricted programs, a result that we believe is of independent interest. Additional approximation algorithms for disjoint-paths are presented that are simple to implement and achieve good performance when the input has a special structure.Work partially supported by NSERC OG 227809-00 and a CFI New Opportunities Award. Part of this work was done while at the Department of Computer Science, Dartmouth College and partially by NSF Award CCR-9308701 and NSF Career Award CCR-9624828.This work was done while at the Department of Computer Science, Dartmouth College and partially supported by NSF Award CCR-9308701 and NSF Career Award CCR-9624828.     

Chvátal closures for mixed integer programming problems

Chvátal introduced the idea of viewing cutting planes as a system for proving that every integral solution of a given set of linear inequalities satisfies another given linear inequality. This viewpoint has proven to be very useful in many studies of combinatorial and integer programming problems. The basic ingredient in these cutting-plane proofs is that for a polyhedronP and integral vectorw, if max(wx|x P, wx integer} =t, thenwx t is valid for all integral vectors inP. We consider the variant of this step where the requirement thatwx be integer may be replaced by the requirement that be integer for some other integral vector . The cutting-plane proofs thus obtained may be seen either as an abstraction of Gomory's mixed integer cutting-plane technique or as a proof version of a simple class of the disjunctive cutting planes studied by Balas and Jeroslow. Our main result is that for a given polyhedronP, the set of vectors that satisfy every cutting plane forP with respect to a specified subset of integer variables is again a polyhedron. This allows us to obtain a finite recursive procedure for generating the mixed integer hull of a polyhedron, analogous to the process of repeatedly taking Chvátal closures in the integer programming case. These results are illustrated with a number of examples from combinatorial optimization. Our work can be seen as a continuation of that of Nemhauser and Wolsey on mixed integer cutting planes.Supported by Sonderforschungsbereich 303 (DFG) and by NSF Grant Number ECS-8611841.Supported by NSF Grant Number ECS-8418392 and Sonderforschungsbereich 303 (DFG), Institut für Ökonometrie und Operations Research, Universität Bonn, FR Germany.     

A Product Theorem for Intersection Families

We will consider a certain kind of intersection family: a family of vectors over a field of finite characteristic q, such that the generalized inner products of every q or fewer vectors take on prescribed values. For certain values of the parameters, these values distinguish the generalized inner product of any q distinct vectors, from that of any q vectors in which some vector is repeated.We will represent such an intersection family by its incidence matrix, and show that the matrix product of two such matrices is itself an intersection family of the type under consideration. If the factor families distinguish between generalized inner products of q vectors with or without repetition, then so does the product family.     

Linear Independence of Gabor Systems in Finite Dimensional Vector Spaces

We discuss the linear independence of systems ofmvectors in n-dimensional complex vector spaces where the m vectors are time-frequency shifts of one generating vector. Such systems are called Gabor systems. When n is prime, we show that there exists an open, dense subset with full-measure of such generating vectors with the property that any subset of n vectors in the corresponding full Gabor system of n² vectors is linearly independent. We derive consequences relevant to coding, operator identification and time-frequency analysis in general.     

Each four-celled animal tiles the plane

An animal A is a set of unit squares in the plane, parallel to the axes, and with corners at integer lattice points. We show that any animal A with four cells tiles the plane, in the sense that infinitely many copies of A, translated by integer vectors and possibly rotated through 90°, 180°, or 270°, can be placed so as to fill plane exactly without overlap.