We prove a sharp concentration inequality for the spectral norm of sparse random tensors with independent Bernoulli entries. Let $T$ be an order-$k$ tensor of dimension $n\times\cdots\times n$ with independent Bernoulli$(p)$ entries, where $k$ is fixed. For any $c,r>0$, we show that $\|T-\mathbb E T\|\le C_{k,r,c}\sqrt{np}$ with probability at least $1-n^{-r}$ whenever $np\ge c\log n$. We extend this bound to inhomogeneous Bernoulli sampling with deterministic entrywise weights. This removes the logarithmic factor in the work of Zhou and Zhu (2021). The proof follows the Kahn--Szemer\'edi light--heavy decomposition with a refined estimate on the heavy tuple part. We also obtain a log-free second eigenvalue bound for the random hypergraph model of Friedman and Wigderson (1995).
We consider the probability that a discrete random matrix $M_n(\xi)$ is \emph{strongly non-singular}, meaning all its leading principal submatrices are non-singular. This property is equivalent to the existence of an LU factorization. We show that for any discrete random variable $\xi$ with finite support and $|\xi|_\i...
S. Mateo, John Urschel, Nicholas West· 2 citations
For fixed $k\ge3$, we determine the critical law of totally isotropic $r$-spaces for a uniform random map $\Theta_N:\Lambda^k\mathbb {F}_q^N\to\mathbb {F}_q^m$. At the exact balance $m\binom rk=r(N-r)$, the entire null configuration is asymptotically an independent Bernoulli subset of $\operatorname{Gr}(r,\mathbb {F}_q...
We initiate the study of approximating the top eigenvalue and eigenvector of a random symmetric matrix $ A \in \mathbb{R}^{n\times n} $ using $ q(A)b $ where $q$ is a degree-$d$ polynomial and $b$ is a standard Gaussian vector independent of $A$. For spiked GOE $ Y = \lambda vv^\top + X $, we identify $ d_\star = \frac...
Inspired by the planted clique problem for random graphs, we introduce the planted totally-isotropic space problem for random tensors as follows. Let $U\cong \mathbb{F}_q^n$ and $W\cong \mathbb{F}_q^m$ be finite-dimensional vector spaces over a finite field $\mathbb{F}_q$. Given $d\in \mathbb{N}$, choose a random \(d\)...
Yuxuan Liu, You-Ming Qiao, Gang Tang et al.· 1 citation
Let $$X_n=\sum_{i=1}^s t_i A_i^{\otimes n},$$ where $A_1,\ldots,A_s\in M_d(\mathbb C)$ and $t_1,\ldots,t_s\in\mathbb C$ are fixed, while $n$ grows. Direct computation of determinants or Schatten norms of $X_n$ is exponential in $n$. For a single tensor power these quantities are elementary, and even the determinant of...
For a centered, variance-one random variable $X$ with finite fourth moment, let $x$ be the vector of square-free degree-$d$ monomials in $n$ independent copies of $X$. At the critical scale $d^2/n \to \lambda \in (0,\infty)$, the normalized squared length of $x$ converges to the lognormal variable $R = \exp(\sqrt{\lamb...
Xiao-Hui Xie· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
