Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPhase transition in random tensors with multiple independent spikes
65
0
0.0
(
0
)
Added by
Wei-Kuo Chen
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Consider a spiked random tensor obtained as a mixture of two components: noise in the form of a symmetric Gaussian $p$-tensor for $pgeq 3$ and signal in the form of a symmetric low-rank random tensor. The latter is defined as a linear combination of $k$ independent symmetric rank-one random tensors, referred to as spikes, with weights referred to as signal-to-noise ratios (SNRs). The entries of the vectors that determine the spikes are i.i.d. sampled from general probability distributions supported on bounded subsets of $mathbb{R}$. This work focuses on the problem of detecting the presence of these spikes, and establishes the phase transition of this detection problem for any fixed $k geq 1$. In particular, it shows that for a set of relatively low SNRs it is impossible to distinguish between the spiked and non-spiked Gaussian tensors. Furthermore, in the interior of the complement of this set, where at least one of the $k$ SNRs is relatively high, these two tensors are distinguishable by the likelihood ratio test. In addition, when the total number of low-rank components, $k$, of the $p$-tensor of size $N$ grows in the order $o(N^{(p-2)/4})$ as $N$ tends to infinity, the problem exhibits an analogous phase transition. This theory for spike detection is also shown to imply that recovery of the spikes by the minimum mean square error exhibits the same phase transition. The main methods used in this work arise from the study of mean field spin glass models, where the phase transition thresholds are identified as the critical inverse temperatures distinguishing the high and low-temperature regimes of the free energies. In particular, our result formulates the first full characterization of the high temperature regime for vector-valued spin glass models with independent coordinates.
rate research
Read More
This paper introduces the concept of random context representations for the transition probabilities of a finite-alphabet stochastic process. Processes with these representations generalize context tree processes (a.k.a. variable length Markov chains), and are proven to coincide with processes whose transition probabilities are almost surely continuous functions of the (infinite) past. This is similar to a classical result by Kalikow about continuous transition probabilities. Existence and uniqueness of a minimal random context representation are proven, and an estimator of the transition probabilities based on this representation is shown to have very good pastwise adaptativity properties. In particular, it achieves minimax performance, up to logarithmic factors, for binary renewal processes with bounded $2+gamma$ moments.
We prove a non-asymptotic concentration inequality for the spectral norm of sparse inhomogeneous random tensors with Bernoulli entries. For an order-$k$ inhomogeneous random tensor $T$ with sparsity $p_{max}geq frac{clog n}{n }$, we show that $|T-mathbb E T|=O(sqrt{n p_{max}}log^{k-2}(n))$ with high probability. The optimality of this bound up to polylog factors is provided by an information theoretic lower bound. By tensor unfolding, we extend the range of sparsity to $p_{max}geq frac{clog n}{n^{m}}$ with $1leq mleq k-1$ and obtain concentration inequalities for different sparsity regimes. We also provide a simple way to regularize $T$ such that $O(sqrt{n^{m}p_{max}})$ concentration still holds down to sparsity $p_{max}geq frac{c}{n^{m}}$ with $k/2leq mleq k-1$. We present our concentration and regularization results with two applications: (i) a randomized construction of hypergraphs of bounded degrees with good expander mixing properties, (ii) concentration of sparsified tensors under uniform sampling.
We study the independent alignment percolation model on $mathbb{Z}^d$ introduced by Beaton, Grimmett and Holmes [arXiv:1908.07203]. It is a model for random intersecting line segments defined as follows. First the sites of $mathbb{Z}^d$ are independently declared occupied with probability $p$ and vacant otherwise. Conditional on the configuration of occupied vertices, consider the set of all line segments that are parallel to the coordinate axis, whose extremes are occupied vertices and that do not traverse any other occupied vertex. Declare independently the segments on this set open with probability $lambda$ and closed otherwise. All the edges that lie on open segments are also declared open giving rise to a bond percolation model in $mathbb{Z}^d$. We show that for any $d geq 2$ and $p in (0,1]$ the critical value for $lambda$ satisfies $lambda_c(p)<1$ completing the proof that the phase transition is non-trivial over the whole interval $(0,1]$. We also show that the critical curve $p mapsto lambda_c(p)$ is continuous at $p=1$, answering a question posed by the authors in [arXiv:1908.07203].
For $Delta ge 5$ and $q$ large as a function of $Delta$, we give a detailed picture of the phase transition of the random cluster model on random $Delta$-regular graphs. In particular, we determine the limiting distribution of the weights of the ordered and disordered phases at criticality and prove exponential decay of correlations and central limit theorems away from criticality. Our techniques are based on using polymer models and the cluster expansion to control deviations from the ordered and disordered ground states. These techniques also yield efficient approximate counting and sampling algorithms for the Potts and random cluster models on random $Delta$-regular graphs at all temperatures when $q$ is large. This includes the critical temperature at which it is known the Glauber and Swendsen-Wang dynamics for the Potts model mix slowly. We further prove new slow-mixing results for Markov chains, most notably that the Swendsen-Wang dynamics mix exponentially slowly throughout an open interval containing the critical temperature. This was previously only known at the critical temperature. Many of our results apply more generally to $Delta$-regular graphs satisfying a small-set expansion condition.
For $dge 3$ we construct a new coupling of the trace left by a random walk on a large $d$-dimensional discrete torus with the random interlacements on $mathbb Z^d$. This coupling has the advantage of working up to macroscopic subsets of the torus. As an application, we show a sharp phase transition for the diameter of the component of the vacant set on the torus containing a given point. The threshold where this phase transition takes place coincides with the critical value $u_*(d)$ of random interlacements on $mathbb Z^d$. Our main tool is a variant of the soft-local time coupling technique of [PT12].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
