Source author record

Nicole Tomczak-Jaegermann

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

ResearcherUnclaimed source record

math.FA math.PR math.MG Information Theory math.CO math.IT

Catalog footprint

Research overview

16works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Adjacency matrices of random digraphs: singularity and anti-concentration

Let ${\mathcal D}_{n,d}$ be the set of all $d$ -regular directed graphs on $n$ vertices. Let $G$ be a graph chosen uniformly at random from ${\mathcal D}_{n,d}$ and $M$ be its adjacency matrix. We show that $M$ is invertible with probability at least $1-C\ln^{3} d/\sqrt{d}$ for $C\leq d\leq cn/\ln^2 n$ , where $c, C$ are positive absolute constants. To this end, we establish a few properties of $d$ -regular directed graphs. One of them, a Littlewood-Offord type anti-concentration property, is of independent interest. Let $J$ be a subset of vertices of $G$ with $|J|\approx n/d$ . Let $δ_i$ be the indicator of the event that the vertex $i$ is connected to $J$ and define $δ= (δ_1, δ_2, ..., δ_n)\in \{0, 1\}^n$ . Then for every $v\in\{0,1\}^n$ the probability that $δ=v$ is exponentially small. This property holds even if a part of the graph is "frozen".

preprint2016arXiv

On the geometry of projective tensor products

In this work, we study the volume ratio of the projective tensor products $\ell^n_p\otimes_π\ell_q^n\otimes_π\ell_r^n$ with $1\leq p\leq q \leq r \leq \infty$ . We obtain asymptotic formulas that are sharp in almost all cases. As a consequence of our estimates, these spaces allow for a nearly Euclidean decomposition of Kashin type whenever $1\leq p \leq q\leq r \leq 2$ or $1\leq p \leq 2 \leq r \leq \infty$ and $q=2$ . Also, from the Bourgain-Milman bound on the volume ratio of Banach spaces in terms of their cotype $2$ constant, we obtain information on the cotype of these $3$ -fold projective tensor products. Our results naturally generalize to $k$ -fold products $\ell_{p_1}^n\otimes_π\dots \otimes_π\ell_{p_k}^n$ with $k\in\mathbb N$ and $1\leq p_1 \leq \dots\leq p_k \leq \infty$ .

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

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

On approximations by projections of polytopes with few facets

We provide an affirmative answer to a problem posed by Barvinok and Veomett, showing that in general an n-dimensional convex body cannot be approximated by a projection of a section of a simplex of a sub-exponential dimension. Moreover, we establish a lower bound of the Banach-Mazur distance between n-dimensional projections of sections of an N-dimensional simplex and a certain convex symmetric body, which is sharp up to a logarithmic factor for all N>n.

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

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.

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

preprint2008arXiv

On the nontrivial projection problem

The Nontrivial Projection Problem asks whether every finite-dimensional normed space of dimension greater than one admits a well-bounded projection of non-trivial rank and corank or, equivalently, whether every centrally symmetric convex body (of arbitrary dimension greater than one) is approximately affinely equivalent to a direct product of two bodies of non-trivial dimension. We show that this is true "up to a logarithmic factor."

preprint1997arXiv

Proximity to $\ell_1$ and Distortion in Asymptotic $\ell_1$ Spaces

For an asymptotic $\ell_1$ space $X$ with a basis $(x_i)$ certain asymptotic $\ell_1$ constants, $δ_α(X)$ are defined for $α<ω_1$ . $δ_α(X)$ measures the equivalence between all normalized block bases $(y_i)_{i=1}^k$ of $(x_i)$ which are $S_α$ -admissible with respect to $(x_i)$ ( $S_α$ is the $α^{th}$ -Schreier class of sets) and the unit vector basis of $\ell_1^k$ . This leads to the concept of the delta spectrum of $X$ , $Δ(X)$ , which reflects the behavior of stabilized limits of $δ_α(X)$ . The analogues of these constants under all renormings of $X$ are also defined and studied. We investigate $Δ(X)$ both in general and for spaces of bounded distortion. We also prove several results on distorting the classical Tsirelson's space $T$ and its relatives.

preprint1994arXiv

Asymptotic infinite-dimensional theory of Banach spaces

In this paper structure of infinite dimensional Banach spaces is studied by using an asymptotic approach based on stabilization at infinity of finite dimensional subspaces which appear everywhere far away. This leads to notions of asymptotic structures and asymptotic versions of a given Banach space. As an example of application of this approach, a class of asymptotic $l_p$ -spaces is introduced and investigated in detail. Some properties of this class, as duality and complementation, are analogous to properties of classical $l_p$ spaces, although the latter is more ``regular'' than its classical counterpart; in contrast, the property exhibited in the uniqueness theorem is very different than for spaces $l_p$ .

preprint1993arXiv

Banach spaces without local unconditional structure

For a large class of Banach spaces, a general construction of subspaces without local unconditional structure is presented. As an application it is shown that every Banach space of finite cotype contains either $l_2$ or a subspace without unconditional basis, which admits a Schauder basis. Some other interesting applications and corollaries follow.

preprint1992arXiv

Norms of Minimal Projections

It is proved that the projection constants of two- and three-dimensional spaces are bounded by $4/3$ and $(1+\sqrt 5)/2$ , respectively. These bounds are attained precisely by the spaces whose unit balls are the regular hexagon and dodecahedron. In fact, a general inequality for the projection constant of a real or complex $n$ -dimensional space is obtained and the question of equality therein is discussed.

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.

Nicole Tomczak-Jaegermann

Research overview

Is this your work?

16 publications

Adjacency matrices of random digraphs: singularity and anti-concentration

On the geometry of projective tensor products

On the interval of fluctuation of the singular values of random matrices

A short proof of Paouris' inequality

Moment estimates for convex measures

On approximations by projections of polytopes with few facets

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

Chevet type inequality and norms of submatrices

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

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

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

On the nontrivial projection problem

Proximity to $\ell_1$ and Distortion in Asymptotic $\ell_1$ Spaces

Asymptotic infinite-dimensional theory of Banach spaces

Banach spaces without local unconditional structure

Norms of Minimal Projections

See the researcher in context

Building this map preview

Nicole Tomczak-Jaegermann

Research overview

Is this your work?

16 publications

Adjacency matrices of random digraphs: singularity and anti-concentration

On the geometry of projective tensor products

On the interval of fluctuation of the singular values of random matrices

A short proof of Paouris' inequality

Moment estimates for convex measures

On approximations by projections of polytopes with few facets

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

Chevet type inequality and norms of submatrices

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

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

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

On the nontrivial projection problem

Proximity to ℓ1\ell_1ℓ1​ and Distortion in Asymptotic ℓ1\ell_1ℓ1​ Spaces

Asymptotic infinite-dimensional theory of Banach spaces

Banach spaces without local unconditional structure

Norms of Minimal Projections

See the researcher in context

Building this map preview

Proximity to $\ell_1$ and Distortion in Asymptotic $\ell_1$ Spaces