Source author record

Pierre Youssef

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.CO math.OA math.SP

Catalog footprint

Research overview

9works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Regularized modified log-Sobolev inequalities, and comparison of Markov chains

In this work, we develop a comparison procedure for the Modified log-Sobolev Inequality (MLSI) constants of two reversible Markov chains on a finite state space. Efficient comparison of the MLSI Dirichlet forms is a well known obstacle in the theory of Markov chains. We approach this problem by introducing a {\it regularized} MLSI constant which, under some assumptions, has the same order of magnitude as the usual MLSI constant yet is amenable for comparison and thus considerably simpler to estimate in certain cases. As an application of this general comparison procedure, we provide a sharp estimate of the MLSI constant of the switch chain on the the set of simple bipartite regular graphs of size $n$ with a fixed degree $d$ . Our estimate implies that the total variation mixing time of the switch chain is of order $O_d(n\log n)$ . The result is optimal up to a multiple depending on $d$ and resolves a long-standing open problem. We expect that the MLSI comparison technique implemented in this paper will find further applications.

preprint2022arXiv

Sharp Poincaré and log-Sobolev inequalities for the switch chain on regular bipartite graphs

Consider the switch chain on the set of $d$ -regular bipartite graphs on $n$ vertices with $3\leq d\leq n^{c}$ , for a small universal constant $c>0$ . We prove that the chain satisfies a Poincaré inequality with a constant of order $O(nd)$ ; moreover, when $d$ is fixed, we establish a log-Sobolev inequality for the chain with a constant of order $O_d(n\log n)$ . We show that both results are optimal. The Poincaré inequality implies that in the regime $3\leq d\leq n^c$ the mixing time of the switch chain is at most $O\big((nd)^2 \log(nd)\big)$ , improving on the previously known bound $O\big((nd)^{13} \log(nd)\big)$ due to Kannan, Tetali and Vempala and $O\big(n^7d^{18} \log(nd)\big)$ obtained by Dyer et al. The log-Sobolev inequality that we establish for constant $d$ implies a bound $O(n\log^2 n)$ on the mixing time of the chain which, up to the $\log n$ factor, captures a conjectured optimal bound. Our proof strategy relies on building, for any fixed function on the set of $d$ -regular bipartite simple graphs, an appropriate extension to a function on the set of multigraphs given by the configuration model. We then establish a comparison procedure with the well studied random transposition model in order to obtain the corresponding functional inequalities. While our method falls into a rich class of comparison techniques for Markov chains on different state spaces, the crucial feature of the method - dealing with chains with a large distortion between their stationary measures - is a novel addition to the theory.

preprint2020arXiv

Matrix Poincaré inequalities and concentration

We show that any probability measure satisfying a Matrix Poincaré inequality with respect to some reversible Markov generator satisfies an exponential matrix concentration inequality depending on the associated matrix carré du champ operator. This extends to the matrix setting a classical phenomenon in the scalar case. Moreover, the proof gives rise to new matrix trace inequalities which could be of independent interest. We then apply this general fact by establishing matrix Poincaré inequalities to derive matrix concentration inequalities for Gaussian measures, product measures and for Strong Rayleigh measures. The latter represents the first instance of matrix concentration for general matrix functions of negatively dependent random variables.

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

Restricted invertibility revisited

Suppose that $m,n\in \mathbb{N}$ and that $A:\mathbb{R}^m\to \mathbb{R}^n$ is a linear operator. It is shown here that if $k,r\in \mathbb{N}$ satisfy $k<r\le \mathrm{\bf rank(A)}$ then there exists a subset $σ\subseteq \{1,\ldots,m\}$ with $|σ|=k$ such that the restriction of $A$ to $\mathbb{R}^σ\subseteq \mathbb{R}^m$ is invertible, and moreover the operator norm of the inverse $A^{-1}:A(\mathbb{R}^σ)\to \mathbb{R}^m$ is at most a constant multiple of the quantity $\sqrt{mr/((r-k)\sum_{i=r}^m \mathsf{s}_i(A)^2)}$ , where $\mathsf{s}_1(A)\geqslant\ldots\geqslant \mathsf{s}_m(A)$ are the singular values of $A$ . This improves over a series of works, starting from the seminal Bourgain--Tzafriri Restricted Invertibility Principle, through the works of Vershynin, Spielman--Srivastava and Marcus--Spielman--Srivastava. In particular, this directly implies an improved restricted invertibility principle in terms of Schatten--von Neumann norms.

preprint2015arXiv

Extracting a basis with fixed block inside a matrix

Given $U$ an $n\times m$ matrix of rank $n$ and $V$ block of columns inside $U$ , we consider the problem of extracting a block of columns of rank $n$ which minimize the Hilbert-Schmidt norm of the inverse while preserving the block $V$ . This generalizes a previous result of Gluskin-Olevskii, and improves the estimates when given a "good" block $V$ .

preprint2015arXiv

Minimax of an n-dimensional Brownian motion

For some absolute constants $c$ , $n_0$ and any $n\geq n_0$ , we show that with probability close to one the convex hull of the $n$ -dimensional Brownian motion ${\rm conv}\{BM_n(t):\, t\in[1,2^{cn}]\}$ does not contain the origin. The result can be interpreted as an estimate of the minimax of the Gaussian process $\{ \langle \bar{u},BM_n(t)\rangle,\, \bar{u}\in S^{n-1},\, t\in [1,2^{cn}]\}$ .

preprint2013arXiv

A note on column subset selection

Given a matrix U, using a deterministic method, we extract a "large" submatrix of U'(whose columns are obtained by normalizing those of U) and estimate its smallest and largest singular value. We apply this result to the study of contact points of the unit ball with its maximal volume ellipsoid. We consider also the paving problem and give a deterministic algorithm to partition a matrix into almost isometric blocks recovering previous results of Bourgain-Tzafriri and Tropp. Finally, we partially answer a question raised by Naor about finding an algorithm in the spirit of Batson-Spielman-Srivastava's work to extract a "large" square submatrix of "small" norm.

preprint2013arXiv

Estimating the covariance of random matrices

We extend to the matrix setting a recent result of Srivastava-Vershynin about estimating the covariance matrix of a random vector. The result can be in- terpreted as a quantified version of the law of large numbers for positive semi-definite matrices which verify some regularity assumption. Beside giving examples, we dis- cuss the notion of log-concave matrices and give estimates on the smallest and largest eigenvalues of a sum of such matrices.

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.