Source author record

Radosław Adamczak

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.PR math.FA math.MG Information Theory Machine Learning math-ph math.CO math.IT math.MP math.ST quant-ph Statistics Theory

Catalog footprint

Research overview

25works

12topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Limit theorems for the volumes of small codimensional random sections of $\ell_p^n$ -balls

We establish Central Limit Theorems for the volumes of intersections of $B_{p}^n$ (the unit ball of $\ell_p^n$ ) with uniform random subspaces of codimension $d$ for fixed $d$ and $n\to \infty$ . As a corollary we obtain higher order approximations for expected volumes, refining previous results by Koldobsky and Lifschitz and approximations obtained from the Eldan--Klartag version of CLT for convex bodies. We also obtain a Central Limit Theorem for the Minkowski functional of the intersection body of $B_p^n$ , evaluated on a random vector distributed uniformly on the unit sphere.

preprint2020arXiv

Modified log-Sobolev inequalities, Beckner inequalities and moment estimates

We prove that in the context of general Markov semigroups Beckner inequalities with constants separated from zero as $p\to 1^+$ are equivalent to the modified log Sobolev inequality (previously only one implication was known to hold in this generality). Further, by adapting an argument by Boucheron et al. we derive Sobolev type moment estimates which hold under these functional inequalities. We illustrate our results with applications to concentration of measure estimates (also of higher order, beyond the case of Lipschitz functions) for various stochastic models, including random permutations, zero-range processes, strong Rayleigh measures, exponential random graphs, and geometric functionals on the Poisson path space.

preprint2016arXiv

A note on the sample complexity of the Er-SpUD algorithm by Spielman, Wang and Wright for exact recovery of sparsely used dictionaries

We consider the problem of recovering an invertible $n \times n$ matrix $A$ and a sparse $n \times p$ random matrix $X$ based on the observation of $Y = AX$ (up to a scaling and permutation of columns of $A$ and rows of $X$ ). Using only elementary tools from the theory of empirical processes we show that a version of the Er-SpUD algorithm by Spielman, Wang and Wright with high probability recovers $A$ and $X$ exactly, provided that $p \ge Cn\log n$ , which is optimal up to the constant $C$ .

preprint2015arXiv

Asymptotic entropic uncertainty relations

We analyze entropic uncertainty relations for two orthogonal measurements on a $N$ -dimensional Hilbert space, performed in two generic bases. It is assumed that the unitary matrix $U$ relating both bases is distributed according to the Haar measure on the unitary group. We provide lower bounds on the average Shannon entropy of probability distributions related to both measurements. The bounds are stronger than these obtained with use of the entropic uncertainty relation by Maassen and Uffink, and they are optimal up to additive constants. We also analyze the case of a large number of measurements and obtain strong entropic uncertainty relations which hold with high probability with respect to the random choice of bases. The lower bounds we obtain are optimal up to additive constants and allow us to establish the conjecture by Wehner and Winter on the asymptotic behavior of constants in entropic uncertainty relations as the dimension tends to infinity. As a tool we develop estimates on the maximum operator norm of a submatrix of a fixed size of a random unitary matrix distributed according to the Haar measure, which are of an independent interest.

preprint2015arXiv

Modified log-Sobolev inequalities for convex functions on the real line. Sufficient conditions

We provide a mild sufficient condition for a probability measure on the real line to satisfy a modified log-Sobolev inequality for convex functions, interpolating between the classical log-Sobolev inequality and a Bobkov-Ledoux type inequality. As a consequence we obtain dimension-free two-level concentration results for convex function of independent random variables with sufficiently regular tail decay. We also provide a link between modified log-Sobolev inequalities for convex functions and weak transport-entropy inequalities, complementing recent work by Gozlan, Roberto, Samson, and Tetali.

preprint2015arXiv

Moment estimates implied by modified log-Sobolev inequalities

We study a class of logarithmic Sobolev inequalities with a general form of the energy functional. The class generalizes various examples of modified logarithmic Sobolev inequalities considered previously in the literature. Refining a method of Aida and Stroock for the classical logarithmic Sobolev inequality, we prove that if a measure on $\mathbb{R}^n$ satisfies a modified logarithmic Sobolev inequality then it satisfies a family of $L^p$ -Sobolev-type inequalities with non-Euclidean norms of gradients (and dimension-independent constants). The latter are shown to yield various concentration-type estimates for deviations of smooth (not necessarily Lipschitz) functions and measures of enlargements of sets corresponding to non-Euclidean norms. We also prove a two-level concentration result for functions of bounded Hessian and measures satisfying the classical logarithmic Sobolev inequality.

preprint2015arXiv

Some remarks on MCMC estimation of spectra of integral operators

We prove a law of large numbers for empirical approximations of the spectrum of a kernel integral operator by the spectrum of random matrices based on a sample drawn from a Markov chain, which complements the results by V. Koltchinskii and E. Giné for i.i.d. sequences. In a special case of Mercer's kernels and geometrically ergodic chains, we also provide exponential inequalities, quantifying the speed of convergence.

preprint2014arXiv

A note on the Hanson-Wright inequality for random vectors with dependencies

We prove that quadratic forms in isotropic random vectors $X$ in $\mathbb{R}^n$ , possessing the convex concentration property with constant $K$ , satisfy the Hanson-Wright inequality with constant $CK$ , where $C$ is an absolute constant, thus eliminating the logarithmic (in the dimension) factors in a recent estimate by Vu and Wang. We also show that the concentration inequality for all Lipschitz functions implies a uniform version of the Hanson-Wright inequality for suprema of quadratic forms (in the spirit of the inequalities by Borell, Arcones-Giné and Ledoux-Talagrand). Previous results of this type relied on stronger isoperimetric properties of $X$ and in some cases provided an upper bound on the deviations rather than a concentration inequality. In the last part of the paper we show that the uniform version of the Hanson-Wright inequality for Gaussian vectors can be used to recover a recent concentration inequality for empirical estimators of the covariance operator of $B$ -valued Gaussian variables due to Koltchinskii and Lounici.

preprint2014arXiv

Circular law for random matrices with exchangeable entries

An exchangeable random matrix is a random matrix with distribution invariant under any permutation of the entries. For such random matrices, we show, as the dimension tends to infinity, that the empirical spectral distribution tends to the uniform law on the unit disc. This is an instance of the universality phenomenon known as the circular law, for a model of random matrices with dependent entries, rows, and columns. It is also a non-Hermitian counterpart of a result of Chatterjee on the semi-circular law for random Hermitian matrices with exchangeable entries. The proof relies in particular on a reduction to a simpler model given by a random shuffle of a rigid deterministic matrix, on Hermitization, and also on combinatorial concentration of measure and combinatorial Central Limit Theorem. A crucial step is a polynomial bound on the smallest singular value of exchangeable random matrices, which may be of independent interest.

preprint2013arXiv

Circular law for random matrices with unconditional log-concave distribution

We explore the validity of the circular law for random matrices with non i.i.d. entries. Let A be a random n \times n real matrix having as a random vector in R^{n^2} a log-concave isotropic unconditional law. In particular, the entries are uncorellated and have a symmetric law of zero mean and unit variance. This allows for some dependence and non equidistribution among the entries, while keeping the special case of i.i.d. standard Gaussian entries. Our main result states that as n goes to infinity, the empirical spectral distribution of n^{-1/2}A tends to the uniform law on the unit disc of the complex plane.

preprint2013arXiv

Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order

Building on the inequalities for homogeneous tetrahedral polynomials in independent Gaussian variables due to R. Latała we provide a concentration inequality for non-necessarily Lipschitz functions $f\colon \R^n \to \R$ with bounded derivatives of higher orders, which hold when the underlying measure satisfies a family of Sobolev type inequalities $\|g- \E g\|_p \le C(p)\|\nabla g\|_p.$ Such Sobolev type inequalities hold, e.g., if the underlying measure satisfies the log-Sobolev inequality (in which case $C(p) \le C\sqrt{p}$ ) or the Poincaré inequality (then $C(p) \le Cp$ ). Our concentration estimates are expressed in terms of tensor-product norms of the derivatives of $f$ . When the underlying measure is Gaussian and $f$ is a polynomial (non-necessarily tetrahedral or homogeneous), our estimates can be reversed (up to a constant depending only on the degree of the polynomial). We also show that for polynomial functions, analogous estimates hold for arbitrary random vectors with independent sub-Gaussian coordinates. We apply our inequalities to general additive functionals of random vectors (in particular linear eigenvalue statistics of random matrices) and the problem of counting cycles of fixed length in Erdős-R{é}nyi random graphs, obtaining new estimates, optimal in a certain range of parameters.

preprint2013arXiv

Exponential Concentration Inequalities for Additive Functionals of Markov Chains

Using the renewal approach we prove exponential inequalities for additive functionals and empirical processes of ergodic Markov chains, thus obtaining counterparts of inequalities for sums of independent random variables. The inequalities do not require functions of the chain to be bounded and moreover all the involved constants are given by explicit formulas whenever the usual drift condition holds, which may be of interest in practical applications e.g. to MCMC algorithms.

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}$ .

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))$.

preprint2012arXiv

Orlicz integrability of additive functionals of Harris ergodic Markov chains

For a Harris ergodic Markov chain $(X_n)_{n\ge 0}$ , on a general state space, started from the so called small measure or from the stationary distribution we provide optimal estimates for Orlicz norms of sums $\sum_{i=0}^τf(X_i)$ , where $τ$ is the first regeneration time of the chain. The estimates are expressed in terms of other Orlicz norms of the function $f$ (wrt the stationary distribution) and the regeneration time $τ$ (wrt the small measure). We provide applications to tail estimates for additive functionals of the chain $(X_n)$ generated by unbounded functions as well as to classical limit theorems (CLT, LIL, Berry-Esseen).

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.

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.

preprint2011arXiv

CLT for Ornstein-Uhlenbeck branching particle system

In this paper we consider a branching particle system consisting of particles moving according to the Ornstein-Uhlenbeck process in $\Rd$ and undergoing a binary, supercritical branching with a constant rate $λ>0$ . This system is known to fulfil a law of large numbers (under exponential scaling). In the paper we prove the corresponding central limit theorem. The limit and the CLT normalisation fall into three qualitatively different classes. In, what we call, the small branching rate case the situation resembles the classical one. The weak limit is Gaussian and normalisation is the square root of the size of the system. In the critical case the limit is still Gaussian, however the normalisation requires an additional term. Finally, when branching has large rate the situation is completely different. The limit is no longer Gaussian, the normalisation is substantially larger than the classical one and the convergence holds in probability. We prove also that the spatial fluctuations are asymptotically independent of the fluctuations of the total number of particles (which is a Galton-Watson process).

preprint2011arXiv

CLT for U-statistics of Ornstein-Uhlenbeck branching particle system with small branching rate

In this paper we consider a branching particle system consisting of particles moving according to the Ornstein-Uhlenbeck process in R^d and undergoing a binary, supercritical branching with a constant rate λ>0. This system is known to fulfil a law of large numbers (under exponential scaling). In the paper we prove the corresponding central limit theorem. Moreover, in the second part of the paper we consider U-statistics of the system, for which, under mild assumptions, we prove a law of large numbers and a central limit theorem. The limits are expressed in terms of multiple stochastic integrals with respect to a random Gaussian measure. The second order behaviour depends qualitatively on the growth rate of the system. In this paper we concentrate on the case when the growth rate is relatively small comparing to smoothing properties of particles' movement.

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.

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.

preprint2011arXiv

U-statistics of Ornstein-Uhlenbeck branching particle system

We consider a branching particle system consisting of particles moving according to the Ornstein-Uhlenbeck process in $\Rd$ and undergoing a binary, supercritical branching with a constant rate $λ>0$ . This system is known to fulfil a law of large numbers (under exponential scaling). Recently the question of the corresponding central limit theorem has been addressed. It turns out that the normalization and form of the limit in the CLT fall into three qualitatively different regimes, depending on the relation between the branching intensity and the parameters of the Orstein-Uhlenbeck process. In the present paper we extend those results to $U$ -statistics of the system proving a law of large numbers and a central limit theorem.

preprint2010arXiv

Tail and moment estimates for chaoses generated by symmetric random variables with logarithmically concave tails

We present two-sided estimates of moments and tails of polynomial chaoses of order at most three generated by independent symmetric random variables with log-concave tails as well as for chaoses of arbitrary order generated by independent symmetric exponential variables. The estimates involve only deterministic quantities and are optimal up to constants depending only on the order of the chaos variable.

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)$ .

preprint2007arXiv

The LIL for $U$ -statistics in Hilbert spaces

We give necessary and sufficient conditions for the (bounded) law of the iterated logarithm for $U$ -statistics in Hilbert spaces. As a tool we also develop moment and tail estimates for canonical Hilbert-space valued $U$ -statistics of arbitrary order, which are of independent interest.

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.

Radosław Adamczak

Research overview

Is this your work?

25 publications

Limit theorems for the volumes of small codimensional random sections of $\ell_p^n$ -balls

Modified log-Sobolev inequalities, Beckner inequalities and moment estimates

A note on the sample complexity of the Er-SpUD algorithm by Spielman, Wang and Wright for exact recovery of sparsely used dictionaries

Asymptotic entropic uncertainty relations

Modified log-Sobolev inequalities for convex functions on the real line. Sufficient conditions

Moment estimates implied by modified log-Sobolev inequalities

Some remarks on MCMC estimation of spectra of integral operators

A note on the Hanson-Wright inequality for random vectors with dependencies

Circular law for random matrices with exchangeable entries

Circular law for random matrices with unconditional log-concave distribution

Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order

Exponential Concentration Inequalities for Additive Functionals of Markov Chains

A short proof of Paouris' inequality

Moment estimates for convex measures

Orlicz integrability of additive functionals of Harris ergodic Markov chains

Sharp bounds on the rate of convergence of the empirical covariance matrix

Chevet type inequality and norms of submatrices

CLT for Ornstein-Uhlenbeck branching particle system

CLT for U-statistics of Ornstein-Uhlenbeck branching particle system with small branching rate

Geometry of log-concave Ensembles of random matrices and approximate reconstruction

Tail estimates for norms of sums of log-concave random vectors

U-statistics of Ornstein-Uhlenbeck branching particle system

Tail and moment estimates for chaoses generated by symmetric random variables with logarithmically concave tails

Quantitative estimates of the convergence of the empirical covariance matrix in Log-concave Ensembles

The LIL for $U$ -statistics in Hilbert spaces

See the researcher in context

Building this map preview

Radosław Adamczak

Research overview

Is this your work?

25 publications

Limit theorems for the volumes of small codimensional random sections of ℓpn\ell_p^nℓpn​-balls

Modified log-Sobolev inequalities, Beckner inequalities and moment estimates

A note on the sample complexity of the Er-SpUD algorithm by Spielman, Wang and Wright for exact recovery of sparsely used dictionaries

Asymptotic entropic uncertainty relations

Modified log-Sobolev inequalities for convex functions on the real line. Sufficient conditions

Moment estimates implied by modified log-Sobolev inequalities

Some remarks on MCMC estimation of spectra of integral operators

A note on the Hanson-Wright inequality for random vectors with dependencies

Circular law for random matrices with exchangeable entries

Circular law for random matrices with unconditional log-concave distribution

Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order

Exponential Concentration Inequalities for Additive Functionals of Markov Chains

A short proof of Paouris' inequality

Moment estimates for convex measures

Orlicz integrability of additive functionals of Harris ergodic Markov chains

Sharp bounds on the rate of convergence of the empirical covariance matrix

Chevet type inequality and norms of submatrices

CLT for Ornstein-Uhlenbeck branching particle system

CLT for U-statistics of Ornstein-Uhlenbeck branching particle system with small branching rate

Geometry of log-concave Ensembles of random matrices and approximate reconstruction

Tail estimates for norms of sums of log-concave random vectors

U-statistics of Ornstein-Uhlenbeck branching particle system

Tail and moment estimates for chaoses generated by symmetric random variables with logarithmically concave tails

Quantitative estimates of the convergence of the empirical covariance matrix in Log-concave Ensembles

The LIL for UUU-statistics in Hilbert spaces

See the researcher in context

Building this map preview

Limit theorems for the volumes of small codimensional random sections of $\ell_p^n$ -balls

The LIL for $U$ -statistics in Hilbert spaces