A remark on measures of sections of $L_p$-balls
We show that the slicing problem holds true for subspaces of $L_p,p>2$ in the setting of arbitrary measures in place of volume. This generalizes a result of Milman for the original slicing problem.
Source author record
Alain Pajor
Alain Pajor appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
ResearcherUnclaimed source record
Catalog footprint
What is connected
12works
5topics
4close collaborators
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
12 published item(s)
preprint2015arXiv
On the interval of fluctuation of the singular values of random matrices
Let $A$ be a matrix whose columns $X_1,\dots, X_N$ are independent random vectors in $\mathbb{R}^n$. Assume that the tails of the 1-dimensional marginals decay as $\mathbb{P}(|\langle X_i, a\rangle|\geq t)\leq t^{-p}$ uniformly in $a\in S^{n-1}$ and $i\leq N$. Then for $p>4$ we prove that with high probability $A/{\sqrt{n}}$ has the Restricted Isometry Property (RIP) provided that Euclidean norms $|X_i|$ are concentrated around $\sqrt{n}$. We also show that the covariance matrix is well approximated by the empirical covariance matrix and establish corresponding quantitative estimates on the rate of convergence in terms of the ratio $n/N$. Moreover, we obtain sharp bounds for both problems when the decay is of the type $ \exp({-t^α})$ with $α\in (0,2]$, extending the known case $α\in[1, 2]$.
0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv
Thin-shell concentration for convex measures
We prove that for $s<0$, $s$-concave measures on ${\mathbb R}^n$ satisfy a thin shell concentration similar to the log-concave one. It leads to a Berry-Esseen type estimate for their one dimensional marginal distributions. We also establish sharp reverse Hölder inequalities for $s$-concave measures.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
A short proof of Paouris' inequality
We give a short proof of a result of G. Paouris on the tail behaviour of the Euclidean norm $|X|$ of an isotropic log-concave random vector $X\in\R^n$, stating that for every $t\geq 1$, $P(|X|\geq ct\sqrt n)\leq \exp(-t\sqrt n)$. More precisely we show that for any log-concave random vector $X$ and any $p\geq 1$, $(E|X|^p)^{1/p}\sim E |X|+\sup_{z\in S^{n-1}}(E |< z,X>|^p)^{1/p}$.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Moment estimates for convex measures
Let $p\geq 1$, $\eps >0$, $r\geq (1+\eps) p$, and $X$ be a $(-1/r)$-concave random vector in $\R^n$ with Euclidean norm $|X|$. We prove that $(\E |X|^{p})^{1/{p}}\leq c (C(\eps) \E|X|+σ_{p}(X))$, where $σ_{p}(X)=\sup_{|z|\leq 1}(\E|<z,X>|^{p})^{1/p}$, $C(\eps)$ depends only on $\eps$ and $c$ is a universal constant. Moreover, if in addition $X$ is centered then $(\E |X|^{-p})^{-1/{p}}\geq c(\eps) (\E|X| - C σ_{p}(X))$.
0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv
Sharp bounds on the rate of convergence of the empirical covariance matrix
Let $X_1,..., X_N\in\R^n$ be independent centered random vectors with log-concave distribution and with the identity as covariance matrix. We show that with overwhelming probability at least $1 - 3 \exp(-c\sqrt{n}\r)$ one has $ \sup_{x\in S^{n-1}} \Big|\frac{1/N}\sum_{i=1}^N (|<X_i, x>|^2 - \E|<X_i, x>|^2\r)\Big| \leq C \sqrt{\frac{n/N}},$ where $C$ is an absolute positive constant. This result is valid in a more general framework when the linear forms $(<X_i,x>)_{i\leq N, x\in S^{n-1}}$ and the Euclidean norms $(|X_i|/\sqrt n)_{i\leq N}$ exhibit uniformly a sub-exponential decay. As a consequence, if $A$ denotes the random matrix with columns $(X_i)$, then with overwhelming probability, the extremal singular values $λ_{\rm min}$ and $λ_{\rm max}$ of $AA^\top$ satisfy the inequalities $ 1 - C\sqrt{n/N} \le {λ_{\rm min}/N} \le \frac{λ_{\rm max}/N} \le 1 + C\sqrt{n/N} $ which is a quantitative version of Bai-Yin theorem \cite{BY} known for random matrices with i.i.d. entries.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Chevet type inequality and norms of submatrices
We prove a Chevet type inequality which gives an upper bound for the norm of an isotropic log-concave unconditional random matrix in terms of expectation of the supremum of "symmetric exponential" processes compared to the Gaussian ones in the Chevet inequality. This is used to give sharp upper estimate for a quantity $Γ_{k,m}$ that controls uniformly the Euclidean operator norm of the sub-matrices with $k$ rows and $m$ columns of an isotropic log-concave unconditional random matrix. We apply these estimates to give a sharp bound for the Restricted Isometry Constant of a random matrix with independent log-concave unconditional rows. We show also that our Chevet type inequality does not extend to general isotropic log-concave random matrices.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Geometry of log-concave Ensembles of random matrices and approximate reconstruction
We study the Restricted Isometry Property of a random matrix $Γ$ with independent isotropic log-concave rows. To this end, we introduce a parameter $Γ_{k,m}$ that controls uniformly the operator norm of sub-matrices with $k$ rows and $m$ columns. This parameter is estimated by means of new tail estimates of order statistics and deviation inequalities for norms of projections of an isotropic log-concave vector.
0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv
Tail estimates for norms of sums of log-concave random vectors
We establish new tail estimates for order statistics and for the Euclidean norms of projections of an isotropic log-concave random vector. More generally, we prove tail estimates for the norms of projections of sums of independent log-concave random vectors, and uniform versions of these in the form of tail estimates for operator norms of matrices and their sub-matrices in the setting of a log-concave ensemble. This is used to study a quantity $A_{k,m}$ that controls uniformly the operator norm of the sub-matrices with $k$ rows and $m$ columns of a matrix $A$ with independent isotropic log-concave random rows. We apply our tail estimates of $A_{k,m}$ to the study of Restricted Isometry Property that plays a major role in the Compressive Sensing theory.
0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv
The Gelfand widths of $\ell_p$-balls for $0<p\leq 1$
We provide sharp lower and upper bounds for the Gelfand widths of $\ell_p$-balls in the $N$-dimensional $\ell_q^N$-space for $0<p\leq 1$ and $p<q \leq 2$. Such estimates are highly relevant to the novel theory of compressive sensing, and our proofs rely on methods from this area.
0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv
Quantitative estimates of the convergence of the empirical covariance matrix in Log-concave Ensembles
Let $K$ be an isotropic convex body in $\R^n$. Given $\eps>0$, how many independent points $X_i$ uniformly distributed on $K$ are needed for the empirical covariance matrix to approximate the identity up to $\eps$ with overwhelming probability? Our paper answers this question posed by Kannan, Lovasz and Simonovits. More precisely, let $X\in\R^n$ be a centered random vector with a log-concave distribution and with the identity as covariance matrix. An example of such a vector $X$ is a random point in an isotropic convex body. We show that for any $\eps>0$, there exists $C(\eps)>0$, such that if $N\sim C(\eps) n$ and $(X_i)_{i\le N}$ are i.i.d. copies of $X$, then $ \Big\|\frac{1}{N}\sum_{i=1}^N X_i\otimes X_i - \Id\Big\| \le ε, $ with probability larger than $1-\exp(-c\sqrt n)$.
0 citations0 reviewsNo code linkedOpen access
preprint1989arXiv
Convex bodies with few faces
It is proved that if $u_1,\ldots, u_n$ are vectors in ${\Bbb R}^k, k\le n, 1 \le p < \infty$ and $$r = ({1\over k} \sum ^n_1 |u_i|^p)^{1\over p}$$ then the volume of the symmetric convex body whose boundary functionals are $\pm u_1,\ldots, \pm u_n$, is bounded from below as $$|\{ x\in {\Bbb R}^k\colon \ |\langle x,u_i\rangle | \le 1 \ \hbox{for every} \ i\}|^{1\over k} \ge {1\over \sqrtρr}.$$ An application to number theory is stated.
0 citations0 reviewsNo code linkedOpen access