Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe rank of sparse random matrices
118
0
0.0
(
0
)
Added by
Amin Coja-Oghlan
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We determine the rank of a random matrix over an arbitrary field with prescribed numbers of non-zero entries in each row and column. As an application we obtain a formula for the rate of low-density parity check codes. This formula vindicates a conjecture of Lelarge (2013). The proofs are based on coupling arguments and a novel random perturbation, applicable to any matrix, that diminishes the number of short linear relations.
rate research
Read More
Let $Q_{n,d}$ denote the random combinatorial matrix whose rows are independent of one another and such that each row is sampled uniformly at random from the subset of vectors in ${0,1}^n$ having precisely $d$ entries equal to $1$. We present a short proof of the fact that $Pr[det(Q_{n,d})=0] = Oleft(frac{n^{1/2}log^{3/2} n}{d}right)=o(1)$, whenever $d=omega(n^{1/2}log^{3/2} n)$. In particular, our proof accommodates sparse random combinatorial matrices in the sense that $d = o(n)$ is allowed. We also consider the singularity of deterministic integer matrices $A$ randomly perturbed by a sparse combinatorial matrix. In particular, we prove that $Pr[det(A+Q_{n,d})=0]=Oleft(frac{n^{1/2}log^{3/2} n}{d}right)$, again, whenever $d=omega(n^{1/2}log^{3/2} n)$ and $A$ has the property that $(1,-d)$ is not an eigenpair of $A$.
The Ising antiferromagnet is an important statistical physics model with close connections to the {sc Max Cut} problem. Combining spatial mixing arguments with the method of moments and the interpolation method, we pinpoint the replica symmetry breaking phase transition predicted by physicists. Additionally, we rigorously establish upper bounds on the {sc Max Cut} of random regular graphs predicted by Zdeborova and Boettcher [Journal of Statistical Mechanics 2010]. As an application we prove that the information-theoretic threshold of the disassortative stochastic block model on random regular graphs coincides with the Kesten-Stigum bound.
We introduce the random graph $mathcal{P}(n,q)$ which results from taking the union of two paths of length $ngeq 1$, where the vertices of one of the paths have been relabelled according to a Mallows permutation with real parameter $0<q(n)leq 1$. This random graph model, the tangled path, goes through an evolution: if $q$ is close to $0$ the graph bears resemblance to a path and as $q$ tends to $1$ it becomes an expander. In an effort to understand the evolution of $mathcal{P}(n,q)$ we determine the treewidth and cutwidth of $mathcal{P}(n,q)$ up to log factors for all $q$. We also show that the property of having a separator of size one has a sharp threshold. In addition, we prove bounds on the diameter, and vertex isoperimetric number for specific values of $q$.
We study a natural question about sparse random matrices which arises from an application in distributed computing: what is the distance from a fixed vector to the column span of a sparse random matrix $A in R^{n times m}$? We answer this question for several ensembles of sparse random matrices in which the average number of non-zero entries per column, $d$, is smaller than $log(n)$. Key to our analysis is a new characterization of linear dependencies in sparse random matrices. We show that with high probability, in certain random matrices, including rectangular matrices with i.i.d.~Bernoulli entries and $m geq (1 + epsilon)n$, and symmetric random matrices with Bernoulli entries, any linear dependency must be caused by one of three specific combinatorial structures. We show applications of our result to analyzing and designing em gradient codesem, replication schemes used in distributed machine learning to mitigate the effect of slow machines, called em stragglersem. We give the first known construction for a gradient code that achieves near-optimal error for both random and adversarial choices of stragglers.
Let $M_n$ be a random $ntimes n$ matrix with i.i.d. $text{Bernoulli}(1/2)$ entries. We show that for fixed $kge 1$, [lim_{nto infty}frac{1}{n}log_2mathbb{P}[text{corank }M_nge k] = -k.]
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
