A Polynomial-Time Algorithm to Approximate the Mixed Volume within a Simply Exponential Factor

Let K=(K ₁,…,K _n ) be an n-tuple of convex compact subsets in the Euclidean space R ⁿ , and let V(⋅) be the Euclidean volume in R ⁿ . The Minkowski polynomial V _K is defined as V _K (λ ₁,…,λ _n )=V(λ ₁ K ₁+⋅⋅⋅+λ _n K _n ) and the mixed volume V(K ₁,…,K _n ) as

Symmetric block bases of sequences with large average growth

We show that if 0<ε≦1, 1≦p<2 andx ₁, …,x _n is a sequence of unit vectors in a normed spaceX such thatE ‖∑ _l ⁿ ε_i x _l‖≧n ^1/p, then one can find a block basisy ₁, …,y _m ofx ₁, …,x _n which is (1+ε)-symmetric and has cardinality at leastγn ^2/p-1(logn)⁻¹, where γ depends on ε only. Two examples are given which show that this bound is close to being best possible. The first is a sequencex ₁, …,x _n satisfying the above conditions with no 2-symmetric block basis of cardinality exceeding 2n ^2/p-1. This sequence is not linearly independent. The second example is a sequence which satisfies a lowerp-estimate but which has no 2-symmetric block basis of cardinality exceedingCn ^2/p-1(logn)^4/3, whereC is an absolute constant. This applies when 1≦p≦3/2. Finally, we obtain improvements of the lower bound when the spaceX containing the sequence satisfies certain type-condition. These results extend results of Amir and Milman in [1] and [2]. We include an appendix giving a simple counterexample to a question about norm-attaining operators.     

相关序的进一步研究

Let (X1,X2,…,Xn) and (Y1,Y2,…Yn) be real random vectors with the same marginal distributions,if (X1,X2,…,Xn)≤c(Y1,Y2,…Yn), it is showed in this paper that ∑i=1^n Xi≤cx∑i=1^n Yi and max1≤k≤n∑i=1^k Xi≤icx max1≤k≤n∑i=1^k Yi hold. Based on this fact,a more general comparison theorem is obtained.     

Ideal einstein,conformally flat and semi-symmetric immersions

Recently, B. Y. Chen introduced a new intrinsic invariant of a manifold, and proved that everyn-dimensional submanifold of real space formsR ^m (ε) of constant sectional curvature ε satisfies a basic inequality δ(n ₁,…,n _k )≤c(n ₁,…,n _k )H ²+b(n ₁,…,n _k )ε, whereH is the mean curvature of the immersion, andc(n ₁,…,n _k ) andb(n ₁,…,n _k ) are constants depending only onn ₁,…,n _k ,n andk. The immersion is calledideal if it satisfies the equality case of the above inequality identically for somek-tuple (n ₁,…,n _k ). In this paper, we first prove that every ideal Einstein immersion satisfyingn≥n ₁+…+n _k +1 is totally geodesic, and that every ideal conformally flat immersion satisfyingn≥n ₁+…+n _k +2 andk≥2 is also totally geodesic. Secondly we completely classify all ideal semi-symmetric hypersurfaces in real space forms. The author was supported by the NSFC and RFDP.     

Finitary reconstruction of a measure preserving transformation

This paper considers thefinitary reconstruction of an ergodic measure preserving transformationT of a complete separable metric spaceX from a single trajectoryx, Tx, …, or more generally, from a suitable reconstruction sequence x=x ₁,x ₂, … withx _i∈X. Ann-sample reconstruction is a functionT _n: X ⁿ⁺¹ →X; the map (·;x ₁, …,x _n)is treated as an estimate ofT(·) based on then initial elements of x. Given a reference probability measureμ ₀ and constantM>1, functionsT ₁,T ₂, … are defined, and it is shown that for everyμ with 1/M≤dμ/dμ ₀≤M, everyμ-preserving transformationT, and every reconstruction sequence x forT, the estimates (·;x ₁, …,x _nconverge toT in the weak topology. For the family of interval exchange transformations of [0, 1] a simple family of estimates is described and shown to be consistent both pointwise and in the strong topology. However, it is also shown that no finitary estimation scheme is consistent in the strong topology for the family of all ergodic Lebesgue measure preserving transformations of the unit interval, even if x is assumed to be a generic trajectory ofT. Supported in part by NSF Grant DMS-9501926.     

Affine cross-polytopes inscribed in a convex body

Let X be an affine cross-polytope, i.e., the convex hull of n segments A ₁ B ₁,…, A _n B _n in \mathbbRⁿ {\mathbb{R}^n} that have a common midpoint O and do not lie in a hyperplane. The affine flag F(X) of X is the chain O ∈ L ₁ ⊂⋯ ⊂ L _n = \mathbbRⁿ {\mathbb{R}^n} , where L _k is the k-dimensional affine hull of the segments A ₁ B ₁,…, A _k B _k , k ≤ n. It is proved that each convex body K ⊂ \mathbbRⁿ {\mathbb{R}^n} is circumscribed about an affine cross-polytope X such that the flag F(X) satisfies the following condition for each k ∈{2,…, n}:the (k−1)-planes of support at A _k and B _k to the body L _k ∩ K in the k-plane L _k are parallel to L _k −1.Each such X has volume at least V(K)/2 ^n(n−1)/2. Bibliography: 5 titles.     

Regression of polynomial statistics on the sample mean and natural exponential families

A polynomial Q = Q(X ₁, …, X _n ) of degree m in independent identically distributed random variables with distribution function F is an unbiased estimator of a functional q(α ₁(F), …, α _m (F)), where q(u ₁, …, u _m ) is a polynomial in u ₁, …, u _m and α _j (F) is the jth moment of F (assuming the necessary moment of F exists). It is shown that the relation E(Q | X ₁ + … + X n) = 0 holds if and only if q(α ₁(θ), …, α _m (θ)) ≡ 0, where α _j (θ) is the jth moment of the natural exponential family generated by F. This result, based on the fact that X ₁ + … + X n is a complete sufficient statistic for a parameter θ in a sample from a natural exponential family of distributions F _θ(x) = ∫_−∞ ^x e ^θu−k(θ) dF(u), explains why the distributions appearing as solutions of regression problems are the same as solutions of problems for natural exponential families though, at the first glance, the latter seem unrelated to the former.     

Restricted Isometry Property of Matrices with?Independent Columns and Neighborly Polytopes by?Random Sampling

This paper considers compressed sensing matrices and neighborliness of a centrally symmetric convex polytope generated by vectors ±X ₁,…,±X _N ∈ℝ ⁿ , (N≥n). We introduce a class of random sampling matrices and show that they satisfy a restricted isometry property with overwhelming probability. In particular, we prove that matrices with i.i.d. centered and variance 1 entries that satisfy uniformly a subexponential tail inequality possess the restricted isometry property with overwhelming probability. We show that such “sensing” matrices are valid for the exact reconstruction process of m-sparse vectors via ℓ ₁ minimization with m≤Cn/log ²(cN/n). The class of sampling matrices we study includes the case of matrices with columns that are independent isotropic vectors with log-concave densities. We deduce that if K⊂ℝ ⁿ is a convex body and X ₁,…,X _N ∈K are i.i.d. random vectors uniformly distributed on K, then, with overwhelming probability, the symmetric convex hull of these points is an m-centrally-neighborly polytope with m∼n/log ²(cN/n).     

Rates of Convergence of Means of Euclidean Functionals

Let L be the Euclidean functional with p-th power-weighted edges. Examples include the sum of the p-th power-weighted lengths of the edges in minimal spanning trees, traveling salesman tours, and minimal matchings. Motivated by the works of Steele, Redmond and Yukich (Ann. Appl. Probab. 4, 1057–1073, 1994, Stoch. Process. Appl. 61, 289–304, 1996) have shown that for n i.i.d. sample points {X ₁,…,X _n } from [0,1] ^d , L({X ₁,…,X _n })/n ^(d−p)/d converges a.s. to a finite constant. Here we bound the rate of convergence of EL({X ₁,…,X _n })/n ^(d−p)/d . Y. Koo supported by the BK21 project of the Department of Mathematics, Sungkyunkwan University. S. Lee supported by the BK21 project of the Department of Mathematics, Yonsei University.     

Central polynomials and matrix invariants

LetK be a field, charK=0 andM _n (K) the algebra ofn×n matrices overK. If λ=(λ₁,…,λ _m ) andμ=(μ ₁,…,μ _m ) are partitions ofn ² let wherex ₁,…,x _n ²,y ₁,…,y _n ² are noncommuting indeterminates andS _n ² is the symmetric group of degreen ². The polynomialsF ^{λ, μ} , when evaluated inM _n (K), take central values and we study the problem of classifying those partitions λ,μ for whichF ^{λ, μ} is a central polynomial (not a polynomial identity) forM _n (K). We give a formula that allows us to evaluateF ^{λ, μ} inM(K) in general and we prove that if λ andμ are not both derived in a suitable way from the partition δ=(1, 3,…, 2n−3, 2n−1), thenF ^{λ, μ} is a polynomial identity forM _n (K). As an application, we exhibit a new class of central polynomials forM _n (K). In memory of Shimshon Amitsur Research supported by a grant from MURST of Italy.     

On the strong law of large numbers for sequences of random variables without the independence condition

New sufficient conditions for the applicability of the strong law of large numbers to a sequence of dependent random variables X ₁, X ₂, …, with finite variances are established. No particular type of dependence between the random variables in the sequence is assumed. The statement of the theorem involves the classical condition Σ _n ^∞ (log₂ n)²/n ² < ∞, which appears in various theorems on the strong law of large numbers for sequences of random variables without the independence condition.     

Quintuplets of orthoprojectors associated by a linear relation

We consider the equation α₁ P ₁ + α₂ P ₂ + … α _n P _n = I over orthoprojectors P ₁, … ,P _n in a Hilbert space. We show that the set of real parameters (α₁, … α _n ) for which there exists a solution of this equation in orthoprojectors contains an open set from ℝ⁵.     

Positive definite functions and stable random vectors

We say that a random vector X = (X ₁, …, X _n ) in ℝ ⁿ is an n-dimensional version of a random variable Y if, for any a ∈ ℝ ⁿ , the random variables Σa _i X _i and γ(a)Y are identically distributed, where γ: ℝ ⁿ → [0,∞) is called the standard of X. An old problem is to characterize those functions γ that can appear as the standard of an n-dimensional version. In this paper, we prove the conjecture of Lisitsky that every standard must be the norm of a space that embeds in L ₀. This result is almost optimal, as the norm of any finite-dimensional subspace of L _p with p ∈ (0, 2] is the standard of an n-dimensional version (p-stable random vector) by the classical result of P. Lèvy. An equivalent formulation is that if a function of the form f(‖ · ‖ _K ) is positive definite on ℝ ⁿ , where K is an origin symmetric star body in ℝ ⁿ and f: ℝ → ℝ is an even continuous function, then either the space (ℝ ⁿ , ‖·‖ _K ) embeds in L ₀ or f is a constant function. Combined with known facts about embedding in L ₀, this result leads to several generalizations of the solution of Schoenberg’s problem on positive definite functions.     

A necessary and sufficient condition for a lower bound for fourth-order pseudodifferential operators

We give necessary and sufficient conditions for the lower bound {fx55-01} to hold for any compact setK ⊂X, an open set ofR ⁿ , andP =P* ∃ ψ _phg ⁴ (X) with p(x, ξ) ~ q ₂ ² + p₃ + p₂ + ..., q₂ beingtransversally elliptic with respect to the characteristic manifold Σ =q ₂ ^-1 (0).     

On central division algebras

For any integern such that 8|n or for which there exists an odd primeq such thatq ²|n, there is a central division algebra of dimensionn ² over its center which is not a crossed product. The algebra constructed in this paper is the algebraQ(X ₁,…,X)_m, the algebra generated over the rationalQ bym(≧2) generic matrices. To the memory of A. A. Albert This paper was originally presented in November, 1971 for publication elsewhere in a volume in honor of Prof. A. A. Albert on the occasion of his 65th birthday. The volume was never published due to the death of Prof. Albert in June 1972.     

The Johnson–Lindenstrauss Lemma Almost Characterizes Hilbert Space, But Not Quite

Let X be a normed space that satisfies the Johnson–Lindenstrauss lemma (J–L lemma, in short) in the sense that for any integer n and any x ₁,…,x _n ∈X, there exists a linear mapping L:X→F, where F⊆X is a linear subspace of dimension O(log n), such that ‖x _i −x _j ‖≤‖L(x _i )−L(x _j )‖≤O(1)⋅‖x _i −x _j ‖ for all i,j∈{1,…,n}. We show that this implies that X is almost Euclidean in the following sense: Every n-dimensional subspace of X embeds into Hilbert space with distortion 2^2O(log*n)2^{2^{O(\log^{*}n)}} . On the other hand, we show that there exists a normed space Y which satisfies the J–L lemma, but for every n, there exists an n-dimensional subspace E _n ⊆Y whose Euclidean distortion is at least 2^Ω(α(n)), where α is the inverse Ackermann function.     

A joint norm control Nehari type theorem forN-tuples of Hardy spaces

If N ∈ ℕ, 0 < p ≤ 1, and(X_k) _k=1 ^N are r.i.p-spaces, it is shown that there is C(= C(p, N)) > 0, such that for every ƒ ∈ ∩ _k=1 ^N X_k, there exists with , for every 1 ≤ k ≤ N. Also, if ⊓ is a convex polygon in ℝ², it is proved that the N-tuple (H(X₁),…, H(X_n)) is K_⊓-closed with respect to (X₁,…, X_N) in the sense of Pisier. Everything follows from Theorem 2.1, which is a general analytic partition of unity type result.     

Approximations simultanées de nombres algébriques de Q p par des rationnels

 In this paper, we prove that if β₁,…, β _n are p-adic numbers belonging to an algebraic number field K of degree n + 1 over Q such that 1, β₁,…,β _n are linearly independent over Z, there exist infinitely many sets of integers (q ₀,…, q _n ), with q ₀ ≠ 0 and

Asymptotic relation for the density of a multidimensional random evolution with rare poisson switchings

A symmetric random evolution X(t) = (X ₁ (t), …, X _m (t)) controlled by a homogeneous Poisson process with parameter λ > 0 is considered in the Euclidean space ℝ ^m , m ≥ 2. We obtain an asymptotic relation for the transition density p(x, t), t > 0, of the process X(t) as λ → 0 and describe the behavior of p(x, t) near the boundary of the diffusion domain in spaces of different dimensions. Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 60, No. 12, pp. 1631 – 1641, December, 2008.     

On Large Deviations of Multivariate Heavy-Tailed Random Walks

Let {S _n ;n=1,2,…} be a random walk in R ^d and E(S ₁)=(μ ₁,…,μ _d ). Let a _j >μ _j for j=1,…,d and A=(a ₁,∞)×⋅⋅⋅×(a _d ,∞). We are interested in the probability P(S _n /n∈A) for large n in the case where the components of S ₁ are heavy tailed. An objective is to associate an exact power with the aforementioned probability. We also derive sharper asymptotic bounds for the probability and show that in essence, the occurrence of the event {S _n /n∈A} is caused by large single increments of the components in a specific way.