Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLarge deviation principles induced by the Stiefel manifold, and random multi-dimensional projections
124
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Given an $n$-dimensional random vector $X^{(n)}$ , for $k < n$, consider its $k$-dimensional projection $mathbf{a}_{n,k}X^{(n)}$, where $mathbf{a}_{n,k}$ is an $n times k$-dimensional matrix belonging to the Stiefel manifold $mathbb{V}_{n,k}$ of orthonormal $k$-frames in $mathbb{R}^n$. For a class of sequences ${X^{(n)}}$ that includes the uniform distributions on scaled $ell_p^n$ balls, $p in (1,infty]$, and product measures with sufficiently light tails, it is shown that the sequence of projected vectors ${mathbf{a}_{n,k}^intercal X^{(n)}}$ satisfies a large deviation principle whenever the empirical measures of the rows of $sqrt{n} mathbf{a}_{n,k}$ converge, as $n rightarrow infty$, to a probability measure on $mathbb{R}^k$. In particular, when $mathbf{A}_{n,k}$ is a random matrix drawn from the Haar measure on $mathbb{V}_{n,k}$, this is shown to imply a large deviation principle for the sequence of random projections ${mathbf{A}_{n,k}^intercal X^{(n)}}$ in the quenched sense (that is, conditioned on almost sure realizations of ${mathbf{A}_{n,k}}$). Moreover, a variational formula is obtained for the rate function of the large deviation principle for the annealed projections ${mathbf{A}_{n,k}^intercal X^{(n)}}$, which is expressed in terms of a family of quenched rate functions and a modified entropy term. A key step in this analysis is a large deviation principle for the sequence of empirical measures of rows of $sqrt{n} mathbf{A}_{n,k}$, which may be of independent interest. The study of multi-dimensional random projections of high-dimensional measures is of interest in asymptotic functional analysis, convex geometry and statistics. Prior results on quenched large deviations for random projections of $ell_p^n$ balls have been essentially restricted to the one-dimensional setting.
rate research
Read More
For $ninmathbb N$ let $Theta^{(n)}$ be a random vector uniformly distributed on the unit sphere $mathbb S^{n-1}$, and consider the associated random probability measure $mu_{Theta^{(n)}}$ given by setting [ mu_{Theta^{(n)}}(A) := mathbb{P} left[ langle U, Theta^{(n)} rangle in A right],qquad U sim text{Unif}([-1,1]^n) ] for Borel subets $A$ of $mathbb{R}$. It is known that the sequence of random probability measures $mu_{Theta^{(n)}}$ converges weakly to the centered Gaussian distribution with variance $1/3$. We prove a large deviation principle for the sequence $mu_{Theta^{(n)}}$ with speed $n$ and explicit good rate rate function given by $I( u(alpha)) := - frac{1}{2} log ( 1 - ||alpha||_2^2)$ whenever $ u(alpha)$ is the law of a random variable of the form begin{align*} sqrt{1 - ||alpha||_2^2 } frac{Z}{sqrt 3} + sum_{ k = 1}^infty alpha_k U_k, end{align*} where $Z$ is standard Gaussian independent of $U_1,U_2,ldots$ which are i.i.d. $text{Unif}[-1,1]$, and $alpha_1 geq alpha_2 geq ldots $ is a non-increasing sequence of non-negative reals with $||alpha||_2<1$. We obtain a similar result for projections of the uniform distribution on the discrete cube ${-1,+1}^n$.
Consider the projection of an $n$-dimensional random vector onto a random $k_n$-dimensional basis, $k_n leq n$, drawn uniformly from the Haar measure on the Stiefel manifold of orthonormal $k_n$-frames in $mathbb{R}^n$, in three different asymptotic regimes as $n rightarrow infty$: constant ($k_n=k$), sublinear ($k_n rightarrow infty$ but $k_n/n rightarrow 0$) and linear $k_n/n rightarrow lambda$ with $0 < lambda le 1$). When the sequence of random vectors satisfies a certain asymptotic thin shell condition, we establish annealed large deviation principles (LDPs) for the corresponding sequence of random projections in the constant regime, and for the sequence of empirical measures of the coordinates of the random projections in the sublinear and linear regimes. We also establish LDPs for certain scaled $ell_q$ norms of the random projections in these different regimes. Moreover, we verify our assumptions for various sequences of random vectors of interest, including those distributed according to Gibbs measures with superquadratic interaction potential, or the uniform measure on suitably scaled $ell_p^n$ balls, for $p in [1,infty)$, and generalized Orlicz balls defined via a superquadratic function. Our results complement the central limit theorem for convex sets and related results which are known to hold under a thin shell condition. These results also substantially extend existing large deviation results for random projections, which are first, restricted to the setting of measures on $ell_p^n$ balls, and secondly, limited to univariate LDPs (i.e., in $mathbb{R}$) involving either the norm of a $k_n$-dimensional projection or the projection of $X^{(n)}$ onto a random one-dimensional subspace. Random projections of high-dimensional random vectors are of interest in a range of fields including asymptotic convex geometry and high-dimensional statistics.
Borgs, Chayes, Gaudio, Petti and Sen [arXiv:2007.14508] proved a large deviation principle for block model random graphs with rational block ratios. We strengthen their result by allowing any block ratios (and also establish a simpler formula for the rate function). We apply the new result to derive a large deviation principle for graph sampling from any given step graphon.
Accurate estimation of tail probabilities of projections of high-dimensional probability measures is of relevance in high-dimensional statistics and asymptotic geometric analysis. For fixed $p in (1,infty)$, let $(X^{(n,p)})$ and $(theta^n)$ be independent sequences of random vectors with $theta^n$ distributed according to the normalized cone measure on the unit $ell_2^n$ sphere, and $X^{(n,p)}$ distributed according to the normalized cone measure on the unit $ell_p^n$ sphere. For almost every sequence of projection directions $(theta^n)$, (quenched) sharp large deviation estimates are established for suitably normalized (scalar) projections of $X^{n,p}$ onto $theta^n$, that are asymptotically exact (as the dimension $n$ tends to infinity). Furthermore, the case when $(X^{(n,p)})$ is replaced with $(mathscr{X}^{(n,p)})$, where $mathscr{X}^{(n,p)}$ is distributed according to the uniform (or normalized volume) measure on the unit $ell_p^n$ ball, is also considered. In both cases, in contrast to the (quenched) large deviation rate function, the prefactor exhibits a dependence on the projection directions $(theta^n)$ that encodes geometric information. Moreover, although the (quenched) large deviation rate functions for the sequences of random projections of $(X^{(n,p)})$ and $(mathscr{X}^{(n,p)})$ are known to coincide, it is shown that the prefactor distinguishes between these two cases. The results on the one hand provide quantitative estimates of tail probabilities of random projections of $ell_p^n$ balls and spheres, valid for finite $n$, generalizing previous results due to Gantert, Kim and Ramanan, and on the other hand, generalize classical sharp large deviation estimates in the spirit of Bahadur and Ranga Rao to a geometric setting.
We derive properties of the rate function in Varadhans (annealed) large deviation principle for multidimensional, ballistic random walk in random environment, in a certain neighborhood of the zero set of the rate function. Our approach relates the LDP to that of regeneration times and distances. The analysis of the latter is possible due to the i.i.d. structure of regenerations.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
