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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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