pr.probability – Lower-bound for smallest singular-value of matrix $c_{ij} := psi(x_i^top w_j)$ where $x_1,ldots,x_n,w_1,ldots,x_k sim N(0,(1/d)I_d)$ iid

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)$. Let $psi$ $1$-Lipschitz and consider the $n times k$ matrix $C$ defined by $c_{i,j} = psi(x_i^top w_j)$.

Question. What is a good lower-bounds for the smallest singular-value of $C$ ?


  • The rows of $C$ should be independent and sub-exponential.