Vishesh Jain

activity

20132023

most citedSingularity of random symmetric matrices -- a combinatorial approach to improved bounds

25 citations · 70 across the 30 of their papers we have counts for

collaborators

Showing math.PRShow all

18 papers · 1 filter

math.PR2023

Universality of Spectral Independence with Applications to Fast Mixing in Spin Glasses

Nima Anari, Vishesh Jain, Frederic Koehler +2

We study Glauber dynamics for sampling from discrete distributions $μ$ on the hypercube ${\pm 1}^{n}$ . Recently, techniques based on spectral independence have successfully yielded…

math.PR2022

Optimal minimization of the covariance loss

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Let $X$ be a random vector valued in $R^{m}$ such that $∥ X ∥_{2} \leq 1$ almost surely. For every $k \geq 3$ , we show that there exists a sigma algebra $F$ generat…

math.PR2021

Random symmetric matrices: rank distribution and irreducibility of the characteristic polynomial

Asaf Ferber, Vishesh Jain, Ashwin Sah +1

Conditional on the extended Riemann hypothesis, we show that with high probability, the characteristic polynomial of a random symmetric ${\pm 1}$ -matrix is irreducible. This addr…

math.PR2021

Rank deficiency of random matrices

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Let $M_{n}$ be a random $n \times n$ matrix with i.i.d. $Bernoulli (1/2)$ entries. We show that for fixed $k \geq 1$ , \[\lim_{n\to \infty}\frac{1}{n}\log_2\mathbb{P}[\text{corank…

math.PR2020

Optimal and algorithmic norm regularization of random matrices

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Let $A$ be an $n \times n$ random matrix whose entries are i.i.d. with mean $0$ and variance $1$ . We present a deterministic polynomial time algorithm which, with probability at lea…

math.PR2020

On the smallest singular value of symmetric random matrices

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

We show that for an $n \times n$ random symmetric matrix $A_{n}$ , whose entries on and above the diagonal are independent copies of a sub-Gaussian random variable $ξ$ with mean $0$ an…

math.PR2020

Singularity of discrete random matrices

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Let $ξ$ be a non-constant real-valued random variable with finite support, and let $M_{n} (ξ)$ denote an $n \times n$ random matrix with entries that are independent copies of $ξ$ . F…

math.PR2020★ 2 cited

Sharp invertibility of random Bernoulli matrices

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Let $p \in (0, 1/2)$ be fixed, and let $B_{n} (p)$ be an $n \times n$ random matrix with i.i.d. Bernoulli random variables with mean $p$ . We show that for all $t \geq 0$ , \[\mathbb{P}[s_…

math.PR2020

On the smoothed analysis of the smallest singular value with discrete noise

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Let $A$ be an $n \times n$ real matrix, and let $M$ be an $n \times n$ random matrix whose entries are i.i.d sub-Gaussian random variables with mean $0$ and variance $1$ . We make two…

math.PR2020

The smallest singular value of dense random regular digraphs

Vishesh Jain, Ashwin Sah, Mehtaab Sawhney

Let $A$ be the adjacency matrix of a uniformly random $d$ -regular digraph on $n$ vertices, and suppose that $min (d, n - d) \geq λn$ . We show that for any $κ \geq 0$ , \[\mathbb{P}[s_n(A)…

math.PR2020★ 3 cited

Circular Law for Random Block Band Matrices with Genuinely Sublinear Bandwidth

Vishesh Jain, Indrajit Jana, Kyle Luh +1

We prove the circular law for a class of non-Hermitian random block band matrices with genuinely sublinear bandwidth. Namely, we show there exists $τ \in (0, 1)$ so that if the bandw…

math.PR2020

Universality and least singular values of random matrix products: a simplified approach

Rohit Chaudhuri, Vishesh Jain, Natesh S. Pillai

In this note, we show how to provide sharp control on the least singular value of a certain translated linearization matrix arising in the study of the local universality of produc…

math.PR2020

A note on the universality of ESDs of inhomogeneous random matrices

Vishesh Jain, Sandeep Silwal

In this short note, we extend the celebrated results of Tao and Vu, and Krishnapur on the universality of empirical spectral distributions to a wide class of inhomogeneous complex…

math.PR2019★ 5 cited

Quantitative invertibility of random matrices: a combinatorial perspective

Vishesh Jain

We study the lower tail behavior of the least singular value of an $n \times n$ random matrix $M_{n} := M + N_{n}$ , where $M$ is a fixed complex matrix with operator norm at most $\exp(n^…

math.PR2019★ 2 cited

Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices

Vishesh Jain

An approximate Spielman-Teng theorem for the least singular value $s_{n} (M_{n})$ of a random $n \times n$ square matrix $M_{n}$ is a statement of the following form: there exist constants…

math.PR2019

The strong circular law: a combinatorial view

Vishesh Jain

Let $N_{n}$ be an $n \times n$ complex random matrix, each of whose entries is an independent copy of a centered complex random variable $z$ with finite non-zero variance $σ^{2}$ . The…

math.PR2018★ 25 cited

Singularity of random symmetric matrices -- a combinatorial approach to improved bounds

Asaf Ferber, Vishesh Jain

Let $M_{n}$ denote a random symmetric $n \times n$ matrix whose upper diagonal entries are independent and identically distributed Bernoulli random variables (which take values $1$ a…

math.PR2018★ 2 cited

On the number of Hadamard matrices via anti-concentration

Asaf Ferber, Vishesh Jain, Yufei Zhao

Many problems in combinatorial linear algebra require upper bounds on the number of solutions to an underdetermined system of linear equations $A x = b$ , where the coordinates of th…