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

Improve this question
$\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
    Commented Feb 20, 2021 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$
    – ofer zeitouni
    Commented Feb 20, 2021 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
    Commented Feb 20, 2021 at 22:04
  • $\begingroup$ I missed that. Not sure. Have you tried to compute high moments? $\endgroup$
    – ofer zeitouni
    Commented Feb 20, 2021 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
    Commented Feb 20, 2021 at 22:19

1 Answer 1

Reset to default
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$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .