1
$\begingroup$

Let $n,d,k$ be large positive integers such that $\max(n/d,k/d) =: \lambda < 1$. Let $X$ be a random $n \times d$ matrix with entries drawn iid from $N(0,1/d)$ and let $W$ be a $k \times d$ random matrix, independent of $X$, with entries drawn iid from $N(0,1/d)$. Consider the $n \times k$ matrix $C$ defined by $c_{ij} = \max(x_i^\top w_j, 0)$.

Question. What are good bounds for the extreme singular-values of $C$ ?

Empirical observations

enter image description here Related: https://math.stackexchange.com/q/4031609/168758

$\endgroup$
15
  • $\begingroup$ @oferzeitouni I've added a figure from simulations. There seems to be concentration of the extreme singular-values $C$ but I have no clue how to prove it. $\endgroup$
    – dohmatob
    Feb 20 at 14:52
  • 1
    $\begingroup$ You are basically asking about the top eigenvalue of a product of two Wishart matrices. Corollary 2.2 in Male's paper arxiv.org/pdf/1004.4155.pdf should be enough to show that the spectrum is contained in the limiting spectrum (which can be computed using free probability). $\endgroup$ Feb 20 at 21:46
  • $\begingroup$ @oferzeitouni Thanks for the input. What about the case where the entries of the product are thresholded (as in my question) ? (from a quick look, the paper you linked doesn't seem to cover this) ? My real issue is the thresholding, not the product (which as you say, is covered by classical results). That is, I'm interested in the singular-values of $C=\psi(XW^\top)$, where $\psi(t):=\max(t,0)$ is applied entrywise. $\endgroup$
    – dohmatob
    Feb 20 at 22:04
  • $\begingroup$ I missed that. Not sure. Have you tried to compute high moments? $\endgroup$ Feb 20 at 22:07
  • $\begingroup$ You mean like moments of $c_{ij}$ ? A quick calculation gives $\mathbb E [c_{ij}] = \mathcal O(1/\sqrt{d})$ and $\mathbb E[c_{i,j}^2]=\mathcal O(1/d)$. In fact, it should also be possible to compute $\mathbb E[(c_{ij}c_{i'j'})^p]$ say for $p=1,2$; this presumably decays rapidly as a function of $d$. Given such correlation information, are there any general tools that can give info abound extreme singular-values of $C$ (I'm guessing this is what you have in mind, but I may be wrong). $\endgroup$
    – dohmatob
    Feb 20 at 22:19
1
$\begingroup$

Claim. Rescale things so that $\mathbb E [c_{11}^2] = 1$. In the limit when $n,k \to \infty$ such that $k/n=\lambda \in(0,\infty)$, the spectral density of $C$ converges to $MP(\lambda)$.

Proof. Follows from directly Corollary 6 of this paper. In fact the same result holds if we consider the general scenario in which $c_{ij}:=\psi(x_i^\top w_j)$, with $\psi:\mathbb R \to \mathbb R$ such that $|\psi(t)| \le \alpha(1 + |t|)^\alpha$ for some $\alpha \ge 0$ and for every $t \in \mathbb R$. $\quad\Box$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.