Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top

2013 | Book

Bracketing Entropy of High Dimensional Distributions Read chapter Read first chapter

High Dimensional Probability VI

The Banff Volume

Editors: Christian Houdré, David M. Mason, Jan Rosiński, Jon A. Wellner

Publisher: Springer Basel

Book Series : Progress in Probability

Part of: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Login to get access
insite
SEARCH

About this book

This is a collection of papers by participants at High Dimensional Probability VI Meeting held from October 9-14, 2011 at the Banff International Research Station in Banff, Alberta, Canada.

High Dimensional Probability (HDP) is an area of mathematics that includes the study of probability distributions and limit theorems in infinite-dimensional spaces such as Hilbert spaces and Banach spaces. The most remarkable feature of this area is that it has resulted in the creation of powerful new tools and perspectives, whose range of application has led to interactions with other areas of mathematics, statistics, and computer science. These include random matrix theory, nonparametric statistics, empirical process theory, statistical learning theory, concentration of measure phenomena, strong and weak approximations, distribution function estimation in high dimensions, combinatorial optimization, and random graph theory.

The papers in this volume show that HDP theory continues to develop new tools, methods, techniques and perspectives to analyze the random phenomena. Both researchers and advanced students will find this book of great use for learning about new avenues of research.​

Table of Contents

Frontmatter

Inequalities and Convexity

Frontmatter
Bracketing Entropy of High Dimensional Distributions
Abstract
Let \(\mathcal{F}_{d}\) be the class of probability distribution functions on \([0,\,1]^{d},\,{d}\geq{2}\). The following estimate for the bracketing entropy of \(\mathcal{F}_{d}\) in the \([L]^{p}\) norm, \(1\,\leq\,p\,{<} \infty \), is obtained:
$${\rm log}{N_{[\,]}}(\varepsilon, \mathcal{F}_{d},{\parallel.\parallel}_p)=O(\varepsilon^{-1}{|\rm log\varepsilon|^{2(\rm d-1)}}).$$
Based on this estimate, a general relation between bracketing entropy in the L p norm and metric entropy in the L 1 norm for multivariate smooth functions is established.
Fuchang Gao
Slepian’s Inequality, Modularity and Integral Orderings
Abstract
Slepian’s inequality comes in many variants under different sets of regularity conditions. Unfortunately, some of these variants are wrong and other variants are imposing to strong regularity conditions. The first part of this paper contains a unified version of Slepian’s inequality under minimal regularity conditions, covering all the variants I know about. It is well known that Slepian’s inequality is closely connected to integral orderings in general and the supermodular ordering in particular. In the last part of the paper I explore this connection and corrects some results in the theory of integral orderings.
J. Hoffmann-Jørgensen
A More General Maximal Bernstein-type Inequality
Abstract
We extend a general Bernstein-type maximal inequality of Kevei and Mason (2011) for sums of random variables.
Péter Kevei, David M. Mason
Maximal Inequalities for Centered Norms of Sums of Independent Random Vectors
Abstract
Let \( X_1,\,X_2 ,\,.\,.\,.\,,X_n \) be independent random variables and \( S_k = \sum\nolimits_{i = 1}^k {X_i } \) We show that for any constants a k
$$\mathbb{P}(\mathop \mathrm{max}\limits_{1\leq k \leq n} \|S_k |-{a_k}|>11{t})\leq 30 \mathop \mathrm{max}\limits_{1\leq k \leq n} \mathbb{P}(\|S_k | -{a_k}|>t).$$
We also discuss similar inequalities for sums of Hilbert and Banach spacevalued random vectors.
Rafał Latała
A Probabilistic Inequality Related to Negative Definite Functions
Abstract
We prove that for any pair of i.i.d. random vectors X,Y in \(\mathbb{R}^n\) and any real-valued continuous negative definite function \(\psi\; : \;\mathbb{R}^n\rightarrow\mathbb{R}\) the inequality
$$\mathbb{E}\;\psi\;(X\;-\;Y)\leqslant\mathbb{E}\;\psi\;(X\;+\;Y).$$
holds. In particular, for \(\alpha\;\in\;(0,2]\) and the Euclidean norm \(\|\cdot\|_2\) one has
$$\mathbb{E}\|(X\;-\;Y)\|^\alpha_2\leqslant\mathbb{E}\|(X\;+\;Y)\|^\alpha_2.$$
The latter inequality is due to A. Buja et al. [4] where it is used for some applications in multivariate statistics. We show a surprising connection with bifractional Brownian motion and provide some related counter-examples.
Mikhail Lifshits, René L. Schilling, Ilya Tyurin
Optimal Re-centering Bounds, with Applications to Rosenthal-type Concentration of Measure Inequalities
Abstract
For any nonnegative Borel-measurable function f such that \(f(x)\;=\;0\) if and only if \(x\;=\;0\), the best constant c f in the inequality \(Ef(X\;-\;E\;X)\leqslant c_f E\;f(X)\) for all random variables X with a finite mean is obtained. Properties of the constant c f in the case when \(f\;=\;|\cdot|^p\) for \(p>0\) are studied. Applications to concentration of measure in the form of Rosenthal-type bounds on the moments of separately Lipschitz functions on product spaces are given.
Iosif Pinelis
Strong Log-concavity is Preserved by Convolution
Abstract
We review and formulate results concerning strong-log-concavity in both discrete and continuous settings. Although four different proofs of preservation of strong log-concavity are known in the discrete setting (where strong log-concavity is known as “ultra-log-concavity”), preservation of strong logconcavity under convolution has apparently not been investigated previously in the continuous case.
Jon A. Wellner
On Some Gaussian Concentration Inequality for Non-Lipschitz Functions
Abstract
A concentration inequality for functions of a pair of Gaussian random vectors is established. Instead of the usual Lipschitz condition some boundedness of second-order derivatives is assumed. This result can be viewed as an extension of a well-known tail estimate for Gaussian random bi-linear forms to the non-linear case.
Paweł Wolff

Limit Theorems

Frontmatter
Rates of Convergence in the Strong Invariance Principle for Non-adapted Sequences Application to Ergodic Automorphisms of the Torus
Abstract
In this paper, we give rates of convergence in the strong invariance principle for non-adapted sequences satisfying projective criteria. The results apply to the iterates of ergodic automorphisms T of the d-dimensional torus \(\mathbb{T}^d\), even in the non hyperbolic case. In this context, we give a large class of unbounded function f from \(\mathbb{T}^d\) to \(\mathbb{R}\), for which the partial sum \(f\;\circ\;T\;+\;f\;\circ\;T^{2}\;+\;.\;.\;.\;+\;f\;\circ\;T^{n}\) satisfies a strong invariance principle with an explicit rate of convergence.
Jérôme Dedecker, Florence Merlevède, Françoise Pène
On the Rate of Convergence to the Semi-circular Law
Abstract
Let \(X\;=\;(X_{jk})^n_{j,k=1}\) denote a Hermitian random matrix with entries X jk, which are independent for \(1\;\leq\;j\;\leq\;k\;\leq\;n\). We consider the rate of convergence of the empirical spectral distribution function of the matrix X to the semi-circular law assuming that \(\mathbf{E}X_{jk}\;=\;0,\;\mathbf{E}X^2_{jk}\;=\;1\) and that the distributions of the matrix elements X jk have a uniform sub exponential decay in the sense that there exists a constant ϰ> 0 such that for any \(1\;\leq\;j\;\leq\;k\;\leq\;n\) and any \(t\;\geq\;1\) we have
$$\mathrm{Pr}\left\{|X_{jk}|\;>\;t \right\}\leq\;x^{-1}\;\exp\left\{-t^x\right\}$$
By means of a short recursion argument it is shown that the Kolmogorov distance between the empirical spectral distribution of the Wigner matrix \(\mathbf{W}\;=\;\frac{1}{\sqrt{n}}\mathbf{X}\) and the semicircular law is of order \(O(n^{-1}\;\log^b\;n)\) with some positive constant \(b\;>\;0\)
Friedrich Götze, Alexandre Tikhomirov
Empirical Quantile CLTs for Time-dependent Data
Abstract
We establish empirical quantile process CLTs based on n independent copies of a stochastic process {X t : t ∈ E} that are uniform in t ∈ E and quantile levels α ∈ I, where I is a closed sub-interval of (0, 1). The process {X t : t ∈ E} may be chosen from a broad collection of Gaussian processes, compound Poisson processes, stationary independent increment stable processes, and martingales.
James Kuelbs, Joel Zinn
Asymptotic Properties for Linear Processes of Functionals of Reversible or Normal Markov Chains
Abstract
In this paper we study the asymptotic behavior of linear processes having as innovations mean zero, square integrable functions of stationary reversible or normal Markov chains. In doing so we shall preserve the generality of coefficients assuming only that they are square summable. In this way we include in our study the long range dependence case. The only assumption imposed on the innovations for reversible Markov chains is the absolute summability of their covariances. Besides the central limit theorem we also study the convergence to fractional Brownian motion. The proofs are based on general results for linear processes with stationary innovations that have interest in themselves.
Magda Peligrad

Stochastic Processes

Frontmatter
First Exit of Brownian Motion from a One-sided Moving Boundary
Abstract
We revisit a result of Uchiyama (1980):giv en that a certain integral test is satisfied, the rate of the probability that Brownian motion remains below the moving boundary f is asymptotically the same as for the constant boundary. The integral test for f is also necessary in some sense.
After Uchiyama’s result, a number of different proofs appeared simplifying the original arguments, which strongly rely on some known identities for Brownian motion. In particular, Novikov (1996) gives an elementary proof in the case of an increasing boundary. Here, we provide an elementary, halfpage proof for the case of a decreasing boundary. Further, we identify that the integral test is related to a repulsion effect of the three-dimensional Bessel process. Our proof gives some hope to be generalized to other processes such as FBM.
Frank Aurzada, Tanja Kramm
On Lévy’s Equivalence Theorem in Skorohod Space
Abstract
A new and simple proof of Lévy’s Equivalence Theorem in Skorohod space is given. This result and its consequences complement and complete the recent work of the authors [1].
Andreas Basse-O’Connor, Jan Rosiński
Continuity Conditions for a Class of Second-order Permanental Chaoses
Abstract
Just as permanental processes are generalizations of stochastic processes that are the square of Gaussian processes we define permanental fields as a generalization of certain second-order Gaussian chaos processes. A sufficient condition for the continuity of permanental fields is obtained that generalizes an earlier result for second-order Gaussian chaoses.
Michael B. Marcus, Jay Rosen

Random Matrices and Applications

Frontmatter
On the Operator Norm of Random Rectangular Toeplitz Matrices
Abstract
We consider rectangular N x n Toeplitz matrices generated by sequences of centered independent random variables and provide bounds on their operator norm under the assumption of finiteness of pth moments (p > 2). We also show that if N ≫ n log n then with high probability such matrices preserve the Euclidean norm up to an arbitrarily small error.
Radosław Adamczak
Edge Fluctuations of Eigenvalues of Wigner Matrices
Abstract
We establish a moderate deviation principle (MDP) for the number of eigenvalues of a Wigner matrix in an interval close to the edge of the spectrum. Moreover we prove a MDP for the jth largest eigenvalue close to the edge. The proof relies on fine asymptotics of the variance of the eigenvalue counting function of GUE matrices due to Gustavsson. The extension to large families of Wigner matrices is based on the Tao and Vu Four Moment Theorem. Possible extensions to other random matrix ensembles are commented.
Hanna Döring, Peter Eichelsbacher
On the Limiting Shape of Young Diagrams Associated with Inhomogeneous Random Words
Abstract
The limiting shape of the random Young diagrams associated with an inhomogeneous random word is identified as a multidimensional Brownian functional. This functional is identical in law to the spectrum of a Gaussian random matrix. Since the length of the top row of the Young diagrams is also the length of the longest (weakly) increasing subsequence of the random word, the corresponding limiting law follows. The Poissonized word problem is also briefly studied, and the asymptotic behavior of the shape analyzed.
Christian Houdré, Hua Xu

High Dimensional Statistics

Frontmatter
Low Rank Estimation of Similarities on Graphs
Abstract
Let (V,E) be a graph with vertex set V and edge set E. Let (X,X’,Y ) ∈ V × V × {−1, 1} be a random triple, where X,X’ are independent uniformly distributed vertices and Y is a label indicating whether X,X’ are “similar” (Y = +1), or not (Y = −1). Our goal is to estimate the regression function \(S_*(u,v)\,=\, {\mathbb{E}{(Y|X\,=\,u,X^\prime\,=v)}},u,v\, \in\,V\) based on training data consisting of n i.i.d. copies of (X,X’,Y ). We are interested in this problem in the case when S * is a symmetric low rank kernel and, in addition to this, it is assumed that S * is “smooth” on the graph. We study estimators based on a modified least squares method with complexity penalization involving both the nuclear norm and Sobolev type norms of symmetric kernels on the graph and prove upper bounds on L2-type errors of such estimators with explicit dependence both on the rank of S * and on the degree of its smoothness.
Vladimir Koltchinskii, Pedro Rangel
Sparse Principal Component Analysis with Missing Observations
Abstract
In this paper, we study the problem of sparse Principal Component Analysis (PCA) in the high dimensional setting with missing observations. Our goal is to estimate the first principal component when we only have access to partial observations. Existing estimation techniques are usually derived for fully observed data sets and require a prior knowledge of the sparsity of the first principal component in order to achieve good statistical guarantees. Our contributions is essentially theoretical in nature. First, we establish the first information-theoretic lower bound for the sparse PCA problem with missing observations. Second, we study the properties of a BIC type estimator that does not require any prior knowledge on the sparsity of the unknown first principal component or any imputation of the missing observations and adapts to the unknown sparsity of the first principal component. Third, if the covariance matrix of interest admits a sparse first principal component and is in addition approximately low-rank, then we can derive a completely datadriven choice of the regularization parameter and the resulting BIC estimator will also enjoy optimal statistical performances (up to a logarithmic factor).
Karim Lounici
High Dimensional CLT and its Applications
Abstract
We study the behavior of empirical processes indexed by finite classes of functions but we allow that the cardinality of these classes tend to infinity. We prove general results showing that one can bootstrap these types of processes even if they do not converge. We show that these results can be used to construct novel statistical tests. To this end we offer a new goodness of fit test.
Dragan Radulovic
Metadata
Title
High Dimensional Probability VI
Editors
Christian Houdré
David M. Mason
Jan Rosiński
Jon A. Wellner
Copyright Year
2013
Publisher
Springer Basel
Electronic ISBN
978-3-0348-0490-5
Print ISBN
978-3-0348-0489-9
DOI
https://doi.org/10.1007/978-3-0348-0490-5