No Arabic abstract
We consider the asymptotic behavior as $ntoinfty$ of the spectra of random matrices of the form [frac{1}{sqrt{n-1}}sum_{k=1}^{n-1}Z_{nk}rho_n ((k,k+1)),] where for each $n$ the random variables $Z_{nk}$ are i.i.d. standard Gaussian and the matrices $rho_n((k,k+1))$ are obtained by applying an irreducible unitary representation $rho_n$ of the symmetric group on ${1,2,...,n}$ to the transposition $(k,k+1)$ that interchanges $k$ and $k+1$ [thus, $rho_n((k,k+1))$ is both unitary and self-adjoint, with all eigenvalues either +1 or -1]. Irreducible representations of the symmetric group on ${1,2,...,n}$ are indexed by partitions $lambda_n$ of $n$. A consequence of the results we establish is that if $lambda_{n,1}gelambda_{n,2}ge...ge0$ is the partition of $n$ corresponding to $rho_n$, $mu_{n,1}gemu_{n,2}ge >...ge0$ is the corresponding conjugate partition of $n$ (i.e., the Young diagram of $mu_n$ is the transpose of the Young diagram of $lambda_n$), $lim_{ntoinfty}frac{lambda_{n,i}}{n}=p_i$ for each $ige1$, and $lim_{ntoinfty}frac{mu_{n,j}}{n}=q_j$ for each $jge1$, then the spectral measure of the resulting random matrix converges in distribution to a random probability measure that is Gaussian with random mean $theta Z$ and variance $1-theta^2$, where $theta$ is the constant $sum_ip_i^2-sum_jq_j^2$ and $Z$ is a standard Gaussian random variable.
We show that for an $ntimes n$ random symmetric matrix $A_n$, whose entries on and above the diagonal are independent copies of a sub-Gaussian random variable $xi$ with mean $0$ and variance $1$, [mathbb{P}[s_n(A_n) le epsilon/sqrt{n}] le O_{xi}(epsilon^{1/8} + exp(-Omega_{xi}(n^{1/2}))) quad text{for all } epsilon ge 0.] This improves a result of Vershynin, who obtained such a bound with $n^{1/2}$ replaced by $n^{c}$ for a small constant $c$, and $1/8$ replaced by $(1/8) + eta$ (with implicit constants also depending on $eta > 0$). Furthermore, when $xi$ is a Rademacher random variable, we prove that [mathbb{P}[s_n(A_n) le epsilon/sqrt{n}] le O(epsilon^{1/8} + exp(-Omega((log{n})^{1/4}n^{1/2}))) quad text{for all } epsilon ge 0.] The special case $epsilon = 0$ improves a recent result of Campos, Mattos, Morris, and Morrison, which showed that $mathbb{P}[s_n(A_n) = 0] le O(exp(-Omega(n^{1/2}))).$ The main innovation in our work are new notions of arithmetic structure -- the Median Regularized Least Common Denominator and the Median Threshold, which we believe should be more generally useful in contexts where one needs to combine anticoncentration information of different parts of a vector.
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 addresses a question raised by Eberhard in recent work. The main innovation in our work is establishing sharp estimates regarding the rank distribution of symmetric random ${pm 1}$-matrices over $mathbb{F}_p$ for primes $2 < p leq exp(O(n^{1/4}))$. Previously, such estimates were available only for $p = o(n^{1/8})$. At the heart of our proof is a way to combine multiple inverse Littlewood--Offord-type results to control the contribution to singularity-type events of vectors in $mathbb{F}_p^{n}$ with anticoncentration at least $1/p + Omega(1/p^2)$. Previously, inverse Littlewood--Offord-type results only allowed control over vectors with anticoncentration at least $C/p$ for some large constant $C > 1$.
We show that there exists a family of groups $G_n$ and nontrivial irreducible representations $rho_n$ such that, for any constant $t$, the average of $rho_n$ over $t$ uniformly random elements $g_1, ldots, g_t in G_n$ has operator norm $1$ with probability approaching 1 as $n rightarrow infty$. More quantitatively, we show that there exist families of finite groups for which $Omega(log log |G|)$ random elements are required to bound the norm of a typical representation below $1$. This settles a conjecture of A. Wigderson.
Multi-target regression is concerned with the simultaneous prediction of multiple continuous target variables based on the same set of input variables. It arises in several interesting industrial and environmental application domains, such as ecological modelling and energy forecasting. This paper presents an ensemble method for multi-target regression that constructs new target variables via random linear combinations of existing targets. We discuss the connection of our approach with multi-label classification algorithms, in particular RA$k$EL, which originally inspired this work, and a family of recent multi-label classification algorithms that involve output coding. Experimental results on 12 multi-target datasets show that it performs significantly better than a strong baseline that learns a single model for each target using gradient boosting and compares favourably to multi-objective random forest approach, which is a state-of-the-art approach. The experiments further show that our approach improves more when stronger unconditional dependencies exist among the targets.
We prove large (and moderate) deviations for a class of linear combinations of spacings generated by i.i.d. exponentially distributed random variables. We allow a wide class of coefficients which can be expressed in terms of continuous functions defined on [0, 1] which satisfy some suitable conditions. In this way we generalize some recent results by Giuliano et al. (2015) which concern the empirical cumulative entropies defined in Di Crescenzo and Longobardi (2009a).