Showing 1–44 of 44 results for author: Litvak, A

Minimal dispersion on the cube and the torus

Authors: Andrii Arman, Alexander E. Litvak

Abstract: We improve some upper bounds for minimal dispersion on the cube and torus. /Our new ingredient is an improvement of a probabilistic lemma used to obtain upper bounds for dispersion in several previous works. Our new lemma combines a random and non-random choice of points in the cube. This leads to better upper bounds for the minimal dispersion. We improve some upper bounds for minimal dispersion on the cube and torus. /Our new ingredient is an improvement of a probabilistic lemma used to obtain upper bounds for dispersion in several previous works. Our new lemma combines a random and non-random choice of points in the cube. This leads to better upper bounds for the minimal dispersion. △ Less

Submitted 4 June, 2024; originally announced June 2024.

Comments: 10 pages, 1 figure

MSC Class: 52B55; 52A23; 68Q25; 65Y20

Ensemble sampling for linear bandits: small ensembles suffice

Authors: David Janz, Alexander E. Litvak, Csaba Szepesvári

Abstract: We provide the first useful and rigorous analysis of ensemble sampling for the stochastic linear bandit setting. In particular, we show that, under standard assumptions, for a $d$-dimensional stochastic linear bandit with an interaction horizon $T$, ensemble sampling with an ensemble of size of order $\smash{d \log T}$ incurs regret at most of the order $\smash{(d \log T)^{5/2} \sqrt{T}}$. Ours is… ▽ More We provide the first useful and rigorous analysis of ensemble sampling for the stochastic linear bandit setting. In particular, we show that, under standard assumptions, for a $d$-dimensional stochastic linear bandit with an interaction horizon $T$, ensemble sampling with an ensemble of size of order $\smash{d \log T}$ incurs regret at most of the order $\smash{(d \log T)^{5/2} \sqrt{T}}$. Ours is the first result in any structured setting not to require the size of the ensemble to scale linearly with $T$ -- which defeats the purpose of ensemble sampling -- while obtaining near $\smash{\sqrt{T}}$ order regret. Ours is also the first result that allows infinite action sets. △ Less

Submitted 6 March, 2024; v1 submitted 14 November, 2023; originally announced November 2023.

On the volume ratio of projections of convex bodies

Authors: Daniel Galicer, Alexander E. Litvak, Mariano Merzbacher, Damián Pinasco

Abstract: We study the volume ratio between projections of two convex bodies. Given a high-dimensional convex body $K$ we show that there is another convex body $L$ such that the volume ratio between any two projections of fixed rank of the bodies $K$ and $L$ is large. Namely, we prove that for every $1\leq k\leq n$ and for each convex body $K\subset \mathbb{R}^n$ there is a centrally symmetric body… ▽ More We study the volume ratio between projections of two convex bodies. Given a high-dimensional convex body $K$ we show that there is another convex body $L$ such that the volume ratio between any two projections of fixed rank of the bodies $K$ and $L$ is large. Namely, we prove that for every $1\leq k\leq n$ and for each convex body $K\subset \mathbb{R}^n$ there is a centrally symmetric body $L \subset \mathbb{R}^n$ such that for any two projections $P, Q: \mathbb{R}^n \to \mathbb{R}^n$ of rank $k$ one has $$ \mbox{vr}(PK, QL) \geq c \, \min\left\{\frac{ k}{ \sqrt{n}} \, \sqrt{\frac{1}{\log \log \log(\frac{n\log(n)}{k})}}, \, \frac{\sqrt{k}}{\sqrt{\log(\frac{n\log(n)}{k})}}\right\}, $$ where $c>0$ is an absolute constant. This general lower bound is sharp (up to logarithmic factors) in the regime $k\geq n^{2/3}$. △ Less

Submitted 11 November, 2022; originally announced November 2022.

Comments: 21 pages, 2 figures

MSC Class: 52A23; 52A38; 52A40 (primary); 52A21; 52A20 (secondary)

New bounds on the minimal dispersion

Authors: Alexander E. Litvak, Galyna V. Livshyts

Abstract: We provide a new construction for a set of boxes approximating axis-parallel boxes of fixed volume in $[0, 1]^d$. This improves upper bounds for the minimal dispersion of a point set in the unit cube and its inverse in both the periodic and non-periodic settings in certain regimes. Up to double logarithmic factor, our bounds are sharp. We also apply our construction to $k$-dispersion. We provide a new construction for a set of boxes approximating axis-parallel boxes of fixed volume in $[0, 1]^d$. This improves upper bounds for the minimal dispersion of a point set in the unit cube and its inverse in both the periodic and non-periodic settings in certain regimes. Up to double logarithmic factor, our bounds are sharp. We also apply our construction to $k$-dispersion. △ Less

Submitted 20 January, 2022; v1 submitted 23 August, 2021; originally announced August 2021.

Comments: 17 pages; final version uploaded

Out-of-phase few-cycle solitons in multicore fibers

Authors: S. A. Skobelev, A. A. Balakin, E. A. Anashkina, A. V. Andrianov, A. G. Litvak

Abstract: An equation is derived for analyzing the self-action of a wave packets with few optical cycles in multicore fibers (MCF). A new class of stable out-of-phase spatio-temporal solitons with few cycle durations in the MCF with cores located in a ring is found and analyzed. The stability boundary of the obtained solutions is determined. As an example of using such solitons, we considered the problem of… ▽ More An equation is derived for analyzing the self-action of a wave packets with few optical cycles in multicore fibers (MCF). A new class of stable out-of-phase spatio-temporal solitons with few cycle durations in the MCF with cores located in a ring is found and analyzed. The stability boundary of the obtained solutions is determined. As an example of using such solitons, we considered the problem of their self-compression in the process of multisoliton dynamics in the MCF. The formation of laser pulses with a duration of few optical cycles at the output of a ten-core MCF is shown. △ Less

Submitted 15 March, 2021; originally announced March 2021.

Journal ref: Phys. Rev. A 104, 023522 (2021)

Random section and random simplex inequality

Authors: Alexander E. Litvak, Dmitry Zaporozhets

Abstract: Consider some convex body $K\subset\mathbb R^d$. Let $X_1,\dots, X_k$, where $k\leq d$, be random points independently and uniformly chosen in $K$, and let $ξ_k$ be a uniformly distributed random linear $k$-plane. We show that for $p\geq-d+k+1$, \[ \mathbb E\,|K\capξ_k|^{d+p}\leq c_{d,k,p} \cdot|K|^k\, \,\mathbb E\,|\mathrm{conv}(0,X_1, \dots,X_k)|^p, \] where $|\cdot|$ and $\mathrm{conv}$ denote… ▽ More Consider some convex body $K\subset\mathbb R^d$. Let $X_1,\dots, X_k$, where $k\leq d$, be random points independently and uniformly chosen in $K$, and let $ξ_k$ be a uniformly distributed random linear $k$-plane. We show that for $p\geq-d+k+1$, \[ \mathbb E\,|K\capξ_k|^{d+p}\leq c_{d,k,p} \cdot|K|^k\, \,\mathbb E\,|\mathrm{conv}(0,X_1, \dots,X_k)|^p, \] where $|\cdot|$ and $\mathrm{conv}$ denote the volume of correspondent dimension and the convex hull. The constant $c_{d,k,p}$ is such that for $k>1$ the equality holds if and only if $K$ is an ellipsoid centered at the origin, and for $k=1$ the inequality turns to equality. If $p=0$, then the inequality reduces to the Busemann intersection inequality, and if $k=d$ -- to the Busemann random simplex inequality. We also present an affine version of this inequality which similarly generalizes the Schneider inequality and the Blaschke-Grömer inequality. △ Less

Submitted 4 February, 2022; v1 submitted 13 July, 2020; originally announced July 2020.

MSC Class: 60D05; (primary) 52A55; 46B06 (secondary)

Journal ref: Zap. Nauchn. Sem. POMI, 505, POMI, 2021, 162-171

A remark on the minimal dispersion

Authors: A. E. Litvak

Abstract: We improve known upper bounds for the minimal dispersion of a point set in the unit cube and its inverse in both the periodic and non-periodic settings. Some of our bounds are sharp up to logarithmic factors. We improve known upper bounds for the minimal dispersion of a point set in the unit cube and its inverse in both the periodic and non-periodic settings. Some of our bounds are sharp up to logarithmic factors. △ Less

Submitted 25 September, 2021; v1 submitted 25 May, 2020; originally announced May 2020.

Comments: More typos are corrected. No other changes. The paper (without corrections) has appeared in Comm. in Cont. Math. 23/6 (2021), 2050060

MSC Class: 52B55; 52A23 (Primary) 68Q25; 65Y20 (Secondary)

Singularity of sparse Bernoulli matrices

Authors: Alexander E. Litvak, Konstantin E. Tikhomirov

Abstract: Let $M_n$ be an $n\times n$ random matrix with i.i.d. Bernoulli(p) entries. We show that there is a universal constant $C\geq 1$ such that, whenever $p$ and $n$ satisfy $C\log n/n\leq p\leq C^{-1}$, \begin{align*} {\mathbb P}\big\{\mbox{$M_n$ is singular}\big\}&=(1+o_n(1)){\mathbb P}\big\{\mbox{$M_n$ contains a zero row or column}\big\}\\ &=(2+o_n(1))n\,(1-p)^n, \end{align*} where $o_n(1)$ denotes… ▽ More Let $M_n$ be an $n\times n$ random matrix with i.i.d. Bernoulli(p) entries. We show that there is a universal constant $C\geq 1$ such that, whenever $p$ and $n$ satisfy $C\log n/n\leq p\leq C^{-1}$, \begin{align*} {\mathbb P}\big\{\mbox{$M_n$ is singular}\big\}&=(1+o_n(1)){\mathbb P}\big\{\mbox{$M_n$ contains a zero row or column}\big\}\\ &=(2+o_n(1))n\,(1-p)^n, \end{align*} where $o_n(1)$ denotes a quantity which converges to zero as $n\to\infty$. We provide the corresponding upper and lower bounds on the smallest singular value of $M_n$ as well. △ Less

Submitted 7 April, 2020; originally announced April 2020.

Stability of out-of-phase solitons and laser pulse self-compression in active multi-core fibers

Authors: A. A. Balakin, A. G. Litvak, S. A. Skobelev

Abstract: The out-of-phase soliton distribution of the wave field was found for a multicore fiber (MCF) from an even number of cores located in a ring. Its stability is proved both with respect to small wave field perturbations, including azimuthal ones and to small deformations of the MCF structure. As an example of using this soliton distribution, the problem of laser pulse compression in an active MCF is… ▽ More The out-of-phase soliton distribution of the wave field was found for a multicore fiber (MCF) from an even number of cores located in a ring. Its stability is proved both with respect to small wave field perturbations, including azimuthal ones and to small deformations of the MCF structure. As an example of using this soliton distribution, the problem of laser pulse compression in an active MCF is studied. The optimal fiber parameters, the minimum duration of the output pulse, and the compression length have been found, which are in good agreement with the results of numerical simulation. In order to achieve high energies in the output laser pulse, the requirements for MCF deformations are determined. △ Less

Submitted 11 September, 2019; originally announced September 2019.

Journal ref: Phys. Rev. A 100, 053834 (2019)

MCF solitons and laser pulse self-compression at light bullet excitation in the central core of MCF

Authors: Alexey A. Balakin, Alexander G. Litvak, Sergey A. Skobelev

Abstract: The propagation of laser pulses in multi-core fibers (MCF) made of a central core and an even number of cores located in a ring around it is studied. Approximate quasi-soliton homogeneous solutions of the wave field in the considered MCF are found. The stability of the in-phase soliton distribution is shown analytically and numerically. At low energies, its wave field is distributed over all MCF c… ▽ More The propagation of laser pulses in multi-core fibers (MCF) made of a central core and an even number of cores located in a ring around it is studied. Approximate quasi-soliton homogeneous solutions of the wave field in the considered MCF are found. The stability of the in-phase soliton distribution is shown analytically and numerically. At low energies, its wave field is distributed over all MCF cores and has a duration, which exceeds the duration of the NSE soliton with the same energy by many (five-six) times. On the contrary, almost all of the radiation at high energies is concentrated in the central core with a duration similar to the NSE soliton. The transition between the two types of distributions is very sharp and occurs at a critical energy, which is weakly dependent on the number of cores and on the coupling coefficient with the central core. The self-compression mechanism of laser pulses was proposed. It consists in injecting such MCF with a wave packet being similar to the found soliton and having an energy larger than the critical value. It is shown that the compression ratio weakly depends on the energy and the number of cores and is approximately equal to 6 times with an energy efficiency of almost 100\%. The use of longer laser pulses allows one to increase the compression ratio up to 30-40 times with an energy efficiency of more than 50\%. The obtained analytical estimates of the compression ratio and its efficiency are in good agreement with the results of numerical simulation. △ Less

Submitted 12 July, 2019; v1 submitted 2 July, 2019; originally announced July 2019.

Journal ref: Phys. Rev. A 100, 053830 (2019)

Small ball probability for the condition number of random matrices

Authors: Alexander E. Litvak, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann

Abstract: Let $A$ be an $n\times n$ random matrix with i.i.d. entries of zero mean, unit variance and a bounded subgaussian moment. We show that the condition number $s_{\max}(A)/s_{\min}(A)$ satisfies the small ball probability estimate $${\mathbb P}\big\{s_{\max}(A)/s_{\min}(A)\leq n/t\big\}\leq 2\exp(-c t^2),\quad t\geq 1,$$ where $c>0$ may only depend on the subgaussian moment. Although the estimate can… ▽ More Let $A$ be an $n\times n$ random matrix with i.i.d. entries of zero mean, unit variance and a bounded subgaussian moment. We show that the condition number $s_{\max}(A)/s_{\min}(A)$ satisfies the small ball probability estimate $${\mathbb P}\big\{s_{\max}(A)/s_{\min}(A)\leq n/t\big\}\leq 2\exp(-c t^2),\quad t\geq 1,$$ where $c>0$ may only depend on the subgaussian moment. Although the estimate can be obtained as a combination of known results and techniques, it was not noticed in the literature before. As a key step of the proof, we apply estimates for the singular values of $A$, ${\mathbb P}\big\{s_{n-k+1}(A)\leq ck/\sqrt{n}\big\}\leq 2 \exp(-c k^2), \quad 1\leq k\leq n,$ obtained (under some additional assumptions) by Nguyen. △ Less

Submitted 16 June, 2019; v1 submitted 24 January, 2019; originally announced January 2019.

Comments: Some changes according to the Referee's comments

Estimates for order statistics in terms of quantiles

Authors: Alexander E. Litvak, Konstantin Tikhomirov

Abstract: Let $X_1, \ldots, X_n$ be independent non-negative random variables with cumulative distribution functions $F_1,F_2,\ldots,F_n$, each satisfying certain (rather mild) conditions. We show that the median of $k$-th smallest order statistic of the vector $(X_1, \ldots, X_n)$ is equivalent to the quantile of order $(k-1/2)/n$ with respect to the averaged distribution $F=\frac{1}{n}\sum_{i=1}^n F_i$. Let $X_1, \ldots, X_n$ be independent non-negative random variables with cumulative distribution functions $F_1,F_2,\ldots,F_n$, each satisfying certain (rather mild) conditions. We show that the median of $k$-th smallest order statistic of the vector $(X_1, \ldots, X_n)$ is equivalent to the quantile of order $(k-1/2)/n$ with respect to the averaged distribution $F=\frac{1}{n}\sum_{i=1}^n F_i$. △ Less

Submitted 18 January, 2019; originally announced January 2019.

Comments: A small observation published in Zapiski Nauchnykh Seminarov POMI, 457 (2017), 265--275. arXiv admin note: substantial text overlap with arXiv:1609.02126

Random polytopes obtained by matrices with heavy tailed entries

Authors: Olivier Guédon, A. E. Litvak, K. Tatarko

Abstract: Let $Γ$ be an $N\times n$ random matrix with independent entries and such that in each row entries are i.i.d. Assume also that the entries are symmetric, have unit variances, and satisfy a small ball probabilistic estimate uniformly. We investigate properties of the corresponding random polytope $Γ^* B_1^N$ in $\mathbb{R}$ (the absolute convex hull of rows of $Γ$). In particular, we show that… ▽ More Let $Γ$ be an $N\times n$ random matrix with independent entries and such that in each row entries are i.i.d. Assume also that the entries are symmetric, have unit variances, and satisfy a small ball probabilistic estimate uniformly. We investigate properties of the corresponding random polytope $Γ^* B_1^N$ in $\mathbb{R}$ (the absolute convex hull of rows of $Γ$). In particular, we show that $$ ΓB_1^N \supset b^{-1} \left( B_{\infty}^n \cap \sqrt{\ln (N/n)}\, B_2^n \right). $$ where $b$ depends only on parameters in small ball inequality. This extends results of \cite{LPRT} and recent results of \cite{KKR}. This inclusion is equivalent to so-called $\ell_1$-quotient property and plays an important role in compressive sensing (see \cite{KKR} and references therein). △ Less

Submitted 7 February, 2019; v1 submitted 29 November, 2018; originally announced November 2018.

Comments: Last version, to appear in Communications in Contemporary Mathematics

MSC Class: primary: 52A22; 46B06; 60B20; secondary: 52A23; 46B09; 15B52

The rank of random regular digraphs of constant degree

Authors: Alexander Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann, Pierre Youssef

Abstract: Let $d$ be a fixed large integer. For any $n$ larger than $d$, let $A_n$ be the adjacency matrix of the random directed $d$-regular graph on $n$ vertices, with the uniform distribution. We show that $A_n$ has rank at least $n-1$ with probability going to one as $n$ goes to infinity. The proof combines the method of simple switchings and a recent result of the authors on delocalization of eigenvect… ▽ More Let $d$ be a fixed large integer. For any $n$ larger than $d$, let $A_n$ be the adjacency matrix of the random directed $d$-regular graph on $n$ vertices, with the uniform distribution. We show that $A_n$ has rank at least $n-1$ with probability going to one as $n$ goes to infinity. The proof combines the method of simple switchings and a recent result of the authors on delocalization of eigenvectors of $A_n$. △ Less

Submitted 18 July, 2018; v1 submitted 17 January, 2018; originally announced January 2018.

MSC Class: 60B20; 15B52; 46B06; 05C80

Journal ref: Journal of Complexity Volume 48, October 2018, Pages 103-110

Circular law for sparse random regular digraphs

Authors: Alexander Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann, Pierre Youssef

Abstract: Fix a constant $C\geq 1$ and let $d=d(n)$ satisfy $d\leq \ln^{C} n$ for every large integer $n$. Denote by $A_n$ the adjacency matrix of a uniform random directed $d$-regular graph on $n$ vertices. We show that, as long as $d\to\infty$ with $n$, the empirical spectral distribution of appropriately rescaled matrix $A_n$ converges weakly in probability to the circular law. This result, together with… ▽ More Fix a constant $C\geq 1$ and let $d=d(n)$ satisfy $d\leq \ln^{C} n$ for every large integer $n$. Denote by $A_n$ the adjacency matrix of a uniform random directed $d$-regular graph on $n$ vertices. We show that, as long as $d\to\infty$ with $n$, the empirical spectral distribution of appropriately rescaled matrix $A_n$ converges weakly in probability to the circular law. This result, together with an earlier work of Cook, completely settles the problem of weak convergence of the empirical distribution in directed $d$-regular setting with the degree tending to infinity. As a crucial element of our proof, we develop a technique of bounding intermediate singular values of $A_n$ based on studying random normals to rowspaces and on constructing a product structure to deal with the lack of independence between the matrix entries. △ Less

Submitted 21 January, 2018; v1 submitted 17 January, 2018; originally announced January 2018.

MSC Class: 60B20; 15B52; 46B06; 05C80

Structure of eigenvectors of random regular digraphs

Authors: Alexander Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann, Pierre Youssef

Abstract: Let $d$ and $n$ be integers satisfying $C\leq d\leq \exp(c\sqrt{\ln n})$ for some universal constants $c, C>0$, and let $z\in \mathbb{C}$. Denote by $M$ the adjacency matrix of a random $d$-regular directed graph on $n$ vertices. In this paper, we study the structure of the kernel of submatrices of $M-z\,{\rm Id}$, formed by removing a subset of rows. We show that with large probability the kernel… ▽ More Let $d$ and $n$ be integers satisfying $C\leq d\leq \exp(c\sqrt{\ln n})$ for some universal constants $c, C>0$, and let $z\in \mathbb{C}$. Denote by $M$ the adjacency matrix of a random $d$-regular directed graph on $n$ vertices. In this paper, we study the structure of the kernel of submatrices of $M-z\,{\rm Id}$, formed by removing a subset of rows. We show that with large probability the kernel consists of two non-intersecting types of vectors, which we call very steep and gradual with many levels. As a corollary, we show, in particular, that every eigenvector of $M$, except for constant multiples of $(1,1,\dots,1)$, possesses a weak delocalization property: its level sets have cardinality less than $Cn\ln^2 d/\ln n$. For a large constant $d$ this provides a principally new structural information on eigenvectors, implying that the number of their level sets grows to infinity with $n$. As a key technical ingredient of our proofs we introduce a decomposition of $\mathbb{C}^n$ into vectors of different degrees of `structuredness', which is an alternative to the decomposition based on the least common denominator in the regime when the underlying random matrix is very sparse. △ Less

Submitted 25 October, 2018; v1 submitted 17 January, 2018; originally announced January 2018.

Comments: Accepted in Transactions of the American Mathematical Society

MSC Class: 60B20; 15B52; 46B06; 05C80

Quantitative version of a Silverstein's result

Authors: Alexander Litvak, Susanna Spektor

Abstract: We prove a quantitative version of a Silverstein's Theorem on a condition for convergence in probability of the norm of random matrix. More precisely, we show that for a random matrix whose entries are i.i.d. random variables, $w_{i,j}$, satisfying certain natural conditions, is not small with large probability. We prove a quantitative version of a Silverstein's Theorem on a condition for convergence in probability of the norm of random matrix. More precisely, we show that for a random matrix whose entries are i.i.d. random variables, $w_{i,j}$, satisfying certain natural conditions, is not small with large probability. △ Less

Submitted 27 August, 2017; originally announced August 2017.

Journal ref: GAFA, Lecture Notes in Math., 2116 (2014), 335-340

The smallest singular value of a shifted $d$-regular random square matrix

Authors: Alexander Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann, Pierre Youssef

Abstract: We derive a lower bound on the smallest singular value of a random $d$-regular matrix, that is, the adjacency matrix of a random $d$-regular directed graph. More precisely, let $C_1<d< c_1 n/\log^2 n$ and let $\mathcal{M}_{n,d}$ be the set of all $0/1$-valued square $n\times n$ matrices such that each row and each column of a matrix $M\in \mathcal{M}_{n,d}$ has exactly $d$ ones. Let $M$ be uniform… ▽ More We derive a lower bound on the smallest singular value of a random $d$-regular matrix, that is, the adjacency matrix of a random $d$-regular directed graph. More precisely, let $C_1<d< c_1 n/\log^2 n$ and let $\mathcal{M}_{n,d}$ be the set of all $0/1$-valued square $n\times n$ matrices such that each row and each column of a matrix $M\in \mathcal{M}_{n,d}$ has exactly $d$ ones. Let $M$ be uniformly distributed on $\mathcal{M}_{n,d}$. Then the smallest singular value $s_{n} (M)$ of $M$ is greater than $c_2 n^{-6}$ with probability at least $1-C_2\log^2 d/\sqrt{d}$, where $c_1$, $c_2$, $C_1$, and $C_2$ are absolute positive constants independent of any other parameters. △ Less

Submitted 18 July, 2018; v1 submitted 9 July, 2017; originally announced July 2017.

MSC Class: 60B20; 15B52; 46B06; 05C80

Journal ref: Probability Theory and Related Fields, 2018

Self-compression of spatially limited laser pulses in a system of coupled light-guides

Authors: A. A. Balakin, A. G. Litvak, V. A. Mironov, S. A. Skobelev

Abstract: The self-action features of wave packets propagating in a two-dimensional system of equidistantly arranged fibers are studied analytically and numerically on the basis of the discrete nonlinear Schrödinger equation. Self-consistent equations for the characteristic scales of a Gaussian wave packet are derived on the basis of the variational approach, which are proved numerically for powers… ▽ More The self-action features of wave packets propagating in a two-dimensional system of equidistantly arranged fibers are studied analytically and numerically on the basis of the discrete nonlinear Schrödinger equation. Self-consistent equations for the characteristic scales of a Gaussian wave packet are derived on the basis of the variational approach, which are proved numerically for powers $\mathcal{P} < 10 \mathcal{P}_\text{cr}$ exceeding slightly the critical one for self-focusing. At higher powers, the wave beams become filamented, and their amplitude is limited due to nonlinear breaking of the interaction between neighbor light-guides. This make impossible to collect a powerful wave beam into the single light-guide. The variational analysis show the possibility of adiabatic self-compression of soliton-like laser pulses in the process of their three-dimensional self-focusing to the central light-guide. However, the further increase of the field amplitude during self-compression leads to the longitudinal modulation instability development and formation of a set of light bullets in the central fiber. In the regime of hollow wave beams, filamentation instability becomes predominant. As a result, it becomes possible to form a set of light bullets in optical fibers located on the ring. △ Less

Submitted 18 September, 2017; v1 submitted 16 May, 2017; originally announced May 2017.

Self-compression of soliton-like laser pulses in the process of self-focusing

Authors: A. A. Balakin, A. G. Litvak, V. A. Mironov, S. A. Skobelev

Abstract: We study the possibility of efficient self-compression of femtosecond laser pulses in nonlinear media with anomalous dispersion of group velocity during the self-focusing of wave packets with a power several times greater than the critical self-focusing power. The results of qualitative analysis of the evolution of three-dimensional wave packets with the quasi-soliton field distribution are confir… ▽ More We study the possibility of efficient self-compression of femtosecond laser pulses in nonlinear media with anomalous dispersion of group velocity during the self-focusing of wave packets with a power several times greater than the critical self-focusing power. The results of qualitative analysis of the evolution of three-dimensional wave packets with the quasi-soliton field distribution are confirmed by the computer simulation. The simulation proves that the considered regime of compression of high-power laser pulses with initial durations of about ten optical cycles is stable relative to filamentation instability due to the influence of the nonlinear dispersion. We demonstrate the possibility of self-compression of laser pulses at a multi-millijoule energy level and up to one optical cycle with an energy efficiency of more then 50%. △ Less

Submitted 7 February, 2017; originally announced February 2017.

Order statistics of vectors with dependent coordinates, and the Karhunen-Loève basis

Authors: Alexander E. Litvak, Konstantin Tikhomirov

Abstract: Let $X$ be an $n$-dimensional random centered Gaussian vector with independent but not identically distributed coordinates and let $T$ be an orthogonal trasformation of $\mathbb R^n$. We show that the random vector $Y=T(X)$ satisfies $$\mathbb E\sum\limits_{j=1}^k j\mbox{-}\min_{i\leq n}{X_{i}}^2 \leq C\mathbb E\sum\limits_{j=1}^k j\mbox{-}\min_{i\leq n}{Y_{i}}^2$$ for all $k<n$, where "… ▽ More Let $X$ be an $n$-dimensional random centered Gaussian vector with independent but not identically distributed coordinates and let $T$ be an orthogonal trasformation of $\mathbb R^n$. We show that the random vector $Y=T(X)$ satisfies $$\mathbb E\sum\limits_{j=1}^k j\mbox{-}\min_{i\leq n}{X_{i}}^2 \leq C\mathbb E\sum\limits_{j=1}^k j\mbox{-}\min_{i\leq n}{Y_{i}}^2$$ for all $k<n$, where "$j\mbox{-}\min$" denotes the $j$-th smallest component of corresponding vector and $C>0$ is a universal constant. This resolves (up to a multiplicative constant) an old question of S.Mallat and O.Zeitouni regarding optimality of the Karhunen-Loeve basis for the nonlinear signal approximation. As a by-product we obtain some relations for order statistics of random vectors (not only Gaussian) which are of independent interest. △ Less

Submitted 28 May, 2017; v1 submitted 7 September, 2016; originally announced September 2016.

Comments: minor fixes

On the expectation of operator norms of random matrices

Authors: Olivier Guédon, Aicke Hinrichs, Alexander E. Litvak, Joscha Prochno

Abstract: We prove estimates for the expected value of operator norms of Gaussian random matrices with independent and mean-zero entries, acting as operators from $\ell^m_{p^*}$ to $\ell_q^n$, $1\leq p^* \leq 2 \leq q \leq \infty$. We prove estimates for the expected value of operator norms of Gaussian random matrices with independent and mean-zero entries, acting as operators from $\ell^m_{p^*}$ to $\ell_q^n$, $1\leq p^* \leq 2 \leq q \leq \infty$. △ Less

Submitted 8 March, 2016; originally announced March 2016.

MSC Class: Primary 60B20; Secondary 46B09

Mean width of regular polytopes and expected maxima of correlated Gaussian variables

Authors: Zakhar Kabluchko, Alexander E. Litvak, Dmitry Zaporozhets

Abstract: An old conjecture states that among all simplices inscribed in the unit sphere the regular one has the maximal mean width. An equivalent formulation is that for any centered Gaussian vector $(ξ_1,\dots,ξ_n)$ satisfying $\mathbb Eξ_1^2= \dots =\mathbb Eξ_n^2=1$ one has $$ \mathbb E\,\max\{ξ_1,\dots,ξ_n\}\leq\sqrt{\frac{n}{n-1}}\, \mathbb E\,\max\{η_1,\dots,η_n\}, $$ where $η_1,η_2,\dots,$ are ind… ▽ More An old conjecture states that among all simplices inscribed in the unit sphere the regular one has the maximal mean width. An equivalent formulation is that for any centered Gaussian vector $(ξ_1,\dots,ξ_n)$ satisfying $\mathbb Eξ_1^2= \dots =\mathbb Eξ_n^2=1$ one has $$ \mathbb E\,\max\{ξ_1,\dots,ξ_n\}\leq\sqrt{\frac{n}{n-1}}\, \mathbb E\,\max\{η_1,\dots,η_n\}, $$ where $η_1,η_2,\dots,$ are independent standard Gaussian variables. Using this probabilistic interpretation we derive an asymptotic version of the conjecture. We also show that the mean width of the regular simplex with $2n$ vertices is remarkably close to the mean width of the regular crosspolytope with the same number of vertices. Interpreted probabilistically, our result states that $$ 1\leq\frac{\mathbb E\,\max\{|η_1|,\dots,|η_n|\}}{\mathbb E\,\max\{η_1,\dots,η_{2n}\}} \leq\min\left\{\sqrt{\frac{2n}{2n-1}}, \, 1+\frac{C}{n\, \log n} \right\}, $$ where $C>0$ is an absolute constant. We also compute the higher moments of the projection length $W$ of the regular cube, simplex and crosspolytope onto a line with random direction, thus proving several formulas conjectured by S. Finch. Finally, we prove distributional limit theorems for the length of random projection as the dimension goes to $\infty$. In the case of the $n$-dimensional unit cube $Q_n$, we prove that $$ W_{Q_n} - \sqrt{\frac{2n}π} \overset{d}{\underset{n\to\infty}\longrightarrow} {\mathcal{N}} \left(0, \frac{π-3}π\right), $$ whereas for the simplex and the crosspolytope the limiting distributions are related to the Gumbel double exponential law. △ Less

Submitted 6 April, 2016; v1 submitted 26 November, 2015; originally announced November 2015.

MSC Class: 52A23 (Primary); 52A39; 52A20; 60G15; 60G70; 46B06 (Secondary)

Adjacency matrices of random digraphs: singularity and anti-concentration

Authors: Alexander E. Litvak, Anna Lytova, Konstantin Tikhomirov, Nicole Tomczak-Jaegermann, Pierre Youssef

Abstract: 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$-… ▽ More 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". △ Less

Submitted 18 October, 2016; v1 submitted 31 October, 2015; originally announced November 2015.

Comments: Final version

MSC Class: 60C05; 60B20; 05C80; 15B52; 46B06

Journal ref: J. of Math. Analysis and Appl., 445 (2017), 1447--1491

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

Authors: Olivier Guédon, Alexander E. Litvak, Alain Pajor, Nicole Tomczak-Jaegermann

Abstract: 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… ▽ More 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]$. △ Less

Submitted 8 September, 2015; originally announced September 2015.

Comments: To appear in J. Eur. Math. Soc

MSC Class: 60B20; 46B06; 15B52; 46B09; 60D05

Packing convex bodies by cylinders

Authors: Karoly Bezdek, Alexander Litvak

Abstract: In [BL] in relation to the unsolved Bang's plank problem (1951) we obtained a lower bound for the sum of relevant measures of cylinders covering a given d-dimensional convex body. In this paper we provide the packing counterpart of these estimates. We also extend bounds to the case of r-fold covering and packing and show a packing analog of Falconer's results ([Fa]). In [BL] in relation to the unsolved Bang's plank problem (1951) we obtained a lower bound for the sum of relevant measures of cylinders covering a given d-dimensional convex body. In this paper we provide the packing counterpart of these estimates. We also extend bounds to the case of r-fold covering and packing and show a packing analog of Falconer's results ([Fa]). △ Less

Submitted 21 November, 2015; v1 submitted 17 July, 2015; originally announced July 2015.

Comments: 14 pages

MSC Class: 52A40; 46B07; 46B20; 52C17

Journal ref: Discrete and Computational Geometry, Volume 55, Issue 3 (2016), 725-738

Numerical range for random matrices

Authors: Benoît Collins, Piotr Gawron, Alexander E. Litvak, Karol Życzkowski

Abstract: We analyze the numerical range of high-dimensional random matrices, obtaining limit results and corresponding quantitative estimates in the non-limit case. For a large class of random matrices their numerical range is shown to converge to a disc. In particular, numerical range of complex Ginibre matrix almost surely converges to the disk of radius $\sqrt{2}$. Since the spectrum of non-hermitian ra… ▽ More We analyze the numerical range of high-dimensional random matrices, obtaining limit results and corresponding quantitative estimates in the non-limit case. For a large class of random matrices their numerical range is shown to converge to a disc. In particular, numerical range of complex Ginibre matrix almost surely converges to the disk of radius $\sqrt{2}$. Since the spectrum of non-hermitian random matrices from the Ginibre ensemble lives asymptotically in a neighborhood of the unit disk, it follows that the outer belt of width $\sqrt{2}-1$ containing no eigenvalues can be seen as a quantification the non-normality of the complex Ginibre random matrix. We also show that the numerical range of upper triangular Gaussian matrices converges to the same disk of radius $\sqrt{2}$, while all eigenvalues are equal to zero and we prove that the operator norm of such matrices converges to $\sqrt{2e}$. △ Less

Submitted 10 March, 2014; v1 submitted 24 September, 2013; originally announced September 2013.

Comments: 23 pages, 4 figures

MSC Class: 5A60; 47A12; 15B52 (primary); 46B06; 60B20 (secondary)

Journal ref: J. Math. Anal. Appl. 418 (2014) 516-533

On approximations by projections of polytopes with few facets

Authors: Alexander E. Litvak, Mark Rudelson, Nicole Tomczak-Jaegermann

Abstract: 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 bo… ▽ More 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. △ Less

Submitted 27 September, 2012; originally announced September 2012.

Comments: 22 pages

MSC Class: Primary: 52A23; 52A27; Secondary: 52B55; 46B09

Moment estimates for convex measures

Authors: Radosław Adamczak, Olivier Guédon, Rafał Latała, Alexander E. Litvak, Krzysztof Oleszkiewicz, Alain Pajor, Nicole Tomczak-Jaegermann

Abstract: 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… ▽ More 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))$. △ Less

Submitted 27 July, 2012; originally announced July 2012.

MSC Class: 46B06; 60E15; 60F10 (Primary) 52A23; 52A40 (Secondary)

Journal ref: Electron. J. Probab. 17 (2012), no. 101, 1-19

A short proof of Paouris' inequality

Authors: Radosław Adamczak, Rafał Latała, Alexander E. Litvak, Krzysztof Oleszkiewicz, Alain Pajor, Nicole Tomczak-Jaegermann

Abstract: 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}$. 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}$. △ Less

Submitted 11 May, 2012; originally announced May 2012.

MSC Class: 46B06; 46B09 (Primary); 52A23 (Secondary)

Journal ref: Can. Math. Bull. 57 (2014), 3-8

On radiative damping in plasma-based accelerators

Authors: I. Yu. Kostyukov, E. N. Nerush, A. G. Litvak

Abstract: Radiative damping in plasma-based electron accelerators is analyzed. The electron dynamics under combined influence of the constant accelerating force and the classical radiation reaction force is studied. It is shown that electron acceleration cannot be limited by radiation reaction. If initially the accelerating force was stronger than the radiation reaction force then the electron acceleration… ▽ More Radiative damping in plasma-based electron accelerators is analyzed. The electron dynamics under combined influence of the constant accelerating force and the classical radiation reaction force is studied. It is shown that electron acceleration cannot be limited by radiation reaction. If initially the accelerating force was stronger than the radiation reaction force then the electron acceleration is unlimited. Otherwise the electron is decelerated by radiative damping up to a certain instant of time and then accelerated without limits. Regardless of the initial conditions the infinite-time asymptotic behavior of an electron is governed by self-similar solution providing unlimited acceleration. The relative energy spread induced by the radiative damping decreases with time in the infinite-time limit. △ Less

Submitted 11 May, 2012; originally announced May 2012.

On the vertex index of convex bodies

Authors: Karoly Bezdek, Alexander E. Litvak

Abstract: We introduce the vertex index, vein(K), of a given centrally symmetric convex body K, which, in a sense, measures how well K can be inscribed into a convex polytope with small number of vertices. This index is closely connected to the illumination parameter of a body, introduced earlier by the first named author, and, thus, related to the famous conjecture in Convex Geometry about covering of a d-… ▽ More We introduce the vertex index, vein(K), of a given centrally symmetric convex body K, which, in a sense, measures how well K can be inscribed into a convex polytope with small number of vertices. This index is closely connected to the illumination parameter of a body, introduced earlier by the first named author, and, thus, related to the famous conjecture in Convex Geometry about covering of a d-dimensional body by 2^d smaller positively homothetic copies. We provide asymptotically sharp estimates (up to a logarithmic term) of this index in the general case. Also, we provide sharp estimates in dimensions 2 and 3. △ Less

Submitted 19 October, 2011; originally announced October 2011.

Comments: 20 pages

Journal ref: Adv. Math. 215 (2007), no. 2, 626-641

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

Authors: Radosław Adamczak, Rafał Latała, Alexander E. Litvak, Alain Pajor, Nicole Tomczak-Jaegermann

Abstract: 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-con… ▽ More 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. △ Less

Submitted 20 July, 2011; originally announced July 2011.

MSC Class: 46B06; 15B52; 60E15; 60B20

Journal ref: Proc. London Math. Soc. 108 (2014), 600-637

Chevet type inequality and norms of submatrices

Authors: Radosław Adamczak, Rafał Latała, Alexander E. Litvak, Alain Pajor, Nicole Tomczak-Jaegermann

Abstract: 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-matrice… ▽ More 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. △ Less

Submitted 20 July, 2011; originally announced July 2011.

MSC Class: Primary 52A23; 46B06; 46B09; 60E15 Secondary 15B52; 94B75

Journal ref: Studia Math. 210 (2012), 35-56

Smallest singular value of sparse random matrices

Authors: Alexander Litvak, Omar Rivasplata

Abstract: We extend probability estimates on the smallest singular value of random matrices with independent entries to a class of sparse random matrices. We show that one can relax a previously used condition of uniform boundedness of the variances from below. This allows us to consider matrices with null entries or, more generally, with entries having small variances. Our results do not assume identical d… ▽ More We extend probability estimates on the smallest singular value of random matrices with independent entries to a class of sparse random matrices. We show that one can relax a previously used condition of uniform boundedness of the variances from below. This allows us to consider matrices with null entries or, more generally, with entries having small variances. Our results do not assume identical distribution of the entries of a random matrix and help to clarify the role of the variances of the entries. We also show that it is enough to require boundedness from above of the $r$-th moment, $r > 2$, of the corresponding entries. △ Less

Submitted 19 December, 2012; v1 submitted 5 June, 2011; originally announced June 2011.

Comments: 25 pages, a condition on one parameter was added in the statement of Theorem 1.3 and Lemma 6.2, results unchanged

MSC Class: 46B06; 60B20; 15B52

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

Authors: Radosław Adamczak, Rafał Latała, Alexander E. Litvak, Alain Pajor, Nicole Tomczak-Jaegermann

Abstract: 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-co… ▽ More 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. △ Less

Submitted 2 March, 2011; originally announced March 2011.

MSC Class: Primary 52A23; 46B06; 46B09; 60E15 Secondary 15B52; 94B75

Journal ref: C. R. Math. Acad. Sci. Paris. 349 (2011), 783-786

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

Authors: Radosław Adamczak, Alexander E. Litvak, Alain Pajor, Nicole Tomczak-Jaegermann

Abstract: 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 resul… ▽ More 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. △ Less

Submitted 30 October, 2012; v1 submitted 1 December, 2010; originally announced December 2010.

MSC Class: 52A20; 46B09; 52A21 (Primary) 15A52; 60E15 (Secondary)

Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling

Authors: Radosław Adamczak, Alexander E. Litvak, Alain Pajor, Nicole Tomczak-Jaegermann

Abstract: This paper considers compressed sensing matrices and neighborliness of a centrally symmetric convex polytope generated by vectors $\pm X_1,...,\pm X_N\in\R^n$, ($N\ge n$). We introduce a class of random sampling matrices and show that they satisfy a restricted isometry property (RIP) with overwhelming probability. In particular, we prove that matrices with i.i.d. centered and variance 1 entries… ▽ More This paper considers compressed sensing matrices and neighborliness of a centrally symmetric convex polytope generated by vectors $\pm X_1,...,\pm X_N\in\R^n$, ($N\ge n$). We introduce a class of random sampling matrices and show that they satisfy a restricted isometry property (RIP) with overwhelming probability. In particular, we prove that matrices with i.i.d. centered and variance 1 entries that satisfy uniformly a sub-exponential tail inequality possess this property RIP with overwhelming probability. We show that such "sensing" matrices are valid for the exact reconstruction process of $m$-sparse vectors via $\ell_1$ minimization with $m\le Cn/\log^2 (cN/n)$. The class of sampling matrices we study includes the case of matrices with columns that are independent isotropic vectors with log-concave densities. We deduce that if $K\subset \R^n$ is a convex body and $X_1,..., X_N\in K$ are i.i.d. random vectors uniformly distributed on $K$, then, with overwhelming probability, the symmetric convex hull of these points is an $m$-centrally-neighborly polytope with $m\sim n/\log^2 (cN/n)$. △ Less

Submitted 29 April, 2009; originally announced April 2009.

MSC Class: 52A20; 94A12; 52B12; 46B09 (Primary) 15A52; 41A45; 94B75 (Secondary)

Covering convex bodies by cylinders and lattice points by flats

Authors: Karoly Bezdek, Alexander Litvak

Abstract: In connection with an unsolved problem of Bang (1951) we give a lower bound for the sum of the base volumes of cylinders covering a d-dimensional convex body in terms of the relevant basic measures of the given convex body. As an application we establish lower bounds on the number of k-dimensional flats (i.e. translates of k-dimensional linear subspaces) needed to cover all the integer points of… ▽ More In connection with an unsolved problem of Bang (1951) we give a lower bound for the sum of the base volumes of cylinders covering a d-dimensional convex body in terms of the relevant basic measures of the given convex body. As an application we establish lower bounds on the number of k-dimensional flats (i.e. translates of k-dimensional linear subspaces) needed to cover all the integer points of a given convex body in d-dimensional Euclidean space for 0<k<d. △ Less

Submitted 27 March, 2009; originally announced March 2009.

MSC Class: 52A40; 46B07; 46B20; 52C17

Journal ref: J. Geom. Anal. 19/2 (2009), 233-243

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

Authors: Radosław Adamczak, Alexander E. Litvak, Alain Pajor, Nicole Tomczak-Jaegermann

Abstract: 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 dis… ▽ More 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)$. △ Less

Submitted 27 August, 2009; v1 submitted 13 March, 2009; originally announced March 2009.

Comments: Exposition changed, several explanatory remarks added, some proofs simplified

MSC Class: 52A20; 46B09; 52A21 (Primary) 15A52; 60E15 (Secondary)

Uniform estimates for order statistics and Orlicz functions

Authors: Yehoram Gordon, Alexander Litvak, Carsten Schütt, Elisabeth Werner

Abstract: We establish uniform estimates for order statistics of sequences of independent identically distributed random variables with log-concave distribution in terms of Orlicz norms associated with the distribution function of the random variables. We establish uniform estimates for order statistics of sequences of independent identically distributed random variables with log-concave distribution in terms of Orlicz norms associated with the distribution function of the random variables. △ Less

Submitted 17 September, 2008; originally announced September 2008.

MSC Class: 60E15; 62G30; 60G15; 60B11; 46E40; 46B45

Quotients of finite-dimensional quasi-normed spaces

Authors: N. J. Kalton, A. E. Litvak

Abstract: We study the existence of cubic quotients of finite-dimensional quasi-normed spaces, that is, quotients well isomorphic to $\ell_{\infty}^k$ for some $k.$ We give two results of this nature. The first guarantees a proportional dimensional cubic quotient when the envelope is cubic; the second gives an estimate for the size of a cubic quotient in terms of a measure of non-convexity of the quasi-no… ▽ More We study the existence of cubic quotients of finite-dimensional quasi-normed spaces, that is, quotients well isomorphic to $\ell_{\infty}^k$ for some $k.$ We give two results of this nature. The first guarantees a proportional dimensional cubic quotient when the envelope is cubic; the second gives an estimate for the size of a cubic quotient in terms of a measure of non-convexity of the quasi-norm. △ Less

Submitted 11 April, 2001; originally announced April 2001.

Comments: 13 pages

MSC Class: 46B07

Covering numbers and ``low $M^{*}$-estimate'' for quasi-convex bodies

Authors: A. E. Litvak, V. D. Milman, A. Pajor

Abstract: This article gives estimates on covering numbers and diameters of random proportional sections and projections of symmetric quasi-convex bodies in $\mathbb R$. These results were known for the convex case and played an essential role in development of the theory. Because duality relations can not be applied in the quasi-convex setting, new ingredients were introduced that give new understanding… ▽ More This article gives estimates on covering numbers and diameters of random proportional sections and projections of symmetric quasi-convex bodies in $\mathbb R$. These results were known for the convex case and played an essential role in development of the theory. Because duality relations can not be applied in the quasi-convex setting, new ingredients were introduced that give new understanding for the convex case as well. △ Less

Submitted 19 May, 1996; originally announced May 1996.

Report number: MSRI 1996-038

Strong Phase Correlations of Solitons of Nonlinear Schrödinger Equation

Authors: A. G. Litvak, V. A. Mironov, A. P. Protogenov

Abstract: We discuss the possibility to suppress the collapse in the nonlinear 2+1 D Schrödinger equation by using the gauge theory of strong phase correlations. It is shown that invariance relative to $q$-deformed Hopf algebra with deformation parameter $q$ being the fourth root of unity makes the values of the Chern-Simons term coefficient, $k=2$, and of the coupling constant, $g=1/2$, fixed; no collaps… ▽ More We discuss the possibility to suppress the collapse in the nonlinear 2+1 D Schrödinger equation by using the gauge theory of strong phase correlations. It is shown that invariance relative to $q$-deformed Hopf algebra with deformation parameter $q$ being the fourth root of unity makes the values of the Chern-Simons term coefficient, $k=2$, and of the coupling constant, $g=1/2$, fixed; no collapsing solutions are present at those values. △ Less

Submitted 7 July, 1994; originally announced July 1994.